Generated on Thu Jan 16 2025 00:00:00 for Gecode by doxygen 1.14.0
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
38namespace 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
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
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.
int max(int i) const
Return maximum of range at position i.
int ranges(void) const
Return number of ranges of the specification.
unsigned int width(int i) const
Return width of range at position i.
Lists of ranges (intervals)
void dispose(Space &home, RangeList *l)
Free memory for all elements between this and l (inclusive)
RangeList * next(void) const
Return next element.
int min(void) const
Return smallest element.
bool isConsistent(void) const
Check whether internal invariants hold.
RangeList * lst(void) const
Return last range.
unsigned int size(void) const
Return size.
void lst(RangeList *r)
Set last range to r.
BndSet(void)
Default constructor. Creates an empty set.
int max(void) const
Return greatest element.
unsigned int _size
The size of this set.
Definition var-imp.hpp:95
RangeList * fst(void) const
Return first range.
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
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
Gecode::FloatVal c(-8, 8)
Gecode::IntSet d(v, 7)