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
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
* Last modified:
10
* $Date: 2009-01-20 23:44:27 +0100 (Tue, 20 Jan 2009) $ by $Author: schulte $
11
* $Revision: 8082 $
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
39
40
#include <
gecode/set.hh
>
41
42
namespace
Gecode
{
namespace
Set {
43
44
BndSet::BndSet
(
Space
& home,
const
IntSet
& is) {
45
if
(is.
ranges
()==0) {
46
fst
(NULL);
lst
(NULL);
_size
= 0;
47
}
else
{
48
int
n
= is.
ranges
();
49
RangeList
*
r
= home.
alloc
<
RangeList
>(
n
);
50
fst
(
r
);
lst
(
r
+
n
-1);
51
unsigned
int
s = 0;
52
for
(
int
i
=
n
;
i
--; ) {
53
s += is.
width
(
i
);
54
r
[
i
].min(is.
min
(
i
));
r
[
i
].max(is.
max
(
i
));
55
r
[
i
].next(&
r
[
i
+1]);
56
}
57
r
[
n
-1].next(NULL);
58
_size
= s;
59
}
60
assert(
isConsistent
());
61
}
62
63
bool
64
GLBndSet::include_full(
Space
& home,
int
mi,
int
ma,
SetDelta
&
d
) {
65
assert(ma >= mi);
66
assert(
fst
() != NULL);
67
68
RangeList
*
p
= NULL;
69
RangeList
*
c
=
fst
();
70
71
while
(
c
!= NULL) {
72
if
(
c
->
max
() >= mi-1){
73
if
(
c
->
min
() > ma+1) {
//in a hole before c
74
_size
+=(ma-mi+1);
75
d
._glbMin = mi;
76
d
._glbMax = ma;
77
RangeList
* q =
new
(home)
RangeList
(mi,ma,
c
);
78
if
(
p
==NULL)
79
//the new range is the first
80
fst
(q);
81
else
82
p
->next(q);
83
return
true
;
84
}
85
//if the range starts before c, update c->min and size
86
bool
result =
false
;
87
if
(
c
->
min
()>mi) {
88
_size
+=(
c
->
min
()-mi);
89
c
->
min
(mi);
90
d
._glbMin = mi;
91
result =
true
;
92
}
else
{
93
d
._glbMin =
c
->
max
()+1;
94
}
95
assert(
c
->
min
()<=mi);
96
assert(
c
->
max
()+1>=mi);
97
if
(
c
->
max
() >= ma) {
98
d
._glbMax =
c
->
min
()-1;
99
return
result;
100
}
101
RangeList* q =
c
;
102
//sum up the size of holes eaten
103
int
prevMax =
c
->
max
();
104
int
growth = 0;
105
// invariant: q->min()<=ma+1
106
while
(q->next() != NULL && q->next()->min() <= ma+1) {
107
q = q->next();
108
growth += q->
min
()-prevMax-1;
109
prevMax = q->
max
();
110
}
111
assert(growth>=0);
112
_size
+=growth;
113
if
(q->max() < ma) {
114
_size
+= ma-q->max();
115
d
._glbMax = ma;
116
}
else
{
117
d
._glbMax = q->
min
()-1;
118
}
119
c
->
max
(
std::max
(ma,q->max()));
120
if
(
c
!=q) {
121
RangeList* oldCNext =
c
->next();
122
assert(oldCNext!=NULL);
//q would have stayed c if c was last.
123
c
->next(q->next());
124
if
(q->next()==NULL){
125
assert(q==
lst
());
126
lst
(
c
);
127
}
128
oldCNext->dispose(home,q);
129
}
130
return
true
;
131
}
132
RangeList* nc =
c
->next();
133
p
=
c
;
c
=nc;
134
}
135
//the new range is disjoint from the old domain and we add it as last:
136
assert(mi>
max
()+1);
137
RangeList* q =
new
(home) RangeList(mi, ma, NULL);
138
lst
()->
next
(q);
139
lst
(q);
140
_size
+= q->width();
141
d
._glbMin = mi;
142
d
._glbMax = ma;
143
return
true
;
144
}
145
146
bool
147
LUBndSet::intersect_full(Space& home,
int
mi,
int
ma) {
148
RangeList*
p
= NULL;
149
RangeList*
c
=
fst
();
150
151
assert(
c
!= NULL);
// Never intersect with an empty set
152
153
// Skip ranges that are before mi
154
while
(
c
!= NULL &&
c
->
max
() < mi) {
155
_size
-=
c
->width();
156
RangeList *nc =
c
->next();
157
p
=
c
;
c
=nc;
158
}
159
if
(
c
== NULL) {
160
// Delete entire domain
161
fst
()->
dispose
(home,
lst
());
162
fst
(NULL);
lst
(NULL);
163
return
true
;
164
}
165
166
bool
changed =
false
;
167
if
(
c
!=
fst
()) {
168
fst
()->
dispose
(home,
p
);
169
fst
(
c
);
170
p
= NULL;
171
changed =
true
;
172
}
173
// We have found the first range that intersects with [mi,ma]
174
if
(mi >
c
->
min
()) {
175
_size
-= mi-
c
->
min
();
176
c
->
min
(mi);
177
changed =
true
;
178
}
179
180
while
(
c
!= NULL &&
c
->
max
() <= ma) {
181
RangeList *nc =
c
->next();
182
p
=
c
;
c
=nc;
183
}
184
185
if
(
c
== NULL)
186
return
changed;
187
188
RangeList* newlst =
p
;
189
if
(ma >=
c
->
min
()) {
190
_size
-=
c
->
max
() - ma;
191
c
->
max
(ma);
192
newlst =
c
;
193
RangeList* nc =
c
->next();
194
c
->next(NULL);
195
p
=
c
;
c
=nc;
196
}
else
if
(
p
!= NULL) {
197
p
->next(NULL);
198
}
199
if
(
c
!= NULL) {
200
for
(RangeList* cc =
c
; cc != NULL; cc = cc->next())
201
_size
-= cc->width();
202
c
->dispose(home,
lst
());
203
}
204
lst
(newlst);
205
if
(newlst==NULL)
206
fst
(NULL);
207
return
true
;
208
}
209
210
bool
211
LUBndSet::exclude_full(Space& home,
int
mi,
int
ma, SetDelta&
d
) {
212
assert(ma >= mi);
213
assert(mi <=
max
() && ma >=
min
() &&
214
(mi >
min
() || ma <
max
()));
215
bool
result=
false
;
216
217
RangeList*
p
= NULL;
218
RangeList*
c
=
fst
();
219
d
._lubMin =
Limits::max
+1;
220
while
(
c
!= NULL) {
221
if
(
c
->
max
() >= mi){
222
if
(
c
->
min
() > ma) {
return
result; }
//in a hole
223
224
if
(
c
->
min
()<mi &&
c
->
max
() > ma) {
//Range split:
225
RangeList* q =
226
new
(home) RangeList(ma+1,
c
->
max
(),
c
->next());
227
c
->
max
(mi-1);
228
if
(
c
==
lst
()) {
229
lst
(q);
230
}
231
c
->next(q);
232
_size
-= (ma-mi+1);
233
d
._lubMin = mi;
234
d
._lubMax = ma;
235
return
true
;
236
}
237
238
if
(
c
->
max
() > ma) {
//start of range clipped, end remains
239
d
._lubMin =
std::min
(
d
._lubMin,
c
->
min
());
240
d
._lubMax = ma;
241
_size
-=(ma-
c
->
min
()+1);
242
c
->
min
(ma+1);
243
return
true
;
244
}
245
246
if
(
c
->
min
() < mi) {
//end of range clipped, start remains
247
_size
-=(
c
->
max
()-mi+1);
248
d
._lubMin = mi;
249
d
._lubMax =
c
->
max
();
250
c
->
max
(mi-1);
251
result=
true
;
252
}
else
{
//range *c destroyed
253
d
._lubMin =
c
->
min
();
254
_size
-=
c
->width();
255
RangeList *cend =
c
;
256
while
((cend->next()!=NULL) && (cend->next()->max()<=ma)){
257
cend = cend->next();
258
_size
-=cend->width();
259
}
260
d
._lubMax = cend->
max
();
261
if
(
fst
()==
c
) {
262
fst
(cend->next());
263
}
else
{
264
p
->next(cend->next());
265
}
266
if
(
lst
()==cend) {
267
lst
(
p
);
268
}
269
RangeList* nc=cend->next();
//performs loop step!
270
c
->dispose(home,cend);
271
p
=cend;
272
c
=nc;
273
if
(
c
!= NULL &&
c
->
min
() <= ma ) {
274
//start of range clipped, end remains
275
_size
-=(ma-
c
->
min
()+1);
276
c
->
min
(ma+1);
277
d
._lubMax = ma;
278
}
279
return
true
;
280
}
281
}
282
RangeList *nc =
c
->next();
283
p
=
c
;
c
=nc;
284
}
285
return
result;
286
}
287
288
#ifndef NDEBUG
289
using namespace
Gecode::Int
;
290
#endif
291
292
bool
293
BndSet::isConsistent
(
void
)
const
{
294
#ifndef NDEBUG
295
if
(fst()==NULL) {
296
if
(lst()!=NULL ||
size
()!=0) {
297
std::cerr<<
"Strange empty set.\n"
;
298
return
false
;
299
}
else
return
true
;
300
}
301
302
if
(fst()!=NULL && lst()==NULL) {
303
std::cerr<<
"First is not null, last is.\n"
;
304
return
false
;
305
}
306
307
RangeList
*
p
=NULL;
308
RangeList
*
c
=fst();
309
310
int
min
=
c
->
min
();
311
int
max
=
c
->
max
();
312
313
if
(
max
<
min
) {
314
std::cerr <<
"Single range list twisted: ("
<<
min
<<
","
<<
max
<<
")"
;
315
return
false
;
316
}
317
318
RangeList
*nc=
c
->next();
319
p
=
c
;
c
=nc;
320
while
(
c
) {
321
if
(
max
<
min
) {
322
std::cerr <<
"1"
;
323
return
false
;
324
}
325
if
((
max
+1)>=
c
->
min
()) {
326
std::cerr <<
"2"
;
327
return
false
;
328
}
329
if
(
c
->next()==NULL &&
c
!=lst()) {
330
std::cerr <<
"3"
;
331
return
false
;
332
}
333
334
min
=
c
->
min
();
335
max
=
c
->
max
();
336
337
nc=
c
->next();
338
p
=
c
;
c
=nc;
339
}
340
#endif
341
return
true
;
342
}
343
344
345
}}
346
347
// STATISTICS: set-var
348
Gecode::Set::BndSet::min
int min(void) const
Return smallest element.
Definition:
integerset.hpp:107
Gecode::IntSet::min
int min(int i) const
Return minimum of range at position i.
Definition:
int-set-1.hpp:115
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:390
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:53
Gecode::IntSet::max
int max(int i) const
Return maximum of range at position i.
Definition:
int-set-1.hpp:121
Gecode::FloatVal::min
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition:
val.hpp:402
Gecode::Set::BndSet::max
int max(void) const
Return greatest element.
Definition:
integerset.hpp:115
Gecode::Iter::Ranges::size
unsigned int size(I &i)
Size of all ranges of range iterator i.
Definition:
ranges-operations.hpp:78
Gecode::Set::BndSet::lst
RangeList * lst(void) const
Return last range.
Definition:
integerset.hpp:59
Test::Int::Basic::i
Gecode::IntArgs i(4, 1, 2, 3, 4)
Gecode::Float::Limits::min
const FloatNum min
Smallest allowed float value.
Definition:
float.hh:850
Gecode::Space
Computation spaces.
Definition:
core.hpp:1748
Gecode::Set::BndSet::fst
RangeList * fst(void) const
Return first range.
Definition:
integerset.hpp:54
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:101
Gecode::Set::BndSet::isConsistent
bool isConsistent(void) const
Check whether internal invariants hold.
Definition:
integerset.cpp:293
Gecode::r
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition:
set.hh:784
Gecode::Space::alloc
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition:
core.hpp:2868
Gecode::Set::BndSet::_size
unsigned int _size
The size of this set.
Definition:
var-imp.hpp:99
Gecode::Set::SetDelta
Finite set delta information for advisors.
Definition:
var-imp.hpp:56
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:205
set.hh
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition:
arithmetic.cpp:71
Test::Float::Arithmetic::c
Gecode::FloatVal c(-8, 8)
Gecode::RangeList::next
RangeList * next(void) const
Return next element.
Definition:
range-list.hpp:145
n
int n
Number of negative literals for node type.
Definition:
bool-expr.cpp:238
Gecode::RangeList
Lists of ranges (intervals)
Definition:
range-list.hpp:53
Gecode::IntSet::width
unsigned int width(int i) const
Return width of range at position i.
Definition:
int-set-1.hpp:127
p
int p
Number of positive literals for node type.
Definition:
bool-expr.cpp:236
Gecode::Float::Limits::max
const FloatNum max
Largest allowed float value.
Definition:
float.hh:848
Gecode::Set::BndSet::BndSet
BndSet(void)
Default constructor. Creates an empty set.
Definition:
integerset.hpp:50
Gecode::IntSet::ranges
int ranges(void) const
Return number of ranges of the specification.
Definition:
int-set-1.hpp:134
Gecode::Int
Finite domain integers.
Definition:
abs.hpp:42