Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
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
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
418
419}}
420
421// STATISTICS: set-var
422
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.
Range iterator for computing the complement (described by template arguments)
Range iterator for computing set difference.
Range iterator for computing intersection (binary)
int min(void) const
Return smallest value of range.
int max(void) const
Return largest value of range.
void init(const Gecode::RangeList *s)
Initialize with range list s.
RangeList(void)
Default constructor.
Range iterator for computing union (binary)
Lists of ranges (intervals)
int max(void) const
Return maximum.
int min(void) const
Return minimum.
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
RangeList * next(void) const
Return next element.
unsigned int width(void) const
Return width (distance between maximum and minimum)
Range iterator for integer sets.
Definition var-imp.hpp:185
BndSetRanges(void)
Default constructor.
void init(const BndSet &s)
Initialize with BndSet s.
Sets of integers.
Definition var-imp.hpp:89
int min(void) const
Return smallest element.
bool isConsistent(void) const
Check whether internal invariants hold.
int minN(unsigned int n) const
Return n -th smallest element.
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
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.
void fst(RangeList *r)
Set first range to r.
unsigned int size(void) const
Return size.
void lst(RangeList *r)
Set last range to r.
BndSet(void)
Default constructor. Creates an empty set.
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
unsigned int _card
The cardinality this set represents.
Definition var-imp.hpp:97
bool empty(void) const
Test whether this set is empty.
bool in(int i) const
Test whether i is an element of this set.
void become(Space &home, const BndSet &s)
Make this set equal to s.
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.
unsigned int card(void) const
Return cardinality.
RangeList * ranges(void) const
Return range list for iteration.
void dispose(Space &home)
Free memory used by this set.
unsigned int _size
The size of this set.
Definition var-imp.hpp:95
RangeList * fst(void) const
Return first range.
GLBndSet(void)
Default constructor. Creates an empty set.
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
void init(Space &home)
Initialize as the empty set.
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
LUBndSet(void)
Default constructor. Creates an empty set.
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
void excludeAll(Space &home)
Exclude all elements from this set.
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
void init(I &i)
Initialize with iterator i.
RangesCompl(void)
Default constructor.
Finite set delta information for advisors.
Definition var-imp.hpp:52
Computation spaces.
Definition core.hpp:1744
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition core.hpp:2841
Numerical limits for integer variables.
Definition int.hh:114
Range and value iterators.
Definition iter.hh:41
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
Finite integer sets.
Definition var-imp.hpp:137
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition set.hh:773
#define forceinline
Definition config.hpp:194