00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 namespace Gecode { namespace Int {
00043
00044
00045
00046
00047
00048
00049 #define GECODE_INT_RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
00050 #define GECODE_INT_PD2RL(p) reinterpret_cast<RangeList*>(p)
00051
00052 forceinline
00053 IntVarImp::RangeList::RangeList(void) {}
00054
00055 forceinline
00056 IntVarImp::RangeList::RangeList(int min, int max)
00057 : _min(min), _max(max) {}
00058
00059 forceinline
00060 IntVarImp::RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
00061 : _min(min), _max(max) {
00062 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
00063 }
00064
00065 forceinline IntVarImp::RangeList*
00066 IntVarImp::RangeList::next(const RangeList* p) const {
00067 return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(p));
00068 }
00069 forceinline IntVarImp::RangeList*
00070 IntVarImp::RangeList::prev(const RangeList* n) const {
00071 return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(n));
00072 }
00073 forceinline void
00074 IntVarImp::RangeList::prevnext(RangeList* p, RangeList* n) {
00075 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
00076 }
00077 forceinline void
00078 IntVarImp::RangeList::next(RangeList* o, RangeList* n) {
00079 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
00080 (GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
00081 }
00082 forceinline void
00083 IntVarImp::RangeList::prev(RangeList* o, RangeList* n) {
00084 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
00085 (GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
00086 }
00087 forceinline void
00088 IntVarImp::RangeList::fix(RangeList* n) {
00089 _next = n;
00090 }
00091
00092 forceinline void
00093 IntVarImp::RangeList::min(int n) {
00094 _min = n;
00095 }
00096 forceinline void
00097 IntVarImp::RangeList::max(int n) {
00098 _max = n;
00099 }
00100
00101 forceinline int
00102 IntVarImp::RangeList::min(void) const {
00103 return _min;
00104 }
00105 forceinline int
00106 IntVarImp::RangeList::max(void) const {
00107 return _max;
00108 }
00109 forceinline unsigned int
00110 IntVarImp::RangeList::width(void) const {
00111 return static_cast<unsigned int>(_max - _min) + 1;
00112 }
00113
00114
00115 forceinline void
00116 IntVarImp::RangeList::operator delete(void*) {}
00117
00118 forceinline void
00119 IntVarImp::RangeList::operator delete(void*, Space&) {
00120 GECODE_NEVER;
00121 }
00122 forceinline void
00123 IntVarImp::RangeList::operator delete(void*, void*) {
00124 GECODE_NEVER;
00125 }
00126
00127 forceinline void*
00128 IntVarImp::RangeList::operator new(size_t, Space& home) {
00129 return home.fl_alloc<sizeof(RangeList)>();
00130 }
00131
00132 forceinline void*
00133 IntVarImp::RangeList::operator new(size_t, void* p) {
00134 return p;
00135 }
00136
00137 forceinline void
00138 IntVarImp::RangeList::dispose(Space& home, RangeList* p, RangeList* l) {
00139 RangeList* c = this;
00140 while (c != l) {
00141 RangeList* n = c->next(p);
00142 c->fix(n);
00143 p=c; c=n;
00144 }
00145 home.fl_dispose<sizeof(RangeList)>(this,l);
00146 }
00147
00148 forceinline void
00149 IntVarImp::RangeList::dispose(Space& home, RangeList* l) {
00150 home.fl_dispose<sizeof(RangeList)>(this,l);
00151 }
00152
00153 forceinline void
00154 IntVarImp::RangeList::dispose(Space& home) {
00155 home.fl_dispose<sizeof(RangeList)>(this,this);
00156 }
00157
00158 #undef GECODE_INT_RL2PD
00159 #undef GECODE_INT_PD2RL
00160
00161
00162
00163
00164
00165
00166 forceinline IntVarImp::RangeList*
00167 IntVarImp::fst(void) const {
00168 return dom.next(NULL);
00169 }
00170
00171 forceinline void
00172 IntVarImp::fst(IntVarImp::RangeList* f) {
00173 dom.prevnext(NULL,f);
00174 }
00175
00176 forceinline IntVarImp::RangeList*
00177 IntVarImp::lst(void) const {
00178 return _lst;
00179 }
00180
00181 forceinline void
00182 IntVarImp::lst(IntVarImp::RangeList* l) {
00183 _lst = l;
00184 }
00185
00186
00187
00188
00189
00190
00191 forceinline
00192 IntVarImp::IntVarImp(Space& home, int min, int max)
00193 : IntVarImpBase(home), dom(min,max,NULL,NULL), holes(0) {}
00194
00195 forceinline
00196 IntVarImp::IntVarImp(Space& home, const IntSet& d)
00197 : IntVarImpBase(home), dom(d.min(),d.max()) {
00198 if (d.ranges() > 1) {
00199 int n = d.ranges();
00200 assert(n >= 2);
00201 RangeList* r = home.alloc<RangeList>(n);
00202 fst(r); lst(r+n-1);
00203 unsigned int h = static_cast<unsigned int>(d.max()-d.min())+1;
00204 h -= d.width(0);
00205 r[0].min(d.min(0)); r[0].max(d.max(0));
00206 r[0].prevnext(NULL,&r[1]);
00207 for (int i = 1; i < n-1; i++) {
00208 h -= d.width(i);
00209 r[i].min(d.min(i)); r[i].max(d.max(i));
00210 r[i].prevnext(&r[i-1],&r[i+1]);
00211 }
00212 h -= d.width(n-1);
00213 r[n-1].min(d.min(n-1)); r[n-1].max(d.max(n-1));
00214 r[n-1].prevnext(&r[n-2],NULL);
00215 holes = h;
00216 } else {
00217 fst(NULL); holes = 0;
00218 }
00219 }
00220
00221
00222
00223
00224
00225
00226
00227 forceinline int
00228 IntVarImp::min(void) const {
00229 return dom.min();
00230 }
00231 forceinline int
00232 IntVarImp::max(void) const {
00233 return dom.max();
00234 }
00235 forceinline int
00236 IntVarImp::val(void) const {
00237 assert(dom.min() == dom.max());
00238 return dom.min();
00239 }
00240
00241 forceinline bool
00242 IntVarImp::range(void) const {
00243 return fst() == NULL;
00244 }
00245 forceinline bool
00246 IntVarImp::assigned(void) const {
00247 return dom.min() == dom.max();
00248 }
00249
00250
00251 forceinline unsigned int
00252 IntVarImp::width(void) const {
00253 return dom.width();
00254 }
00255
00256 forceinline unsigned int
00257 IntVarImp::size(void) const {
00258 return dom.width() - holes;
00259 }
00260
00261 forceinline unsigned int
00262 IntVarImp::regret_min(void) const {
00263 if (fst() == NULL) {
00264 return (dom.min() == dom.max()) ? 0U : 1U;
00265 } else if (dom.min() == fst()->max()) {
00266 return static_cast<unsigned int>(fst()->next(NULL)->min()-dom.min());
00267 } else {
00268 return 1U;
00269 }
00270 }
00271 forceinline unsigned int
00272 IntVarImp::regret_max(void) const {
00273 if (fst() == NULL) {
00274 return (dom.min() == dom.max()) ? 0U : 1U;
00275 } else if (dom.max() == lst()->min()) {
00276 return static_cast<unsigned int>(dom.max()-lst()->prev(NULL)->max());
00277 } else {
00278 return 1U;
00279 }
00280 }
00281
00282
00283
00284
00285
00286
00287
00288
00289 forceinline bool
00290 IntVarImp::in(int n) const {
00291 if ((n < dom.min()) || (n > dom.max()))
00292 return false;
00293 return (fst() == NULL) || in_full(n);
00294 }
00295 forceinline bool
00296 IntVarImp::in(double n) const {
00297 if ((n < dom.min()) || (n > dom.max()))
00298 return false;
00299 return (fst() == NULL) || in_full(static_cast<int>(n));
00300 }
00301
00302
00303
00304
00305
00306
00307
00308 forceinline const IntVarImp::RangeList*
00309 IntVarImp::ranges_fwd(void) const {
00310 return (fst() == NULL) ? &dom : fst();
00311 }
00312
00313 forceinline const IntVarImp::RangeList*
00314 IntVarImp::ranges_bwd(void) const {
00315 return (fst() == NULL) ? &dom : lst();
00316 }
00317
00318
00319
00320
00321
00322
00323
00324 forceinline ModEvent
00325 IntVarImp::modevent(const Delta& d) {
00326 return d.modevent();
00327 }
00328 forceinline int
00329 IntVarImp::min(const Delta& d) {
00330 return static_cast<const IntDelta&>(d).min();
00331 }
00332 forceinline int
00333 IntVarImp::max(const Delta& d) {
00334 return static_cast<const IntDelta&>(d).max();
00335 }
00336 forceinline bool
00337 IntVarImp::any(const Delta& d) {
00338 return static_cast<const IntDelta&>(d).any();
00339 }
00340
00341
00342
00343
00344
00345
00346
00347 forceinline ModEvent
00348 IntVarImp::gq(Space& home, int n) {
00349 if (n <= dom.min()) return ME_INT_NONE;
00350 if (n > dom.max()) return ME_INT_FAILED;
00351 ModEvent me = gq_full(home,n);
00352 GECODE_ASSUME((me == ME_INT_FAILED) |
00353 (me == ME_INT_VAL) |
00354 (me == ME_INT_BND));
00355 return me;
00356 }
00357 forceinline ModEvent
00358 IntVarImp::gq(Space& home, double n) {
00359 if (n <= dom.min()) return ME_INT_NONE;
00360 if (n > dom.max()) return ME_INT_FAILED;
00361 ModEvent me = gq_full(home,static_cast<int>(n));
00362 GECODE_ASSUME((me == ME_INT_FAILED) |
00363 (me == ME_INT_VAL) |
00364 (me == ME_INT_BND));
00365 return me;
00366 }
00367
00368
00369 forceinline ModEvent
00370 IntVarImp::lq(Space& home, int n) {
00371 if (n >= dom.max()) return ME_INT_NONE;
00372 if (n < dom.min()) return ME_INT_FAILED;
00373 ModEvent me = lq_full(home,n);
00374 GECODE_ASSUME((me == ME_INT_FAILED) |
00375 (me == ME_INT_VAL) |
00376 (me == ME_INT_BND));
00377 return me;
00378 }
00379 forceinline ModEvent
00380 IntVarImp::lq(Space& home, double n) {
00381 if (n >= dom.max()) return ME_INT_NONE;
00382 if (n < dom.min()) return ME_INT_FAILED;
00383 ModEvent me = lq_full(home,static_cast<int>(n));
00384 GECODE_ASSUME((me == ME_INT_FAILED) |
00385 (me == ME_INT_VAL) |
00386 (me == ME_INT_BND));
00387 return me;
00388 }
00389
00390
00391 forceinline ModEvent
00392 IntVarImp::eq(Space& home, int n) {
00393 if ((n < dom.min()) || (n > dom.max()))
00394 return ME_INT_FAILED;
00395 if ((n == dom.min()) && (n == dom.max()))
00396 return ME_INT_NONE;
00397 ModEvent me = eq_full(home,n);
00398 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
00399 return me;
00400 }
00401 forceinline ModEvent
00402 IntVarImp::eq(Space& home, double m) {
00403 if ((m < dom.min()) || (m > dom.max()))
00404 return ME_INT_FAILED;
00405 int n = static_cast<int>(m);
00406 if ((n == dom.min()) && (n == dom.max()))
00407 return ME_INT_NONE;
00408 ModEvent me = eq_full(home,n);
00409 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
00410 return me;
00411 }
00412
00413
00414 forceinline ModEvent
00415 IntVarImp::nq(Space& home, int n) {
00416 if ((n < dom.min()) || (n > dom.max()))
00417 return ME_INT_NONE;
00418 return nq_full(home,n);
00419 }
00420 forceinline ModEvent
00421 IntVarImp::nq(Space& home, double d) {
00422 if ((d < dom.min()) || (d > dom.max()))
00423 return ME_INT_NONE;
00424 return nq_full(home,static_cast<int>(d));
00425 }
00426
00427
00428
00429
00430
00431
00432
00433 forceinline
00434 IntVarImpFwd::IntVarImpFwd(void) {}
00435 forceinline
00436 IntVarImpFwd::IntVarImpFwd(const IntVarImp* x)
00437 : p(NULL), c(x->ranges_fwd()) {}
00438 forceinline void
00439 IntVarImpFwd::init(const IntVarImp* x) {
00440 p=NULL; c=x->ranges_fwd();
00441 }
00442
00443 forceinline bool
00444 IntVarImpFwd::operator ()(void) const {
00445 return c != NULL;
00446 }
00447 forceinline void
00448 IntVarImpFwd::operator ++(void) {
00449 const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
00450 }
00451
00452 forceinline int
00453 IntVarImpFwd::min(void) const {
00454 return c->min();
00455 }
00456 forceinline int
00457 IntVarImpFwd::max(void) const {
00458 return c->max();
00459 }
00460 forceinline unsigned int
00461 IntVarImpFwd::width(void) const {
00462 return c->width();
00463 }
00464
00465
00466
00467
00468
00469
00470
00471 forceinline
00472 IntVarImpBwd::IntVarImpBwd(void) {}
00473 forceinline
00474 IntVarImpBwd::IntVarImpBwd(const IntVarImp* x)
00475 : n(NULL), c(x->ranges_bwd()) {}
00476 forceinline void
00477 IntVarImpBwd::init(const IntVarImp* x) {
00478 n=NULL; c=x->ranges_bwd();
00479 }
00480
00481 forceinline bool
00482 IntVarImpBwd::operator ()(void) const {
00483 return c != NULL;
00484 }
00485 forceinline void
00486 IntVarImpBwd::operator ++(void) {
00487 const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
00488 }
00489
00490 forceinline int
00491 IntVarImpBwd::min(void) const {
00492 return c->min();
00493 }
00494 forceinline int
00495 IntVarImpBwd::max(void) const {
00496 return c->max();
00497 }
00498 forceinline unsigned int
00499 IntVarImpBwd::width(void) const {
00500 return c->width();
00501 }
00502
00503
00504
00505
00506
00507
00508 template<class I>
00509 forceinline ModEvent
00510 IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
00511 Iter::Ranges::IsRangeIter<I>();
00512
00513 if (!ri())
00514 return ME_INT_FAILED;
00515
00516 int min0 = ri.min();
00517 int max0 = ri.max();
00518 ++ri;
00519
00520 ModEvent me;
00521
00522
00523 if (!ri()) {
00524
00525
00526 if (fst()) {
00527 fst()->dispose(home,NULL,lst());
00528 fst(NULL); holes = 0;
00529 }
00530 const int min1 = dom.min(); dom.min(min0);
00531 const int max1 = dom.max(); dom.max(max0);
00532 if ((min0 == min1) && (max0 == max1))
00533 return ME_INT_NONE;
00534 me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND;
00535 goto notify;
00536 }
00537
00538 if (depends || range()) {
00539
00540 RangeList* f = new (home) RangeList(min0,max0,NULL,NULL);
00541 RangeList* l = f;
00542 unsigned int s = static_cast<unsigned int>(max0-min0+1);
00543 do {
00544 RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
00545 l->next(NULL,n);
00546 l = n;
00547 s += ri.width();
00548 ++ri;
00549 } while (ri());
00550 if (fst() != NULL)
00551 fst()->dispose(home,NULL,lst());
00552 fst(f); lst(l);
00553
00554
00555 if (size() == s)
00556 return ME_INT_NONE;
00557
00558 const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
00559 const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
00560 holes = width() - s;
00561
00562 me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND;
00563 goto notify;
00564 } else {
00565
00566 RangeList f, l;
00567
00568 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00569 fst()->prev(NULL,&f); lst()->next(NULL,&l);
00570
00571
00572 unsigned int h = 0;
00573
00574 RangeList* p = &f;
00575
00576 RangeList* r = f.next(NULL);
00577
00578 while (true) {
00579 assert((r != &f) && (r != &l));
00580 if (r->max() < min0) {
00581
00582 h += r->width();
00583 RangeList* n=r->next(p);
00584 p->next(r,n); n->prev(r,p);
00585 r->dispose(home);
00586 r=n;
00587 if (r == &l)
00588 goto done;
00589 } else if ((r->min() == min0) && (r->max() == max0)) {
00590
00591 RangeList* n=r->next(p); p=r; r=n;
00592 if (r == &l)
00593 goto done;
00594 if (!ri())
00595 goto done;
00596 min0=ri.min(); max0=ri.max(); ++ri;
00597 } else {
00598
00599 assert((r->min() <= min0) && (max0 <= r->max()));
00600 h += r->width();
00601 int end = r->max();
00602
00603 r->min(min0); r->max(max0);
00604 assert(h > r->width());
00605 h -= r->width();
00606 {
00607 RangeList* n=r->next(p); p=r; r=n;
00608 }
00609 while (true) {
00610 if (!ri())
00611 goto done;
00612 min0=ri.min(); max0=ri.max(); ++ri;
00613 if (max0 > end)
00614 break;
00615 assert(h > static_cast<unsigned int>(max0-min0+1));
00616 h -= max0-min0+1;
00617 RangeList* n = new (home) RangeList(min0,max0,p,r);
00618 p->next(r,n); r->prev(p,n);
00619 p=n;
00620 }
00621 if (r == &l)
00622 goto done;
00623 }
00624 }
00625 done:
00626
00627
00628 while (r != &l) {
00629 h += r->width();
00630 RangeList* n=r->next(p);
00631 p->next(r,n); n->prev(r,p);
00632 r->dispose(home);
00633 r=n;
00634 }
00635
00636 assert((r == &l) && !ri());
00637
00638
00639 RangeList* fn = f.next(NULL);
00640 RangeList* ln = l.prev(NULL);
00641
00642
00643 assert(fn != &l);
00644
00645
00646 assert(fn != ln);
00647
00648
00649 holes += h;
00650
00651 fn->prev(&f,NULL); ln->next(&l,NULL);
00652
00653 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00654 static_cast<unsigned int>(dom.max()-ln->max()));
00655
00656 fst(fn); lst(ln);
00657
00658 if (b > 0) {
00659 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00660 dom.min(fn->min()); dom.max(ln->max());
00661 holes -= b;
00662 me = ME_INT_BND; goto notify;
00663 }
00664
00665 if (h > 0) {
00666 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00667 me = ME_INT_DOM; goto notify;
00668 }
00669 return ME_INT_NONE;
00670 }
00671 notify:
00672 IntDelta d;
00673 return notify(home,me,d);
00674 }
00675
00676 template<class I>
00677 forceinline ModEvent
00678 IntVarImp::inter_r(Space& home, I& i, bool) {
00679 Iter::Ranges::IsRangeIter<I>();
00680 IntVarImpFwd j(this);
00681 Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
00682 return narrow_r(home,ij,true);
00683 }
00684
00685 template<class I>
00686 forceinline ModEvent
00687 IntVarImp::minus_r(Space& home, I& i, bool depends) {
00688 Iter::Ranges::IsRangeIter<I>();
00689 if (depends) {
00690 IntVarImpFwd j(this);
00691 Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
00692 return narrow_r(home,ij,true);
00693 }
00694
00695
00696 while (i() && (i.max() < dom.min()))
00697 ++i;
00698
00699
00700 if (!i() || (i.min() > dom.max()))
00701 return ME_INT_NONE;
00702
00703 int i_min = i.min();
00704 int i_max = i.max();
00705 ++i;
00706
00707 if ((i_min <= dom.min()) && (i_max >= dom.max()))
00708 return ME_INT_FAILED;
00709
00710 if ((i_min > dom.min()) && (i_max >= dom.max()))
00711 return lq(home,i_min-1);
00712
00713 if ((i_min <= dom.min()) && (i_max < dom.max()) &&
00714 (!i() || (i.min() > dom.max())))
00715 return gq(home,i_max+1);
00716
00717
00718 RangeList f, l;
00719
00720 if (range()) {
00721
00722 RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00723 f.prevnext(NULL,n); l.prevnext(n,NULL);
00724 } else {
00725
00726 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00727 fst()->prev(NULL,&f); lst()->next(NULL,&l);
00728 }
00729
00730
00731 unsigned int h = 0;
00732
00733 RangeList* p = &f;
00734
00735 RangeList* r = f.next(NULL);
00736
00737 while (true) {
00738 assert((r != &f) && (r != &l));
00739 if (i_min > r->max()) {
00740 RangeList* n=r->next(p); p=r; r=n;
00741 if (r == &l)
00742 break;
00743 } else if (i_max < r->min()) {
00744 if (!i())
00745 break;
00746 i_min = i.min();
00747 i_max = i.max();
00748 ++i;
00749 } else if ((i_min <= r->min()) && (r->max() <= i_max)) {
00750
00751 h += r->width();
00752 RangeList* n=r->next(p);
00753 p->next(r,n); n->prev(r,p);
00754 r->dispose(home);
00755 r=n;
00756 if (r == &l)
00757 break;
00758 } else if ((i_min > r->min()) && (i_max < r->max())) {
00759
00760 h += static_cast<unsigned int>(i_max - i_min) + 1;
00761 RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r);
00762 r->min(i_max+1);
00763 p->next(r,n); r->prev(p,n);
00764 p=n;
00765 if (!i())
00766 break;
00767 i_min = i.min();
00768 i_max = i.max();
00769 ++i;
00770 } else if (i_max < r->max()) {
00771 assert(i_min <= r->min());
00772
00773 h += i_max-r->min()+1;
00774 r->min(i_max+1);
00775 if (!i())
00776 break;
00777 i_min = i.min();
00778 i_max = i.max();
00779 ++i;
00780 } else {
00781 assert((i_max >= r->max()) && (r->min() < i_min));
00782
00783 h += r->max()-i_min+1;
00784 r->max(i_min-1);
00785 RangeList* n=r->next(p); p=r; r=n;
00786 if (r == &l)
00787 break;
00788 }
00789 }
00790
00791
00792 RangeList* fn = f.next(NULL);
00793 RangeList* ln = l.prev(NULL);
00794
00795
00796 if (fn == &l) {
00797 fst(NULL); lst(NULL); holes=0;
00798 return ME_INT_FAILED;
00799 }
00800
00801 ModEvent me;
00802 unsigned int b;
00803
00804
00805 if (fn == ln) {
00806 assert(h > 0);
00807 dom.min(fn->min()); dom.max(fn->max());
00808 fn->dispose(home);
00809 fst(NULL); lst(NULL);
00810 holes = 0;
00811 me = assigned() ? ME_INT_VAL : ME_INT_BND;
00812 goto notify;
00813 }
00814
00815
00816 holes += h;
00817
00818 fn->prev(&f,NULL); ln->next(&l,NULL);
00819
00820 b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00821 static_cast<unsigned int>(dom.max()-ln->max()));
00822
00823 fst(fn); lst(ln);
00824
00825 if (b > 0) {
00826 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00827 dom.min(fn->min()); dom.max(ln->max());
00828 holes -= b;
00829 me = ME_INT_BND; goto notify;
00830 }
00831
00832 if (h > 0) {
00833 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00834 me = ME_INT_DOM; goto notify;
00835 }
00836
00837 return ME_INT_NONE;
00838 notify:
00839 IntDelta d;
00840 return notify(home,me,d);
00841 }
00842
00843 template<class I>
00844 forceinline ModEvent
00845 IntVarImp::narrow_v(Space& home, I& i, bool depends) {
00846 Iter::Values::IsValueIter<I>();
00847 Iter::Values::ToRanges<I> r(i);
00848 return narrow_r(home,r,depends);
00849 }
00850
00851 template<class I>
00852 forceinline ModEvent
00853 IntVarImp::inter_v(Space& home, I& i, bool depends) {
00854 Iter::Values::IsValueIter<I>();
00855 Iter::Values::ToRanges<I> r(i);
00856 return inter_r(home,r,depends);
00857 }
00858
00859 template<class I>
00860 forceinline ModEvent
00861 IntVarImp::minus_v(Space& home, I& i, bool depends) {
00862 Iter::Values::IsValueIter<I>();
00863 if (depends) {
00864 Iter::Values::ToRanges<I> r(i);
00865 return minus_r(home, r, true);
00866 }
00867
00868
00869 while (i() && (i.val() < dom.min()))
00870 ++i;
00871
00872
00873 if (!i() || (i.val() > dom.max()))
00874 return ME_INT_NONE;
00875
00876 int v = i.val();
00877
00878 do {
00879 ++i;
00880 } while (i() && (i.val() == v));
00881
00882
00883 if (!i() || (i.val() > dom.max()))
00884 return nq_full(home,v);
00885
00886
00887 RangeList f, l;
00888
00889 if (range()) {
00890
00891 RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00892 f.prevnext(NULL,n); l.prevnext(n,NULL);
00893 } else {
00894
00895 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00896 fst()->prev(NULL,&f); lst()->next(NULL,&l);
00897 }
00898
00899
00900 unsigned int h = 0;
00901
00902 RangeList* p = &f;
00903
00904 RangeList* r = f.next(NULL);
00905
00906 while (true) {
00907 assert((r != &f) && (r != &l));
00908 if (v > r->max()) {
00909
00910 RangeList* n=r->next(p); p=r; r=n;
00911 if (r == &l)
00912 break;
00913 } else {
00914 if ((v == r->min()) && (v == r->max())) {
00915
00916 h++;
00917 RangeList* n=r->next(p);
00918 p->next(r,n); n->prev(r,p);
00919 r->dispose(home);
00920 r=n;
00921 if (r == &l)
00922 break;
00923 } else if (v == r->min()) {
00924 h++; r->min(v+1);
00925 } else if (v == r->max()) {
00926 h++; r->max(v-1);
00927 RangeList* n=r->next(p); p=r; r=n;
00928 if (r == &l)
00929 break;
00930 } else if (v > r->min()) {
00931
00932 assert(v < r->max());
00933 h++;
00934 RangeList* n = new (home) RangeList(r->min(),v-1,p,r);
00935 r->min(v+1);
00936 p->next(r,n); r->prev(p,n);
00937 p=n;
00938 }
00939 if (!i())
00940 break;
00941
00942 v = i.val(); ++i;
00943 }
00944 }
00945 assert((r == &l) || !i());
00946
00947
00948 RangeList* fn = f.next(NULL);
00949 RangeList* ln = l.prev(NULL);
00950
00951
00952 if (fn == &l) {
00953 fst(NULL); lst(NULL); holes=0;
00954 return ME_INT_FAILED;
00955 }
00956
00957 IntDelta d;
00958
00959
00960 if (fn == ln) {
00961 assert(h > 0);
00962 dom.min(fn->min()); dom.max(fn->max());
00963 fn->dispose(home);
00964 fst(NULL); lst(NULL);
00965 holes = 0;
00966 if (assigned())
00967 return notify(home,ME_INT_VAL,d);
00968 else
00969 return notify(home,ME_INT_BND,d);
00970 }
00971
00972
00973 holes += h;
00974
00975 fn->prev(&f,NULL); ln->next(&l,NULL);
00976
00977 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00978 static_cast<unsigned int>(dom.max()-ln->max()));
00979
00980 fst(fn); lst(ln);
00981
00982 if (b > 0) {
00983 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00984 dom.min(fn->min()); dom.max(ln->max());
00985 holes -= b;
00986 return notify(home,ME_INT_BND,d);
00987 }
00988
00989 if (h > 0) {
00990 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00991 return notify(home,ME_INT_DOM,d);
00992 }
00993
00994 return ME_INT_NONE;
00995 }
00996
00997
00998
00999
01000
01001
01002
01003 forceinline IntVarImp*
01004 IntVarImp::copy(Space& home, bool share) {
01005 return copied() ? static_cast<IntVarImp*>(forward())
01006 : perform_copy(home,share);
01007 }
01008
01009
01010
01011
01012
01013
01014 forceinline void
01015 IntVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool process) {
01016 IntVarImpBase::subscribe(home,p,pc,dom.min()==dom.max(),process);
01017 }
01018 forceinline void
01019 IntVarImp::cancel(Space& home, Propagator& p, PropCond pc) {
01020 IntVarImpBase::cancel(home,p,pc,dom.min()==dom.max());
01021 }
01022
01023 forceinline void
01024 IntVarImp::subscribe(Space& home, Advisor& a) {
01025 IntVarImpBase::subscribe(home,a,dom.min()==dom.max());
01026 }
01027 forceinline void
01028 IntVarImp::cancel(Space& home, Advisor& a) {
01029 IntVarImpBase::cancel(home,a,dom.min()==dom.max());
01030 }
01031
01032 forceinline ModEventDelta
01033 IntVarImp::med(ModEvent me) {
01034 return IntVarImpBase::med(me);
01035 }
01036
01037 }}
01038
01039