Generated on Thu Jan 20 2022 00:00:00 for Gecode by doxygen 1.9.1
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  * This file is part of Gecode, the generic constraint
10  * development environment:
11  * http://www.gecode.org
12  *
13  * Permission is hereby granted, free of charge, to any person obtaining
14  * a copy of this software and associated documentation files (the
15  * "Software"), to deal in the Software without restriction, including
16  * without limitation the rights to use, copy, modify, merge, publish,
17  * distribute, sublicense, and/or sell copies of the Software, and to
18  * permit persons to whom the Software is furnished to do so, subject to
19  * the following conditions:
20  *
21  * The above copyright notice and this permission notice shall be
22  * included in all copies or substantial portions of the Software.
23  *
24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 
35 
36 #include <gecode/set.hh>
37 
38 namespace Gecode { namespace Set {
39 
40  BndSet::BndSet(Space& home, const IntSet& is) {
41  if (is.ranges()==0) {
42  fst(NULL); lst(NULL); _size = 0;
43  } else {
44  int n = is.ranges();
45  RangeList* r = home.alloc<RangeList>(n);
46  fst(r); lst(r+n-1);
47  unsigned int s = 0;
48  for (int i = n; i--; ) {
49  s += is.width(i);
50  r[i].min(is.min(i)); r[i].max(is.max(i));
51  r[i].next(&r[i+1]);
52  }
53  r[n-1].next(NULL);
54  _size = s;
55  }
56  assert(isConsistent());
57  }
58 
59  bool
60  GLBndSet::include_full(Space& home, int mi, int ma, SetDelta& d) {
61  assert(ma >= mi);
62  assert(fst() != NULL);
63 
64  RangeList* p = NULL;
65  RangeList* c = fst();
66 
67  while (c != NULL) {
68  if (c->max() >= mi-1) {
69  if (c->min() > ma+1) { //in a hole before c
70  _size+=(ma-mi+1);
71  d._glbMin = mi;
72  d._glbMax = ma;
73  RangeList* q = new (home) RangeList(mi,ma,c);
74  if (p==NULL)
75  //the new range is the first
76  fst(q);
77  else
78  p->next(q);
79  return true;
80  }
81  //if the range starts before c, update c->min and size
82  bool result = false;
83  if (c->min()>mi) {
84  _size+=(c->min()-mi);
85  c->min(mi);
86  d._glbMin = mi;
87  result = true;
88  } else {
89  d._glbMin = c->max()+1;
90  }
91  assert(c->min()<=mi);
92  assert(c->max()+1>=mi);
93  if (c->max() >= ma) {
94  d._glbMax = c->min()-1;
95  return result;
96  }
97  RangeList* q = c;
98  //sum up the size of holes eaten
99  int prevMax = c->max();
100  int growth = 0;
101  // invariant: q->min()<=ma+1
102  while (q->next() != NULL && q->next()->min() <= ma+1) {
103  q = q->next();
104  growth += q->min()-prevMax-1;
105  prevMax = q->max();
106  }
107  assert(growth>=0);
108  _size+=growth;
109  if (q->max() < ma) {
110  _size += ma-q->max();
111  d._glbMax = ma;
112  } else {
113  d._glbMax = q->min()-1;
114  }
115  c->max(std::max(ma,q->max()));
116  if (c!=q) {
117  RangeList* oldCNext = c->next();
118  assert(oldCNext!=NULL); //q would have stayed c if c was last.
119  c->next(q->next());
120  if (q->next()==NULL) {
121  assert(q==lst());
122  lst(c);
123  }
124  oldCNext->dispose(home,q);
125  }
126  return true;
127  }
128  RangeList* nc = c->next();
129  p=c; c=nc;
130  }
131  //the new range is disjoint from the old domain and we add it as last:
132  assert(mi>max()+1);
133  RangeList* q = new (home) RangeList(mi, ma, NULL);
134  lst()->next(q);
135  lst(q);
136  _size+= q->width();
137  d._glbMin = mi;
138  d._glbMax = ma;
139  return true;
140  }
141 
142  bool
143  LUBndSet::intersect_full(Space& home, int mi, int ma) {
144  RangeList* p = NULL;
145  RangeList* c = fst();
146 
147  assert(c != NULL); // Never intersect with an empty set
148 
149  // Skip ranges that are before mi
150  while (c != NULL && c->max() < mi) {
151  _size -= c->width();
152  RangeList *nc = c->next();
153  p=c; c=nc;
154  }
155  if (c == NULL) {
156  // Delete entire domain
157  fst()->dispose(home, lst());
158  fst(NULL); lst(NULL);
159  return true;
160  }
161 
162  bool changed = false;
163  if (c != fst()) {
164  fst()->dispose(home, p);
165  fst(c);
166  p = NULL;
167  changed = true;
168  }
169  // We have found the first range that intersects with [mi,ma]
170  if (mi > c->min()) {
171  _size -= mi-c->min();
172  c->min(mi);
173  changed = true;
174  }
175 
176  while (c != NULL && c->max() <= ma) {
177  RangeList *nc = c->next();
178  p=c; c=nc;
179  }
180 
181  if (c == NULL)
182  return changed;
183 
184  RangeList* newlst = p;
185  if (ma >= c->min()) {
186  _size -= c->max() - ma;
187  c->max(ma);
188  newlst = c;
189  RangeList* nc = c->next();
190  c->next(NULL);
191  p=c; c=nc;
192  } else if (p != NULL) {
193  p->next(NULL);
194  }
195  if (c != NULL) {
196  for (RangeList* cc = c ; cc != NULL; cc = cc->next())
197  _size -= cc->width();
198  c->dispose(home, lst());
199  }
200  lst(newlst);
201  if (newlst==NULL)
202  fst(NULL);
203  return true;
204  }
205 
206  bool
207  LUBndSet::exclude_full(Space& home, int mi, int ma, SetDelta& d) {
208  assert(ma >= mi);
209  assert(mi <= max() && ma >= min() &&
210  (mi > min() || ma < max()));
211  bool result=false;
212 
213  RangeList* p = NULL;
214  RangeList* c = fst();
215  d._lubMin = Limits::max+1;
216  while (c != NULL) {
217  if (c->max() >= mi) {
218  if (c->min() > ma) { return result; } //in a hole
219 
220  if (c->min()<mi && c->max() > ma) { //Range split:
221  RangeList* q =
222  new (home) RangeList(ma+1,c->max(),c->next());
223  c->max(mi-1);
224  if (c == lst()) {
225  lst(q);
226  }
227  c->next(q);
228  _size -= (ma-mi+1);
229  d._lubMin = mi;
230  d._lubMax = ma;
231  return true;
232  }
233 
234  if (c->max() > ma) { //start of range clipped, end remains
235  d._lubMin = std::min(d._lubMin, c->min());
236  d._lubMax = ma;
237  _size-=(ma-c->min()+1);
238  c->min(ma+1);
239  return true;
240  }
241 
242  if (c->min() < mi) { //end of range clipped, start remains
243  _size-=(c->max()-mi+1);
244  d._lubMin = mi;
245  d._lubMax = c->max();
246  c->max(mi-1);
247  result=true;
248  } else { //range *c destroyed
249  d._lubMin = c->min();
250  _size-=c->width();
251  RangeList *cend = c;
252  while ((cend->next()!=NULL) && (cend->next()->max()<=ma)) {
253  cend = cend->next();
254  _size-=cend->width();
255  }
256  d._lubMax = cend->max();
257  if (fst()==c) {
258  fst(cend->next());
259  } else {
260  p->next(cend->next());
261  }
262  if (lst()==cend) {
263  lst(p);
264  }
265  RangeList* nc=cend->next(); //performs loop step!
266  c->dispose(home,cend);
267  p=cend;
268  c=nc;
269  if (c != NULL && c->min() <= ma ) {
270  //start of range clipped, end remains
271  _size-=(ma-c->min()+1);
272  c->min(ma+1);
273  d._lubMax = ma;
274  }
275  return true;
276  }
277  }
278  RangeList *nc = c->next();
279  p=c; c=nc;
280  }
281  return result;
282  }
283 
284 #ifndef NDEBUG
285  using namespace Gecode::Int;
286 #endif
287 
288  bool
289  BndSet::isConsistent(void) const {
290 #ifndef NDEBUG
291  if (fst()==NULL) {
292  if (lst()!=NULL || size()!=0) {
293  std::cerr<<"Strange empty set.\n";
294  return false;
295  } else return true;
296  }
297 
298  if (fst()!=NULL && lst()==NULL) {
299  std::cerr<<"First is not null, last is.\n";
300  return false;
301  }
302 
303  RangeList *p=NULL;
304  RangeList *c=fst();
305 
306  int min = c->min();
307  int max = c->max();
308 
309  if (max<min) {
310  std::cerr << "Single range list twisted: ("<<min<<","<<max<<")" ;
311  return false;
312  }
313 
314  RangeList *nc=c->next();
315  p=c; c=nc;
316  while (c) {
317  if (max<min) {
318  std::cerr << "1";
319  return false;
320  }
321  if ((max+1)>=c->min()) {
322  std::cerr << "2";
323  return false;
324  }
325  if (c->next()==NULL && c!=lst()) {
326  std::cerr << "3";
327  return false;
328  }
329 
330  min = c->min();
331  max = c->max();
332 
333  nc=c->next();
334  p=c; c=nc;
335  }
336 #endif
337  return true;
338  }
339 
340 
341 }}
342 
343 // STATISTICS: set-var
344 
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
NNF * r
Right subtree.
Definition: bool-expr.cpp:242
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
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:152
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:158
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:171
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:164
Lists of ranges (intervals)
Definition: range-list.hpp:49
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: range-list.hpp:201
RangeList * next(void) const
Return next element.
Definition: range-list.hpp:141
int min(void) const
Return smallest element.
Definition: integerset.hpp:103
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:289
RangeList * lst(void) const
Return last range.
Definition: integerset.hpp:55
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:46
int max(void) const
Return greatest element.
Definition: integerset.hpp:111
unsigned int _size
The size of this set.
Definition: var-imp.hpp:95
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:50
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 FloatNum max
Largest allowed float value.
Definition: float.hh:844
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Finite domain integers.
Definition: abs.hpp:38
unsigned int size(I &i)
Size of all ranges of range iterator i.
const int max
Largest allowed integer in integer set.
Definition: set.hh:97
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
Gecode::IntSet d(v, 7)