main page
modules
namespaces
classes
files
Gecode home
Generated on Wed Jan 1 2020 10:37:59 for Gecode by
doxygen
1.8.16
gecode
set
var-imp
integerset.cpp
Go to the documentation of this file.
1
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2
/*
3
* Main authors:
4
* Guido Tack <tack@gecode.org>
5
*
6
* Copyright:
7
* Guido Tack, 2004
8
*
9
* This file is part of Gecode, the generic constraint
10
* development environment:
11
* http://www.gecode.org
12
*
13
* Permission is hereby granted, free of charge, to any person obtaining
14
* a copy of this software and associated documentation files (the
15
* "Software"), to deal in the Software without restriction, including
16
* without limitation the rights to use, copy, modify, merge, publish,
17
* distribute, sublicense, and/or sell copies of the Software, and to
18
* permit persons to whom the Software is furnished to do so, subject to
19
* the following conditions:
20
*
21
* The above copyright notice and this permission notice shall be
22
* included in all copies or substantial portions of the Software.
23
*
24
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31
*
32
*/
33
34
35
36
#include <
gecode/set.hh
>
37
38
namespace
Gecode
{
namespace
Set {
39
40
BndSet::BndSet
(
Space
& home,
const
IntSet
& is) {
41
if
(is.
ranges
()==0) {
42
fst
(NULL);
lst
(NULL);
_size
= 0;
43
}
else
{
44
int
n
= is.
ranges
();
45
RangeList
*
r
= home.
alloc
<
RangeList
>(
n
);
46
fst
(
r
);
lst
(
r
+
n
-1);
47
unsigned
int
s = 0;
48
for
(
int
i
=
n
;
i
--; ) {
49
s += is.
width
(
i
);
50
r
[
i
].min(is.
min
(
i
));
r
[
i
].max(is.
max
(
i
));
51
r
[
i
].next(&
r
[
i
+1]);
52
}
53
r
[
n
-1].next(NULL);
54
_size
= s;
55
}
56
assert(
isConsistent
());
57
}
58
59
bool
60
GLBndSet::include_full(
Space
& home,
int
mi,
int
ma,
SetDelta
&
d
) {
61
assert(ma >= mi);
62
assert(
fst
() != NULL);
63
64
RangeList
*
p
= NULL;
65
RangeList
*
c
=
fst
();
66
67
while
(
c
!= NULL) {
68
if
(
c
->
max
() >= mi-1) {
69
if
(
c
->
min
() > ma+1) {
//in a hole before c
70
_size
+=(ma-mi+1);
71
d
._glbMin = mi;
72
d
._glbMax = ma;
73
RangeList
* q =
new
(home)
RangeList
(mi,ma,
c
);
74
if
(
p
==NULL)
75
//the new range is the first
76
fst
(q);
77
else
78
p
->next(q);
79
return
true
;
80
}
81
//if the range starts before c, update c->min and size
82
bool
result =
false
;
83
if
(
c
->
min
()>mi) {
84
_size
+=(
c
->
min
()-mi);
85
c
->
min
(mi);
86
d
._glbMin = mi;
87
result =
true
;
88
}
else
{
89
d
._glbMin =
c
->
max
()+1;
90
}
91
assert(
c
->
min
()<=mi);
92
assert(
c
->
max
()+1>=mi);
93
if
(
c
->
max
() >= ma) {
94
d
._glbMax =
c
->
min
()-1;
95
return
result;
96
}
97
RangeList* q =
c
;
98
//sum up the size of holes eaten
99
int
prevMax =
c
->
max
();
100
int
growth = 0;
101
// invariant: q->min()<=ma+1
102
while
(q->next() != NULL && q->next()->min() <= ma+1) {
103
q = q->next();
104
growth += q->
min
()-prevMax-1;
105
prevMax = q->
max
();
106
}
107
assert(growth>=0);
108
_size
+=growth;
109
if
(q->max() < ma) {
110
_size
+= ma-q->max();
111
d
._glbMax = ma;
112
}
else
{
113
d
._glbMax = q->
min
()-1;
114
}
115
c
->
max
(
std::max
(ma,q->max()));
116
if
(
c
!=q) {
117
RangeList* oldCNext =
c
->next();
118
assert(oldCNext!=NULL);
//q would have stayed c if c was last.
119
c
->next(q->next());
120
if
(q->next()==NULL) {
121
assert(q==
lst
());
122
lst
(
c
);
123
}
124
oldCNext->dispose(home,q);
125
}
126
return
true
;
127
}
128
RangeList* nc =
c
->next();
129
p
=
c
;
c
=nc;
130
}
131
//the new range is disjoint from the old domain and we add it as last:
132
assert(mi>
max
()+1);
133
RangeList* q =
new
(home) RangeList(mi, ma, NULL);
134
lst
()->
next
(q);
135
lst
(q);
136
_size
+= q->width();
137
d
._glbMin = mi;
138
d
._glbMax = ma;
139
return
true
;
140
}
141
142
bool
143
LUBndSet::intersect_full(Space& home,
int
mi,
int
ma) {
144
RangeList*
p
= NULL;
145
RangeList*
c
=
fst
();
146
147
assert(
c
!= NULL);
// Never intersect with an empty set
148
149
// Skip ranges that are before mi
150
while
(
c
!= NULL &&
c
->
max
() < mi) {
151
_size
-=
c
->width();
152
RangeList *nc =
c
->next();
153
p
=
c
;
c
=nc;
154
}
155
if
(
c
== NULL) {
156
// Delete entire domain
157
fst
()->
dispose
(home,
lst
());
158
fst
(NULL);
lst
(NULL);
159
return
true
;
160
}
161
162
bool
changed =
false
;
163
if
(
c
!=
fst
()) {
164
fst
()->
dispose
(home,
p
);
165
fst
(
c
);
166
p
= NULL;
167
changed =
true
;
168
}
169
// We have found the first range that intersects with [mi,ma]
170
if
(mi >
c
->
min
()) {
171
_size
-= mi-
c
->
min
();
172
c
->
min
(mi);
173
changed =
true
;
174
}
175
176
while
(
c
!= NULL &&
c
->
max
() <= ma) {
177
RangeList *nc =
c
->next();
178
p
=
c
;
c
=nc;
179
}
180
181
if
(
c
== NULL)
182
return
changed;
183
184
RangeList* newlst =
p
;
185
if
(ma >=
c
->
min
()) {
186
_size
-=
c
->
max
() - ma;
187
c
->
max
(ma);
188
newlst =
c
;
189
RangeList* nc =
c
->next();
190
c
->next(NULL);
191
p
=
c
;
c
=nc;
192
}
else
if
(
p
!= NULL) {
193
p
->next(NULL);
194
}
195
if
(
c
!= NULL) {
196
for
(RangeList* cc =
c
; cc != NULL; cc = cc->next())
197
_size
-= cc->width();
198
c
->dispose(home,
lst
());
199
}
200
lst
(newlst);
201
if
(newlst==NULL)
202
fst
(NULL);
203
return
true
;
204
}
205
206
bool
207
LUBndSet::exclude_full(Space& home,
int
mi,
int
ma, SetDelta&
d
) {
208
assert(ma >= mi);
209
assert(mi <=
max
() && ma >=
min
() &&
210
(mi >
min
() || ma <
max
()));
211
bool
result=
false
;
212
213
RangeList*
p
= NULL;
214
RangeList*
c
=
fst
();
215
d
._lubMin =
Limits::max
+1;
216
while
(
c
!= NULL) {
217
if
(
c
->
max
() >= mi) {
218
if
(
c
->
min
() > ma) {
return
result; }
//in a hole
219
220
if
(
c
->
min
()<mi &&
c
->
max
() > ma) {
//Range split:
221
RangeList* q =
222
new
(home) RangeList(ma+1,
c
->
max
(),
c
->next());
223
c
->
max
(mi-1);
224
if
(
c
==
lst
()) {
225
lst
(q);
226
}
227
c
->next(q);
228
_size
-= (ma-mi+1);
229
d
._lubMin = mi;
230
d
._lubMax = ma;
231
return
true
;
232
}
233
234
if
(
c
->
max
() > ma) {
//start of range clipped, end remains
235
d
._lubMin =
std::min
(
d
._lubMin,
c
->
min
());
236
d
._lubMax = ma;
237
_size
-=(ma-
c
->
min
()+1);
238
c
->
min
(ma+1);
239
return
true
;
240
}
241
242
if
(
c
->
min
() < mi) {
//end of range clipped, start remains
243
_size
-=(
c
->
max
()-mi+1);
244
d
._lubMin = mi;
245
d
._lubMax =
c
->
max
();
246
c
->
max
(mi-1);
247
result=
true
;
248
}
else
{
//range *c destroyed
249
d
._lubMin =
c
->
min
();
250
_size
-=
c
->width();
251
RangeList *cend =
c
;
252
while
((cend->next()!=NULL) && (cend->next()->max()<=ma)) {
253
cend = cend->next();
254
_size
-=cend->width();
255
}
256
d
._lubMax = cend->
max
();
257
if
(
fst
()==
c
) {
258
fst
(cend->next());
259
}
else
{
260
p
->next(cend->next());
261
}
262
if
(
lst
()==cend) {
263
lst
(
p
);
264
}
265
RangeList* nc=cend->next();
//performs loop step!
266
c
->dispose(home,cend);
267
p
=cend;
268
c
=nc;
269
if
(
c
!= NULL &&
c
->
min
() <= ma ) {
270
//start of range clipped, end remains
271
_size
-=(ma-
c
->
min
()+1);
272
c
->
min
(ma+1);
273
d
._lubMax = ma;
274
}
275
return
true
;
276
}
277
}
278
RangeList *nc =
c
->next();
279
p
=
c
;
c
=nc;
280
}
281
return
result;
282
}
283
284
#ifndef NDEBUG
285
using namespace
Gecode::Int
;
286
#endif
287
288
bool
289
BndSet::isConsistent
(
void
)
const
{
290
#ifndef NDEBUG
291
if
(fst()==NULL) {
292
if
(lst()!=NULL ||
size
()!=0) {
293
std::cerr<<
"Strange empty set.\n"
;
294
return
false
;
295
}
else
return
true
;
296
}
297
298
if
(fst()!=NULL && lst()==NULL) {
299
std::cerr<<
"First is not null, last is.\n"
;
300
return
false
;
301
}
302
303
RangeList
*
p
=NULL;
304
RangeList
*
c
=fst();
305
306
int
min
=
c
->
min
();
307
int
max
=
c
->
max
();
308
309
if
(
max
<
min
) {
310
std::cerr <<
"Single range list twisted: ("
<<
min
<<
","
<<
max
<<
")"
;
311
return
false
;
312
}
313
314
RangeList
*nc=
c
->next();
315
p
=
c
;
c
=nc;
316
while
(
c
) {
317
if
(
max
<
min
) {
318
std::cerr <<
"1"
;
319
return
false
;
320
}
321
if
((
max
+1)>=
c
->
min
()) {
322
std::cerr <<
"2"
;
323
return
false
;
324
}
325
if
(
c
->next()==NULL &&
c
!=lst()) {
326
std::cerr <<
"3"
;
327
return
false
;
328
}
329
330
min
=
c
->
min
();
331
max
=
c
->
max
();
332
333
nc=
c
->next();
334
p
=
c
;
c
=nc;
335
}
336
#endif
337
return
true
;
338
}
339
340
341
}}
342
343
// STATISTICS: set-var
344
Gecode::Set::BndSet::min
int min(void) const
Return smallest element.
Definition:
integerset.hpp:103
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition:
int-set-1.hpp:152
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:386
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:49
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition:
int-set-1.hpp:158
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:398
Gecode::Set::BndSet::max
int max(void) const
Return greatest element.
Definition:
integerset.hpp:111
Gecode::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition:
ranges-operations.hpp:74
Gecode::Set::BndSet::lst
RangeList * lst(void) const
Return last range.
Definition:
integerset.hpp:55
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:846
Gecode::Space
Computation spaces.
Definition:
core.hpp:1742
Gecode::Set::BndSet::fst
RangeList * fst(void) const
Return first range.
Definition:
integerset.hpp:50
Gecode
Gecode toplevel namespace
Gecode::IntSet
Integer sets.
Definition:
int.hh:174
Gecode::Set::Limits::max
const int max
Largest allowed integer in integer set.
Definition:
set.hh:97
Gecode::Set::BndSet::isConsistent
bool isConsistent(void) const
Check whether internal invariants hold.
Definition:
integerset.cpp:289
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:767
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition:
core.hpp:2837
Gecode::Set::BndSet::_size
unsigned int _size
The size of this set.
Definition:
var-imp.hpp:95
Gecode::Set::SetDelta
Finite set delta information for advisors.
Definition:
var-imp.hpp:52
Test::Int::Distinct::d
Gecode::IntSet d(v, 7)
Gecode::RangeList::dispose
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition:
range-list.hpp:201
set.hh
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:67
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Gecode::RangeList::next
RangeList * next(void) const
Return next element.
Definition:
range-list.hpp:141
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:234
Gecode::RangeList
Lists of ranges (intervals)
Definition:
range-list.hpp:49
Gecode::IntSet::width
unsigned int width(int i) const
Return width of range at position i.
Definition:
int-set-1.hpp:164
Test::Int::Basic::i
Gecode::IntArgs i({1, 2, 3, 4})
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:232
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:844
Gecode::Set::BndSet::BndSet
BndSet(void)
Default constructor. Creates an empty set.
Definition:
integerset.hpp:46
Gecode::IntSet::ranges
int ranges(void) const
Return number of ranges of the specification.
Definition:
int-set-1.hpp:171
Gecode::Int
Finite domain integers.
Definition:
abs.hpp:38