Generated on Thu Mar 7 2013 10:21:26 for Gecode by doxygen 1.8.3.1
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  * Last modified:
14  * $Date: 2010-07-29 01:35:33 +1000 (Thu, 29 Jul 2010) $ by $Author: schulte $
15  * $Revision: 11294 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 namespace Gecode { namespace Int {
43 
44  /*
45  * Range lists
46  *
47  */
48 
49 #define GECODE_INT_RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
50 #define GECODE_INT_PD2RL(p) reinterpret_cast<RangeList*>(p)
51 
54 
57  : _min(min), _max(max) {}
58 
61  : _min(min), _max(max) {
63  }
64 
68  }
72  }
73  forceinline void
76  }
77  forceinline void
79  _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
81  }
82  forceinline void
84  _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
86  }
87  forceinline void
89  _next = n;
90  }
91 
92  forceinline void
94  _min = n;
95  }
96  forceinline void
98  _max = n;
99  }
100 
101  forceinline int
103  return _min;
104  }
105  forceinline int
107  return _max;
108  }
109  forceinline unsigned int
111  return static_cast<unsigned int>(_max - _min) + 1;
112  }
113 
114 
115  forceinline void
116  IntVarImp::RangeList::operator delete(void*) {}
117 
118  forceinline void
119  IntVarImp::RangeList::operator delete(void*, Space&) {
120  GECODE_NEVER;
121  }
122  forceinline void
123  IntVarImp::RangeList::operator delete(void*, void*) {
124  GECODE_NEVER;
125  }
126 
127  forceinline void*
128  IntVarImp::RangeList::operator new(size_t, Space& home) {
129  return home.fl_alloc<sizeof(RangeList)>();
130  }
131 
132  forceinline void*
133  IntVarImp::RangeList::operator new(size_t, void* p) {
134  return p;
135  }
136 
137  forceinline void
139  RangeList* c = this;
140  while (c != l) {
141  RangeList* n = c->next(p);
142  c->fix(n);
143  p=c; c=n;
144  }
145  home.fl_dispose<sizeof(RangeList)>(this,l);
146  }
147 
148  forceinline void
150  home.fl_dispose<sizeof(RangeList)>(this,l);
151  }
152 
153  forceinline void
155  home.fl_dispose<sizeof(RangeList)>(this,this);
156  }
157 
158 #undef GECODE_INT_RL2PD
159 #undef GECODE_INT_PD2RL
160 
161  /*
162  * Mainitaining range lists for variable domain
163  *
164  */
165 
167  IntVarImp::fst(void) const {
168  return dom.next(NULL);
169  }
170 
171  forceinline void
173  dom.prevnext(NULL,f);
174  }
175 
177  IntVarImp::lst(void) const {
178  return _lst;
179  }
180 
181  forceinline void
183  _lst = l;
184  }
185 
186  /*
187  * Creation of new variable implementations
188  *
189  */
190 
193  : IntVarImpBase(home), dom(min,max,NULL,NULL), holes(0) {}
194 
197  : IntVarImpBase(home), dom(d.min(),d.max()) {
198  if (d.ranges() > 1) {
199  int n = d.ranges();
200  assert(n >= 2);
201  RangeList* r = home.alloc<RangeList>(n);
202  fst(r); lst(r+n-1);
203  unsigned int h = static_cast<unsigned int>(d.max()-d.min())+1;
204  h -= d.width(0);
205  r[0].min(d.min(0)); r[0].max(d.max(0));
206  r[0].prevnext(NULL,&r[1]);
207  for (int i = 1; i < n-1; i++) {
208  h -= d.width(i);
209  r[i].min(d.min(i)); r[i].max(d.max(i));
210  r[i].prevnext(&r[i-1],&r[i+1]);
211  }
212  h -= d.width(n-1);
213  r[n-1].min(d.min(n-1)); r[n-1].max(d.max(n-1));
214  r[n-1].prevnext(&r[n-2],NULL);
215  holes = h;
216  } else {
217  fst(NULL); holes = 0;
218  }
219  }
220 
221 
222  /*
223  * Operations on integer variable implementations
224  *
225  */
226 
227  forceinline int
228  IntVarImp::min(void) const {
229  return dom.min();
230  }
231  forceinline int
232  IntVarImp::max(void) const {
233  return dom.max();
234  }
235  forceinline int
236  IntVarImp::val(void) const {
237  assert(dom.min() == dom.max());
238  return dom.min();
239  }
240 
241  forceinline bool
242  IntVarImp::range(void) const {
243  return fst() == NULL;
244  }
245  forceinline bool
246  IntVarImp::assigned(void) const {
247  return dom.min() == dom.max();
248  }
249 
250 
251  forceinline unsigned int
252  IntVarImp::width(void) const {
253  return dom.width();
254  }
255 
256  forceinline unsigned int
257  IntVarImp::size(void) const {
258  return dom.width() - holes;
259  }
260 
261  forceinline unsigned int
262  IntVarImp::regret_min(void) const {
263  if (fst() == NULL) {
264  return (dom.min() == dom.max()) ? 0U : 1U;
265  } else if (dom.min() == fst()->max()) {
266  return static_cast<unsigned int>(fst()->next(NULL)->min()-dom.min());
267  } else {
268  return 1U;
269  }
270  }
271  forceinline unsigned int
272  IntVarImp::regret_max(void) const {
273  if (fst() == NULL) {
274  return (dom.min() == dom.max()) ? 0U : 1U;
275  } else if (dom.max() == lst()->min()) {
276  return static_cast<unsigned int>(dom.max()-lst()->prev(NULL)->max());
277  } else {
278  return 1U;
279  }
280  }
281 
282 
283 
284  /*
285  * Tests
286  *
287  */
288 
289  forceinline bool
290  IntVarImp::in(int n) const {
291  if ((n < dom.min()) || (n > dom.max()))
292  return false;
293  return (fst() == NULL) || in_full(n);
294  }
295  forceinline bool
296  IntVarImp::in(double n) const {
297  if ((n < dom.min()) || (n > dom.max()))
298  return false;
299  return (fst() == NULL) || in_full(static_cast<int>(n));
300  }
301 
302 
303  /*
304  * Accessing rangelists for iteration
305  *
306  */
307 
309  IntVarImp::ranges_fwd(void) const {
310  return (fst() == NULL) ? &dom : fst();
311  }
312 
314  IntVarImp::ranges_bwd(void) const {
315  return (fst() == NULL) ? &dom : lst();
316  }
317 
318 
319 
320  /*
321  * Support for delta information
322  *
323  */
324  forceinline int
326  return static_cast<const IntDelta&>(d).min();
327  }
328  forceinline int
330  return static_cast<const IntDelta&>(d).max();
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 ME_INT_FAILED;
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  }
354  IntVarImp::gq(Space& home, double n) {
355  if (n <= dom.min()) return ME_INT_NONE;
356  if (n > dom.max()) return ME_INT_FAILED;
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 
366  IntVarImp::lq(Space& home, int n) {
367  if (n >= dom.max()) return ME_INT_NONE;
368  if (n < dom.min()) return ME_INT_FAILED;
369  ModEvent me = lq_full(home,n);
370  GECODE_ASSUME((me == ME_INT_FAILED) |
371  (me == ME_INT_VAL) |
372  (me == ME_INT_BND));
373  return me;
374  }
376  IntVarImp::lq(Space& home, double n) {
377  if (n >= dom.max()) return ME_INT_NONE;
378  if (n < dom.min()) return ME_INT_FAILED;
379  ModEvent me = lq_full(home,static_cast<int>(n));
380  GECODE_ASSUME((me == ME_INT_FAILED) |
381  (me == ME_INT_VAL) |
382  (me == ME_INT_BND));
383  return me;
384  }
385 
386 
388  IntVarImp::eq(Space& home, int n) {
389  if ((n < dom.min()) || (n > dom.max()))
390  return ME_INT_FAILED;
391  if ((n == dom.min()) && (n == dom.max()))
392  return ME_INT_NONE;
393  ModEvent me = eq_full(home,n);
394  GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
395  return me;
396  }
398  IntVarImp::eq(Space& home, double m) {
399  if ((m < dom.min()) || (m > dom.max()))
400  return ME_INT_FAILED;
401  int n = static_cast<int>(m);
402  if ((n == dom.min()) && (n == dom.max()))
403  return ME_INT_NONE;
404  ModEvent me = eq_full(home,n);
405  GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
406  return me;
407  }
408 
409 
411  IntVarImp::nq(Space& home, int n) {
412  if ((n < dom.min()) || (n > dom.max()))
413  return ME_INT_NONE;
414  return nq_full(home,n);
415  }
417  IntVarImp::nq(Space& home, double d) {
418  if ((d < dom.min()) || (d > dom.max()))
419  return ME_INT_NONE;
420  return nq_full(home,static_cast<int>(d));
421  }
422 
423 
424  /*
425  * Forward range iterator for rangelists
426  *
427  */
428 
433  : p(NULL), c(x->ranges_fwd()) {}
434  forceinline void
436  p=NULL; c=x->ranges_fwd();
437  }
438 
439  forceinline bool
441  return c != NULL;
442  }
443  forceinline void
445  const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
446  }
447 
448  forceinline int
449  IntVarImpFwd::min(void) const {
450  return c->min();
451  }
452  forceinline int
453  IntVarImpFwd::max(void) const {
454  return c->max();
455  }
456  forceinline unsigned int
457  IntVarImpFwd::width(void) const {
458  return c->width();
459  }
460 
461 
462  /*
463  * Backward range iterator for rangelists
464  *
465  */
466 
471  : n(NULL), c(x->ranges_bwd()) {}
472  forceinline void
474  n=NULL; c=x->ranges_bwd();
475  }
476 
477  forceinline bool
479  return c != NULL;
480  }
481  forceinline void
483  const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
484  }
485 
486  forceinline int
487  IntVarImpBwd::min(void) const {
488  return c->min();
489  }
490  forceinline int
491  IntVarImpBwd::max(void) const {
492  return c->max();
493  }
494  forceinline unsigned int
495  IntVarImpBwd::width(void) const {
496  return c->width();
497  }
498 
499 
500  /*
501  * Iterator-based domain operations
502  *
503  */
504  template<class I>
506  IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
507  // Is new domain empty?
508  if (!ri())
509  return ME_INT_FAILED;
510 
511  int min0 = ri.min();
512  int max0 = ri.max();
513  ++ri;
514 
515  ModEvent me;
516 
517  // Is new domain range?
518  if (!ri()) {
519  // Remove possible rangelist (if it was not a range, the domain
520  // must have been narrowed!)
521  if (fst()) {
522  fst()->dispose(home,NULL,lst());
523  fst(NULL); holes = 0;
524  }
525  const int min1 = dom.min(); dom.min(min0);
526  const int max1 = dom.max(); dom.max(max0);
527  if ((min0 == min1) && (max0 == max1))
528  return ME_INT_NONE;
529  me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND;
530  goto notify;
531  }
532 
533  if (depends || range()) {
534  // Construct new rangelist
535  RangeList* f = new (home) RangeList(min0,max0,NULL,NULL);
536  RangeList* l = f;
537  unsigned int s = static_cast<unsigned int>(max0-min0+1);
538  do {
539  RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
540  l->next(NULL,n);
541  l = n;
542  s += ri.width();
543  ++ri;
544  } while (ri());
545  if (fst() != NULL)
546  fst()->dispose(home,NULL,lst());
547  fst(f); lst(l);
548 
549  // Check for modification
550  if (size() == s)
551  return ME_INT_NONE;
552 
553  const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
554  const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
555  holes = width() - s;
556 
557  me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND;
558  goto notify;
559  } else {
560  // Set up two sentinel elements
561  RangeList f, l;
562  // Put all ranges between sentinels
563  f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
564  fst()->prev(NULL,&f); lst()->next(NULL,&l);
565 
566  // Number of values removed (potential holes)
567  unsigned int h = 0;
568  // The previous range
569  RangeList* p = &f;
570  // The current range
571  RangeList* r = f.next(NULL);
572 
573  while (true) {
574  assert((r != &f) && (r != &l));
575  if (r->max() < min0) {
576  // Entire range removed
577  h += r->width();
578  RangeList* n=r->next(p);
579  p->next(r,n); n->prev(r,p);
580  r->dispose(home);
581  r=n;
582  if (r == &l)
583  goto done;
584  } else if ((r->min() == min0) && (r->max() == max0)) {
585  // Range unchanged
586  RangeList* n=r->next(p); p=r; r=n;
587  if (r == &l)
588  goto done;
589  if (!ri())
590  goto done;
591  min0=ri.min(); max0=ri.max(); ++ri;
592  } else {
593  // Range might have been split into many small ranges
594  assert((r->min() <= min0) && (max0 <= r->max()));
595  h += r->width();
596  int end = r->max();
597  // Copy first range
598  r->min(min0); r->max(max0);
599  assert(h > r->width());
600  h -= r->width();
601  {
602  RangeList* n=r->next(p); p=r; r=n;
603  }
604  while (true) {
605  if (!ri())
606  goto done;
607  min0=ri.min(); max0=ri.max(); ++ri;
608  if (max0 > end)
609  break;
610  assert(h > static_cast<unsigned int>(max0-min0+1));
611  h -= max0-min0+1;
612  RangeList* n = new (home) RangeList(min0,max0,p,r);
613  p->next(r,n); r->prev(p,n);
614  p=n;
615  }
616  if (r == &l)
617  goto done;
618  }
619  }
620  done:
621 
622  // Remove remaining ranges
623  while (r != &l) {
624  h += r->width();
625  RangeList* n=r->next(p);
626  p->next(r,n); n->prev(r,p);
627  r->dispose(home);
628  r=n;
629  }
630 
631  assert((r == &l) && !ri());
632 
633  // New first and last ranges
634  RangeList* fn = f.next(NULL);
635  RangeList* ln = l.prev(NULL);
636 
637  // All ranges pruned?
638  assert(fn != &l);
639 
640  // Only a single range left?
641  assert(fn != ln);
642 
643  // The number of removed values
644  holes += h;
645  // Unlink sentinel ranges
646  fn->prev(&f,NULL); ln->next(&l,NULL);
647  // How many values where removed at the bounds
648  unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
649  static_cast<unsigned int>(dom.max()-ln->max()));
650  // Set new first and last ranges
651  fst(fn); lst(ln);
652 
653  if (b > 0) {
654  assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
655  dom.min(fn->min()); dom.max(ln->max());
656  holes -= b;
657  me = ME_INT_BND; goto notify;
658  }
659 
660  if (h > 0) {
661  assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
662  me = ME_INT_DOM; goto notify;
663  }
664  return ME_INT_NONE;
665  }
666  notify:
667  IntDelta d;
668  return notify(home,me,d);
669  }
670 
671  template<class I>
673  IntVarImp::inter_r(Space& home, I& i, bool) {
674  IntVarImpFwd j(this);
676  return narrow_r(home,ij,true);
677  }
678 
679  template<class I>
681  IntVarImp::minus_r(Space& home, I& i, bool depends) {
682  if (depends) {
683  IntVarImpFwd j(this);
685  return narrow_r(home,ij,true);
686  }
687 
688  // Skip all ranges that are too small
689  while (i() && (i.max() < dom.min()))
690  ++i;
691 
692  // Is there no range left or all are too large?
693  if (!i() || (i.min() > dom.max()))
694  return ME_INT_NONE;
695 
696  int i_min = i.min();
697  int i_max = i.max();
698  ++i;
699 
700  if ((i_min <= dom.min()) && (i_max >= dom.max()))
701  return ME_INT_FAILED;
702 
703  if ((i_min > dom.min()) && (i_max >= dom.max()))
704  return lq(home,i_min-1);
705 
706  if ((i_min <= dom.min()) && (i_max < dom.max()) &&
707  (!i() || (i.min() > dom.max())))
708  return gq(home,i_max+1);
709 
710  // Set up two sentinel elements
711  RangeList f, l;
712  // Put all ranges between sentinels
713  if (range()) {
714  // Create a new rangelist just for simplicity
715  RangeList* n = new (home) RangeList(min(),max(),&f,&l);
716  f.prevnext(NULL,n); l.prevnext(n,NULL);
717  } else {
718  // Link the two sentinel elements
719  f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
720  fst()->prev(NULL,&f); lst()->next(NULL,&l);
721  }
722 
723  // Number of values removed (potential holes)
724  unsigned int h = 0;
725  // The previous range
726  RangeList* p = &f;
727  // The current range
728  RangeList* r = f.next(NULL);
729 
730  while (true) {
731  assert((r != &f) && (r != &l));
732  if (i_min > r->max()) {
733  RangeList* n=r->next(p); p=r; r=n;
734  if (r == &l)
735  break;
736  } else if (i_max < r->min()) {
737  if (!i())
738  break;
739  i_min = i.min();
740  i_max = i.max();
741  ++i;
742  } else if ((i_min <= r->min()) && (r->max() <= i_max)) {
743  // r is included in i: remove entire range r
744  h += r->width();
745  RangeList* n=r->next(p);
746  p->next(r,n); n->prev(r,p);
747  r->dispose(home);
748  r=n;
749  if (r == &l)
750  break;
751  } else if ((i_min > r->min()) && (i_max < r->max())) {
752  // i is included in r: create new range before the current one
753  h += static_cast<unsigned int>(i_max - i_min) + 1;
754  RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r);
755  r->min(i_max+1);
756  p->next(r,n); r->prev(p,n);
757  p=n;
758  if (!i())
759  break;
760  i_min = i.min();
761  i_max = i.max();
762  ++i;
763  } else if (i_max < r->max()) {
764  assert(i_min <= r->min());
765  // i ends before r: adjust minimum of r
766  h += i_max-r->min()+1;
767  r->min(i_max+1);
768  if (!i())
769  break;
770  i_min = i.min();
771  i_max = i.max();
772  ++i;
773  } else {
774  assert((i_max >= r->max()) && (r->min() < i_min));
775  // r ends before i: adjust maximum of r
776  h += r->max()-i_min+1;
777  r->max(i_min-1);
778  RangeList* n=r->next(p); p=r; r=n;
779  if (r == &l)
780  break;
781  }
782  }
783 
784  // New first and last ranges
785  RangeList* fn = f.next(NULL);
786  RangeList* ln = l.prev(NULL);
787 
788  // All ranges pruned?
789  if (fn == &l) {
790  fst(NULL); lst(NULL); holes=0;
791  return ME_INT_FAILED;
792  }
793 
794  ModEvent me;
795  unsigned int b;
796 
797  // Only a single range left?
798  if (fn == ln) {
799  assert(h > 0);
800  dom.min(fn->min()); dom.max(fn->max());
801  fn->dispose(home);
802  fst(NULL); lst(NULL);
803  holes = 0;
804  me = assigned() ? ME_INT_VAL : ME_INT_BND;
805  goto notify;
806  }
807 
808  // The number of removed values
809  holes += h;
810  // Unlink sentinel ranges
811  fn->prev(&f,NULL); ln->next(&l,NULL);
812  // How many values where removed at the bounds
813  b = (static_cast<unsigned int>(fn->min()-dom.min()) +
814  static_cast<unsigned int>(dom.max()-ln->max()));
815  // Set new first and last ranges
816  fst(fn); lst(ln);
817 
818  if (b > 0) {
819  assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
820  dom.min(fn->min()); dom.max(ln->max());
821  holes -= b;
822  me = ME_INT_BND; goto notify;
823  }
824 
825  if (h > 0) {
826  assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
827  me = ME_INT_DOM; goto notify;
828  }
829 
830  return ME_INT_NONE;
831  notify:
832  IntDelta d;
833  return notify(home,me,d);
834  }
835 
836  template<class I>
838  IntVarImp::narrow_v(Space& home, I& i, bool depends) {
840  return narrow_r(home,r,depends);
841  }
842 
843  template<class I>
845  IntVarImp::inter_v(Space& home, I& i, bool depends) {
847  return inter_r(home,r,depends);
848  }
849 
850  template<class I>
852  IntVarImp::minus_v(Space& home, I& i, bool depends) {
853  if (depends) {
855  return minus_r(home, r, true);
856  }
857 
858  // Skip all values that are too small
859  while (i() && (i.val() < dom.min()))
860  ++i;
861 
862  // Is there no value left or all are too large?
863  if (!i() || (i.val() > dom.max()))
864  return ME_INT_NONE;
865 
866  int v = i.val();
867  // Skip values that are the same
868  do {
869  ++i;
870  } while (i() && (i.val() == v));
871 
872  // Is there only a single value to be pruned?
873  if (!i() || (i.val() > dom.max()))
874  return nq_full(home,v);
875 
876  // Set up two sentinel elements
877  RangeList f, l;
878  // Put all ranges between sentinels
879  if (range()) {
880  // Create a new rangelist just for simplicity
881  RangeList* n = new (home) RangeList(min(),max(),&f,&l);
882  f.prevnext(NULL,n); l.prevnext(n,NULL);
883  } else {
884  // Link the two sentinel elements
885  f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
886  fst()->prev(NULL,&f); lst()->next(NULL,&l);
887  }
888 
889  // Number of values removed (potential holes)
890  unsigned int h = 0;
891  // The previous range
892  RangeList* p = &f;
893  // The current range
894  RangeList* r = f.next(NULL);
895 
896  while (true) {
897  assert((r != &f) && (r != &l));
898  if (v > r->max()) {
899  // Move to next range
900  RangeList* n=r->next(p); p=r; r=n;
901  if (r == &l)
902  break;
903  } else {
904  if ((v == r->min()) && (v == r->max())) {
905  // Remove range
906  h++;
907  RangeList* n=r->next(p);
908  p->next(r,n); n->prev(r,p);
909  r->dispose(home);
910  r=n;
911  if (r == &l)
912  break;
913  } else if (v == r->min()) {
914  h++; r->min(v+1);
915  } else if (v == r->max()) {
916  h++; r->max(v-1);
917  RangeList* n=r->next(p); p=r; r=n;
918  if (r == &l)
919  break;
920  } else if (v > r->min()) {
921  // Create new range before the current one
922  assert(v < r->max());
923  h++;
924  RangeList* n = new (home) RangeList(r->min(),v-1,p,r);
925  r->min(v+1);
926  p->next(r,n); r->prev(p,n);
927  p=n;
928  }
929  if (!i())
930  break;
931  // Move to next value
932  v = i.val(); ++i;
933  }
934  }
935  assert((r == &l) || !i());
936 
937  // New first and last ranges
938  RangeList* fn = f.next(NULL);
939  RangeList* ln = l.prev(NULL);
940 
941  // All ranges pruned?
942  if (fn == &l) {
943  fst(NULL); lst(NULL); holes=0;
944  return ME_INT_FAILED;
945  }
946 
947  IntDelta d;
948 
949  // Only a single range left?
950  if (fn == ln) {
951  assert(h > 0);
952  dom.min(fn->min()); dom.max(fn->max());
953  fn->dispose(home);
954  fst(NULL); lst(NULL);
955  holes = 0;
956  if (assigned())
957  return notify(home,ME_INT_VAL,d);
958  else
959  return notify(home,ME_INT_BND,d);
960  }
961 
962  // The number of removed values
963  holes += h;
964  // Unlink sentinel ranges
965  fn->prev(&f,NULL); ln->next(&l,NULL);
966  // How many values where removed at the bounds
967  unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
968  static_cast<unsigned int>(dom.max()-ln->max()));
969  // Set new first and last ranges
970  fst(fn); lst(ln);
971 
972  if (b > 0) {
973  assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
974  dom.min(fn->min()); dom.max(ln->max());
975  holes -= b;
976  return notify(home,ME_INT_BND,d);
977  }
978 
979  if (h > 0) {
980  assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
981  return notify(home,ME_INT_DOM,d);
982  }
983 
984  return ME_INT_NONE;
985  }
986 
987 
988  /*
989  * Copying a variable
990  *
991  */
992 
994  IntVarImp::copy(Space& home, bool share) {
995  return copied() ? static_cast<IntVarImp*>(forward())
996  : perform_copy(home,share);
997  }
998 
999 
1000  /*
1001  * Dependencies
1002  *
1003  */
1004  forceinline void
1005  IntVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) {
1006  IntVarImpBase::subscribe(home,p,pc,dom.min()==dom.max(),schedule);
1007  }
1008  forceinline void
1010  IntVarImpBase::cancel(home,p,pc,dom.min()==dom.max());
1011  }
1012 
1013  forceinline void
1015  IntVarImpBase::subscribe(home,a,dom.min()==dom.max());
1016  }
1017  forceinline void
1019  IntVarImpBase::cancel(home,a,dom.min()==dom.max());
1020  }
1021 
1024  return IntVarImpBase::med(me);
1025  }
1026 
1027 }}
1028 
1029 // STATISTICS: int-var