Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.9.1
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  * Last modified:
14  * $Date: 2011-09-19 14:02:26 +0200 (Mon, 19 Sep 2011) $ by $Author: schulte $
15  * $Revision: 12400 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Set {
43 
44  /*
45  * BndSet
46  *
47  */
48 
51  first(NULL), last(NULL), _size(0), _card(0) {}
52 
54  BndSet::fst(void) const {
55  return first;
56  }
57 
59  BndSet::lst(void) const {
60  return last;
61  }
62 
63  forceinline void
65  if (fst()!=NULL)
66  fst()->dispose(home,lst());
67  }
68 
69  forceinline void
71  first = f;
72  }
73 
74  forceinline void
76  last = l;
77  }
78 
80  BndSet::BndSet(Space& home, int mn, int mx) {
81  if (mn>mx) {
82  fst(NULL); lst(NULL); _size = 0;
83  } else {
84  RangeList* p =
85  new (home) RangeList(mn,mx,NULL);
86  fst(p); lst(p);
87  _size = static_cast<unsigned int>(mx-mn+1);
88  }
89  }
90 
92  BndSet::ranges(void) const {
93  return fst();
94  }
95 
96  forceinline unsigned int
97  BndSet::size(void) const {
98  return _size;
99  }
100 
101  forceinline bool
102  BndSet::empty(void) const {
103  return (_size==0);
104  }
105 
106  forceinline int
107  BndSet::min(void) const {
108  if (fst()==NULL)
109  return MIN_OF_EMPTY;
110  else
111  return fst()->min();
112  }
113 
114  forceinline int
115  BndSet::max(void) const {
116  if (lst()==NULL)
117  return MAX_OF_EMPTY;
118  else
119  return lst()->max();
120  }
121 
122  // nth smallest element
123  forceinline int
124  BndSet::minN(unsigned int n) const {
125  for (RangeList* c = fst(); c != NULL; c = c->next()) {
126  if (c->width() > n)
127  return static_cast<int>(c->min() + n);
128  n -= c->width();
129  }
130  return MIN_OF_EMPTY;
131  }
132 
133  forceinline unsigned int
134  BndSet::card(void) const {
135  return _card;
136  }
137 
138  forceinline void
139  BndSet::card(unsigned int c) {
140  _card = c;
141  }
142 
143  forceinline void
145  if (d.fst() == fst())
146  return;
147  if (fst() != NULL)
148  fst()->dispose(home,lst());
149  _size = d.size();
150  if (_size == 0) {
151  fst(NULL); lst(NULL);
152  return;
153  }
154 
155  int n=0;
156  for (RangeList* c = d.fst(); c != NULL; c = c->next())
157  n++;
158 
159  RangeList* r = home.alloc<RangeList>(n);
160  fst(r); lst(r+n-1);
161 
162  {
163  RangeList* c = d.fst();
164  for (int i=0; i<n; i++) {
165  r[i].min(c->min());
166  r[i].max(c->max());
167  r[i].next(&r[i+1]);
168  c = c->next();
169  }
170  }
171  r[n-1].next(NULL);
172  }
173 
174  template<class I> forceinline bool
175  BndSet::overwrite(Space& home, I& ri) {
176  // Is new domain empty?
177  if (!ri()) {
178  //Was it empty?
179  if (fst()==NULL)
180  return false;
181  fst()->dispose(home,lst());
182  _size=0; fst(NULL); lst(NULL);
183  return true;
184  }
185 
186  RangeList* f =
187  new (home) RangeList(ri.min(),ri.max(),NULL);
188  RangeList* l = f;
189  unsigned int s = ri.width();
190 
191  ++ri;
192 
193  while (ri()){
194  RangeList *n = new (home) RangeList(ri.min(),ri.max(),NULL);
195  l->next(n);
196  l=n;
197  s += ri.width();
198  ++ri;
199  }
200 
201  if (fst() != NULL)
202  fst()->dispose(home,lst());
203  fst(f); lst(l);
204 
205  // If the size did not change, nothing changed, as overwriting
206  // must not at the same time include and exclude elements.
207  if (size() == s)
208  return false;
209 
210  _size = s;
211  return true;
212  }
213 
214  forceinline void
215  BndSet::become(Space& home, const BndSet& that){
216  if (fst()!=NULL){
217  assert(lst()!=NULL);
218  assert(fst()!= that.fst());
219  fst()->dispose(home,lst());
220  }
221  fst(that.fst());
222  lst(that.lst());
223  _size = that.size();
224  assert(isConsistent());
225  }
226 
227  forceinline bool
228  BndSet::in(int i) const {
229  for (RangeList* c = fst(); c != NULL; c = c->next()) {
230  if (c->min() <= i && c->max() >= i)
231  return true;
232  if (c->min() > i)
233  return false;
234  }
235  return false;
236  }
237 
238  /*
239  * Range iterator for BndSets
240  *
241  */
242 
245 
248  : Iter::Ranges::RangeList(s.ranges()) {}
249 
250  forceinline void
253  }
254 
255  /*
256  * GLBndSet
257  *
258  */
259 
262 
265 
267  GLBndSet::GLBndSet(Space& home, int mi, int ma)
268  : BndSet(home,mi,ma) {}
269 
271  GLBndSet::GLBndSet(Space& home, const IntSet& s)
272  : BndSet(home,s) {}
273 
274  forceinline void
276  dispose(home);
277  fst(NULL);
278  lst(NULL);
279  _size = 0;
280  }
281 
282  forceinline bool
283  GLBndSet::include(Space& home, int mi, int ma, SetDelta& d) {
284  assert(ma >= mi);
285  if (fst()==NULL) {
286  RangeList* p = new (home) RangeList(mi,ma,NULL);
287  fst(p);
288  lst(p);
289  _size=static_cast<unsigned int>(ma-mi+1);
290  d._glbMin = mi;
291  d._glbMax = ma;
292  return true;
293  }
294  bool ret = include_full(home, mi, ma, d);
295  assert(isConsistent());
296  return ret;
297  }
298 
299  template<class I> bool
301  if (!i())
302  return false;
303  BndSetRanges j(*this);
305  bool me = overwrite(home, ij);
306  assert(isConsistent());
307  return me;
308  }
309 
310 
311  /*
312  * LUBndSet
313  *
314  */
315 
318 
321  : BndSet(home,Limits::min,Limits::max) {}
322 
324  LUBndSet::LUBndSet(Space& home, int mi, int ma)
325  : BndSet(home,mi,ma) {}
326 
328  LUBndSet::LUBndSet(Space& home, const IntSet& s)
329  : BndSet(home,s) {}
330 
331  forceinline void
333  RangeList *p =
334  new (home) RangeList(Limits::min,
335  Limits::max,
336  NULL);
337  fst(p);
338  lst(p);
340  }
341 
342  forceinline bool
343  LUBndSet::exclude(Space& home, int mi, int ma, SetDelta& d) {
344  assert(ma >= mi);
345  if ((mi > max()) || (ma < min())) { return false; }
346  if (mi <= min() && ma >= max() ) { //the range covers the whole set
347  d._lubMin = min();
348  d._lubMax = max();
349  fst()->dispose(home,lst()); fst(NULL); lst(NULL);
350  _size=0;
351  return true;
352  }
353  bool ret = exclude_full(home, mi, ma, d);
354  assert(isConsistent());
355  return ret;
356  }
357 
358  forceinline bool
359  LUBndSet::intersect(Space& home, int mi, int ma) {
360  assert(ma >= mi);
361  if ((mi <= min()) && (ma >= max())) { return false; }
362  if (_size == 0) return false;
363  if (ma < min() || mi > max() ) { // empty the whole set
364  fst()->dispose(home,lst()); fst(NULL); lst(NULL);
365  _size=0;
366  return true;
367  }
368  bool ret = intersect_full(home, mi, ma);
369  assert(isConsistent());
370  return ret;
371  }
372 
373  template<class I> bool
375  if (fst()==NULL) { return false; }
376  if (!i()) {
377  fst()->dispose(home,lst()); fst(NULL); lst(NULL);
378  _size=0;
379  return true;
380  }
381  BndSetRanges j(*this);
383  bool ret = overwrite(home, ij);
384  assert(isConsistent());
385  return ret;
386  }
387 
388  template<class I> bool
390  if (!i()) { return false; }
391  BndSetRanges j(*this);
393  bool ret = overwrite(home, ij);
394  assert(isConsistent());
395  return ret;
396  }
397 
398  forceinline void
400  fst()->dispose(home,lst()); fst(NULL); lst(NULL);
401  _size=0;
402  }
403 
404  /*
405  * A complement iterator spezialized for the BndSet limits
406  *
407  */
408  template<class I>
410 
411  template<class I>
413  : Iter::Ranges::Compl<Limits::min,
414  Limits::max,
415  I>(i) {}
416 
417  template<class I> void
420  Limits::max,I>::init(i);
421  }
422 
423 }}
424 
425 // STATISTICS: set-var
426 
bool in(int i) const
Test whether i is an element of this set.
Definition: integerset.hpp:228
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition: integerset.hpp:389
RangeList * lst(void) const
Return last range.
Definition: integerset.hpp:59
BndSetRanges(void)
Default constructor.
Definition: integerset.hpp:244
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
const int min
Smallest allowed integer in integer set.
Definition: set.hh:101
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:293
void lst(RangeList *r)
Set last range to r.
Definition: integerset.hpp:75
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
RangesCompl(void)
Default constructor.
Definition: integerset.hpp:409
int min(void) const
Return minimum.
Definition: range-list.hpp:142
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:134
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:116
Range iterator for computing the complement (described by template arguments)
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:103
const int max
Largest allowed integer in integer set.
Definition: set.hh:99
Computation spaces.
Definition: core.hpp:1362
int max(void) const
Return maximum.
Definition: range-list.hpp:146
int minN(unsigned int n) const
Return n -th smallest element.
Definition: integerset.hpp:124
Gecode::IntSet d(v, 7)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:114
Gecode::FloatVal c(-8, 8)
unsigned int size(void) const
Return size.
Definition: integerset.hpp:97
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition: integerset.hpp:215
bool empty(void) const
Test whether this set is empty.
Definition: integerset.hpp:102
Range iterator for computing intersection (binary)
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
void init(Space &home)
Initialize as the empty set.
Definition: integerset.hpp:275
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:374
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:54
Sets of integers.
Definition: var-imp.hpp:93
Range iterator for integer sets.
Definition: var-imp.hpp:189
Card _card("Int::Card")
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:251
unsigned int _size
The size of this set.
Definition: var-imp.hpp:99
RangeList * next(void) const
Return next element.
Definition: range-list.hpp:124
void init(I &i)
Initialize with iterator i.
Definition: integerset.hpp:418
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:101
RangeList * ranges(void) const
Return range list for iteration.
Definition: integerset.hpp:92
Integer sets.
Definition: int.hh:171
GLBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:261
LUBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:317
void init(const Gecode::RangeList *s)
Initialize with BndSet s.
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:144
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
Definition: integerset.hpp:332
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition: integerset.hpp:343
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:300
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:64
Range iterator for computing union (binary)
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition: integerset.hpp:359
int min(void) const
Return smallest element.
Definition: integerset.hpp:107
#define forceinline
Definition: config.hpp:132
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: range-list.hpp:179
Lists of ranges (intervals)
Definition: range-list.hpp:53
void fst(RangeList *r)
Set first range to r.
Definition: integerset.hpp:70
Gecode toplevel namespace
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
Definition: integerset.hpp:175
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:390
friend FloatVal min(const FloatVal &x, const FloatVal &y)
Definition: val.hpp:402
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:50
int max(void) const
Return greatest element.
Definition: integerset.hpp:115
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: range-list.hpp:150
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:283
void excludeAll(Space &home)
Exclude all elements from this set.
Definition: integerset.hpp:399
Finite set delta information for advisors.
Definition: var-imp.hpp:56