main page
modules
namespaces
classes
files
Gecode home
Generated on Thu Feb 21 2013 23:11:44 for Gecode by
doxygen
1.8.3.1
gecode
int
extensional
tuple-set.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Mikael Lagerkvist <lagerkvist@gecode.org>
5
*
6
* Copyright:
7
* Mikael Lagerkvist, 2007
8
*
9
* Last modified:
10
* $Date: 2010-07-15 01:46:18 +1000 (Thu, 15 Jul 2010) $ by $Author: schulte $
11
* $Revision: 11192 $
12
*
13
* This file is part of Gecode, the generic constraint
14
* development environment:
15
* http://www.gecode.org
16
*
17
* Permission is hereby granted, free of charge, to any person obtaining
18
* a copy of this software and associated documentation files (the
19
* "Software"), to deal in the Software without restriction, including
20
* without limitation the rights to use, copy, modify, merge, publish,
21
* distribute, sublicense, and/or sell copies of the Software, and to
22
* permit persons to whom the Software is furnished to do so, subject to
23
* the following conditions:
24
*
25
* The above copyright notice and this permission notice shall be
26
* included in all copies or substantial portions of the Software.
27
*
28
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35
*
36
*/
37
38
#include <
gecode/int.hh
>
39
40
namespace
{
41
42
typedef ::Gecode::TupleSet::Tuple
Tuple
;
43
47
class
FullTupleCompare {
48
private
:
50
int
arity;
51
public
:
53
forceinline
54
FullTupleCompare(
int
a
) : arity(a) {}
56
forceinline
bool
57
operator ()(
const
Tuple&
a
,
const
Tuple&
b
) {
58
for
(
int
i
= 0;
i
< arity;
i
++)
59
if
(a[
i
] < b[
i
])
60
return
true
;
61
else
if
(a[i] > b[i])
62
return
false
;
63
return
a <
b
;
64
}
65
};
66
73
class
TuplePosCompare {
74
private
:
76
int
pos
;
77
public
:
79
forceinline
80
TuplePosCompare(
int
p) :
pos
(p) {}
82
forceinline
bool
83
operator ()(
const
Tuple& a,
const
Tuple& b) {
84
if
(a[
pos
] == b[
pos
])
85
return
a <
b
;
86
else
87
return
a[
pos
] < b[
pos
];
88
}
89
};
90
91
}
92
93
namespace
Gecode {
94
95
void
96
TupleSet::TupleSetI::finalize
(
void
) {
97
assert(!
finalized
());
98
assert(
tuples
== NULL);
99
100
// Add final largest tuple
101
IntArgs
ia(arity);
102
for
(
int
i
= arity;
i
--; )
103
ia[
i
] =
Int::Limits::max
+1;
104
int
real_min =
min
, real_max =
max
;
105
add
(ia);
106
min
= real_min;
max
= real_max;
107
108
// Domainsize
109
domsize
=
static_cast<
unsigned
int
>
(
max
-
min
) + 1;
110
111
// Allocate tuple indexing data-structures
112
tuples
=
heap
.
alloc
<Tuple*>(
arity
);
113
tuple_data
=
heap
.
alloc
<Tuple>(
size
*arity+1);
114
tuple_data[
size
*
arity
] = NULL;
115
nullpointer
= tuple_data+(
size
*
arity
);
116
117
// Rearrange the tuples for faster comparisons.
118
for
(
int
i
= arity;
i
--; )
119
tuples
[
i
] = tuple_data + (
i
*
size
);
120
for
(
int
i
= size;
i
--; )
121
tuples
[0][
i
] =
data
+ (
i
* arity);
122
123
FullTupleCompare ftc(arity);
124
Support::quicksort
(
tuples
[0], size, ftc);
125
assert(
tuples
[0][size-1][0] == ia[0]);
126
int
* new_data =
heap
.
alloc
<
int
>(size*
arity
);
127
for
(
int
t = size; t--; )
128
for
(
int
i
= arity;
i
--; )
129
new_data[t*arity +
i
] =
tuples
[0][t][
i
];
130
131
heap
.
rfree
(
data
);
132
data
= new_data;
133
excess
= -1;
134
135
// Set up indexing structure
136
for
(
int
i
= arity;
i
--; )
137
for
(
int
t = size; t--; )
138
tuples
[
i
][t] =
data
+ (t * arity);
139
for
(
int
i
= arity;
i
-->1; ) {
140
TuplePosCompare tpc(
i
);
141
Support::quicksort
(
tuples
[
i
], size, tpc);
142
}
143
144
// Set up initial last-structure
145
last
=
heap
.
alloc
<Tuple*>(
domsize
*
arity
);
146
for
(
int
i
= arity;
i
--; ) {
147
Tuple* t =
tuples
[
i
];
148
for
(
unsigned
int
d
= 0;
d
<
domsize
; ++
d
) {
149
while
(t && *t && (*t)[
i
] <
static_cast<
int
>
(
min
+
d
)) {
150
++t;
151
}
152
if
(t && *t && (*t)[
i
] ==
static_cast<
int
>
(
min
+
d
)) {
153
last
[(
i
*
domsize
) +
d
] = t;
154
++t;
155
}
else
{
156
last
[(
i
*
domsize
) +
d
] =
nullpointer
;
157
}
158
}
159
}
160
161
assert(
finalized
());
162
}
163
164
void
165
TupleSet::TupleSetI::resize
(
void
) {
166
assert(excess == 0);
167
int
ndatasize =
static_cast<
int
>
(1+
size
*1.5);
168
data =
heap
.
realloc
<
int
>(data,
size
*
arity
, ndatasize *
arity
);
169
excess = ndatasize -
size
;
170
}
171
172
SharedHandle::Object
*
173
TupleSet::TupleSetI::copy
(
void
)
const
{
174
assert(
finalized
());
175
TupleSetI
*
d
=
new
TupleSetI
;
176
d->
arity
=
arity
;
177
d->
size
=
size
;
178
d->
excess
= excess;
179
d->
min
=
min
;
180
d->
max
=
max
;
181
d->
domsize
= domsize;
182
183
// Table data
184
d->
data
=
heap
.
alloc
<
int
>(
size
*
arity
);
185
heap
.
copy
(&d->
data
[0], &data[0],
size
*arity);
186
187
// Indexing data
188
d->
tuples
=
heap
.
alloc
<Tuple*>(
arity
);
189
d->
tuple_data
=
heap
.
alloc
<Tuple>(
size
*arity+1);
190
d->
tuple_data
[
size
*
arity
] = NULL;
191
d->
nullpointer
= d->
tuple_data
+(
size
*
arity
);
192
193
// Rearrange the tuples for faster comparisons.
194
for
(
int
i
= arity;
i
--; )
195
d->
tuples
[
i
] = d->
tuple_data
+ (
i
*
size
);
196
for
(
int
a = arity; a--; ) {
197
for
(
int
i
= size;
i
--; ) {
198
d->
tuples
[
a
][
i
] = d->
data
+ (
tuples
[
a
][
i
]-data);
199
}
200
}
201
202
// Last data
203
d->
last
=
heap
.
alloc
<Tuple*>(domsize*
arity
);
204
for
(
int
i
= static_cast<int>(domsize)*
arity
;
i
--; ) {
205
d->
last
[
i
] = d->
tuple_data
+ (last[
i
]-tuple_data);
206
}
207
208
return
d
;
209
}
210
211
TupleSet::TupleSetI::~TupleSetI
(
void
) {
212
excess = -2;
213
heap
.
rfree
(
tuples
);
214
heap
.
rfree
(tuple_data);
215
heap
.
rfree
(data);
216
heap
.
rfree
(last);
217
}
218
219
}
220
221
// STATISTICS: int-prop
222