main page
modules
namespaces
classes
files
Gecode home
Generated on Tue Jan 28 2020 00:00:00 for Gecode by
doxygen
1.8.17
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-14 17:46:18 +0200 (Wed, 14 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
Gecode::Heap::copy
static T * copy(T *d, const T *s, long unsigned int n)
Copy n objects starting at s to d.
Definition:
heap.hpp:587
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition:
int-set-1.hpp:115
forceinline
#define forceinline
Definition:
config.hpp:173
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition:
int-set-1.hpp:121
int.hh
Gecode::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition:
ranges-operations.hpp:78
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::TupleSet::min
int min(void) const
Minimum domain element.
Definition:
tuple-set.hpp:155
t
NodeType t
Type of node.
Definition:
bool-expr.cpp:234
Gecode::TupleSet::max
int max(void) const
Maximum domain element.
Definition:
tuple-set.hpp:162
Gecode::SharedHandle::Object
The shared object.
Definition:
core.hpp:88
Gecode::TupleSet::TupleSetI::~TupleSetI
virtual ~TupleSetI(void)
Delete implementation.
Definition:
tuple-set.cpp:211
Gecode::Heap::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from heap.
Definition:
heap.hpp:435
Gecode::IntSet::size
unsigned int size(void) const
Return size (cardinality) of set.
Definition:
int-set-1.hpp:161
Gecode::TupleSet::TupleSetI::finalized
bool finalized(void) const
Is datastructure finalized.
Definition:
tuple-set.hpp:43
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition:
sort.hpp:134
Gecode
Gecode toplevel namespace
Gecode::TupleSet::TupleSetI::min
int min
Minimum and maximum in domain-values.
Definition:
int.hh:2189
Gecode::TupleSet::TupleSetI::nullpointer
Tuple * nullpointer
Pointer to nullptr-pointer.
Definition:
int.hh:2195
a
struct Gecode::@579::NNF::@61::@63 a
For atomic nodes.
b
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Gecode::TupleSet::TupleSetI::finalize
void finalize(void)
Finalize datastructure (disallows additions of more Tuples)
Definition:
tuple-set.cpp:96
Gecode::TupleSet::TupleSetI::add
void add(T t)
Add Tuple. Assumes that arity matches.
Definition:
tuple-set.hpp:67
Gecode::TupleSet::TupleSetI::arity
int arity
Arity.
Definition:
int.hh:2177
Gecode::TupleSet::TupleSetI::copy
virtual SharedHandle::Object * copy(void) const
Create a copy.
Definition:
tuple-set.cpp:173
Gecode::TupleSet::Tuple
int * Tuple
Type of a tuple.
Definition:
int.hh:2167
Gecode::TupleSet::TupleSetI::max
int max
Definition:
int.hh:2189
Gecode::Int::Limits::max
const int max
Largest allowed integer value.
Definition:
int.hh:116
Gecode::Int::Extensional::Tuple
TupleSet::Tuple Tuple
Definition:
extensional.hh:229
Gecode::TupleSet::finalized
bool finalized(void) const
Is tuple set finalized.
Definition:
tuple-set.hpp:127
Gecode::heap
Heap heap
The single global heap.
Definition:
heap.cpp:48
Gecode::TupleSet::TupleSetI::size
int size
Number of Tuples.
Definition:
int.hh:2179
Gecode::TupleSet::TupleSetI::data
int * data
Tuples data.
Definition:
int.hh:2185
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
Gecode::TupleSet::TupleSetI::domsize
unsigned int domsize
Domain size.
Definition:
int.hh:2191
Gecode::TupleSet::TupleSetI::tuple_data
Tuple * tuple_data
Tuple index data.
Definition:
int.hh:2183
Gecode::TupleSet::tuples
int tuples(void) const
Number of tuples.
Definition:
tuple-set.hpp:141
Gecode::TupleSet::TupleSetI::resize
void resize(void)
Resize data cache.
Definition:
tuple-set.cpp:165
Gecode::TupleSet::arity
int arity(void) const
Arity of tuple set.
Definition:
tuple-set.hpp:134
Gecode::TupleSet::TupleSetI::tuples
Tuple ** tuples
Tuples index.
Definition:
int.hh:2181
Gecode::TupleSet::TupleSetI::excess
int excess
Excess storage.
Definition:
int.hh:2187
Gecode::Heap::rfree
void rfree(void *p)
Free memory block starting at p.
Definition:
heap.hpp:375
Gecode::IntArgs
Passing integer arguments.
Definition:
int.hh:610
Gecode::Float::Arithmetic::pos
bool pos(const View &x)
Test whether x is postive.
Definition:
mult.hpp:45
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:236
Gecode::Heap::realloc
T * realloc(T *b, long unsigned int n, long unsigned int m)
Reallocate block of n objects starting at b to m objects of type T from heap.
Definition:
heap.hpp:486
Gecode::TupleSet::TupleSetI
Data stored for a Table.
Definition:
int.hh:2173
Gecode::TupleSet::TupleSetI::last
Tuple ** last
Initial last structure.
Definition:
int.hh:2193