int.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * 00006 * Contributing authors: 00007 * Guido Tack <tack@gecode.org> 00008 * 00009 * Copyright: 00010 * Christian Schulte, 2003 00011 * Guido Tack, 2004 00012 * 00013 * Last modified: 00014 * $Date: 2010-07-28 17:35:33 +0200 (Wed, 28 Jul 2010) $ by $Author: schulte $ 00015 * $Revision: 11294 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00039 * 00040 */ 00041 00042 namespace Gecode { namespace Int { 00043 00044 /* 00045 * Range lists 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 * Mainitaining range lists for variable domain 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 * Creation of new variable implementations 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 * Operations on integer variable implementations 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 * Tests 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 * Accessing rangelists for iteration 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 * Support for delta information 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 * Tell operations (to be inlined: performing bounds checks first) 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 ME_INT_FAILED; 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, double n) { 00355 if (n <= dom.min()) return ME_INT_NONE; 00356 if (n > dom.max()) return ME_INT_FAILED; 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 00365 forceinline ModEvent 00366 IntVarImp::lq(Space& home, int n) { 00367 if (n >= dom.max()) return ME_INT_NONE; 00368 if (n < dom.min()) return ME_INT_FAILED; 00369 ModEvent me = lq_full(home,n); 00370 GECODE_ASSUME((me == ME_INT_FAILED) | 00371 (me == ME_INT_VAL) | 00372 (me == ME_INT_BND)); 00373 return me; 00374 } 00375 forceinline ModEvent 00376 IntVarImp::lq(Space& home, double n) { 00377 if (n >= dom.max()) return ME_INT_NONE; 00378 if (n < dom.min()) return ME_INT_FAILED; 00379 ModEvent me = lq_full(home,static_cast<int>(n)); 00380 GECODE_ASSUME((me == ME_INT_FAILED) | 00381 (me == ME_INT_VAL) | 00382 (me == ME_INT_BND)); 00383 return me; 00384 } 00385 00386 00387 forceinline ModEvent 00388 IntVarImp::eq(Space& home, int n) { 00389 if ((n < dom.min()) || (n > dom.max())) 00390 return ME_INT_FAILED; 00391 if ((n == dom.min()) && (n == dom.max())) 00392 return ME_INT_NONE; 00393 ModEvent me = eq_full(home,n); 00394 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL)); 00395 return me; 00396 } 00397 forceinline ModEvent 00398 IntVarImp::eq(Space& home, double m) { 00399 if ((m < dom.min()) || (m > dom.max())) 00400 return ME_INT_FAILED; 00401 int n = static_cast<int>(m); 00402 if ((n == dom.min()) && (n == dom.max())) 00403 return ME_INT_NONE; 00404 ModEvent me = eq_full(home,n); 00405 GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL)); 00406 return me; 00407 } 00408 00409 00410 forceinline ModEvent 00411 IntVarImp::nq(Space& home, int n) { 00412 if ((n < dom.min()) || (n > dom.max())) 00413 return ME_INT_NONE; 00414 return nq_full(home,n); 00415 } 00416 forceinline ModEvent 00417 IntVarImp::nq(Space& home, double d) { 00418 if ((d < dom.min()) || (d > dom.max())) 00419 return ME_INT_NONE; 00420 return nq_full(home,static_cast<int>(d)); 00421 } 00422 00423 00424 /* 00425 * Forward range iterator for rangelists 00426 * 00427 */ 00428 00429 forceinline 00430 IntVarImpFwd::IntVarImpFwd(void) {} 00431 forceinline 00432 IntVarImpFwd::IntVarImpFwd(const IntVarImp* x) 00433 : p(NULL), c(x->ranges_fwd()) {} 00434 forceinline void 00435 IntVarImpFwd::init(const IntVarImp* x) { 00436 p=NULL; c=x->ranges_fwd(); 00437 } 00438 00439 forceinline bool 00440 IntVarImpFwd::operator ()(void) const { 00441 return c != NULL; 00442 } 00443 forceinline void 00444 IntVarImpFwd::operator ++(void) { 00445 const IntVarImp::RangeList* n=c->next(p); p=c; c=n; 00446 } 00447 00448 forceinline int 00449 IntVarImpFwd::min(void) const { 00450 return c->min(); 00451 } 00452 forceinline int 00453 IntVarImpFwd::max(void) const { 00454 return c->max(); 00455 } 00456 forceinline unsigned int 00457 IntVarImpFwd::width(void) const { 00458 return c->width(); 00459 } 00460 00461 00462 /* 00463 * Backward range iterator for rangelists 00464 * 00465 */ 00466 00467 forceinline 00468 IntVarImpBwd::IntVarImpBwd(void) {} 00469 forceinline 00470 IntVarImpBwd::IntVarImpBwd(const IntVarImp* x) 00471 : n(NULL), c(x->ranges_bwd()) {} 00472 forceinline void 00473 IntVarImpBwd::init(const IntVarImp* x) { 00474 n=NULL; c=x->ranges_bwd(); 00475 } 00476 00477 forceinline bool 00478 IntVarImpBwd::operator ()(void) const { 00479 return c != NULL; 00480 } 00481 forceinline void 00482 IntVarImpBwd::operator ++(void) { 00483 const IntVarImp::RangeList* p=c->prev(n); n=c; c=p; 00484 } 00485 00486 forceinline int 00487 IntVarImpBwd::min(void) const { 00488 return c->min(); 00489 } 00490 forceinline int 00491 IntVarImpBwd::max(void) const { 00492 return c->max(); 00493 } 00494 forceinline unsigned int 00495 IntVarImpBwd::width(void) const { 00496 return c->width(); 00497 } 00498 00499 00500 /* 00501 * Iterator-based domain operations 00502 * 00503 */ 00504 template<class I> 00505 forceinline ModEvent 00506 IntVarImp::narrow_r(Space& home, I& ri, bool depends) { 00507 // Is new domain empty? 00508 if (!ri()) 00509 return ME_INT_FAILED; 00510 00511 int min0 = ri.min(); 00512 int max0 = ri.max(); 00513 ++ri; 00514 00515 ModEvent me; 00516 00517 // Is new domain range? 00518 if (!ri()) { 00519 // Remove possible rangelist (if it was not a range, the domain 00520 // must have been narrowed!) 00521 if (fst()) { 00522 fst()->dispose(home,NULL,lst()); 00523 fst(NULL); holes = 0; 00524 } 00525 const int min1 = dom.min(); dom.min(min0); 00526 const int max1 = dom.max(); dom.max(max0); 00527 if ((min0 == min1) && (max0 == max1)) 00528 return ME_INT_NONE; 00529 me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND; 00530 goto notify; 00531 } 00532 00533 if (depends || range()) { 00534 // Construct new rangelist 00535 RangeList* f = new (home) RangeList(min0,max0,NULL,NULL); 00536 RangeList* l = f; 00537 unsigned int s = static_cast<unsigned int>(max0-min0+1); 00538 do { 00539 RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL); 00540 l->next(NULL,n); 00541 l = n; 00542 s += ri.width(); 00543 ++ri; 00544 } while (ri()); 00545 if (fst() != NULL) 00546 fst()->dispose(home,NULL,lst()); 00547 fst(f); lst(l); 00548 00549 // Check for modification 00550 if (size() == s) 00551 return ME_INT_NONE; 00552 00553 const int min1 = dom.min(); min0 = f->min(); dom.min(min0); 00554 const int max1 = dom.max(); max0 = l->max(); dom.max(max0); 00555 holes = width() - s; 00556 00557 me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND; 00558 goto notify; 00559 } else { 00560 // Set up two sentinel elements 00561 RangeList f, l; 00562 // Put all ranges between sentinels 00563 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL); 00564 fst()->prev(NULL,&f); lst()->next(NULL,&l); 00565 00566 // Number of values removed (potential holes) 00567 unsigned int h = 0; 00568 // The previous range 00569 RangeList* p = &f; 00570 // The current range 00571 RangeList* r = f.next(NULL); 00572 00573 while (true) { 00574 assert((r != &f) && (r != &l)); 00575 if (r->max() < min0) { 00576 // Entire range removed 00577 h += r->width(); 00578 RangeList* n=r->next(p); 00579 p->next(r,n); n->prev(r,p); 00580 r->dispose(home); 00581 r=n; 00582 if (r == &l) 00583 goto done; 00584 } else if ((r->min() == min0) && (r->max() == max0)) { 00585 // Range unchanged 00586 RangeList* n=r->next(p); p=r; r=n; 00587 if (r == &l) 00588 goto done; 00589 if (!ri()) 00590 goto done; 00591 min0=ri.min(); max0=ri.max(); ++ri; 00592 } else { 00593 // Range might have been split into many small ranges 00594 assert((r->min() <= min0) && (max0 <= r->max())); 00595 h += r->width(); 00596 int end = r->max(); 00597 // Copy first range 00598 r->min(min0); r->max(max0); 00599 assert(h > r->width()); 00600 h -= r->width(); 00601 { 00602 RangeList* n=r->next(p); p=r; r=n; 00603 } 00604 while (true) { 00605 if (!ri()) 00606 goto done; 00607 min0=ri.min(); max0=ri.max(); ++ri; 00608 if (max0 > end) 00609 break; 00610 assert(h > static_cast<unsigned int>(max0-min0+1)); 00611 h -= max0-min0+1; 00612 RangeList* n = new (home) RangeList(min0,max0,p,r); 00613 p->next(r,n); r->prev(p,n); 00614 p=n; 00615 } 00616 if (r == &l) 00617 goto done; 00618 } 00619 } 00620 done: 00621 00622 // Remove remaining ranges 00623 while (r != &l) { 00624 h += r->width(); 00625 RangeList* n=r->next(p); 00626 p->next(r,n); n->prev(r,p); 00627 r->dispose(home); 00628 r=n; 00629 } 00630 00631 assert((r == &l) && !ri()); 00632 00633 // New first and last ranges 00634 RangeList* fn = f.next(NULL); 00635 RangeList* ln = l.prev(NULL); 00636 00637 // All ranges pruned? 00638 assert(fn != &l); 00639 00640 // Only a single range left? 00641 assert(fn != ln); 00642 00643 // The number of removed values 00644 holes += h; 00645 // Unlink sentinel ranges 00646 fn->prev(&f,NULL); ln->next(&l,NULL); 00647 // How many values where removed at the bounds 00648 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) + 00649 static_cast<unsigned int>(dom.max()-ln->max())); 00650 // Set new first and last ranges 00651 fst(fn); lst(ln); 00652 00653 if (b > 0) { 00654 assert((dom.min() != fn->min()) || (dom.max() != ln->max())); 00655 dom.min(fn->min()); dom.max(ln->max()); 00656 holes -= b; 00657 me = ME_INT_BND; goto notify; 00658 } 00659 00660 if (h > 0) { 00661 assert((dom.min() == fn->min()) && (dom.max() == ln->max())); 00662 me = ME_INT_DOM; goto notify; 00663 } 00664 return ME_INT_NONE; 00665 } 00666 notify: 00667 IntDelta d; 00668 return notify(home,me,d); 00669 } 00670 00671 template<class I> 00672 forceinline ModEvent 00673 IntVarImp::inter_r(Space& home, I& i, bool) { 00674 IntVarImpFwd j(this); 00675 Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j); 00676 return narrow_r(home,ij,true); 00677 } 00678 00679 template<class I> 00680 forceinline ModEvent 00681 IntVarImp::minus_r(Space& home, I& i, bool depends) { 00682 if (depends) { 00683 IntVarImpFwd j(this); 00684 Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i); 00685 return narrow_r(home,ij,true); 00686 } 00687 00688 // Skip all ranges that are too small 00689 while (i() && (i.max() < dom.min())) 00690 ++i; 00691 00692 // Is there no range left or all are too large? 00693 if (!i() || (i.min() > dom.max())) 00694 return ME_INT_NONE; 00695 00696 int i_min = i.min(); 00697 int i_max = i.max(); 00698 ++i; 00699 00700 if ((i_min <= dom.min()) && (i_max >= dom.max())) 00701 return ME_INT_FAILED; 00702 00703 if ((i_min > dom.min()) && (i_max >= dom.max())) 00704 return lq(home,i_min-1); 00705 00706 if ((i_min <= dom.min()) && (i_max < dom.max()) && 00707 (!i() || (i.min() > dom.max()))) 00708 return gq(home,i_max+1); 00709 00710 // Set up two sentinel elements 00711 RangeList f, l; 00712 // Put all ranges between sentinels 00713 if (range()) { 00714 // Create a new rangelist just for simplicity 00715 RangeList* n = new (home) RangeList(min(),max(),&f,&l); 00716 f.prevnext(NULL,n); l.prevnext(n,NULL); 00717 } else { 00718 // Link the two sentinel elements 00719 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL); 00720 fst()->prev(NULL,&f); lst()->next(NULL,&l); 00721 } 00722 00723 // Number of values removed (potential holes) 00724 unsigned int h = 0; 00725 // The previous range 00726 RangeList* p = &f; 00727 // The current range 00728 RangeList* r = f.next(NULL); 00729 00730 while (true) { 00731 assert((r != &f) && (r != &l)); 00732 if (i_min > r->max()) { 00733 RangeList* n=r->next(p); p=r; r=n; 00734 if (r == &l) 00735 break; 00736 } else if (i_max < r->min()) { 00737 if (!i()) 00738 break; 00739 i_min = i.min(); 00740 i_max = i.max(); 00741 ++i; 00742 } else if ((i_min <= r->min()) && (r->max() <= i_max)) { 00743 // r is included in i: remove entire range r 00744 h += r->width(); 00745 RangeList* n=r->next(p); 00746 p->next(r,n); n->prev(r,p); 00747 r->dispose(home); 00748 r=n; 00749 if (r == &l) 00750 break; 00751 } else if ((i_min > r->min()) && (i_max < r->max())) { 00752 // i is included in r: create new range before the current one 00753 h += static_cast<unsigned int>(i_max - i_min) + 1; 00754 RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r); 00755 r->min(i_max+1); 00756 p->next(r,n); r->prev(p,n); 00757 p=n; 00758 if (!i()) 00759 break; 00760 i_min = i.min(); 00761 i_max = i.max(); 00762 ++i; 00763 } else if (i_max < r->max()) { 00764 assert(i_min <= r->min()); 00765 // i ends before r: adjust minimum of r 00766 h += i_max-r->min()+1; 00767 r->min(i_max+1); 00768 if (!i()) 00769 break; 00770 i_min = i.min(); 00771 i_max = i.max(); 00772 ++i; 00773 } else { 00774 assert((i_max >= r->max()) && (r->min() < i_min)); 00775 // r ends before i: adjust maximum of r 00776 h += r->max()-i_min+1; 00777 r->max(i_min-1); 00778 RangeList* n=r->next(p); p=r; r=n; 00779 if (r == &l) 00780 break; 00781 } 00782 } 00783 00784 // New first and last ranges 00785 RangeList* fn = f.next(NULL); 00786 RangeList* ln = l.prev(NULL); 00787 00788 // All ranges pruned? 00789 if (fn == &l) { 00790 fst(NULL); lst(NULL); holes=0; 00791 return ME_INT_FAILED; 00792 } 00793 00794 ModEvent me; 00795 unsigned int b; 00796 00797 // Only a single range left? 00798 if (fn == ln) { 00799 assert(h > 0); 00800 dom.min(fn->min()); dom.max(fn->max()); 00801 fn->dispose(home); 00802 fst(NULL); lst(NULL); 00803 holes = 0; 00804 me = assigned() ? ME_INT_VAL : ME_INT_BND; 00805 goto notify; 00806 } 00807 00808 // The number of removed values 00809 holes += h; 00810 // Unlink sentinel ranges 00811 fn->prev(&f,NULL); ln->next(&l,NULL); 00812 // How many values where removed at the bounds 00813 b = (static_cast<unsigned int>(fn->min()-dom.min()) + 00814 static_cast<unsigned int>(dom.max()-ln->max())); 00815 // Set new first and last ranges 00816 fst(fn); lst(ln); 00817 00818 if (b > 0) { 00819 assert((dom.min() != fn->min()) || (dom.max() != ln->max())); 00820 dom.min(fn->min()); dom.max(ln->max()); 00821 holes -= b; 00822 me = ME_INT_BND; goto notify; 00823 } 00824 00825 if (h > 0) { 00826 assert((dom.min() == fn->min()) && (dom.max() == ln->max())); 00827 me = ME_INT_DOM; goto notify; 00828 } 00829 00830 return ME_INT_NONE; 00831 notify: 00832 IntDelta d; 00833 return notify(home,me,d); 00834 } 00835 00836 template<class I> 00837 forceinline ModEvent 00838 IntVarImp::narrow_v(Space& home, I& i, bool depends) { 00839 Iter::Values::ToRanges<I> r(i); 00840 return narrow_r(home,r,depends); 00841 } 00842 00843 template<class I> 00844 forceinline ModEvent 00845 IntVarImp::inter_v(Space& home, I& i, bool depends) { 00846 Iter::Values::ToRanges<I> r(i); 00847 return inter_r(home,r,depends); 00848 } 00849 00850 template<class I> 00851 forceinline ModEvent 00852 IntVarImp::minus_v(Space& home, I& i, bool depends) { 00853 if (depends) { 00854 Iter::Values::ToRanges<I> r(i); 00855 return minus_r(home, r, true); 00856 } 00857 00858 // Skip all values that are too small 00859 while (i() && (i.val() < dom.min())) 00860 ++i; 00861 00862 // Is there no value left or all are too large? 00863 if (!i() || (i.val() > dom.max())) 00864 return ME_INT_NONE; 00865 00866 int v = i.val(); 00867 // Skip values that are the same 00868 do { 00869 ++i; 00870 } while (i() && (i.val() == v)); 00871 00872 // Is there only a single value to be pruned? 00873 if (!i() || (i.val() > dom.max())) 00874 return nq_full(home,v); 00875 00876 // Set up two sentinel elements 00877 RangeList f, l; 00878 // Put all ranges between sentinels 00879 if (range()) { 00880 // Create a new rangelist just for simplicity 00881 RangeList* n = new (home) RangeList(min(),max(),&f,&l); 00882 f.prevnext(NULL,n); l.prevnext(n,NULL); 00883 } else { 00884 // Link the two sentinel elements 00885 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL); 00886 fst()->prev(NULL,&f); lst()->next(NULL,&l); 00887 } 00888 00889 // Number of values removed (potential holes) 00890 unsigned int h = 0; 00891 // The previous range 00892 RangeList* p = &f; 00893 // The current range 00894 RangeList* r = f.next(NULL); 00895 00896 while (true) { 00897 assert((r != &f) && (r != &l)); 00898 if (v > r->max()) { 00899 // Move to next range 00900 RangeList* n=r->next(p); p=r; r=n; 00901 if (r == &l) 00902 break; 00903 } else { 00904 if ((v == r->min()) && (v == r->max())) { 00905 // Remove range 00906 h++; 00907 RangeList* n=r->next(p); 00908 p->next(r,n); n->prev(r,p); 00909 r->dispose(home); 00910 r=n; 00911 if (r == &l) 00912 break; 00913 } else if (v == r->min()) { 00914 h++; r->min(v+1); 00915 } else if (v == r->max()) { 00916 h++; r->max(v-1); 00917 RangeList* n=r->next(p); p=r; r=n; 00918 if (r == &l) 00919 break; 00920 } else if (v > r->min()) { 00921 // Create new range before the current one 00922 assert(v < r->max()); 00923 h++; 00924 RangeList* n = new (home) RangeList(r->min(),v-1,p,r); 00925 r->min(v+1); 00926 p->next(r,n); r->prev(p,n); 00927 p=n; 00928 } 00929 if (!i()) 00930 break; 00931 // Move to next value 00932 v = i.val(); ++i; 00933 } 00934 } 00935 assert((r == &l) || !i()); 00936 00937 // New first and last ranges 00938 RangeList* fn = f.next(NULL); 00939 RangeList* ln = l.prev(NULL); 00940 00941 // All ranges pruned? 00942 if (fn == &l) { 00943 fst(NULL); lst(NULL); holes=0; 00944 return ME_INT_FAILED; 00945 } 00946 00947 IntDelta d; 00948 00949 // Only a single range left? 00950 if (fn == ln) { 00951 assert(h > 0); 00952 dom.min(fn->min()); dom.max(fn->max()); 00953 fn->dispose(home); 00954 fst(NULL); lst(NULL); 00955 holes = 0; 00956 if (assigned()) 00957 return notify(home,ME_INT_VAL,d); 00958 else 00959 return notify(home,ME_INT_BND,d); 00960 } 00961 00962 // The number of removed values 00963 holes += h; 00964 // Unlink sentinel ranges 00965 fn->prev(&f,NULL); ln->next(&l,NULL); 00966 // How many values where removed at the bounds 00967 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) + 00968 static_cast<unsigned int>(dom.max()-ln->max())); 00969 // Set new first and last ranges 00970 fst(fn); lst(ln); 00971 00972 if (b > 0) { 00973 assert((dom.min() != fn->min()) || (dom.max() != ln->max())); 00974 dom.min(fn->min()); dom.max(ln->max()); 00975 holes -= b; 00976 return notify(home,ME_INT_BND,d); 00977 } 00978 00979 if (h > 0) { 00980 assert((dom.min() == fn->min()) && (dom.max() == ln->max())); 00981 return notify(home,ME_INT_DOM,d); 00982 } 00983 00984 return ME_INT_NONE; 00985 } 00986 00987 00988 /* 00989 * Copying a variable 00990 * 00991 */ 00992 00993 forceinline IntVarImp* 00994 IntVarImp::copy(Space& home, bool share) { 00995 return copied() ? static_cast<IntVarImp*>(forward()) 00996 : perform_copy(home,share); 00997 } 00998 00999 01000 /* 01001 * Dependencies 01002 * 01003 */ 01004 forceinline void 01005 IntVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) { 01006 IntVarImpBase::subscribe(home,p,pc,dom.min()==dom.max(),schedule); 01007 } 01008 forceinline void 01009 IntVarImp::cancel(Space& home, Propagator& p, PropCond pc) { 01010 IntVarImpBase::cancel(home,p,pc,dom.min()==dom.max()); 01011 } 01012 01013 forceinline void 01014 IntVarImp::subscribe(Space& home, Advisor& a) { 01015 IntVarImpBase::subscribe(home,a,dom.min()==dom.max()); 01016 } 01017 forceinline void 01018 IntVarImp::cancel(Space& home, Advisor& a) { 01019 IntVarImpBase::cancel(home,a,dom.min()==dom.max()); 01020 } 01021 01022 forceinline ModEventDelta 01023 IntVarImp::med(ModEvent me) { 01024 return IntVarImpBase::med(me); 01025 } 01026 01027 }} 01028 01029 // STATISTICS: int-var