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(long long int 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 int
00325 IntVarImp::min(const Delta& d) {
00326 return static_cast<const IntDelta&>(d).min();
00327 }
00328 forceinline int
00329 IntVarImp::max(const Delta& d) {
00330 return static_cast<const IntDelta&>(d).max();
00331 }
00332 forceinline bool
00333 IntVarImp::any(const Delta& d) {
00334 return static_cast<const IntDelta&>(d).any();
00335 }
00336
00337
00338
00339
00340
00341
00342
00343 forceinline ModEvent
00344 IntVarImp::gq(Space& home, int n) {
00345 if (n <= dom.min()) return ME_INT_NONE;
00346 if (n > dom.max()) return fail(home);
00347 ModEvent me = gq_full(home,n);
00348 GECODE_ASSUME((me == ME_INT_FAILED) |
00349 (me == ME_INT_VAL) |
00350 (me == ME_INT_BND));
00351 return me;
00352 }
00353 forceinline ModEvent
00354 IntVarImp::gq(Space& home, long long int n) {
00355 if (n <= dom.min()) return ME_INT_NONE;
00356 if (n > dom.max()) return fail(home);
00357 ModEvent me = gq_full(home,static_cast<int>(n));
00358 GECODE_ASSUME((me == ME_INT_FAILED) |
00359 (me == ME_INT_VAL) |
00360 (me == ME_INT_BND));
00361 return me;
00362 }
00363
00364 forceinline ModEvent
00365 IntVarImp::lq(Space& home, int n) {
00366 if (n >= dom.max()) return ME_INT_NONE;
00367 if (n < dom.min()) return fail(home);
00368 ModEvent me = lq_full(home,n);
00369 GECODE_ASSUME((me == ME_INT_FAILED) |
00370 (me == ME_INT_VAL) |
00371 (me == ME_INT_BND));
00372 return me;
00373 }
00374 forceinline ModEvent
00375 IntVarImp::lq(Space& home, long long int n) {
00376 if (n >= dom.max()) return ME_INT_NONE;
00377 if (n < dom.min()) return fail(home);
00378 ModEvent me = lq_full(home,static_cast<int>(n));
00379 GECODE_ASSUME((me == ME_INT_FAILED) |
00380 (me == ME_INT_VAL) |
00381 (me == ME_INT_BND));
00382 return me;
00383 }
00384
00385 forceinline ModEvent
00386 IntVarImp::eq(Space& home, int n) {
00387 if ((n < dom.min()) || (n > dom.max()))
00388 return fail(home);
00389 if ((n == dom.min()) && (n == dom.max()))
00390 return ME_INT_NONE;
00391 ModEvent me = eq_full(home,n);
00392 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
00393 return me;
00394 }
00395 forceinline ModEvent
00396 IntVarImp::eq(Space& home, long long int m) {
00397 if ((m < dom.min()) || (m > dom.max()))
00398 return fail(home);
00399 int n = static_cast<int>(m);
00400 if ((n == dom.min()) && (n == dom.max()))
00401 return ME_INT_NONE;
00402 ModEvent me = eq_full(home,n);
00403 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
00404 return me;
00405 }
00406
00407 forceinline ModEvent
00408 IntVarImp::nq(Space& home, int n) {
00409 if ((n < dom.min()) || (n > dom.max()))
00410 return ME_INT_NONE;
00411 return nq_full(home,n);
00412 }
00413 forceinline ModEvent
00414 IntVarImp::nq(Space& home, long long int d) {
00415 if ((d < dom.min()) || (d > dom.max()))
00416 return ME_INT_NONE;
00417 return nq_full(home,static_cast<int>(d));
00418 }
00419
00420
00421
00422
00423
00424
00425
00426 forceinline
00427 IntVarImpFwd::IntVarImpFwd(void) {}
00428 forceinline
00429 IntVarImpFwd::IntVarImpFwd(const IntVarImp* x)
00430 : p(NULL), c(x->ranges_fwd()) {}
00431 forceinline void
00432 IntVarImpFwd::init(const IntVarImp* x) {
00433 p=NULL; c=x->ranges_fwd();
00434 }
00435
00436 forceinline bool
00437 IntVarImpFwd::operator ()(void) const {
00438 return c != NULL;
00439 }
00440 forceinline void
00441 IntVarImpFwd::operator ++(void) {
00442 const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
00443 }
00444
00445 forceinline int
00446 IntVarImpFwd::min(void) const {
00447 return c->min();
00448 }
00449 forceinline int
00450 IntVarImpFwd::max(void) const {
00451 return c->max();
00452 }
00453 forceinline unsigned int
00454 IntVarImpFwd::width(void) const {
00455 return c->width();
00456 }
00457
00458
00459
00460
00461
00462
00463
00464 forceinline
00465 IntVarImpBwd::IntVarImpBwd(void) {}
00466 forceinline
00467 IntVarImpBwd::IntVarImpBwd(const IntVarImp* x)
00468 : n(NULL), c(x->ranges_bwd()) {}
00469 forceinline void
00470 IntVarImpBwd::init(const IntVarImp* x) {
00471 n=NULL; c=x->ranges_bwd();
00472 }
00473
00474 forceinline bool
00475 IntVarImpBwd::operator ()(void) const {
00476 return c != NULL;
00477 }
00478 forceinline void
00479 IntVarImpBwd::operator ++(void) {
00480 const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
00481 }
00482
00483 forceinline int
00484 IntVarImpBwd::min(void) const {
00485 return c->min();
00486 }
00487 forceinline int
00488 IntVarImpBwd::max(void) const {
00489 return c->max();
00490 }
00491 forceinline unsigned int
00492 IntVarImpBwd::width(void) const {
00493 return c->width();
00494 }
00495
00496
00497
00498
00499
00500
00501 template<class I>
00502 forceinline ModEvent
00503 IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
00504
00505 if (!ri())
00506 return fail(home);
00507
00508 int min0 = ri.min();
00509 int max0 = ri.max();
00510 ++ri;
00511
00512 ModEvent me;
00513
00514
00515 if (!ri()) {
00516
00517
00518 if (fst()) {
00519 fst()->dispose(home,NULL,lst());
00520 fst(NULL); holes = 0;
00521 }
00522 const int min1 = dom.min(); dom.min(min0);
00523 const int max1 = dom.max(); dom.max(max0);
00524 if ((min0 == min1) && (max0 == max1))
00525 return ME_INT_NONE;
00526 me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND;
00527 goto notify;
00528 }
00529
00530 if (depends || range()) {
00531
00532 RangeList* f = new (home) RangeList(min0,max0,NULL,NULL);
00533 RangeList* l = f;
00534 unsigned int s = static_cast<unsigned int>(max0-min0+1);
00535 do {
00536 RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
00537 l->next(NULL,n);
00538 l = n;
00539 s += ri.width();
00540 ++ri;
00541 } while (ri());
00542 if (fst() != NULL)
00543 fst()->dispose(home,NULL,lst());
00544 fst(f); lst(l);
00545
00546
00547 if (size() == s)
00548 return ME_INT_NONE;
00549
00550 const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
00551 const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
00552 holes = width() - s;
00553
00554 me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND;
00555 goto notify;
00556 } else {
00557
00558 RangeList f, l;
00559
00560 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00561 fst()->prev(NULL,&f); lst()->next(NULL,&l);
00562
00563
00564 unsigned int h = 0;
00565
00566 RangeList* p = &f;
00567
00568 RangeList* r = f.next(NULL);
00569
00570 while (true) {
00571 assert((r != &f) && (r != &l));
00572 if (r->max() < min0) {
00573
00574 h += r->width();
00575 RangeList* n=r->next(p);
00576 p->next(r,n); n->prev(r,p);
00577 r->dispose(home);
00578 r=n;
00579 if (r == &l)
00580 goto done;
00581 } else if ((r->min() == min0) && (r->max() == max0)) {
00582
00583 RangeList* n=r->next(p); p=r; r=n;
00584 if (r == &l)
00585 goto done;
00586 if (!ri())
00587 goto done;
00588 min0=ri.min(); max0=ri.max(); ++ri;
00589 } else {
00590
00591 assert((r->min() <= min0) && (max0 <= r->max()));
00592 h += r->width();
00593 int end = r->max();
00594
00595 r->min(min0); r->max(max0);
00596 assert(h > r->width());
00597 h -= r->width();
00598 {
00599 RangeList* n=r->next(p); p=r; r=n;
00600 }
00601 while (true) {
00602 if (!ri())
00603 goto done;
00604 min0=ri.min(); max0=ri.max(); ++ri;
00605 if (max0 > end)
00606 break;
00607 assert(h > static_cast<unsigned int>(max0-min0+1));
00608 h -= max0-min0+1;
00609 RangeList* n = new (home) RangeList(min0,max0,p,r);
00610 p->next(r,n); r->prev(p,n);
00611 p=n;
00612 }
00613 if (r == &l)
00614 goto done;
00615 }
00616 }
00617 done:
00618
00619
00620 while (r != &l) {
00621 h += r->width();
00622 RangeList* n=r->next(p);
00623 p->next(r,n); n->prev(r,p);
00624 r->dispose(home);
00625 r=n;
00626 }
00627
00628 assert((r == &l) && !ri());
00629
00630
00631 RangeList* fn = f.next(NULL);
00632 RangeList* ln = l.prev(NULL);
00633
00634
00635 assert(fn != &l);
00636
00637
00638 assert(fn != ln);
00639
00640
00641 holes += h;
00642
00643 fn->prev(&f,NULL); ln->next(&l,NULL);
00644
00645 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00646 static_cast<unsigned int>(dom.max()-ln->max()));
00647
00648 fst(fn); lst(ln);
00649
00650 if (b > 0) {
00651 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00652 dom.min(fn->min()); dom.max(ln->max());
00653 holes -= b;
00654 me = ME_INT_BND; goto notify;
00655 }
00656
00657 if (h > 0) {
00658 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00659 me = ME_INT_DOM; goto notify;
00660 }
00661 return ME_INT_NONE;
00662 }
00663 notify:
00664 IntDelta d;
00665 return notify(home,me,d);
00666 }
00667
00668 template<class I>
00669 forceinline ModEvent
00670 IntVarImp::inter_r(Space& home, I& i, bool) {
00671 IntVarImpFwd j(this);
00672 Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
00673 return narrow_r(home,ij,true);
00674 }
00675
00676 template<class I>
00677 forceinline ModEvent
00678 IntVarImp::minus_r(Space& home, I& i, bool depends) {
00679 if (depends) {
00680 IntVarImpFwd j(this);
00681 Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
00682 return narrow_r(home,ij,true);
00683 }
00684
00685
00686 while (i() && (i.max() < dom.min()))
00687 ++i;
00688
00689
00690 if (!i() || (i.min() > dom.max()))
00691 return ME_INT_NONE;
00692
00693 int i_min = i.min();
00694 int i_max = i.max();
00695 ++i;
00696
00697 if ((i_min <= dom.min()) && (i_max >= dom.max()))
00698 return fail(home);
00699
00700 if ((i_min > dom.min()) && (i_max >= dom.max()))
00701 return lq(home,i_min-1);
00702
00703 if ((i_min <= dom.min()) && (i_max < dom.max()) &&
00704 (!i() || (i.min() > dom.max())))
00705 return gq(home,i_max+1);
00706
00707
00708 RangeList f, l;
00709
00710 if (range()) {
00711
00712 RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00713 f.prevnext(NULL,n); l.prevnext(n,NULL);
00714 } else {
00715
00716 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00717 fst()->prev(NULL,&f); lst()->next(NULL,&l);
00718 }
00719
00720
00721 unsigned int h = 0;
00722
00723 RangeList* p = &f;
00724
00725 RangeList* r = f.next(NULL);
00726
00727 while (true) {
00728 assert((r != &f) && (r != &l));
00729 if (i_min > r->max()) {
00730 RangeList* n=r->next(p); p=r; r=n;
00731 if (r == &l)
00732 break;
00733 } else if (i_max < r->min()) {
00734 if (!i())
00735 break;
00736 i_min = i.min();
00737 i_max = i.max();
00738 ++i;
00739 } else if ((i_min <= r->min()) && (r->max() <= i_max)) {
00740
00741 h += r->width();
00742 RangeList* n=r->next(p);
00743 p->next(r,n); n->prev(r,p);
00744 r->dispose(home);
00745 r=n;
00746 if (r == &l)
00747 break;
00748 } else if ((i_min > r->min()) && (i_max < r->max())) {
00749
00750 h += static_cast<unsigned int>(i_max - i_min) + 1;
00751 RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r);
00752 r->min(i_max+1);
00753 p->next(r,n); r->prev(p,n);
00754 p=n;
00755 if (!i())
00756 break;
00757 i_min = i.min();
00758 i_max = i.max();
00759 ++i;
00760 } else if (i_max < r->max()) {
00761 assert(i_min <= r->min());
00762
00763 h += i_max-r->min()+1;
00764 r->min(i_max+1);
00765 if (!i())
00766 break;
00767 i_min = i.min();
00768 i_max = i.max();
00769 ++i;
00770 } else {
00771 assert((i_max >= r->max()) && (r->min() < i_min));
00772
00773 h += r->max()-i_min+1;
00774 r->max(i_min-1);
00775 RangeList* n=r->next(p); p=r; r=n;
00776 if (r == &l)
00777 break;
00778 }
00779 }
00780
00781
00782 RangeList* fn = f.next(NULL);
00783 RangeList* ln = l.prev(NULL);
00784
00785
00786 if (fn == &l) {
00787 fst(NULL); lst(NULL); holes=0;
00788 return fail(home);
00789 }
00790
00791 ModEvent me;
00792 unsigned int b;
00793
00794
00795 if (fn == ln) {
00796 assert(h > 0);
00797 dom.min(fn->min()); dom.max(fn->max());
00798 fn->dispose(home);
00799 fst(NULL); lst(NULL);
00800 holes = 0;
00801 me = assigned() ? ME_INT_VAL : ME_INT_BND;
00802 goto notify;
00803 }
00804
00805
00806 holes += h;
00807
00808 fn->prev(&f,NULL); ln->next(&l,NULL);
00809
00810 b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00811 static_cast<unsigned int>(dom.max()-ln->max()));
00812
00813 fst(fn); lst(ln);
00814
00815 if (b > 0) {
00816 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00817 dom.min(fn->min()); dom.max(ln->max());
00818 holes -= b;
00819 me = ME_INT_BND; goto notify;
00820 }
00821
00822 if (h > 0) {
00823 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00824 me = ME_INT_DOM; goto notify;
00825 }
00826
00827 return ME_INT_NONE;
00828 notify:
00829 IntDelta d;
00830 return notify(home,me,d);
00831 }
00832
00833 template<class I>
00834 forceinline ModEvent
00835 IntVarImp::narrow_v(Space& home, I& i, bool depends) {
00836 Iter::Values::ToRanges<I> r(i);
00837 return narrow_r(home,r,depends);
00838 }
00839
00840 template<class I>
00841 forceinline ModEvent
00842 IntVarImp::inter_v(Space& home, I& i, bool depends) {
00843 Iter::Values::ToRanges<I> r(i);
00844 return inter_r(home,r,depends);
00845 }
00846
00847 template<class I>
00848 forceinline ModEvent
00849 IntVarImp::minus_v(Space& home, I& i, bool depends) {
00850 if (depends) {
00851 Iter::Values::ToRanges<I> r(i);
00852 return minus_r(home, r, true);
00853 }
00854
00855
00856 while (i() && (i.val() < dom.min()))
00857 ++i;
00858
00859
00860 if (!i() || (i.val() > dom.max()))
00861 return ME_INT_NONE;
00862
00863 int v = i.val();
00864
00865 do {
00866 ++i;
00867 } while (i() && (i.val() == v));
00868
00869
00870 if (!i() || (i.val() > dom.max()))
00871 return nq_full(home,v);
00872
00873
00874 RangeList f, l;
00875
00876 if (range()) {
00877
00878 RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00879 f.prevnext(NULL,n); l.prevnext(n,NULL);
00880 } else {
00881
00882 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00883 fst()->prev(NULL,&f); lst()->next(NULL,&l);
00884 }
00885
00886
00887 unsigned int h = 0;
00888
00889 RangeList* p = &f;
00890
00891 RangeList* r = f.next(NULL);
00892
00893 while (true) {
00894 assert((r != &f) && (r != &l));
00895 if (v > r->max()) {
00896
00897 RangeList* n=r->next(p); p=r; r=n;
00898 if (r == &l)
00899 break;
00900 } else {
00901 if ((v == r->min()) && (v == r->max())) {
00902
00903 h++;
00904 RangeList* n=r->next(p);
00905 p->next(r,n); n->prev(r,p);
00906 r->dispose(home);
00907 r=n;
00908 if (r == &l)
00909 break;
00910 } else if (v == r->min()) {
00911 h++; r->min(v+1);
00912 } else if (v == r->max()) {
00913 h++; r->max(v-1);
00914 RangeList* n=r->next(p); p=r; r=n;
00915 if (r == &l)
00916 break;
00917 } else if (v > r->min()) {
00918
00919 assert(v < r->max());
00920 h++;
00921 RangeList* n = new (home) RangeList(r->min(),v-1,p,r);
00922 r->min(v+1);
00923 p->next(r,n); r->prev(p,n);
00924 p=n;
00925 }
00926 if (!i())
00927 break;
00928
00929 v = i.val(); ++i;
00930 }
00931 }
00932 assert((r == &l) || !i());
00933
00934
00935 RangeList* fn = f.next(NULL);
00936 RangeList* ln = l.prev(NULL);
00937
00938
00939 if (fn == &l) {
00940 fst(NULL); lst(NULL); holes=0;
00941 return fail(home);
00942 }
00943
00944 IntDelta d;
00945
00946
00947 if (fn == ln) {
00948 assert(h > 0);
00949 dom.min(fn->min()); dom.max(fn->max());
00950 fn->dispose(home);
00951 fst(NULL); lst(NULL);
00952 holes = 0;
00953 if (assigned())
00954 return notify(home,ME_INT_VAL,d);
00955 else
00956 return notify(home,ME_INT_BND,d);
00957 }
00958
00959
00960 holes += h;
00961
00962 fn->prev(&f,NULL); ln->next(&l,NULL);
00963
00964 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00965 static_cast<unsigned int>(dom.max()-ln->max()));
00966
00967 fst(fn); lst(ln);
00968
00969 if (b > 0) {
00970 assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00971 dom.min(fn->min()); dom.max(ln->max());
00972 holes -= b;
00973 return notify(home,ME_INT_BND,d);
00974 }
00975
00976 if (h > 0) {
00977 assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00978 return notify(home,ME_INT_DOM,d);
00979 }
00980
00981 return ME_INT_NONE;
00982 }
00983
00984
00985
00986
00987
00988
00989
00990 forceinline IntVarImp*
00991 IntVarImp::copy(Space& home, bool share) {
00992 return copied() ? static_cast<IntVarImp*>(forward())
00993 : perform_copy(home,share);
00994 }
00995
00996
00997 forceinline ModEventDelta
00998 IntVarImp::med(ModEvent me) {
00999 return IntVarImpBase::med(me);
01000 }
01001
01002 }}
01003
01004