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 namespace Gecode { namespace Int {
00039
00040
00041
00042
00043
00044
00045 #define GECODE_INT_RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
00046 #define GECODE_INT_PD2RL(p) reinterpret_cast<RangeList*>(p)
00047
00048 forceinline
00049 IntVarImp::RangeList::RangeList(void) {}
00050
00051 forceinline
00052 IntVarImp::RangeList::RangeList(int min, int max)
00053 : _min(min), _max(max) {}
00054
00055 forceinline
00056 IntVarImp::RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
00057 : _min(min), _max(max) {
00058 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
00059 }
00060
00061 forceinline IntVarImp::RangeList*
00062 IntVarImp::RangeList::next(const RangeList* p) const {
00063 return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(p));
00064 }
00065 forceinline IntVarImp::RangeList*
00066 IntVarImp::RangeList::prev(const RangeList* n) const {
00067 return GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^GECODE_INT_RL2PD(n));
00068 }
00069 forceinline void
00070 IntVarImp::RangeList::prevnext(RangeList* p, RangeList* n) {
00071 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(p)^GECODE_INT_RL2PD(n));
00072 }
00073 forceinline void
00074 IntVarImp::RangeList::next(RangeList* o, RangeList* n) {
00075 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
00076 (GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
00077 }
00078 forceinline void
00079 IntVarImp::RangeList::prev(RangeList* o, RangeList* n) {
00080 _next = GECODE_INT_PD2RL(GECODE_INT_RL2PD(_next)^
00081 (GECODE_INT_RL2PD(o)^GECODE_INT_RL2PD(n)));
00082 }
00083 forceinline void
00084 IntVarImp::RangeList::fix(RangeList* n) {
00085 _next = n;
00086 }
00087
00088 forceinline void
00089 IntVarImp::RangeList::min(int n) {
00090 _min = n;
00091 }
00092 forceinline void
00093 IntVarImp::RangeList::max(int n) {
00094 _max = n;
00095 }
00096
00097 forceinline int
00098 IntVarImp::RangeList::min(void) const {
00099 return _min;
00100 }
00101 forceinline int
00102 IntVarImp::RangeList::max(void) const {
00103 return _max;
00104 }
00105 forceinline unsigned int
00106 IntVarImp::RangeList::width(void) const {
00107 return static_cast<unsigned int>(_max - _min) + 1;
00108 }
00109
00110
00111 forceinline void
00112 IntVarImp::RangeList::operator delete(void*) {}
00113
00114 forceinline void
00115 IntVarImp::RangeList::operator delete(void*, Space&) {
00116 GECODE_NEVER;
00117 }
00118 forceinline void
00119 IntVarImp::RangeList::operator delete(void*, void*) {
00120 GECODE_NEVER;
00121 }
00122
00123 forceinline void*
00124 IntVarImp::RangeList::operator new(size_t, Space& home) {
00125 return home.fl_alloc<sizeof(RangeList)>();
00126 }
00127
00128 forceinline void*
00129 IntVarImp::RangeList::operator new(size_t, void* p) {
00130 return p;
00131 }
00132
00133 forceinline void
00134 IntVarImp::RangeList::dispose(Space& home, RangeList* p, RangeList* l) {
00135 RangeList* c = this;
00136 while (c != l) {
00137 RangeList* n = c->next(p);
00138 c->fix(n);
00139 p=c; c=n;
00140 }
00141 home.fl_dispose<sizeof(RangeList)>(this,l);
00142 }
00143
00144 forceinline void
00145 IntVarImp::RangeList::dispose(Space& home, RangeList* l) {
00146 home.fl_dispose<sizeof(RangeList)>(this,l);
00147 }
00148
00149 forceinline void
00150 IntVarImp::RangeList::dispose(Space& home) {
00151 home.fl_dispose<sizeof(RangeList)>(this,this);
00152 }
00153
00154 #undef GECODE_INT_RL2PD
00155 #undef GECODE_INT_PD2RL
00156
00157
00158
00159
00160
00161
00162 forceinline IntVarImp::RangeList*
00163 IntVarImp::fst(void) const {
00164 return dom.next(NULL);
00165 }
00166
00167 forceinline void
00168 IntVarImp::fst(IntVarImp::RangeList* f) {
00169 dom.prevnext(NULL,f);
00170 }
00171
00172 forceinline IntVarImp::RangeList*
00173 IntVarImp::lst(void) const {
00174 return _lst;
00175 }
00176
00177 forceinline void
00178 IntVarImp::lst(IntVarImp::RangeList* l) {
00179 _lst = l;
00180 }
00181
00182
00183
00184
00185
00186
00187 forceinline
00188 IntVarImp::IntVarImp(Space& home, int min, int max)
00189 : IntVarImpBase(home), dom(min,max,NULL,NULL), holes(0) {}
00190
00191 forceinline
00192 IntVarImp::IntVarImp(Space& home, const IntSet& d)
00193 : IntVarImpBase(home), dom(d.min(),d.max()) {
00194 if (d.ranges() > 1) {
00195 int n = d.ranges();
00196 assert(n >= 2);
00197 RangeList* r = home.alloc<RangeList>(n);
00198 fst(r); lst(r+n-1);
00199 unsigned int h = static_cast<unsigned int>(d.max()-d.min())+1;
00200 h -= d.width(0);
00201 r[0].min(d.min(0)); r[0].max(d.max(0));
00202 r[0].prevnext(NULL,&r[1]);
00203 for (int i = 1; i < n-1; i++) {
00204 h -= d.width(i);
00205 r[i].min(d.min(i)); r[i].max(d.max(i));
00206 r[i].prevnext(&r[i-1],&r[i+1]);
00207 }
00208 h -= d.width(n-1);
00209 r[n-1].min(d.min(n-1)); r[n-1].max(d.max(n-1));
00210 r[n-1].prevnext(&r[n-2],NULL);
00211 holes = h;
00212 } else {
00213 fst(NULL); holes = 0;
00214 }
00215 }
00216
00217
00218
00219
00220
00221
00222
00223 forceinline int
00224 IntVarImp::min(void) const {
00225 return dom.min();
00226 }
00227 forceinline int
00228 IntVarImp::max(void) const {
00229 return dom.max();
00230 }
00231 forceinline int
00232 IntVarImp::val(void) const {
00233 assert(dom.min() == dom.max());
00234 return dom.min();
00235 }
00236
00237 forceinline bool
00238 IntVarImp::range(void) const {
00239 return fst() == NULL;
00240 }
00241 forceinline bool
00242 IntVarImp::assigned(void) const {
00243 return dom.min() == dom.max();
00244 }
00245
00246
00247 forceinline unsigned int
00248 IntVarImp::width(void) const {
00249 return dom.width();
00250 }
00251
00252 forceinline unsigned int
00253 IntVarImp::size(void) const {
00254 return dom.width() - holes;
00255 }
00256
00257 forceinline unsigned int
00258 IntVarImp::regret_min(void) const {
00259 if (fst() == NULL) {
00260 return (dom.min() == dom.max()) ? 0U : 1U;
00261 } else if (dom.min() == fst()->max()) {
00262 return static_cast<unsigned int>(fst()->next(NULL)->min()-dom.min());
00263 } else {
00264 return 1U;
00265 }
00266 }
00267 forceinline unsigned int
00268 IntVarImp::regret_max(void) const {
00269 if (fst() == NULL) {
00270 return (dom.min() == dom.max()) ? 0U : 1U;
00271 } else if (dom.max() == lst()->min()) {
00272 return static_cast<unsigned int>(dom.max()-lst()->prev(NULL)->max());
00273 } else {
00274 return 1U;
00275 }
00276 }
00277
00278
00279
00280
00281
00282
00283
00284
00285 forceinline bool
00286 IntVarImp::in(int n) const {
00287 if ((n < dom.min()) || (n > dom.max()))
00288 return false;
00289 return (fst() == NULL) || in_full(n);
00290 }
00291 forceinline bool
00292 IntVarImp::in(long long int n) const {
00293 if ((n < dom.min()) || (n > dom.max()))
00294 return false;
00295 return (fst() == NULL) || in_full(static_cast<int>(n));
00296 }
00297
00298
00299
00300
00301
00302
00303
00304 forceinline const IntVarImp::RangeList*
00305 IntVarImp::ranges_fwd(void) const {
00306 return (fst() == NULL) ? &dom : fst();
00307 }
00308
00309 forceinline const IntVarImp::RangeList*
00310 IntVarImp::ranges_bwd(void) const {
00311 return (fst() == NULL) ? &dom : lst();
00312 }
00313
00314
00315
00316
00317
00318
00319
00320 forceinline int
00321 IntVarImp::min(const Delta& d) {
00322 return static_cast<const IntDelta&>(d).min();
00323 }
00324 forceinline int
00325 IntVarImp::max(const Delta& d) {
00326 return static_cast<const IntDelta&>(d).max();
00327 }
00328 forceinline unsigned int
00329 IntVarImp::width(const Delta& d) {
00330 return static_cast<const IntDelta&>(d).width();
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) {
00992 return copied() ? static_cast<IntVarImp*>(forward())
00993 : perform_copy(home);
00994 }
00995
00996
00997 forceinline ModEventDelta
00998 IntVarImp::med(ModEvent me) {
00999 return IntVarImpBase::med(me);
01000 }
01001
01002 }}
01003
01004