Generated on Thu Jul 21 2022 00:00:00 for Gecode by doxygen 1.9.4
integerset.hpp
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 * Gabor Szokoli <szokoli@gecode.org>
6 * Christian Schulte <schulte@gecode.org>
7 *
8 * Copyright:
9 * Guido Tack, 2004
10 * Christian Schulte, 2004
11 * Gabor Szokoli, 2004
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
38namespace Gecode { namespace Set {
39
40 /*
41 * BndSet
42 *
43 */
44
47 first(NULL), last(NULL), _size(0), _card(0) {}
48
50 BndSet::fst(void) const {
51 return first;
52 }
53
55 BndSet::lst(void) const {
56 return last;
57 }
58
59 forceinline void
61 if (fst()!=NULL)
62 fst()->dispose(home,lst());
63 }
64
65 forceinline void
67 first = f;
68 }
69
70 forceinline void
72 last = l;
73 }
74
76 BndSet::BndSet(Space& home, int mn, int mx) {
77 if (mn>mx) {
78 fst(NULL); lst(NULL); _size = 0;
79 } else {
80 RangeList* p =
81 new (home) RangeList(mn,mx,NULL);
82 fst(p); lst(p);
83 _size = static_cast<unsigned int>(mx-mn+1);
84 }
85 }
86
88 BndSet::ranges(void) const {
89 return fst();
90 }
91
92 forceinline unsigned int
93 BndSet::size(void) const {
94 return _size;
95 }
96
97 forceinline bool
98 BndSet::empty(void) const {
99 return (_size==0);
100 }
101
102 forceinline int
103 BndSet::min(void) const {
104 if (fst()==NULL)
105 return MIN_OF_EMPTY;
106 else
107 return fst()->min();
108 }
109
110 forceinline int
111 BndSet::max(void) const {
112 if (lst()==NULL)
113 return MAX_OF_EMPTY;
114 else
115 return lst()->max();
116 }
117
118 // nth smallest element
119 forceinline int
120 BndSet::minN(unsigned int n) const {
121 for (RangeList* c = fst(); c != NULL; c = c->next()) {
122 if (c->width() > n)
123 return static_cast<int>(c->min() + n);
124 n -= c->width();
125 }
126 return MIN_OF_EMPTY;
127 }
128
129 forceinline unsigned int
130 BndSet::card(void) const {
131 return _card;
132 }
133
134 forceinline void
135 BndSet::card(unsigned int c) {
136 _card = c;
137 }
138
139 forceinline void
141 if (d.fst() == fst())
142 return;
143 if (fst() != NULL)
144 fst()->dispose(home,lst());
145 _size = d.size();
146 if (_size == 0) {
147 fst(NULL); lst(NULL);
148 return;
149 }
150
151 int n=0;
152 for (RangeList* c = d.fst(); c != NULL; c = c->next())
153 n++;
154
155 RangeList* r = home.alloc<RangeList>(n);
156 fst(r); lst(r+n-1);
157
158 {
159 RangeList* c = d.fst();
160 for (int i=0; i<n; i++) {
161 r[i].min(c->min());
162 r[i].max(c->max());
163 r[i].next(&r[i+1]);
164 c = c->next();
165 }
166 }
167 r[n-1].next(NULL);
168 }
169
170 template<class I> forceinline bool
171 BndSet::overwrite(Space& home, I& ri) {
172 // Is new domain empty?
173 if (!ri()) {
174 //Was it empty?
175 if (fst()==NULL)
176 return false;
177 fst()->dispose(home,lst());
178 _size=0; fst(NULL); lst(NULL);
179 return true;
180 }
181
182 RangeList* f =
183 new (home) RangeList(ri.min(),ri.max(),NULL);
184 RangeList* l = f;
185 unsigned int s = ri.width();
186
187 ++ri;
188
189 while (ri()) {
190 RangeList *n = new (home) RangeList(ri.min(),ri.max(),NULL);
191 l->next(n);
192 l=n;
193 s += ri.width();
194 ++ri;
195 }
196
197 if (fst() != NULL)
198 fst()->dispose(home,lst());
199 fst(f); lst(l);
200
201 // If the size did not change, nothing changed, as overwriting
202 // must not at the same time include and exclude elements.
203 if (size() == s)
204 return false;
205
206 _size = s;
207 return true;
208 }
209
210 forceinline void
211 BndSet::become(Space& home, const BndSet& that) {
212 if (fst()!=NULL) {
213 assert(lst()!=NULL);
214 assert(fst()!= that.fst());
215 fst()->dispose(home,lst());
216 }
217 fst(that.fst());
218 lst(that.lst());
219 _size = that.size();
220 assert(isConsistent());
221 }
222
223 forceinline bool
224 BndSet::in(int i) const {
225 for (RangeList* c = fst(); c != NULL; c = c->next()) {
226 if (c->min() <= i && c->max() >= i)
227 return true;
228 if (c->min() > i)
229 return false;
230 }
231 return false;
232 }
233
234 /*
235 * Range iterator for BndSets
236 *
237 */
238
241
244 : Iter::Ranges::RangeList(s.ranges()) {}
245
246 forceinline void
249 }
250
251 /*
252 * GLBndSet
253 *
254 */
255
258
261
263 GLBndSet::GLBndSet(Space& home, int mi, int ma)
264 : BndSet(home,mi,ma) {}
265
268 : BndSet(home,s) {}
269
270 forceinline void
272 dispose(home);
273 fst(NULL);
274 lst(NULL);
275 _size = 0;
276 }
277
278 forceinline bool
279 GLBndSet::include(Space& home, int mi, int ma, SetDelta& d) {
280 assert(ma >= mi);
281 if (fst()==NULL) {
282 RangeList* p = new (home) RangeList(mi,ma,NULL);
283 fst(p);
284 lst(p);
285 _size=static_cast<unsigned int>(ma-mi+1);
286 d._glbMin = mi;
287 d._glbMax = ma;
288 return true;
289 }
290 bool ret = include_full(home, mi, ma, d);
291 assert(isConsistent());
292 return ret;
293 }
294
295 template<class I> bool
297 if (!i())
298 return false;
299 BndSetRanges j(*this);
301 bool me = overwrite(home, ij);
302 assert(isConsistent());
303 return me;
304 }
305
306
307 /*
308 * LUBndSet
309 *
310 */
311
314
317 : BndSet(home,Limits::min,Limits::max) {}
318
320 LUBndSet::LUBndSet(Space& home, int mi, int ma)
321 : BndSet(home,mi,ma) {}
322
325 : BndSet(home,s) {}
326
327 forceinline void
329 RangeList *p =
330 new (home) RangeList(Limits::min,
332 NULL);
333 fst(p);
334 lst(p);
336 }
337
338 forceinline bool
339 LUBndSet::exclude(Space& home, int mi, int ma, SetDelta& d) {
340 assert(ma >= mi);
341 if ((mi > max()) || (ma < min())) { return false; }
342 if (mi <= min() && ma >= max() ) { //the range covers the whole set
343 d._lubMin = min();
344 d._lubMax = max();
345 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
346 _size=0;
347 return true;
348 }
349 bool ret = exclude_full(home, mi, ma, d);
350 assert(isConsistent());
351 return ret;
352 }
353
354 forceinline bool
355 LUBndSet::intersect(Space& home, int mi, int ma) {
356 assert(ma >= mi);
357 if ((mi <= min()) && (ma >= max())) { return false; }
358 if (_size == 0) return false;
359 if (ma < min() || mi > max() ) { // empty the whole set
360 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
361 _size=0;
362 return true;
363 }
364 bool ret = intersect_full(home, mi, ma);
365 assert(isConsistent());
366 return ret;
367 }
368
369 template<class I> bool
371 if (fst()==NULL) { return false; }
372 if (!i()) {
373 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
374 _size=0;
375 return true;
376 }
377 BndSetRanges j(*this);
379 bool ret = overwrite(home, ij);
380 assert(isConsistent());
381 return ret;
382 }
383
384 template<class I> bool
386 if (!i()) { return false; }
387 BndSetRanges j(*this);
389 bool ret = overwrite(home, ij);
390 assert(isConsistent());
391 return ret;
392 }
393
394 forceinline void
396 fst()->dispose(home,lst()); fst(NULL); lst(NULL);
397 _size=0;
398 }
399
400 /*
401 * A complement iterator spezialized for the BndSet limits
402 *
403 */
404 template<class I>
406
407 template<class I>
409 : Iter::Ranges::Compl<Limits::min,
410 Limits::max,
411 I>(i) {}
412
413 template<class I> void
416 Limits::max,I>::init(i);
417 }
418
419}}
420
421// STATISTICS: set-var
422
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:386
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:398
Integer sets.
Definition: int.hh:174
unsigned int size(void) const
Return size (cardinality) of set.
Definition: int-set-1.hpp:198
Range iterator for computing the complement (described by template arguments)
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
Range iterator for computing intersection (binary)
void init(const Gecode::RangeList *s)
Initialize with range list s.
Range iterator for computing union (binary)
Lists of ranges (intervals)
Definition: range-list.hpp:49
int max(void) const
Return maximum.
Definition: range-list.hpp:168
int min(void) const
Return minimum.
Definition: range-list.hpp:164
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: range-list.hpp:201
Range iterator for integer sets.
Definition: var-imp.hpp:185
BndSetRanges(void)
Default constructor.
Definition: integerset.hpp:240
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:247
Sets of integers.
Definition: var-imp.hpp:89
int min(void) const
Return smallest element.
Definition: integerset.hpp:103
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:289
int minN(unsigned int n) const
Return n -th smallest element.
Definition: integerset.hpp:120
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
Definition: integerset.hpp:171
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:110
RangeList * lst(void) const
Return last range.
Definition: integerset.hpp:55
void fst(RangeList *r)
Set first range to r.
Definition: integerset.hpp:66
unsigned int size(void) const
Return size.
Definition: integerset.hpp:93
void lst(RangeList *r)
Set last range to r.
Definition: integerset.hpp:71
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:46
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:140
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:97
bool empty(void) const
Test whether this set is empty.
Definition: integerset.hpp:98
bool in(int i) const
Test whether i is an element of this set.
Definition: integerset.hpp:224
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition: integerset.hpp:211
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:112
int max(void) const
Return greatest element.
Definition: integerset.hpp:111
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:130
RangeList * ranges(void) const
Return range list for iteration.
Definition: integerset.hpp:88
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:60
unsigned int _size
The size of this set.
Definition: var-imp.hpp:95
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:50
GLBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:257
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
void init(Space &home)
Initialize as the empty set.
Definition: integerset.hpp:271
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:279
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
Definition: integerset.hpp:328
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:370
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition: integerset.hpp:385
LUBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:313
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition: integerset.hpp:355
void excludeAll(Space &home)
Exclude all elements from this set.
Definition: integerset.hpp:395
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition: integerset.hpp:339
void init(I &i)
Initialize with iterator i.
Definition: integerset.hpp:414
RangesCompl(void)
Default constructor.
Definition: integerset.hpp:405
Finite set delta information for advisors.
Definition: var-imp.hpp:52
Computation spaces.
Definition: core.hpp:1742
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
const int min
Smallest allowed integer in integer set.
Definition: set.hh:99
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:101
const int max
Largest allowed integer in integer set.
Definition: set.hh:97
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)
Card _card("Int::Card")
#define forceinline
Definition: config.hpp:194