this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Contributing authors:
7 * Guido Tack <tack@gecode.org>
8 *
9 * Copyright:
10 * Christian Schulte, 2003
11 * Guido Tack, 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 Int {
39
40 /*
41 * Range lists
42 *
43 */
44
45#define GECODE_INT_RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
46#define GECODE_INT_PD2RL(p) reinterpret_cast<RangeList*>(p)
47
48 forceinline
49 IntVarImp::RangeList::RangeList(void) {}
50
51 forceinline
52 IntVarImp::RangeList::RangeList(int min, int max)
53 : _min(min), _max(max) {}
54
55 forceinline
56 IntVarImp::RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
57 : _min(min), _max(max) {
58 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
59 }
60
61 forceinline IntVarImp::RangeList*
62 IntVarImp::RangeList::next(const RangeList* p) const {
63 return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(p));
64 }
65 forceinline IntVarImp::RangeList*
66 IntVarImp::RangeList::prev(const RangeList* n) const {
67 return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(n));
68 }
69 forceinline void
70 IntVarImp::RangeList::prevnext(RangeList* p, RangeList* n) {
71 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
72 }
73 forceinline void
74 IntVarImp::RangeList::next(RangeList* o, RangeList* n) {
75 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
76 (GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
77 }
78 forceinline void
79 IntVarImp::RangeList::prev(RangeList* o, RangeList* n) {
80 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
81 (GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
82 }
83 forceinline void
84 IntVarImp::RangeList::fix(RangeList* n) {
85 _next = n;
86 }
87
88 forceinline void
89 IntVarImp::RangeList::min(int n) {
90 _min = n;
91 }
92 forceinline void
93 IntVarImp::RangeList::max(int n) {
94 _max = n;
95 }
96
97 forceinline int
98 IntVarImp::RangeList::min(void) const {
99 return _min;
100 }
101 forceinline int
102 IntVarImp::RangeList::max(void) const {
103 return _max;
104 }
105 forceinline unsigned int
106 IntVarImp::RangeList::width(void) const {
107 return static_cast<unsigned int>(_max - _min) + 1;
108 }
109
110
111 forceinline void
112 IntVarImp::RangeList::operator delete(void*) {}
113
114 forceinline void
115 IntVarImp::RangeList::operator delete(void*, Space&) {
116 GECODE_NEVER;
117 }
118 forceinline void
119 IntVarImp::RangeList::operator delete(void*, void*) {
120 GECODE_NEVER;
121 }
122
123 forceinline void*
124 IntVarImp::RangeList::operator new(size_t, Space& home) {
125 return home.fl_alloc<sizeof(RangeList)>();
126 }
127
128 forceinline void*
129 IntVarImp::RangeList::operator new(size_t, void* p) {
130 return p;
131 }
132
133 forceinline void
134 IntVarImp::RangeList::dispose(Space& home, RangeList* p, RangeList* l) {
135 RangeList* c = this;
136 while (c != l) {
137 RangeList* n = c->next(p);
138 c->fix(n);
139 p=c; c=n;
140 }
141 home.fl_dispose<sizeof(RangeList)>(this,l);
142 }
143
144 forceinline void
145 IntVarImp::RangeList::dispose(Space& home, RangeList* l) {
146 home.fl_dispose<sizeof(RangeList)>(this,l);
147 }
148
149 forceinline void
150 IntVarImp::RangeList::dispose(Space& home) {
151 home.fl_dispose<sizeof(RangeList)>(this,this);
152 }
153
154#undef GECODE_INT_RL2PD
155#undef GECODE_INT_PD2RL
156
157 /*
158 * Mainitaining range lists for variable domain
159 *
160 */
161
162 forceinline IntVarImp::RangeList*
163 IntVarImp::fst(void) const {
164 return dom.next(nullptr);
165 }
166
167 forceinline void
168 IntVarImp::fst(IntVarImp::RangeList* f) {
169 dom.prevnext(nullptr,f);
170 }
171
172 forceinline IntVarImp::RangeList*
173 IntVarImp::lst(void) const {
174 return _lst;
175 }
176
177 forceinline void
178 IntVarImp::lst(IntVarImp::RangeList* l) {
179 _lst = l;
180 }
181
182 /*
183 * Creation of new variable implementations
184 *
185 */
186
187 forceinline
188 IntVarImp::IntVarImp(Space& home, int min, int max)
189 : IntVarImpBase(home), dom(min,max,nullptr,nullptr), holes(0) {}
190
191 forceinline
192 IntVarImp::IntVarImp(Space& home, const IntSet& d)
193 : IntVarImpBase(home), dom(d.min(),d.max()) {
194 if (d.ranges() > 1) {
195 int n = d.ranges();
196 assert(n >= 2);
197 RangeList* r = home.alloc<RangeList>(n);
198 fst(r); lst(r+n-1);
199 unsigned int h = static_cast<unsigned int>(d.max()-d.min())+1;
200 h -= d.width(0);
201 r[0].min(d.min(0)); r[0].max(d.max(0));
202 r[0].prevnext(nullptr,&r[1]);
203 for (int i = 1; i < n-1; i++) {
204 h -= d.width(i);
205 r[i].min(d.min(i)); r[i].max(d.max(i));
206 r[i].prevnext(&r[i-1],&r[i+1]);
207 }
208 h -= d.width(n-1);
209 r[n-1].min(d.min(n-1)); r[n-1].max(d.max(n-1));
210 r[n-1].prevnext(&r[n-2],nullptr);
211 holes = h;
212 } else {
213 fst(nullptr); holes = 0;
214 }
215 }
216
217
218 /*
219 * Operations on integer variable implementations
220 *
221 */
222
223 forceinline int
224 IntVarImp::min(void) const {
225 return dom.min();
226 }
227 forceinline int
228 IntVarImp::max(void) const {
229 return dom.max();
230 }
231 forceinline int
232 IntVarImp::val(void) const {
233 assert(dom.min() == dom.max());
234 return dom.min();
235 }
236
237 forceinline bool
238 IntVarImp::range(void) const {
239 return fst() == nullptr;
240 }
241 forceinline bool
242 IntVarImp::assigned(void) const {
243 return dom.min() == dom.max();
244 }
245
246
247 forceinline unsigned int
248 IntVarImp::width(void) const {
249 return dom.width();
250 }
251
252 forceinline unsigned int
253 IntVarImp::size(void) const {
254 return dom.width() - holes;
255 }
256
257 forceinline unsigned int
258 IntVarImp::regret_min(void) const {
259 if (fst() == nullptr) {
260 return (dom.min() == dom.max()) ? 0U : 1U;
261 } else if (dom.min() == fst()->max()) {
262 return static_cast<unsigned int>(fst()->next(nullptr)->min()-dom.min());
263 } else {
264 return 1U;
265 }
266 }
267 forceinline unsigned int
268 IntVarImp::regret_max(void) const {
269 if (fst() == nullptr) {
270 return (dom.min() == dom.max()) ? 0U : 1U;
271 } else if (dom.max() == lst()->min()) {
272 return static_cast<unsigned int>(dom.max()-lst()->prev(nullptr)->max());
273 } else {
274 return 1U;
275 }
276 }
277
278
279
280 /*
281 * Tests
282 *
283 */
284
285 forceinline bool
286 IntVarImp::in(int n) const {
287 if ((n < dom.min()) || (n > dom.max()))
288 return false;
289 return (fst() == nullptr) || in_full(n);
290 }
291 forceinline bool
292 IntVarImp::in(long long int n) const {
293 if ((n < dom.min()) || (n > dom.max()))
294 return false;
295 return (fst() == nullptr) || in_full(static_cast<int>(n));
296 }
297
298
299 /*
300 * Accessing rangelists for iteration
301 *
302 */
303
304 forceinline const IntVarImp::RangeList*
305 IntVarImp::ranges_fwd(void) const {
306 return (fst() == nullptr) ? &dom : fst();
307 }
308
309 forceinline const IntVarImp::RangeList*
310 IntVarImp::ranges_bwd(void) const {
311 return (fst() == nullptr) ? &dom : lst();
312 }
313
314
315
316 /*
317 * Support for delta information
318 *
319 */
320 forceinline int
321 IntVarImp::min(const Delta& d) {
322 return static_cast<const IntDelta&>(d).min();
323 }
324 forceinline int
325 IntVarImp::max(const Delta& d) {
326 return static_cast<const IntDelta&>(d).max();
327 }
328 forceinline unsigned int
329 IntVarImp::width(const Delta& d) {
330 return static_cast<const IntDelta&>(d).width();
331 }
332 forceinline bool
333 IntVarImp::any(const Delta& d) {
334 return static_cast<const IntDelta&>(d).any();
335 }
336
337
338 /*
339 * Tell operations (to be inlined: performing bounds checks first)
340 *
341 */
342
343 forceinline ModEvent
344 IntVarImp::gq(Space& home, int n) {
345 if (n <= dom.min()) return ME_INT_NONE;
346 if (n > dom.max()) return fail(home);
347 ModEvent me = gq_full(home,n);
348 GECODE_ASSUME((me == ME_INT_FAILED) |
349 (me == ME_INT_VAL) |
350 (me == ME_INT_BND));
351 return me;
352 }
353 forceinline ModEvent
354 IntVarImp::gq(Space& home, long long int n) {
355 if (n <= dom.min()) return ME_INT_NONE;
356 if (n > dom.max()) return fail(home);
357 ModEvent me = gq_full(home,static_cast<int>(n));
358 GECODE_ASSUME((me == ME_INT_FAILED) |
359 (me == ME_INT_VAL) |
360 (me == ME_INT_BND));
361 return me;
362 }
363
364 forceinline ModEvent
365 IntVarImp::lq(Space& home, int n) {
366 if (n >= dom.max()) return ME_INT_NONE;
367 if (n < dom.min()) return fail(home);
368 ModEvent me = lq_full(home,n);
369 GECODE_ASSUME((me == ME_INT_FAILED) |
370 (me == ME_INT_VAL) |
371 (me == ME_INT_BND));
372 return me;
373 }
374 forceinline ModEvent
375 IntVarImp::lq(Space& home, long long int n) {
376 if (n >= dom.max()) return ME_INT_NONE;
377 if (n < dom.min()) return fail(home);
378 ModEvent me = lq_full(home,static_cast<int>(n));
379 GECODE_ASSUME((me == ME_INT_FAILED) |
380 (me == ME_INT_VAL) |
381 (me == ME_INT_BND));
382 return me;
383 }
384
385 forceinline ModEvent
386 IntVarImp::eq(Space& home, int n) {
387 if ((n < dom.min()) || (n > dom.max()))
388 return fail(home);
389 if ((n == dom.min()) && (n == dom.max()))
390 return ME_INT_NONE;
391 ModEvent me = eq_full(home,n);
392 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
393 return me;
394 }
395 forceinline ModEvent
396 IntVarImp::eq(Space& home, long long int m) {
397 if ((m < dom.min()) || (m > dom.max()))
398 return fail(home);
399 int n = static_cast<int>(m);
400 if ((n == dom.min()) && (n == dom.max()))
401 return ME_INT_NONE;
402 ModEvent me = eq_full(home,n);
403 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
404 return me;
405 }
406
407 forceinline ModEvent
408 IntVarImp::nq(Space& home, int n) {
409 if ((n < dom.min()) || (n > dom.max()))
410 return ME_INT_NONE;
411 return nq_full(home,n);
412 }
413 forceinline ModEvent
414 IntVarImp::nq(Space& home, long long int d) {
415 if ((d < dom.min()) || (d > dom.max()))
416 return ME_INT_NONE;
417 return nq_full(home,static_cast<int>(d));
418 }
419
420
421 /*
422 * Forward range iterator for rangelists
423 *
424 */
425
426 forceinline
427 IntVarImpFwd::IntVarImpFwd(void) {}
428 forceinline
429 IntVarImpFwd::IntVarImpFwd(const IntVarImp* x)
430 : p(nullptr), c(x->ranges_fwd()) {}
431 forceinline void
432 IntVarImpFwd::init(const IntVarImp* x) {
433 p=nullptr; c=x->ranges_fwd();
434 }
435
436 forceinline bool
437 IntVarImpFwd::operator ()(void) const {
438 return c != nullptr;
439 }
440 forceinline void
441 IntVarImpFwd::operator ++(void) {
442 const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
443 }
444
445 forceinline int
446 IntVarImpFwd::min(void) const {
447 return c->min();
448 }
449 forceinline int
450 IntVarImpFwd::max(void) const {
451 return c->max();
452 }
453 forceinline unsigned int
454 IntVarImpFwd::width(void) const {
455 return c->width();
456 }
457
458
459 /*
460 * Backward range iterator for rangelists
461 *
462 */
463
464 forceinline
465 IntVarImpBwd::IntVarImpBwd(void) {}
466 forceinline
467 IntVarImpBwd::IntVarImpBwd(const IntVarImp* x)
468 : n(nullptr), c(x->ranges_bwd()) {}
469 forceinline void
470 IntVarImpBwd::init(const IntVarImp* x) {
471 n=nullptr; c=x->ranges_bwd();
472 }
473
474 forceinline bool
475 IntVarImpBwd::operator ()(void) const {
476 return c != nullptr;
477 }
478 forceinline void
479 IntVarImpBwd::operator ++(void) {
480 const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
481 }
482
483 forceinline int
484 IntVarImpBwd::min(void) const {
485 return c->min();
486 }
487 forceinline int
488 IntVarImpBwd::max(void) const {
489 return c->max();
490 }
491 forceinline unsigned int
492 IntVarImpBwd::width(void) const {
493 return c->width();
494 }
495
496
497 /*
498 * Iterator-based domain operations
499 *
500 */
501 template<class I>
502 forceinline ModEvent
503 IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
504 // Is new domain empty?
505 if (!ri())
506 return fail(home);
507
508 int min0 = ri.min();
509 int max0 = ri.max();
510 ++ri;
511
512 ModEvent me;
513
514 // Is new domain range?
515 if (!ri()) {
516 // Remove possible rangelist (if it was not a range, the domain
517 // must have been narrowed!)
518 if (fst()) {
519 fst()->dispose(home,nullptr,lst());
520 fst(nullptr); holes = 0;
521 }
522 const int min1 = dom.min(); dom.min(min0);
523 const int max1 = dom.max(); dom.max(max0);
524 if ((min0 == min1) && (max0 == max1))
525 return ME_INT_NONE;
526 me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND;
527 goto notify;
528 }
529
530 if (depends || range()) {
531 // Construct new rangelist
532 RangeList* f = new (home) RangeList(min0,max0,nullptr,nullptr);
533 RangeList* l = f;
534 unsigned int s = static_cast<unsigned int>(max0-min0+1);
535 do {
536 RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,nullptr);
537 l->next(nullptr,n);
538 l = n;
539 s += ri.width();
540 ++ri;
541 } while (ri());
542 if (fst() != nullptr)
543 fst()->dispose(home,nullptr,lst());
544 fst(f); lst(l);
545
546 // Check for modification
547 if (size() == s)
548 return ME_INT_NONE;
549
550 const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
551 const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
552 holes = width() - s;
553
554 me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND;
555 goto notify;
556 } else {
557 // Set up two sentinel elements
558 RangeList f, l;
559 // Put all ranges between sentinels
560 f.prevnext(nullptr,fst()); l.prevnext(lst(),nullptr);
561 fst()->prev(nullptr,&f); lst()->next(nullptr,&l);
562
563 // Number of values removed (potential holes)
564 unsigned int h = 0;
565 // The previous range
566 RangeList* p = &f;
567 // The current range
568 RangeList* r = f.next(nullptr);
569
570 while (true) {
571 assert((r != &f) && (r != &l));
572 if (r->max() < min0) {
573 // Entire range removed
574 h += r->width();
575 RangeList* n=r->next(p);
576 p->next(r,n); n->prev(r,p);
577 r->dispose(home);
578 r=n;
579 if (r == &l)
580 goto done;
581 } else if ((r->min() == min0) && (r->max() == max0)) {
582 // Range unchanged
583 RangeList* n=r->next(p); p=r; r=n;
584 if (r == &l)
585 goto done;
586 if (!ri())
587 goto done;
588 min0=ri.min(); max0=ri.max(); ++ri;
589 } else {
590 // Range might have been split into many small ranges
591 assert((r->min() <= min0) && (max0 <= r->max()));
592 h += r->width();
593 int end = r->max();
594 // Copy first range
595 r->min(min0); r->max(max0);
596 assert(h > r->width());
597 h -= r->width();
598 {
599 RangeList* n=r->next(p); p=r; r=n;
600 }
601 while (true) {
602 if (!ri())
603 goto done;
604 min0=ri.min(); max0=ri.max(); ++ri;
605 if (max0 > end)
606 break;
607 assert(h > static_cast<unsigned int>(max0-min0+1));
608 h -= max0-min0+1;
609 RangeList* n = new (home) RangeList(min0,max0,p,r);
610 p->next(r,n); r->prev(p,n);
611 p=n;
612 }
613 if (r == &l)
614 goto done;
615 }
616 }
617 done:
618
619 // Remove remaining ranges
620 while (r != &l) {
621 h += r->width();
622 RangeList* n=r->next(p);
623 p->next(r,n); n->prev(r,p);
624 r->dispose(home);
625 r=n;
626 }
627
628 assert((r == &l) && !ri());
629
630 // New first and last ranges
631 RangeList* fn = f.next(nullptr);
632 RangeList* ln = l.prev(nullptr);
633
634 // All ranges pruned?
635 assert(fn != &l);
636
637 // Only a single range left?
638 assert(fn != ln);
639
640 // The number of removed values
641 holes += h;
642 // Unlink sentinel ranges
643 fn->prev(&f,nullptr); ln->next(&l,nullptr);
644 // How many values where removed at the bounds
645 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
646 static_cast<unsigned int>(dom.max()-ln->max()));
647 // Set new first and last ranges
648 fst(fn); lst(ln);
649
650 if (b > 0) {
651 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
652 dom.min(fn->min()); dom.max(ln->max());
653 holes -= b;
654 me = ME_INT_BND; goto notify;
655 }
656
657 if (h > 0) {
658 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
659 me = ME_INT_DOM; goto notify;
660 }
661 return ME_INT_NONE;
662 }
663 notify:
664 IntDelta d;
665 return notify(home,me,d);
666 }
667
668 template<class I>
669 forceinline ModEvent
670 IntVarImp::inter_r(Space& home, I& i, bool) {
671 IntVarImpFwd j(this);
672 Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
673 return narrow_r(home,ij,true);
674 }
675
676 template<class I>
677 forceinline ModEvent
678 IntVarImp::minus_r(Space& home, I& i, bool depends) {
679 if (depends) {
680 IntVarImpFwd j(this);
681 Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
682 return narrow_r(home,ij,true);
683 }
684
685 // Skip all ranges that are too small
686 while (i() && (i.max() < dom.min()))
687 ++i;
688
689 // Is there no range left or all are too large?
690 if (!i() || (i.min() > dom.max()))
691 return ME_INT_NONE;
692
693 int i_min = i.min();
694 int i_max = i.max();
695 ++i;
696
697 if ((i_min <= dom.min()) && (i_max >= dom.max()))
698 return fail(home);
699
700 if ((i_min > dom.min()) && (i_max >= dom.max()))
701 return lq(home,i_min-1);
702
703 if ((i_min <= dom.min()) && (i_max < dom.max()) &&
704 (!i() || (i.min() > dom.max())))
705 return gq(home,i_max+1);
706
707 // Set up two sentinel elements
708 RangeList f, l;
709 // Put all ranges between sentinels
710 if (range()) {
711 // Create a new rangelist just for simplicity
712 RangeList* n = new (home) RangeList(min(),max(),&f,&l);
713 f.prevnext(nullptr,n); l.prevnext(n,nullptr);
714 } else {
715 // Link the two sentinel elements
716 f.prevnext(nullptr,fst()); l.prevnext(lst(),nullptr);
717 fst()->prev(nullptr,&f); lst()->next(nullptr,&l);
718 }
719
720 // Number of values removed (potential holes)
721 unsigned int h = 0;
722 // The previous range
723 RangeList* p = &f;
724 // The current range
725 RangeList* r = f.next(nullptr);
726
727 while (true) {
728 assert((r != &f) && (r != &l));
729 if (i_min > r->max()) {
730 RangeList* n=r->next(p); p=r; r=n;
731 if (r == &l)
732 break;
733 } else if (i_max < r->min()) {
734 if (!i())
735 break;
736 i_min = i.min();
737 i_max = i.max();
738 ++i;
739 } else if ((i_min <= r->min()) && (r->max() <= i_max)) {
740 // r is included in i: remove entire range r
741 h += r->width();
742 RangeList* n=r->next(p);
743 p->next(r,n); n->prev(r,p);
744 r->dispose(home);
745 r=n;
746 if (r == &l)
747 break;
748 } else if ((i_min > r->min()) && (i_max < r->max())) {
749 // i is included in r: create new range before the current one
750 h += static_cast<unsigned int>(i_max - i_min) + 1;
751 RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r);
752 r->min(i_max+1);
753 p->next(r,n); r->prev(p,n);
754 p=n;
755 if (!i())
756 break;
757 i_min = i.min();
758 i_max = i.max();
759 ++i;
760 } else if (i_max < r->max()) {
761 assert(i_min <= r->min());
762 // i ends before r: adjust minimum of r
763 h += i_max-r->min()+1;
764 r->min(i_max+1);
765 if (!i())
766 break;
767 i_min = i.min();
768 i_max = i.max();
769 ++i;
770 } else {
771 assert((i_max >= r->max()) && (r->min() < i_min));
772 // r ends before i: adjust maximum of r
773 h += r->max()-i_min+1;
774 r->max(i_min-1);
775 RangeList* n=r->next(p); p=r; r=n;
776 if (r == &l)
777 break;
778 }
779 }
780
781 // New first and last ranges
782 RangeList* fn = f.next(nullptr);
783 RangeList* ln = l.prev(nullptr);
784
785 // All ranges pruned?
786 if (fn == &l) {
787 fst(nullptr); lst(nullptr); holes=0;
788 return fail(home);
789 }
790
791 ModEvent me;
792 unsigned int b;
793
794 // Only a single range left?
795 if (fn == ln) {
796 assert(h > 0);
797 dom.min(fn->min()); dom.max(fn->max());
798 fn->dispose(home);
799 fst(nullptr); lst(nullptr);
800 holes = 0;
801 me = assigned() ? ME_INT_VAL : ME_INT_BND;
802 goto notify;
803 }
804
805 // The number of removed values
806 holes += h;
807 // Unlink sentinel ranges
808 fn->prev(&f,nullptr); ln->next(&l,nullptr);
809 // How many values where removed at the bounds
810 b = (static_cast<unsigned int>(fn->min()-dom.min()) +
811 static_cast<unsigned int>(dom.max()-ln->max()));
812 // Set new first and last ranges
813 fst(fn); lst(ln);
814
815 if (b > 0) {
816 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
817 dom.min(fn->min()); dom.max(ln->max());
818 holes -= b;
819 me = ME_INT_BND; goto notify;
820 }
821
822 if (h > 0) {
823 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
824 me = ME_INT_DOM; goto notify;
825 }
826
827 return ME_INT_NONE;
828 notify:
829 IntDelta d;
830 return notify(home,me,d);
831 }
832
833 template<class I>
834 forceinline ModEvent
835 IntVarImp::narrow_v(Space& home, I& i, bool depends) {
836 Iter::Values::ToRanges<I> r(i);
837 return narrow_r(home,r,depends);
838 }
839
840 template<class I>
841 forceinline ModEvent
842 IntVarImp::inter_v(Space& home, I& i, bool depends) {
843 Iter::Values::ToRanges<I> r(i);
844 return inter_r(home,r,depends);
845 }
846
847 template<class I>
848 forceinline ModEvent
849 IntVarImp::minus_v(Space& home, I& i, bool depends) {
850 if (depends) {
851 Iter::Values::ToRanges<I> r(i);
852 return minus_r(home, r, true);
853 }
854
855 // Skip all values that are too small
856 while (i() && (i.val() < dom.min()))
857 ++i;
858
859 // Is there no value left or all are too large?
860 if (!i() || (i.val() > dom.max()))
861 return ME_INT_NONE;
862
863 int v = i.val();
864 // Skip values that are the same
865 do {
866 ++i;
867 } while (i() && (i.val() == v));
868
869 // Is there only a single value to be pruned?
870 if (!i() || (i.val() > dom.max()))
871 return nq_full(home,v);
872
873 // Set up two sentinel elements
874 RangeList f, l;
875 // Put all ranges between sentinels
876 if (range()) {
877 // Create a new rangelist just for simplicity
878 RangeList* n = new (home) RangeList(min(),max(),&f,&l);
879 f.prevnext(nullptr,n); l.prevnext(n,nullptr);
880 } else {
881 // Link the two sentinel elements
882 f.prevnext(nullptr,fst()); l.prevnext(lst(),nullptr);
883 fst()->prev(nullptr,&f); lst()->next(nullptr,&l);
884 }
885
886 // Number of values removed (potential holes)
887 unsigned int h = 0;
888 // The previous range
889 RangeList* p = &f;
890 // The current range
891 RangeList* r = f.next(nullptr);
892
893 while (true) {
894 assert((r != &f) && (r != &l));
895 if (v > r->max()) {
896 // Move to next range
897 RangeList* n=r->next(p); p=r; r=n;
898 if (r == &l)
899 break;
900 } else {
901 if ((v == r->min()) && (v == r->max())) {
902 // Remove range
903 h++;
904 RangeList* n=r->next(p);
905 p->next(r,n); n->prev(r,p);
906 r->dispose(home);
907 r=n;
908 if (r == &l)
909 break;
910 } else if (v == r->min()) {
911 h++; r->min(v+1);
912 } else if (v == r->max()) {
913 h++; r->max(v-1);
914 RangeList* n=r->next(p); p=r; r=n;
915 if (r == &l)
916 break;
917 } else if (v > r->min()) {
918 // Create new range before the current one
919 assert(v < r->max());
920 h++;
921 RangeList* n = new (home) RangeList(r->min(),v-1,p,r);
922 r->min(v+1);
923 p->next(r,n); r->prev(p,n);
924 p=n;
925 }
926 if (!i())
927 break;
928 // Move to next value
929 v = i.val(); ++i;
930 }
931 }
932 assert((r == &l) || !i());
933
934 // New first and last ranges
935 RangeList* fn = f.next(nullptr);
936 RangeList* ln = l.prev(nullptr);
937
938 // All ranges pruned?
939 if (fn == &l) {
940 fst(nullptr); lst(nullptr); holes=0;
941 return fail(home);
942 }
943
944 IntDelta d;
945
946 // Only a single range left?
947 if (fn == ln) {
948 assert(h > 0);
949 dom.min(fn->min()); dom.max(fn->max());
950 fn->dispose(home);
951 fst(nullptr); lst(nullptr);
952 holes = 0;
953 if (assigned())
954 return notify(home,ME_INT_VAL,d);
955 else
956 return notify(home,ME_INT_BND,d);
957 }
958
959 // The number of removed values
960 holes += h;
961 // Unlink sentinel ranges
962 fn->prev(&f,nullptr); ln->next(&l,nullptr);
963 // How many values where removed at the bounds
964 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
965 static_cast<unsigned int>(dom.max()-ln->max()));
966 // Set new first and last ranges
967 fst(fn); lst(ln);
968
969 if (b > 0) {
970 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
971 dom.min(fn->min()); dom.max(ln->max());
972 holes -= b;
973 return notify(home,ME_INT_BND,d);
974 }
975
976 if (h > 0) {
977 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
978 return notify(home,ME_INT_DOM,d);
979 }
980
981 return ME_INT_NONE;
982 }
983
984
985 /*
986 * Copying a variable
987 *
988 */
989
990 forceinline IntVarImp*
991 IntVarImp::copy(Space& home) {
992 return copied() ? static_cast<IntVarImp*>(forward())
993 : perform_copy(home);
994 }
995
996
997 forceinline ModEventDelta
998 IntVarImp::med(ModEvent me) {
999 return IntVarImpBase::med(me);
1000 }
1001
1002}}
1003
1004// STATISTICS: int-var