Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
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$ by $Author$
15  * $Revision$
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
81  }
82  forceinline void
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(long long int 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 unsigned int
334  return static_cast<const IntDelta&>(d).width();
335  }
336  forceinline bool
338  return static_cast<const IntDelta&>(d).any();
339  }
340 
341 
342  /*
343  * Tell operations (to be inlined: performing bounds checks first)
344  *
345  */
346 
348  IntVarImp::gq(Space& home, int n) {
349  if (n <= dom.min()) return ME_INT_NONE;
350  if (n > dom.max()) return fail(home);
351  ModEvent me = gq_full(home,n);
352  GECODE_ASSUME((me == ME_INT_FAILED) |
353  (me == ME_INT_VAL) |
354  (me == ME_INT_BND));
355  return me;
356  }
358  IntVarImp::gq(Space& home, long long int n) {
359  if (n <= dom.min()) return ME_INT_NONE;
360  if (n > dom.max()) return fail(home);
361  ModEvent me = gq_full(home,static_cast<int>(n));
362  GECODE_ASSUME((me == ME_INT_FAILED) |
363  (me == ME_INT_VAL) |
364  (me == ME_INT_BND));
365  return me;
366  }
367 
369  IntVarImp::lq(Space& home, int n) {
370  if (n >= dom.max()) return ME_INT_NONE;
371  if (n < dom.min()) return fail(home);
372  ModEvent me = lq_full(home,n);
373  GECODE_ASSUME((me == ME_INT_FAILED) |
374  (me == ME_INT_VAL) |
375  (me == ME_INT_BND));
376  return me;
377  }
379  IntVarImp::lq(Space& home, long long int n) {
380  if (n >= dom.max()) return ME_INT_NONE;
381  if (n < dom.min()) return fail(home);
382  ModEvent me = lq_full(home,static_cast<int>(n));
383  GECODE_ASSUME((me == ME_INT_FAILED) |
384  (me == ME_INT_VAL) |
385  (me == ME_INT_BND));
386  return me;
387  }
388 
390  IntVarImp::eq(Space& home, int n) {
391  if ((n < dom.min()) || (n > dom.max()))
392  return fail(home);
393  if ((n == dom.min()) && (n == dom.max()))
394  return ME_INT_NONE;
395  ModEvent me = eq_full(home,n);
396  GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
397  return me;
398  }
400  IntVarImp::eq(Space& home, long long int m) {
401  if ((m < dom.min()) || (m > dom.max()))
402  return fail(home);
403  int n = static_cast<int>(m);
404  if ((n == dom.min()) && (n == dom.max()))
405  return ME_INT_NONE;
406  ModEvent me = eq_full(home,n);
407  GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
408  return me;
409  }
410 
412  IntVarImp::nq(Space& home, int n) {
413  if ((n < dom.min()) || (n > dom.max()))
414  return ME_INT_NONE;
415  return nq_full(home,n);
416  }
418  IntVarImp::nq(Space& home, long long int d) {
419  if ((d < dom.min()) || (d > dom.max()))
420  return ME_INT_NONE;
421  return nq_full(home,static_cast<int>(d));
422  }
423 
424 
425  /*
426  * Forward range iterator for rangelists
427  *
428  */
429 
434  : p(NULL), c(x->ranges_fwd()) {}
435  forceinline void
437  p=NULL; c=x->ranges_fwd();
438  }
439 
440  forceinline bool
442  return c != NULL;
443  }
444  forceinline void
446  const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
447  }
448 
449  forceinline int
450  IntVarImpFwd::min(void) const {
451  return c->min();
452  }
453  forceinline int
454  IntVarImpFwd::max(void) const {
455  return c->max();
456  }
457  forceinline unsigned int
458  IntVarImpFwd::width(void) const {
459  return c->width();
460  }
461 
462 
463  /*
464  * Backward range iterator for rangelists
465  *
466  */
467 
472  : n(NULL), c(x->ranges_bwd()) {}
473  forceinline void
475  n=NULL; c=x->ranges_bwd();
476  }
477 
478  forceinline bool
480  return c != NULL;
481  }
482  forceinline void
484  const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
485  }
486 
487  forceinline int
488  IntVarImpBwd::min(void) const {
489  return c->min();
490  }
491  forceinline int
492  IntVarImpBwd::max(void) const {
493  return c->max();
494  }
495  forceinline unsigned int
496  IntVarImpBwd::width(void) const {
497  return c->width();
498  }
499 
500 
501  /*
502  * Iterator-based domain operations
503  *
504  */
505  template<class I>
507  IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
508  // Is new domain empty?
509  if (!ri())
510  return fail(home);
511 
512  int min0 = ri.min();
513  int max0 = ri.max();
514  ++ri;
515 
516  ModEvent me;
517 
518  // Is new domain range?
519  if (!ri()) {
520  // Remove possible rangelist (if it was not a range, the domain
521  // must have been narrowed!)
522  if (fst()) {
523  fst()->dispose(home,NULL,lst());
524  fst(NULL); holes = 0;
525  }
526  const int min1 = dom.min(); dom.min(min0);
527  const int max1 = dom.max(); dom.max(max0);
528  if ((min0 == min1) && (max0 == max1))
529  return ME_INT_NONE;
530  me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND;
531  goto notify;
532  }
533 
534  if (depends || range()) {
535  // Construct new rangelist
536  RangeList* f = new (home) RangeList(min0,max0,NULL,NULL);
537  RangeList* l = f;
538  unsigned int s = static_cast<unsigned int>(max0-min0+1);
539  do {
540  RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
541  l->next(NULL,n);
542  l = n;
543  s += ri.width();
544  ++ri;
545  } while (ri());
546  if (fst() != NULL)
547  fst()->dispose(home,NULL,lst());
548  fst(f); lst(l);
549 
550  // Check for modification
551  if (size() == s)
552  return ME_INT_NONE;
553 
554  const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
555  const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
556  holes = width() - s;
557 
558  me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND;
559  goto notify;
560  } else {
561  // Set up two sentinel elements
562  RangeList f, l;
563  // Put all ranges between sentinels
564  f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
565  fst()->prev(NULL,&f); lst()->next(NULL,&l);
566 
567  // Number of values removed (potential holes)
568  unsigned int h = 0;
569  // The previous range
570  RangeList* p = &f;
571  // The current range
572  RangeList* r = f.next(NULL);
573 
574  while (true) {
575  assert((r != &f) && (r != &l));
576  if (r->max() < min0) {
577  // Entire range removed
578  h += r->width();
579  RangeList* n=r->next(p);
580  p->next(r,n); n->prev(r,p);
581  r->dispose(home);
582  r=n;
583  if (r == &l)
584  goto done;
585  } else if ((r->min() == min0) && (r->max() == max0)) {
586  // Range unchanged
587  RangeList* n=r->next(p); p=r; r=n;
588  if (r == &l)
589  goto done;
590  if (!ri())
591  goto done;
592  min0=ri.min(); max0=ri.max(); ++ri;
593  } else {
594  // Range might have been split into many small ranges
595  assert((r->min() <= min0) && (max0 <= r->max()));
596  h += r->width();
597  int end = r->max();
598  // Copy first range
599  r->min(min0); r->max(max0);
600  assert(h > r->width());
601  h -= r->width();
602  {
603  RangeList* n=r->next(p); p=r; r=n;
604  }
605  while (true) {
606  if (!ri())
607  goto done;
608  min0=ri.min(); max0=ri.max(); ++ri;
609  if (max0 > end)
610  break;
611  assert(h > static_cast<unsigned int>(max0-min0+1));
612  h -= max0-min0+1;
613  RangeList* n = new (home) RangeList(min0,max0,p,r);
614  p->next(r,n); r->prev(p,n);
615  p=n;
616  }
617  if (r == &l)
618  goto done;
619  }
620  }
621  done:
622 
623  // Remove remaining ranges
624  while (r != &l) {
625  h += r->width();
626  RangeList* n=r->next(p);
627  p->next(r,n); n->prev(r,p);
628  r->dispose(home);
629  r=n;
630  }
631 
632  assert((r == &l) && !ri());
633 
634  // New first and last ranges
635  RangeList* fn = f.next(NULL);
636  RangeList* ln = l.prev(NULL);
637 
638  // All ranges pruned?
639  assert(fn != &l);
640 
641  // Only a single range left?
642  assert(fn != ln);
643 
644  // The number of removed values
645  holes += h;
646  // Unlink sentinel ranges
647  fn->prev(&f,NULL); ln->next(&l,NULL);
648  // How many values where removed at the bounds
649  unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
650  static_cast<unsigned int>(dom.max()-ln->max()));
651  // Set new first and last ranges
652  fst(fn); lst(ln);
653 
654  if (b > 0) {
655  assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
656  dom.min(fn->min()); dom.max(ln->max());
657  holes -= b;
658  me = ME_INT_BND; goto notify;
659  }
660 
661  if (h > 0) {
662  assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
663  me = ME_INT_DOM; goto notify;
664  }
665  return ME_INT_NONE;
666  }
667  notify:
668  IntDelta d;
669  return notify(home,me,d);
670  }
671 
672  template<class I>
674  IntVarImp::inter_r(Space& home, I& i, bool) {
675  IntVarImpFwd j(this);
677  return narrow_r(home,ij,true);
678  }
679 
680  template<class I>
682  IntVarImp::minus_r(Space& home, I& i, bool depends) {
683  if (depends) {
684  IntVarImpFwd j(this);
686  return narrow_r(home,ij,true);
687  }
688 
689  // Skip all ranges that are too small
690  while (i() && (i.max() < dom.min()))
691  ++i;
692 
693  // Is there no range left or all are too large?
694  if (!i() || (i.min() > dom.max()))
695  return ME_INT_NONE;
696 
697  int i_min = i.min();
698  int i_max = i.max();
699  ++i;
700 
701  if ((i_min <= dom.min()) && (i_max >= dom.max()))
702  return fail(home);
703 
704  if ((i_min > dom.min()) && (i_max >= dom.max()))
705  return lq(home,i_min-1);
706 
707  if ((i_min <= dom.min()) && (i_max < dom.max()) &&
708  (!i() || (i.min() > dom.max())))
709  return gq(home,i_max+1);
710 
711  // Set up two sentinel elements
712  RangeList f, l;
713  // Put all ranges between sentinels
714  if (range()) {
715  // Create a new rangelist just for simplicity
716  RangeList* n = new (home) RangeList(min(),max(),&f,&l);
717  f.prevnext(NULL,n); l.prevnext(n,NULL);
718  } else {
719  // Link the two sentinel elements
720  f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
721  fst()->prev(NULL,&f); lst()->next(NULL,&l);
722  }
723 
724  // Number of values removed (potential holes)
725  unsigned int h = 0;
726  // The previous range
727  RangeList* p = &f;
728  // The current range
729  RangeList* r = f.next(NULL);
730 
731  while (true) {
732  assert((r != &f) && (r != &l));
733  if (i_min > r->max()) {
734  RangeList* n=r->next(p); p=r; r=n;
735  if (r == &l)
736  break;
737  } else if (i_max < r->min()) {
738  if (!i())
739  break;
740  i_min = i.min();
741  i_max = i.max();
742  ++i;
743  } else if ((i_min <= r->min()) && (r->max() <= i_max)) {
744  // r is included in i: remove entire range r
745  h += r->width();
746  RangeList* n=r->next(p);
747  p->next(r,n); n->prev(r,p);
748  r->dispose(home);
749  r=n;
750  if (r == &l)
751  break;
752  } else if ((i_min > r->min()) && (i_max < r->max())) {
753  // i is included in r: create new range before the current one
754  h += static_cast<unsigned int>(i_max - i_min) + 1;
755  RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r);
756  r->min(i_max+1);
757  p->next(r,n); r->prev(p,n);
758  p=n;
759  if (!i())
760  break;
761  i_min = i.min();
762  i_max = i.max();
763  ++i;
764  } else if (i_max < r->max()) {
765  assert(i_min <= r->min());
766  // i ends before r: adjust minimum of r
767  h += i_max-r->min()+1;
768  r->min(i_max+1);
769  if (!i())
770  break;
771  i_min = i.min();
772  i_max = i.max();
773  ++i;
774  } else {
775  assert((i_max >= r->max()) && (r->min() < i_min));
776  // r ends before i: adjust maximum of r
777  h += r->max()-i_min+1;
778  r->max(i_min-1);
779  RangeList* n=r->next(p); p=r; r=n;
780  if (r == &l)
781  break;
782  }
783  }
784 
785  // New first and last ranges
786  RangeList* fn = f.next(NULL);
787  RangeList* ln = l.prev(NULL);
788 
789  // All ranges pruned?
790  if (fn == &l) {
791  fst(NULL); lst(NULL); holes=0;
792  return fail(home);
793  }
794 
795  ModEvent me;
796  unsigned int b;
797 
798  // Only a single range left?
799  if (fn == ln) {
800  assert(h > 0);
801  dom.min(fn->min()); dom.max(fn->max());
802  fn->dispose(home);
803  fst(NULL); lst(NULL);
804  holes = 0;
805  me = assigned() ? ME_INT_VAL : ME_INT_BND;
806  goto notify;
807  }
808 
809  // The number of removed values
810  holes += h;
811  // Unlink sentinel ranges
812  fn->prev(&f,NULL); ln->next(&l,NULL);
813  // How many values where removed at the bounds
814  b = (static_cast<unsigned int>(fn->min()-dom.min()) +
815  static_cast<unsigned int>(dom.max()-ln->max()));
816  // Set new first and last ranges
817  fst(fn); lst(ln);
818 
819  if (b > 0) {
820  assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
821  dom.min(fn->min()); dom.max(ln->max());
822  holes -= b;
823  me = ME_INT_BND; goto notify;
824  }
825 
826  if (h > 0) {
827  assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
828  me = ME_INT_DOM; goto notify;
829  }
830 
831  return ME_INT_NONE;
832  notify:
833  IntDelta d;
834  return notify(home,me,d);
835  }
836 
837  template<class I>
839  IntVarImp::narrow_v(Space& home, I& i, bool depends) {
841  return narrow_r(home,r,depends);
842  }
843 
844  template<class I>
846  IntVarImp::inter_v(Space& home, I& i, bool depends) {
848  return inter_r(home,r,depends);
849  }
850 
851  template<class I>
853  IntVarImp::minus_v(Space& home, I& i, bool depends) {
854  if (depends) {
856  return minus_r(home, r, true);
857  }
858 
859  // Skip all values that are too small
860  while (i() && (i.val() < dom.min()))
861  ++i;
862 
863  // Is there no value left or all are too large?
864  if (!i() || (i.val() > dom.max()))
865  return ME_INT_NONE;
866 
867  int v = i.val();
868  // Skip values that are the same
869  do {
870  ++i;
871  } while (i() && (i.val() == v));
872 
873  // Is there only a single value to be pruned?
874  if (!i() || (i.val() > dom.max()))
875  return nq_full(home,v);
876 
877  // Set up two sentinel elements
878  RangeList f, l;
879  // Put all ranges between sentinels
880  if (range()) {
881  // Create a new rangelist just for simplicity
882  RangeList* n = new (home) RangeList(min(),max(),&f,&l);
883  f.prevnext(NULL,n); l.prevnext(n,NULL);
884  } else {
885  // Link the two sentinel elements
886  f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
887  fst()->prev(NULL,&f); lst()->next(NULL,&l);
888  }
889 
890  // Number of values removed (potential holes)
891  unsigned int h = 0;
892  // The previous range
893  RangeList* p = &f;
894  // The current range
895  RangeList* r = f.next(NULL);
896 
897  while (true) {
898  assert((r != &f) && (r != &l));
899  if (v > r->max()) {
900  // Move to next range
901  RangeList* n=r->next(p); p=r; r=n;
902  if (r == &l)
903  break;
904  } else {
905  if ((v == r->min()) && (v == r->max())) {
906  // Remove range
907  h++;
908  RangeList* n=r->next(p);
909  p->next(r,n); n->prev(r,p);
910  r->dispose(home);
911  r=n;
912  if (r == &l)
913  break;
914  } else if (v == r->min()) {
915  h++; r->min(v+1);
916  } else if (v == r->max()) {
917  h++; r->max(v-1);
918  RangeList* n=r->next(p); p=r; r=n;
919  if (r == &l)
920  break;
921  } else if (v > r->min()) {
922  // Create new range before the current one
923  assert(v < r->max());
924  h++;
925  RangeList* n = new (home) RangeList(r->min(),v-1,p,r);
926  r->min(v+1);
927  p->next(r,n); r->prev(p,n);
928  p=n;
929  }
930  if (!i())
931  break;
932  // Move to next value
933  v = i.val(); ++i;
934  }
935  }
936  assert((r == &l) || !i());
937 
938  // New first and last ranges
939  RangeList* fn = f.next(NULL);
940  RangeList* ln = l.prev(NULL);
941 
942  // All ranges pruned?
943  if (fn == &l) {
944  fst(NULL); lst(NULL); holes=0;
945  return fail(home);
946  }
947 
948  IntDelta d;
949 
950  // Only a single range left?
951  if (fn == ln) {
952  assert(h > 0);
953  dom.min(fn->min()); dom.max(fn->max());
954  fn->dispose(home);
955  fst(NULL); lst(NULL);
956  holes = 0;
957  if (assigned())
958  return notify(home,ME_INT_VAL,d);
959  else
960  return notify(home,ME_INT_BND,d);
961  }
962 
963  // The number of removed values
964  holes += h;
965  // Unlink sentinel ranges
966  fn->prev(&f,NULL); ln->next(&l,NULL);
967  // How many values where removed at the bounds
968  unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
969  static_cast<unsigned int>(dom.max()-ln->max()));
970  // Set new first and last ranges
971  fst(fn); lst(ln);
972 
973  if (b > 0) {
974  assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
975  dom.min(fn->min()); dom.max(ln->max());
976  holes -= b;
977  return notify(home,ME_INT_BND,d);
978  }
979 
980  if (h > 0) {
981  assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
982  return notify(home,ME_INT_DOM,d);
983  }
984 
985  return ME_INT_NONE;
986  }
987 
988 
989  /*
990  * Copying a variable
991  *
992  */
993 
996  return copied() ? static_cast<IntVarImp*>(forward())
997  : perform_copy(home);
998  }
999 
1000 
1003  return IntVarImpBase::med(me);
1004  }
1005 
1006 }}
1007 
1008 // STATISTICS: int-var
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:412
RangeList * next(const RangeList *p) const
Return next element (from previous p)
Definition: int.hpp:66
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:390
int min(void) const
Return minimum.
Definition: int.hpp:102
int min(void) const
Return minimum of domain.
Definition: int.hpp:228
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:321
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: int.hpp:138
#define GECODE_ASSUME(p)
Assert certain property.
Definition: macros.hpp:118
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:496
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:242
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition: int.hpp:88
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:70
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:479
int min(void) const
Return smallest value of range.
Definition: int.hpp:450
const RangeList * ranges_bwd(void) const
Return range list for backward iteration.
Definition: int.hpp:314
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:253
RangeList * _lst
Link the last element.
Definition: var-imp.hpp:194
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:127
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:290
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:177
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
int ModEvent
Type for modification events.
Definition: core.hpp:64
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:369
IntVarImpFwd(void)
Default constructor.
Definition: int.hpp:431
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4123
#define forceinline
Definition: config.hpp:182
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Computation spaces.
Definition: core.hpp:1668
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:115
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:474
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition: int.hpp:309
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:50
RangeList(void)
Default constructor (noop)
Definition: int.hpp:53
Gecode::IntSet d(v, 7)
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2757
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:236
IntVarImpBwd(void)
Default constructor.
Definition: int.hpp:469
Gecode::FloatVal c(-8, 8)
int _max
Maximum of range.
Definition: var-imp.hpp:111
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:246
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:458
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: int.hpp:272
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: int.hpp:252
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4117
int max(void) const
Return maximum.
Definition: int.hpp:106
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: int.hpp:262
Range iterator for computing intersection (binary)
void operator++(void)
Move iterator to previous range (if possible)
Definition: int.hpp:483
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:121
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
Range iterator from value iterator.
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:167
unsigned int size(I &i)
Size of all ranges of range iterator i.
void range(Home home, const IntVarArgs &x, SetVar y, SetVar z)
Post constraint .
Definition: minimodel.hh:2030
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:396
const Gecode::ModEvent ME_INT_BND
Domain operation has changed the minimum or maximum of the domain.
Definition: var-type.hpp:65
FreeList * _next
Pointer to next freelist object.
Definition: manager.hpp:105
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: int.hpp:110
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:674
Integer sets.
Definition: int.hh:174
#define GECODE_INT_PD2RL(p)
Definition: int.hpp:50
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:204
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:853
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
const int v[7]
Definition: distinct.cpp:263
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:839
Integer delta information for advisors.
Definition: var-imp.hpp:55
struct Gecode::@585::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
int max(void) const
Return largest value of range.
Definition: int.hpp:454
Integer variable implementation.
Definition: var-imp.hpp:93
RangeList dom
Domain information.
Definition: var-imp.hpp:192
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:846
Generic domain change information to be supplied to advisors.
Definition: core.hpp:205
Lists of ranges (intervals)
Definition: var-imp.hpp:106
const Gecode::ModEvent ME_INT_DOM
Domain operation has changed the domain.
Definition: var-type.hpp:72
void operator++(void)
Move iterator to next range (if possible)
Definition: int.hpp:445
IntVarImp * copy(Space &home)
Return copy of this variable.
Definition: int.hpp:995
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
int max(void) const
Return largest value of range.
Definition: int.hpp:492
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition: int.hpp:74
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:682
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4417
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2747
Post propagator for SetVar x
Definition: set.hh:769
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:257
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:134
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: int.hpp:337
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
int min(void) const
Return smallest value of range.
Definition: int.hpp:488
int _min
Minimum of range.
Definition: var-imp.hpp:109
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:436
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:441
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: int.hpp:507
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:60
const Gecode::ModEvent ME_INT_NONE
Domain operation has not changed domain.
Definition: var-type.hpp:54
ModEvent gq(Space &home, int n)
Restrict domain values to be greater or equal than n.
Definition: int.hpp:348
#define GECODE_INT_RL2PD(r)
Definition: int.hpp:49
int max(void) const
Return maximum of domain.
Definition: int.hpp:232