Generated on Sat Jan 12 2019 20:58:51 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  * 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 
38 namespace 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&) {
116  GECODE_NEVER;
117  }
118  forceinline void
119  IntVarImp::RangeList::operator delete(void*, void*) {
120  GECODE_NEVER;
121  }
122 
123  forceinline void*
124  IntVarImp::RangeList::operator new(size_t, Space& home) {
125  return home.fl_alloc<sizeof(RangeList)>();
126  }
127 
128  forceinline void*
129  IntVarImp::RangeList::operator new(size_t, void* p) {
130  return p;
131  }
132 
133  forceinline void
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
242  IntVarImp::assigned(void) const {
243  return dom.min() == dom.max();
244  }
245 
246 
247  forceinline unsigned int
248  IntVarImp::width(void) const {
249  return dom.width();
250  }
251 
252  forceinline unsigned int
253  IntVarImp::size(void) const {
254  return dom.width() - holes;
255  }
256 
257  forceinline unsigned int
258  IntVarImp::regret_min(void) const {
259  if (fst() == 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
268  IntVarImp::regret_max(void) const {
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 
305  IntVarImp::ranges_fwd(void) const {
306  return (fst() == NULL) ? &dom : fst();
307  }
308 
310  IntVarImp::ranges_bwd(void) const {
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);
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, long long int n) {
355  if (n <= dom.min()) return ME_INT_NONE;
356  if (n > dom.max()) return fail(home);
357  ModEvent me = gq_full(home,static_cast<int>(n));
358  GECODE_ASSUME((me == ME_INT_FAILED) |
359  (me == ME_INT_VAL) |
360  (me == ME_INT_BND));
361  return me;
362  }
363 
365  IntVarImp::lq(Space& home, int n) {
366  if (n >= dom.max()) return ME_INT_NONE;
367  if (n < dom.min()) return fail(home);
368  ModEvent me = lq_full(home,n);
369  GECODE_ASSUME((me == ME_INT_FAILED) |
370  (me == ME_INT_VAL) |
371  (me == ME_INT_BND));
372  return me;
373  }
375  IntVarImp::lq(Space& home, long long int n) {
376  if (n >= dom.max()) return ME_INT_NONE;
377  if (n < dom.min()) return fail(home);
378  ModEvent me = lq_full(home,static_cast<int>(n));
379  GECODE_ASSUME((me == ME_INT_FAILED) |
380  (me == ME_INT_VAL) |
381  (me == ME_INT_BND));
382  return me;
383  }
384 
386  IntVarImp::eq(Space& home, int n) {
387  if ((n < dom.min()) || (n > dom.max()))
388  return fail(home);
389  if ((n == dom.min()) && (n == dom.max()))
390  return ME_INT_NONE;
391  ModEvent me = eq_full(home,n);
392  GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
393  return me;
394  }
396  IntVarImp::eq(Space& home, long long int m) {
397  if ((m < dom.min()) || (m > dom.max()))
398  return fail(home);
399  int n = static_cast<int>(m);
400  if ((n == dom.min()) && (n == dom.max()))
401  return ME_INT_NONE;
402  ModEvent me = eq_full(home,n);
403  GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
404  return me;
405  }
406 
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
454  IntVarImpFwd::width(void) const {
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
492  IntVarImpBwd::width(void) const {
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;
801  me = assigned() ? ME_INT_VAL : ME_INT_BND;
802  goto notify;
803  }
804 
805  // The number of removed values
806  holes += h;
807  // Unlink sentinel ranges
808  fn->prev(&f,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
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:408
RangeList * next(const RangeList *p) const
Return next element (from previous p)
Definition: int.hpp:62
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:386
int min(void) const
Return minimum.
Definition: int.hpp:98
int min(void) const
Return minimum of domain.
Definition: int.hpp:224
IntVarImp(Space &home, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:317
NNF * l
Left subtree.
Definition: bool-expr.cpp:240
void dispose(Space &home, RangeList *p, RangeList *l)
Free memory for all elements between this and l (inclusive)
Definition: int.hpp:134
#define GECODE_ASSUME(p)
Assert certain property.
Definition: macros.hpp:114
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:492
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:238
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition: int.hpp:84
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:66
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:446
const RangeList * ranges_bwd(void) const
Return range list for backward iteration.
Definition: int.hpp:310
FreeList * next(void) const
Return next freelist object.
Definition: manager.hpp:249
RangeList * _lst
Link the last element.
Definition: var-imp.hpp:190
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:161
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:286
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:173
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:40
int ModEvent
Type for modification events.
Definition: core.hpp:62
ModEvent lq(Space &home, int n)
Restrict domain values to be less or equal than n.
Definition: int.hpp:365
IntVarImpFwd(void)
Default constructor.
Definition: int.hpp:427
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Definition: core.hpp:4203
#define forceinline
Definition: config.hpp:185
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Computation spaces.
Definition: core.hpp:1701
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:149
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:470
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition: int.hpp:305
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:46
RangeList(void)
Default constructor (noop)
Definition: int.hpp:49
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:2794
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:232
IntVarImpBwd(void)
Default constructor.
Definition: int.hpp:465
Gecode::FloatVal c(-8, 8)
int _max
Maximum of range.
Definition: var-imp.hpp:107
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:242
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:454
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: int.hpp:268
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: int.hpp:248
Gecode::IntArgs i({1, 2, 3, 4})
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Definition: core.hpp:4197
int max(void) const
Return maximum.
Definition: int.hpp:102
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: int.hpp:258
Range iterator for computing intersection (binary)
void operator++(void)
Move iterator to previous range (if possible)
Definition: int.hpp:479
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:155
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
Range iterator from value iterator.
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:163
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:2026
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:392
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:101
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: int.hpp:106
ModEvent inter_r(Space &home, I &i, bool depends=true)
Intersect domain with ranges described by i.
Definition: int.hpp:670
Integer sets.
Definition: int.hh:174
#define GECODE_INT_PD2RL(p)
Definition: int.hpp:46
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:200
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:849
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
const int v[7]
Definition: distinct.cpp:259
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:835
Integer delta information for advisors.
Definition: var-imp.hpp:51
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:450
Integer variable implementation.
Definition: var-imp.hpp:89
RangeList dom
Domain information.
Definition: var-imp.hpp:188
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:842
Generic domain change information to be supplied to advisors.
Definition: core.hpp:203
Lists of ranges (intervals)
Definition: var-imp.hpp:102
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:441
IntVarImp * copy(Space &home)
Return copy of this variable.
Definition: int.hpp:991
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
int max(void) const
Return largest value of range.
Definition: int.hpp:488
void prevnext(RangeList *p, RangeList *n)
Set previous element to p and next element to n.
Definition: int.hpp:70
ModEvent minus_r(Space &home, I &i, bool depends=true)
Remove from domain the ranges described by i.
Definition: int.hpp:678
ModEvent fail(Space &home)
Run advisors to be run on failure and returns ME_GEN_FAILED.
Definition: core.hpp:4497
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2784
Post propagator for SetVar x
Definition: set.hh:767
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:253
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:168
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: int.hpp:333
Gecode toplevel namespace
Range iterator for computing set difference.
Definition: ranges-diff.hpp:43
int min(void) const
Return smallest value of range.
Definition: int.hpp:484
int _min
Minimum of range.
Definition: var-imp.hpp:105
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:437
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: int.hpp:503
#define GECODE_NEVER
Assert that this command is never executed.
Definition: macros.hpp:56
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:344
#define GECODE_INT_RL2PD(r)
Definition: int.hpp:45
int max(void) const
Return maximum of domain.
Definition: int.hpp:228