Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
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
60
69 forceinline void
73 forceinline void
78 forceinline void
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
171
173 IntVarImp::lst(void) const {
174 return _lst;
175 }
176
177 forceinline void
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.
struct Gecode::@603::NNF::@65::@66 b
For binary nodes (and, or, eqv)
int p
Number of positive literals for node type.
int n
Number of negative literals for node type.
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.
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.
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.
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
static ModEvent me(const ModEventDelta &med)
Definition core.hpp:4270
static ModEventDelta med(ModEvent me)
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 .
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 .
Post propagator for SetVar x
Definition set.hh:767
int ModEvent
Type for modification events.
Definition core.hpp:62
#define forceinline
Definition config.hpp:187
#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