Generated on Thu Jan 19 2023 00:00:00 for Gecode by doxygen 1.9.6
int.hpp
Go to the documentation of this file.
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
50
53 : _min(min), _max(max) {}
54
57 : _min(min), _max(max) {
59 }
60
64 }
68 }
69 forceinline void
72 }
73 forceinline void
77 }
78 forceinline void
82 }
83 forceinline void
85 _next = n;
86 }
87
88 forceinline void
90 _min = n;
91 }
92 forceinline void
94 _max = n;
95 }
96
97 forceinline int
99 return _min;
100 }
101 forceinline int
103 return _max;
104 }
105 forceinline unsigned int
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&) {
117 }
118 forceinline void
119 IntVarImp::RangeList::operator delete(void*, void*) {
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
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
146 home.fl_dispose<sizeof(RangeList)>(this,l);
147 }
148
149 forceinline void
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
163 IntVarImp::fst(void) const {
164 return dom.next(NULL);
165 }
166
167 forceinline void
169 dom.prevnext(NULL,f);
170 }
171
173 IntVarImp::lst(void) const {
174 return _lst;
175 }
176
177 forceinline void
179 _lst = l;
180 }
181
182 /*
183 * Creation of new variable implementations
184 *
185 */
186
189 : IntVarImpBase(home), dom(min,max,NULL,NULL), holes(0) {}
190
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(NULL,&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],NULL);
211 holes = h;
212 } else {
213 fst(NULL); 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() == NULL;
240 }
241 forceinline bool
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
259 if (fst() == NULL) {
260 return (dom.min() == dom.max()) ? 0U : 1U;
261 } else if (dom.min() == fst()->max()) {
262 return static_cast<unsigned int>(fst()->next(NULL)->min()-dom.min());
263 } else {
264 return 1U;
265 }
266 }
267 forceinline unsigned int
269 if (fst() == NULL) {
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(NULL)->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() == NULL) || 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() == NULL) || in_full(static_cast<int>(n));
296 }
297
298
299 /*
300 * Accessing rangelists for iteration
301 *
302 */
303
306 return (fst() == NULL) ? &dom : fst();
307 }
308
311 return (fst() == NULL) ? &dom : lst();
312 }
313
314
315
316 /*
317 * Support for delta information
318 *
319 */
320 forceinline int
322 return static_cast<const IntDelta&>(d).min();
323 }
324 forceinline int
326 return static_cast<const IntDelta&>(d).max();
327 }
328 forceinline unsigned int
330 return static_cast<const IntDelta&>(d).width();
331 }
332 forceinline bool
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
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);
349 (me == ME_INT_VAL) |
350 (me == ME_INT_BND));
351 return me;
352 }
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));
359 (me == ME_INT_VAL) |
360 (me == ME_INT_BND));
361 return me;
362 }
363
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);
370 (me == ME_INT_VAL) |
371 (me == ME_INT_BND));
372 return me;
373 }
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));
380 (me == ME_INT_VAL) |
381 (me == ME_INT_BND));
382 return me;
383 }
384
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);
393 return me;
394 }
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);
404 return me;
405 }
406
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 }
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
430 : p(NULL), c(x->ranges_fwd()) {}
431 forceinline void
433 p=NULL; c=x->ranges_fwd();
434 }
435
436 forceinline bool
438 return c != NULL;
439 }
440 forceinline 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
455 return c->width();
456 }
457
458
459 /*
460 * Backward range iterator for rangelists
461 *
462 */
463
468 : n(NULL), c(x->ranges_bwd()) {}
469 forceinline void
471 n=NULL; c=x->ranges_bwd();
472 }
473
474 forceinline bool
476 return c != NULL;
477 }
478 forceinline 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
493 return c->width();
494 }
495
496
497 /*
498 * Iterator-based domain operations
499 *
500 */
501 template<class I>
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,NULL,lst());
520 fst(NULL); 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,NULL,NULL);
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,NULL);
537 l->next(NULL,n);
538 l = n;
539 s += ri.width();
540 ++ri;
541 } while (ri());
542 if (fst() != NULL)
543 fst()->dispose(home,NULL,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(NULL,fst()); l.prevnext(lst(),NULL);
561 fst()->prev(NULL,&f); lst()->next(NULL,&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(NULL);
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(NULL);
632 RangeList* ln = l.prev(NULL);
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,NULL); ln->next(&l,NULL);
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>
670 IntVarImp::inter_r(Space& home, I& i, bool) {
671 IntVarImpFwd j(this);
673 return narrow_r(home,ij,true);
674 }
675
676 template<class I>
678 IntVarImp::minus_r(Space& home, I& i, bool depends) {
679 if (depends) {
680 IntVarImpFwd j(this);
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(NULL,n); l.prevnext(n,NULL);
714 } else {
715 // Link the two sentinel elements
716 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
717 fst()->prev(NULL,&f); lst()->next(NULL,&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(NULL);
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(NULL);
783 RangeList* ln = l.prev(NULL);
784
785 // All ranges pruned?
786 if (fn == &l) {
787 fst(NULL); lst(NULL); 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(NULL); lst(NULL);
800 holes = 0;
802 goto notify;
803 }
804
805 // The number of removed values
806 holes += h;
807 // Unlink sentinel ranges
808 fn->prev(&f,NULL); ln->next(&l,NULL);
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>
835 IntVarImp::narrow_v(Space& home, I& i, bool depends) {
837 return narrow_r(home,r,depends);
838 }
839
840 template<class I>
842 IntVarImp::inter_v(Space& home, I& i, bool depends) {
844 return inter_r(home,r,depends);
845 }
846
847 template<class I>
849 IntVarImp::minus_v(Space& home, I& i, bool depends) {
850 if (depends) {
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(NULL,n); l.prevnext(n,NULL);
880 } else {
881 // Link the two sentinel elements
882 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
883 fst()->prev(NULL,&f); lst()->next(NULL,&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(NULL);
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(NULL);
936 RangeList* ln = l.prev(NULL);
937
938 // All ranges pruned?
939 if (fn == &l) {
940 fst(NULL); lst(NULL); 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(NULL); lst(NULL);
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,NULL); ln->next(&l,NULL);
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
992 return copied() ? static_cast<IntVarImp*>(forward())
993 : perform_copy(home);
994 }
995
996
999 return IntVarImpBase::med(me);
1000 }
1001
1002}}
1003
1004// STATISTICS: int-var
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Generic domain change information to be supplied to advisors.
Definition: core.hpp:204
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:248
FreeList * _next
Pointer to next freelist object.
Definition: manager.hpp:101
Integer sets.
Definition: int.hh:174
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:152
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:158
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:171
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:164
Integer delta information for advisors.
Definition: var-imp.hpp:51
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Gecode::ModEvent notify(Gecode::Space &home, Gecode::ModEvent me, Gecode::Delta &d)
Notify that variable implementation has been modified with modification event me and delta informatio...
Definition: var-imp.hpp:261
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:492
void operator++(void)
Move iterator to previous range (if possible)
Definition: int.hpp:479
int max(void) const
Return largest value of range.
Definition: int.hpp:488
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:475
int min(void) const
Return smallest value of range.
Definition: int.hpp:484
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:470
IntVarImpBwd(void)
Default constructor.
Definition: int.hpp:465
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:392
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
IntVarImpFwd(void)
Default constructor.
Definition: int.hpp:427
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:437
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:454
int min(void) const
Return smallest value of range.
Definition: int.hpp:446
void operator++(void)
Move iterator to next range (if possible)
Definition: int.hpp:441
int max(void) const
Return largest value of range.
Definition: int.hpp:450
Lists of ranges (intervals)
Definition: var-imp.hpp:102
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: int.hpp:106
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition: int.hpp:84
RangeList(void)
Default constructor (noop)
Definition: int.hpp:49
int min(void) const
Return minimum.
Definition: int.hpp:98
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition: int.hpp:70
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:66
RangeList * next(const RangeList *p) const
Return next element (from previous p)
Definition: int.hpp:62
int max(void) const
Return maximum.
Definition: int.hpp:102
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: int.hpp:134
Integer variable implementation.
Definition: var-imp.hpp:89
const RangeList * ranges_bwd(void) const
Return range list for backward iteration.
Definition: int.hpp:310
RangeList * _lst
Link the last element.
Definition: var-imp.hpp:190
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:173
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: int.hpp:248
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:386
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:46
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:835
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: int.hpp:268
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:842
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:286
IntVarImp * copy(Space &home)
Return copy of this variable.
Definition: int.hpp:991
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:242
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:365
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:408
int max(void) const
Return maximum of domain.
Definition: int.hpp:228
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:849
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:232
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:163
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:253
int min(void) const
Return minimum of domain.
Definition: int.hpp:224
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: int.hpp:258
RangeList dom
Domain information.
Definition: var-imp.hpp:188
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:200
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:238
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: int.hpp:503
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:317
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:670
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:678
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:344
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition: int.hpp:305
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: int.hpp:333
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
Range iterator for computing intersection (binary)
Range iterator from value iterator.
Computation spaces.
Definition: core.hpp:1742
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2827
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2837
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4570
bool copied(void) const
Is variable already copied.
Definition: core.hpp:4222
VarImp * forward(void) const
Use forward pointer if variable already copied.
Definition: core.hpp:4228
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4270
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4276
Base * next(void) const
Return next test.
Definition: test.hpp:58
#define GECODE_INT_RL2PD(r)
Definition: int.hpp:45
#define GECODE_INT_PD2RL(p)
Definition: int.hpp:46
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition: var-type.hpp:65
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Post propagator for SetVar x
Definition: set.hh:767
int ModEvent
Type for modification events.
Definition: core.hpp:62
#define forceinline
Definition: config.hpp:194
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
#define GECODE_ASSUME(p)
Assert certain property.
Definition: macros.hpp:114