Generated on Tue Jan 19 2021 06:15:49 for Gecode by doxygen 1.8.13
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 
38 namespace 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 
267  GLBndSet::GLBndSet(Space& home, const IntSet& s)
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 
324  LUBndSet::LUBndSet(Space& home, const IntSet& s)
325  : BndSet(home,s) {}
326 
327  forceinline void
329  RangeList *p =
330  new (home) RangeList(Limits::min,
331  Limits::max,
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 
bool excludeI(Space &home, I &i)
Exclude all elements in the set represented by i from this set.
Definition: integerset.hpp:385
BndSetRanges(void)
Default constructor.
Definition: integerset.hpp:240
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
const int min
Smallest allowed integer in integer set.
Definition: set.hh:99
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
void lst(RangeList *r)
Set last range to r.
Definition: integerset.hpp:71
RangeList * lst(void) const
Return last range.
Definition: integerset.hpp:55
RangeList * next(void) const
Return next element.
Definition: range-list.hpp:141
int max(void) const
Return greatest element.
Definition: integerset.hpp:111
int min(void) const
Return minimum.
Definition: range-list.hpp:164
RangesCompl(void)
Default constructor.
Definition: integerset.hpp:405
int minN(unsigned int n) const
Return n -th smallest element.
Definition: integerset.hpp:120
static const int MIN_OF_EMPTY
Returned by empty sets when asked for their minimum element.
Definition: var-imp.hpp:112
bool in(int i) const
Test whether i is an element of this set.
Definition: integerset.hpp:224
Range iterator for computing the complement (described by template arguments)
#define forceinline
Definition: config.hpp:185
RangeList * ranges(void) const
Return range list for iteration.
Definition: integerset.hpp:88
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
Computation spaces.
Definition: core.hpp:1701
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:50
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:2794
static const int MAX_OF_EMPTY
Returned by empty sets when asked for their maximum element.
Definition: var-imp.hpp:110
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
unsigned int size(void) const
Return size.
Definition: integerset.hpp:93
void become(Space &home, const BndSet &s)
Make this set equal to s.
Definition: integerset.hpp:211
Gecode::IntArgs i({1, 2, 3, 4})
Range iterator for computing intersection (binary)
void init(Space &home)
Initialize as the empty set.
Definition: integerset.hpp:271
int max(void) const
Return maximum.
Definition: range-list.hpp:168
bool intersectI(Space &home, I &i)
Exclude all elements not in the set represented by i from this set.
Definition: integerset.hpp:370
A complement iterator spezialized for the BndSet limits.
Definition: var-imp.hpp:292
Sets of integers.
Definition: var-imp.hpp:89
Range iterator for integer sets.
Definition: var-imp.hpp:185
Card _card("Int::Card")
void init(const BndSet &s)
Initialize with BndSet s.
Definition: integerset.hpp:247
unsigned int _size
The size of this set.
Definition: var-imp.hpp:95
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:289
unsigned int _card
The cardinality this set represents.
Definition: var-imp.hpp:97
Integer sets.
Definition: int.hh:174
GLBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:257
LUBndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:313
void init(const Gecode::RangeList *s)
Initialize with range list s.
void update(Space &home, BndSet &x)
Update this set to be a clone of set x.
Definition: integerset.hpp:140
void init(Space &home)
Initialize as the full set including everything between Limits::min and Limits::max.
Definition: integerset.hpp:328
bool exclude(Space &home, int i, int j, SetDelta &d)
Exclude the set from this set.
Definition: integerset.hpp:339
bool includeI(Space &home, I &i)
Include the set represented by i in this set.
Definition: integerset.hpp:296
void dispose(Space &home)
Free memory used by this set.
Definition: integerset.hpp:60
Range iterator for computing union (binary)
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
bool intersect(Space &home, int i, int j)
Intersect this set with the set .
Definition: integerset.hpp:355
bool empty(void) const
Test whether this set is empty.
Definition: integerset.hpp:98
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: range-list.hpp:201
Lists of ranges (intervals)
Definition: range-list.hpp:49
void fst(RangeList *r)
Set first range to r.
Definition: integerset.hpp:66
Gecode toplevel namespace
bool overwrite(Space &home, I &i)
Overwrite the ranges with those represented by i.
Definition: integerset.hpp:171
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
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
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:46
unsigned int card(void) const
Return cardinality.
Definition: integerset.hpp:130
int min(void) const
Return smallest element.
Definition: integerset.hpp:103
bool include(Space &home, int i, int j, SetDelta &d)
Include the set in this set.
Definition: integerset.hpp:279
void excludeAll(Space &home)
Exclude all elements from this set.
Definition: integerset.hpp:395
Finite set delta information for advisors.
Definition: var-imp.hpp:52