Generated on Sat Feb 7 2015 02:01:30 for Gecode by doxygen 1.8.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  * Last modified:
10  * $Date: 2009-01-20 23:44:27 +0100 (Tue, 20 Jan 2009) $ by $Author: schulte $
11  * $Revision: 8082 $
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 
39 
40 #include <gecode/set.hh>
41 
42 namespace Gecode { namespace Set {
43 
44  BndSet::BndSet(Space& home, const IntSet& is) {
45  if (is.ranges()==0) {
46  fst(NULL); lst(NULL); _size = 0;
47  } else {
48  int n = is.ranges();
49  RangeList* r = home.alloc<RangeList>(n);
50  fst(r); lst(r+n-1);
51  unsigned int s = 0;
52  for (int i = n; i--; ) {
53  s += is.width(i);
54  r[i].min(is.min(i)); r[i].max(is.max(i));
55  r[i].next(&r[i+1]);
56  }
57  r[n-1].next(NULL);
58  _size = s;
59  }
60  assert(isConsistent());
61  }
62 
63  bool
64  GLBndSet::include_full(Space& home, int mi, int ma, SetDelta& d) {
65  assert(ma >= mi);
66  assert(fst() != NULL);
67 
68  RangeList* p = NULL;
69  RangeList* c = fst();
70 
71  while (c != NULL) {
72  if (c->max() >= mi-1){
73  if (c->min() > ma+1) { //in a hole before c
74  _size+=(ma-mi+1);
75  d._glbMin = mi;
76  d._glbMax = ma;
77  RangeList* q = new (home) RangeList(mi,ma,c);
78  if (p==NULL)
79  //the new range is the first
80  fst(q);
81  else
82  p->next(q);
83  return true;
84  }
85  //if the range starts before c, update c->min and size
86  bool result = false;
87  if (c->min()>mi) {
88  _size+=(c->min()-mi);
89  c->min(mi);
90  d._glbMin = mi;
91  result = true;
92  } else {
93  d._glbMin = c->max()+1;
94  }
95  assert(c->min()<=mi);
96  assert(c->max()+1>=mi);
97  if (c->max() >= ma) {
98  d._glbMax = c->min()-1;
99  return result;
100  }
101  RangeList* q = c;
102  //sum up the size of holes eaten
103  int prevMax = c->max();
104  int growth = 0;
105  // invariant: q->min()<=ma+1
106  while (q->next() != NULL && q->next()->min() <= ma+1) {
107  q = q->next();
108  growth += q->min()-prevMax-1;
109  prevMax = q->max();
110  }
111  assert(growth>=0);
112  _size+=growth;
113  if (q->max() < ma) {
114  _size += ma-q->max();
115  d._glbMax = ma;
116  } else {
117  d._glbMax = q->min()-1;
118  }
119  c->max(std::max(ma,q->max()));
120  if (c!=q) {
121  RangeList* oldCNext = c->next();
122  assert(oldCNext!=NULL); //q would have stayed c if c was last.
123  c->next(q->next());
124  if (q->next()==NULL){
125  assert(q==lst());
126  lst(c);
127  }
128  oldCNext->dispose(home,q);
129  }
130  return true;
131  }
132  RangeList* nc = c->next();
133  p=c; c=nc;
134  }
135  //the new range is disjoint from the old domain and we add it as last:
136  assert(mi>max()+1);
137  RangeList* q = new (home) RangeList(mi, ma, NULL);
138  lst()->next(q);
139  lst(q);
140  _size+= q->width();
141  d._glbMin = mi;
142  d._glbMax = ma;
143  return true;
144  }
145 
146  bool
147  LUBndSet::intersect_full(Space& home, int mi, int ma) {
148  RangeList* p = NULL;
149  RangeList* c = fst();
150 
151  assert(c != NULL); // Never intersect with an empty set
152 
153  // Skip ranges that are before mi
154  while (c != NULL && c->max() < mi) {
155  _size -= c->width();
156  RangeList *nc = c->next();
157  p=c; c=nc;
158  }
159  if (c == NULL) {
160  // Delete entire domain
161  fst()->dispose(home, lst());
162  fst(NULL); lst(NULL);
163  return true;
164  }
165 
166  bool changed = false;
167  if (c != fst()) {
168  fst()->dispose(home, p);
169  fst(c);
170  p = NULL;
171  changed = true;
172  }
173  // We have found the first range that intersects with [mi,ma]
174  if (mi > c->min()) {
175  _size -= mi-c->min();
176  c->min(mi);
177  changed = true;
178  }
179 
180  while (c != NULL && c->max() <= ma) {
181  RangeList *nc = c->next();
182  p=c; c=nc;
183  }
184 
185  if (c == NULL)
186  return changed;
187 
188  RangeList* newlst = p;
189  if (ma >= c->min()) {
190  _size -= c->max() - ma;
191  c->max(ma);
192  newlst = c;
193  RangeList* nc = c->next();
194  c->next(NULL);
195  p=c; c=nc;
196  } else if (p != NULL) {
197  p->next(NULL);
198  }
199  if (c != NULL) {
200  for (RangeList* cc = c ; cc != NULL; cc = cc->next())
201  _size -= cc->width();
202  c->dispose(home, lst());
203  }
204  lst(newlst);
205  if (newlst==NULL)
206  fst(NULL);
207  return true;
208  }
209 
210  bool
211  LUBndSet::exclude_full(Space& home, int mi, int ma, SetDelta& d) {
212  assert(ma >= mi);
213  assert(mi <= max() && ma >= min() &&
214  (mi > min() || ma < max()));
215  bool result=false;
216 
217  RangeList* p = NULL;
218  RangeList* c = fst();
219  d._lubMin = Limits::max+1;
220  while (c != NULL) {
221  if (c->max() >= mi){
222  if (c->min() > ma) { return result; } //in a hole
223 
224  if (c->min()<mi && c->max() > ma) { //Range split:
225  RangeList* q =
226  new (home) RangeList(ma+1,c->max(),c->next());
227  c->max(mi-1);
228  if (c == lst()) {
229  lst(q);
230  }
231  c->next(q);
232  _size -= (ma-mi+1);
233  d._lubMin = mi;
234  d._lubMax = ma;
235  return true;
236  }
237 
238  if (c->max() > ma) { //start of range clipped, end remains
239  d._lubMin = std::min(d._lubMin, c->min());
240  d._lubMax = ma;
241  _size-=(ma-c->min()+1);
242  c->min(ma+1);
243  return true;
244  }
245 
246  if (c->min() < mi) { //end of range clipped, start remains
247  _size-=(c->max()-mi+1);
248  d._lubMin = mi;
249  d._lubMax = c->max();
250  c->max(mi-1);
251  result=true;
252  } else { //range *c destroyed
253  d._lubMin = c->min();
254  _size-=c->width();
255  RangeList *cend = c;
256  while ((cend->next()!=NULL) && (cend->next()->max()<=ma)){
257  cend = cend->next();
258  _size-=cend->width();
259  }
260  d._lubMax = cend->max();
261  if (fst()==c) {
262  fst(cend->next());
263  } else {
264  p->next(cend->next());
265  }
266  if (lst()==cend) {
267  lst(p);
268  }
269  RangeList* nc=cend->next(); //performs loop step!
270  c->dispose(home,cend);
271  p=cend;
272  c=nc;
273  if (c != NULL && c->min() <= ma ) {
274  //start of range clipped, end remains
275  _size-=(ma-c->min()+1);
276  c->min(ma+1);
277  d._lubMax = ma;
278  }
279  return true;
280  }
281  }
282  RangeList *nc = c->next();
283  p=c; c=nc;
284  }
285  return result;
286  }
287 
288 #ifndef NDEBUG
289  using namespace Gecode::Int;
290 #endif
291 
292  bool
293  BndSet::isConsistent(void) const {
294 #ifndef NDEBUG
295  if (fst()==NULL) {
296  if (lst()!=NULL || size()!=0) {
297  std::cerr<<"Strange empty set.\n";
298  return false;
299  } else return true;
300  }
301 
302  if (fst()!=NULL && lst()==NULL) {
303  std::cerr<<"First is not null, last is.\n";
304  return false;
305  }
306 
307  RangeList *p=NULL;
308  RangeList *c=fst();
309 
310  int min = c->min();
311  int max = c->max();
312 
313  if (max<min) {
314  std::cerr << "Single range list twisted: ("<<min<<","<<max<<")" ;
315  return false;
316  }
317 
318  RangeList *nc=c->next();
319  p=c; c=nc;
320  while (c) {
321  if (max<min) {
322  std::cerr << "1";
323  return false;
324  }
325  if ((max+1)>=c->min()) {
326  std::cerr << "2";
327  return false;
328  }
329  if (c->next()==NULL && c!=lst()) {
330  std::cerr << "3";
331  return false;
332  }
333 
334  min = c->min();
335  max = c->max();
336 
337  nc=c->next();
338  p=c; c=nc;
339  }
340 #endif
341  return true;
342  }
343 
344 
345 }}
346 
347 // STATISTICS: set-var
348 
RangeList * lst(void) const
Return last range.
Definition: integerset.hpp:59
bool isConsistent(void) const
Check whether internal invariants hold.
Definition: integerset.cpp:293
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
int min(void) const
Return minimum.
Definition: range-list.hpp:142
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
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
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:134
RangeList * fst(void) const
Return first range.
Definition: integerset.hpp:54
unsigned int size(I &i)
Size of all ranges of range iterator i.
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:127
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
Integer sets.
Definition: int.hh:171
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
int min(void) const
Return smallest element.
Definition: integerset.hpp:107
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
Gecode toplevel namespace
Finite domain integers.
Definition: abs.hpp:42
BndSet(void)
Default constructor. Creates an empty set.
Definition: integerset.hpp:50
int max(void) const
Return greatest element.
Definition: integerset.hpp:115
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:121
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:115
Finite set delta information for advisors.
Definition: var-imp.hpp:56