Generated on Sat Feb 7 2015 02:01:22 for Gecode by doxygen 1.8.9.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: 2013-02-14 16:29:11 +0100 (Thu, 14 Feb 2013) $ by $Author: schulte $
15  * $Revision: 13292 $
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(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 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, long long int 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 
365  IntVarImp::lq(Space& home, int n) {
366  if (n >= dom.max()) return ME_INT_NONE;
367  if (n < dom.min()) return ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 ME_INT_FAILED;
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 
991  IntVarImp::copy(Space& home, bool share) {
992  return copied() ? static_cast<IntVarImp*>(forward())
993  : perform_copy(home,share);
994  }
995 
996 
997  /*
998  * Dependencies
999  *
1000  */
1001  forceinline void
1002  IntVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) {
1003  IntVarImpBase::subscribe(home,p,pc,dom.min()==dom.max(),schedule);
1004  }
1005  forceinline void
1007  IntVarImpBase::cancel(home,p,pc,dom.min()==dom.max());
1008  }
1009 
1010  forceinline void
1012  IntVarImpBase::subscribe(home,a,dom.min()==dom.max());
1013  }
1014  forceinline void
1016  IntVarImpBase::cancel(home,a,dom.min()==dom.max());
1017  }
1018 
1021  return IntVarImpBase::med(me);
1022  }
1023 
1024 }}
1025 
1026 // STATISTICS: int-var
ModEvent nq(Space &home, int n)
Restrict domain values to be different from n.
Definition: int.hpp:408
ModEvent eq(Space &home, int n)
Restrict domain values to be equal to n.
Definition: int.hpp:386
unsigned int size(void) const
Return size (cardinality) of domain.
Definition: int.hpp:257
NNF * l
Left subtree.
Definition: bool-expr.cpp:244
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc.
Definition: int.hpp:1006
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:99
void fix(RangeList *n)
Restore simple link to next element (so that it becomes a true free list)
Definition: int.hpp:88
int min(void) const
Return minimum.
Definition: int.hpp:102
int min(void) const
Return smallest value of range.
Definition: int.hpp:484
RangeList * _lst
Link the last element.
Definition: var-imp.hpp:192
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:475
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: int.hpp:1002
void dom(Home home, FloatVar x, FloatVal n)
Propagates .
Definition: dom.cpp:44
int ModEvent
Type for modification events.
Definition: core.hpp:146
static void schedule(Space &home, Propagator &p, ModEvent me, bool force=false)
Schedule propagator p with modification event me.
Base-class for propagators.
Definition: core.hpp:755
bool operator()(void) const
Test whether iterator is still at a range or done.
Definition: int.hpp:437
FreeList * next(void) const
Return next freelist object.
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
Base-class for advisors.
Definition: core.hpp:926
static ModEventDelta med(ModEvent me)
Translate modification event me into modification event delta.
Base-class for Int-variable implementations.
Definition: var-imp.hpp:47
Computation spaces.
Definition: core.hpp:1362
RangeList * lst(void) const
Return last element of rangelist.
Definition: int.hpp:177
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:470
Min _min("Int::Min")
void cancel(Space &home)
Cancel all subscriptions when variable implementation is assigned.
RangeList(void)
Default constructor (noop)
Definition: int.hpp:53
Gecode::IntSet d(v, 7)
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:454
T * alloc(long unsigned int n)
Allocate block of n objects of type T from space heap.
Definition: core.hpp:2397
int val(void) const
Return assigned value (only if assigned)
Definition: int.hpp:236
const Gecode::ModEvent ME_INT_FAILED
Domain operation has resulted in failure.
Definition: var-type.hpp:52
IntVarImpBwd(void)
Default constructor.
Definition: int.hpp:465
Gecode::FloatVal c(-8, 8)
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
bool copied(void) const
Is variable already copied.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
bool assigned(void) const
Test whether variable is assigned.
Definition: int.hpp:246
int max(void) const
Return largest value of range.
Definition: int.hpp:450
static ModEvent me(const ModEventDelta &med)
Project modification event for this variable type from med.
Max _max("Int::Max")
Range iterator for computing intersection (binary)
void operator++(void)
Move iterator to previous range (if possible)
Definition: int.hpp:479
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int ranges(void) const
Return number of ranges of the specification.
Definition: int-set-1.hpp:134
bool range(void) const
Test whether domain is a range.
Definition: int.hpp:242
int PropCond
Type for propagation conditions.
Definition: core.hpp:156
const Gecode::ModEvent ME_INT_VAL
Domain operation has resulted in a value (assigned variable)
Definition: var-type.hpp:56
int max(void) const
Return maximum.
Definition: int.hpp:106
Range iterator from value iterator.
unsigned int width(int i) const
Return width of range at position i.
Definition: int-set-1.hpp:127
Range iterator for ranges of integer variable implementation.
Definition: var-imp.hpp:387
int min(void) const
Return smallest value of range.
Definition: int.hpp:446
unsigned int regret_max(void) const
Return regret of domain maximum (distance to next smaller value)
Definition: int.hpp:272
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.
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:208
RangeList * prev(const RangeList *n) const
Return previous element (from next n)
Definition: int.hpp:70
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:171
IntVarImp * copy(Space &home, bool share)
Return copy of this variable.
Definition: int.hpp:991
#define GECODE_INT_PD2RL(p)
Definition: int.hpp:50
unsigned int holes
Size of holes in the domain.
Definition: var-imp.hpp:202
const RangeList * ranges_bwd(void) const
Return range list for backward iteration.
Definition: int.hpp:314
ModEvent minus_v(Space &home, I &i, bool depends=true)
Remove from domain the values described by i.
Definition: int.hpp:849
const int v[7]
Definition: distinct.cpp:207
ModEvent narrow_v(Space &home, I &i, bool depends=true)
Replace domain by values described by i.
Definition: int.hpp:835
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Integer delta information for advisors.
Definition: var-imp.hpp:55
Integer variable implementation.
Definition: var-imp.hpp:91
RangeList dom
Domain information.
Definition: var-imp.hpp:190
IntVarImp(Space &home, bool share, IntVarImp &x)
Constructor for cloning x.
Definition: int.cpp:319
ModEvent inter_v(Space &home, I &i, bool depends=true)
Intersect domain with values described by i.
Definition: int.hpp:842
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Generic domain change information to be supplied to advisors.
Definition: core.hpp:275
Lists of ranges (intervals)
Definition: var-imp.hpp:104
int max(void) const
Return maximum of domain.
Definition: int.hpp:232
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
unsigned int width(void) const
Return width (distance between maximum and minimum)
Definition: int.hpp:110
#define forceinline
Definition: config.hpp:132
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:678
unsigned int width(void) const
Return width of range (distance between minimum and maximum)
Definition: int.hpp:492
void fl_dispose(FreeList *f, FreeList *l)
Return freelist-managed memory to freelist.
Definition: core.hpp:2387
bool in(int n) const
Test whether n is contained in domain.
Definition: int.hpp:290
RangeList * next(const RangeList *p) const
Return next element (from previous p)
Definition: int.hpp:66
int med(void) const
Return median of domain (greatest element not greater than the median)
Definition: int.cpp:50
static bool any(const Delta &d)
Test whether arbitrary values got pruned.
Definition: int.hpp:333
struct Gecode::@518::NNF::@57::@58 b
For binary nodes (and, or, eqv)
Gecode toplevel namespace
const RangeList * ranges_fwd(void) const
Return range list for forward iteration.
Definition: int.hpp:309
Range iterator for computing set difference.
Definition: ranges-diff.hpp:47
int max(void) const
Return largest value of range.
Definition: int.hpp:488
void init(const IntVarImp *x)
Initialize with ranges from variable implementation x.
Definition: int.hpp:432
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
ModEvent narrow_r(Space &home, I &i, bool depends=true)
Replace domain by ranges described by i.
Definition: int.hpp:503
int min(void) const
Return minimum of domain.
Definition: int.hpp:228
#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
RangeList * fst(void) const
Return first element of rangelist.
Definition: int.hpp:167
struct Gecode::@518::NNF::@57::@59 a
For atomic nodes.
unsigned int regret_min(void) const
Return regret of domain minimum (distance to next larger value)
Definition: int.hpp:262
unsigned int width(void) const
Return width of domain (distance between maximum and minimum)
Definition: int.hpp:252
int max(int i) const
Return maximum of range at position i.
Definition: int-set-1.hpp:121
VarImp * forward(void) const
Use forward pointer if variable already copied.
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:49
int min(int i) const
Return minimum of range at position i.
Definition: int-set-1.hpp:115
void subscribe(Gecode::Space &home, Gecode::Propagator &p, Gecode::PropCond pc, bool assigned, bool schedule)
Subscribe propagator p with propagation condition pc.
Definition: var-imp.hpp:199