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 * 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
38namespace Gecode { namespace Set {
39
40 /*
41 * BndSet
42 *
43 */
44
45 forceinline
46 BndSet::BndSet(void) :
47 first(nullptr), last(nullptr), _size(0), _card(0) {}
48
49 forceinline RangeList*
50 BndSet::fst(void) const {
51 return first;
52 }
53
54 forceinline RangeList*
55 BndSet::lst(void) const {
56 return last;
57 }
58
59 forceinline void
60 BndSet::dispose(Space& home) {
61 if (fst()!=nullptr)
62 fst()->dispose(home,lst());
63 }
64
65 forceinline void
66 BndSet::fst(RangeList* f) {
67 first = f;
68 }
69
70 forceinline void
71 BndSet::lst(RangeList* l) {
72 last = l;
73 }
74
75 forceinline
76 BndSet::BndSet(Space& home, int mn, int mx) {
77 if (mn>mx) {
78 fst(nullptr); lst(nullptr); _size = 0;
79 } else {
80 RangeList* p =
81 new (home) RangeList(mn,mx,nullptr);
82 fst(p); lst(p);
83 _size = static_cast<unsigned int>(mx-mn+1);
84 }
85 }
86
87 forceinline RangeList*
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()==nullptr)
105 return MIN_OF_EMPTY;
106 else
107 return fst()->min();
108 }
109
110 forceinline int
111 BndSet::max(void) const {
112 if (lst()==nullptr)
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 != nullptr; 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
140 BndSet::update(Space& home, BndSet& d) {
141 if (d.fst() == fst())
142 return;
143 if (fst() != nullptr)
144 fst()->dispose(home,lst());
145 _size = d.size();
146 if (_size == 0) {
147 fst(nullptr); lst(nullptr);
148 return;
149 }
150
151 int n=0;
152 for (RangeList* c = d.fst(); c != nullptr; 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(nullptr);
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()==nullptr)
176 return false;
177 fst()->dispose(home,lst());
178 _size=0; fst(nullptr); lst(nullptr);
179 return true;
180 }
181
182 RangeList* f =
183 new (home) RangeList(ri.min(),ri.max(),nullptr);
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(),nullptr);
191 l->next(n);
192 l=n;
193 s += ri.width();
194 ++ri;
195 }
196
197 if (fst() != nullptr)
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()!=nullptr) {
213 assert(lst()!=nullptr);
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 != nullptr; 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
239 forceinline
240 BndSetRanges::BndSetRanges(void) {}
241
242 forceinline
243 BndSetRanges::BndSetRanges(const BndSet& s)
244 : Iter::Ranges::RangeList(s.ranges()) {}
245
246 forceinline void
247 BndSetRanges::init(const BndSet& s) {
248 Iter::Ranges::RangeList::init(s.ranges());
249 }
250
251 /*
252 * GLBndSet
253 *
254 */
255
256 forceinline
257 GLBndSet::GLBndSet(void) {}
258
259 forceinline
260 GLBndSet::GLBndSet(Space&) {}
261
262 forceinline
263 GLBndSet::GLBndSet(Space& home, int mi, int ma)
264 : BndSet(home,mi,ma) {}
265
266 forceinline
267 GLBndSet::GLBndSet(Space& home, const IntSet& s)
268 : BndSet(home,s) {}
269
270 forceinline void
271 GLBndSet::init(Space& home) {
272 dispose(home);
273 fst(nullptr);
274 lst(nullptr);
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()==nullptr) {
282 RangeList* p = new (home) RangeList(mi,ma,nullptr);
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
296 GLBndSet::includeI(Space& home, I& i) {
297 if (!i())
298 return false;
299 BndSetRanges j(*this);
300 Iter::Ranges::Union<BndSetRanges,I> ij(j,i);
301 bool me = overwrite(home, ij);
302 assert(isConsistent());
303 return me;
304 }
305
306
307 /*
308 * LUBndSet
309 *
310 */
311
312 forceinline
313 LUBndSet::LUBndSet(void) {}
314
315 forceinline
316 LUBndSet::LUBndSet(Space& home)
317 : BndSet(home,Limits::min,Limits::max) {}
318
319 forceinline
320 LUBndSet::LUBndSet(Space& home, int mi, int ma)
321 : BndSet(home,mi,ma) {}
322
323 forceinline
324 LUBndSet::LUBndSet(Space& home, const IntSet& s)
325 : BndSet(home,s) {}
326
327 forceinline void
328 LUBndSet::init(Space& home) {
329 RangeList *p =
330 new (home) RangeList(Limits::min,
331 Limits::max,
332 nullptr);
333 fst(p);
334 lst(p);
335 _size = Limits::card;
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(nullptr); lst(nullptr);
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(nullptr); lst(nullptr);
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
370 LUBndSet::intersectI(Space& home, I& i) {
371 if (fst()==nullptr) { return false; }
372 if (!i()) {
373 fst()->dispose(home,lst()); fst(nullptr); lst(nullptr);
374 _size=0;
375 return true;
376 }
377 BndSetRanges j(*this);
378 Iter::Ranges::Inter<BndSetRanges,I> ij(j,i);
379 bool ret = overwrite(home, ij);
380 assert(isConsistent());
381 return ret;
382 }
383
384 template<class I> bool
385 LUBndSet::excludeI(Space& home, I& i) {
386 if (!i()) { return false; }
387 BndSetRanges j(*this);
388 Iter::Ranges::Diff<BndSetRanges,I> ij(j,i);
389 bool ret = overwrite(home, ij);
390 assert(isConsistent());
391 return ret;
392 }
393
394 forceinline void
395 LUBndSet::excludeAll(Space& home) {
396 fst()->dispose(home,lst()); fst(nullptr); lst(nullptr);
397 _size=0;
398 }
399
400 /*
401 * A complement iterator spezialized for the BndSet limits
402 *
403 */
404 template<class I>
405 RangesCompl<I>::RangesCompl(void) {}
406
407 template<class I>
408 RangesCompl<I>::RangesCompl(I& i)
409 : Iter::Ranges::Compl<Limits::min,
410 Limits::max,
411 I>(i) {}
412
413 template<class I> void
414 RangesCompl<I>::init(I& i) {
415 Iter::Ranges::Compl<Limits::min,
416 Limits::max,I>::init(i);
417 }
418
419}}
420
421// STATISTICS: set-var
422