this repo has no description
dekker.one
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(nullptr); lst(nullptr); _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(nullptr);
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() != nullptr);
63
64 RangeList* p = nullptr;
65 RangeList* c = fst();
66
67 while (c != nullptr) {
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==nullptr)
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() != nullptr && 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!=nullptr); //q would have stayed c if c was last.
119 c->next(q->next());
120 if (q->next()==nullptr) {
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, nullptr);
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 = nullptr;
145 RangeList* c = fst();
146
147 assert(c != nullptr); // Never intersect with an empty set
148
149 // Skip ranges that are before mi
150 while (c != nullptr && c->max() < mi) {
151 _size -= c->width();
152 RangeList *nc = c->next();
153 p=c; c=nc;
154 }
155 if (c == nullptr) {
156 // Delete entire domain
157 fst()->dispose(home, lst());
158 fst(nullptr); lst(nullptr);
159 return true;
160 }
161
162 bool changed = false;
163 if (c != fst()) {
164 fst()->dispose(home, p);
165 fst(c);
166 p = nullptr;
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 != nullptr && c->max() <= ma) {
177 RangeList *nc = c->next();
178 p=c; c=nc;
179 }
180
181 if (c == nullptr)
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(nullptr);
191 p=c; c=nc;
192 } else if (p != nullptr) {
193 p->next(nullptr);
194 }
195 if (c != nullptr) {
196 for (RangeList* cc = c ; cc != nullptr; cc = cc->next())
197 _size -= cc->width();
198 c->dispose(home, lst());
199 }
200 lst(newlst);
201 if (newlst==nullptr)
202 fst(nullptr);
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 = nullptr;
214 RangeList* c = fst();
215 d._lubMin = Limits::max+1;
216 while (c != nullptr) {
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()!=nullptr) && (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 != nullptr && 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()==nullptr) {
292 if (lst()!=nullptr || size()!=0) {
293 std::cerr<<"Strange empty set.\n";
294 return false;
295 } else return true;
296 }
297
298 if (fst()!=nullptr && lst()==nullptr) {
299 std::cerr<<"First is not null, last is.\n";
300 return false;
301 }
302
303 RangeList *p=nullptr;
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()==nullptr && 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