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-06-02 14:54:28 +0200 (Wed, 02 Jun 2010) $ by $Author: schulte $ 00015 * $Revision: 11005 $ 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 Iter::Ranges::IsRangeIter<I>(); 00508 // Is new domain empty? 00509 if (!ri()) 00510 return ME_INT_FAILED; 00511 00512 int min0 = ri.min(); 00513 int max0 = ri.max(); 00514 ++ri; 00515 00516 ModEvent me; 00517 00518 // Is new domain range? 00519 if (!ri()) { 00520 // Remove possible rangelist (if it was not a range, the domain 00521 // must have been narrowed!) 00522 if (fst()) { 00523 fst()->dispose(home,NULL,lst()); 00524 fst(NULL); holes = 0; 00525 } 00526 const int min1 = dom.min(); dom.min(min0); 00527 const int max1 = dom.max(); dom.max(max0); 00528 if ((min0 == min1) && (max0 == max1)) 00529 return ME_INT_NONE; 00530 me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND; 00531 goto notify; 00532 } 00533 00534 if (depends || range()) { 00535 // Construct new rangelist 00536 RangeList* f = new (home) RangeList(min0,max0,NULL,NULL); 00537 RangeList* l = f; 00538 unsigned int s = static_cast<unsigned int>(max0-min0+1); 00539 do { 00540 RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL); 00541 l->next(NULL,n); 00542 l = n; 00543 s += ri.width(); 00544 ++ri; 00545 } while (ri()); 00546 if (fst() != NULL) 00547 fst()->dispose(home,NULL,lst()); 00548 fst(f); lst(l); 00549 00550 // Check for modification 00551 if (size() == s) 00552 return ME_INT_NONE; 00553 00554 const int min1 = dom.min(); min0 = f->min(); dom.min(min0); 00555 const int max1 = dom.max(); max0 = l->max(); dom.max(max0); 00556 holes = width() - s; 00557 00558 me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND; 00559 goto notify; 00560 } else { 00561 // Set up two sentinel elements 00562 RangeList f, l; 00563 // Put all ranges between sentinels 00564 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL); 00565 fst()->prev(NULL,&f); lst()->next(NULL,&l); 00566 00567 // Number of values removed (potential holes) 00568 unsigned int h = 0; 00569 // The previous range 00570 RangeList* p = &f; 00571 // The current range 00572 RangeList* r = f.next(NULL); 00573 00574 while (true) { 00575 assert((r != &f) && (r != &l)); 00576 if (r->max() < min0) { 00577 // Entire range removed 00578 h += r->width(); 00579 RangeList* n=r->next(p); 00580 p->next(r,n); n->prev(r,p); 00581 r->dispose(home); 00582 r=n; 00583 if (r == &l) 00584 goto done; 00585 } else if ((r->min() == min0) && (r->max() == max0)) { 00586 // Range unchanged 00587 RangeList* n=r->next(p); p=r; r=n; 00588 if (r == &l) 00589 goto done; 00590 if (!ri()) 00591 goto done; 00592 min0=ri.min(); max0=ri.max(); ++ri; 00593 } else { 00594 // Range might have been split into many small ranges 00595 assert((r->min() <= min0) && (max0 <= r->max())); 00596 h += r->width(); 00597 int end = r->max(); 00598 // Copy first range 00599 r->min(min0); r->max(max0); 00600 assert(h > r->width()); 00601 h -= r->width(); 00602 { 00603 RangeList* n=r->next(p); p=r; r=n; 00604 } 00605 while (true) { 00606 if (!ri()) 00607 goto done; 00608 min0=ri.min(); max0=ri.max(); ++ri; 00609 if (max0 > end) 00610 break; 00611 assert(h > static_cast<unsigned int>(max0-min0+1)); 00612 h -= max0-min0+1; 00613 RangeList* n = new (home) RangeList(min0,max0,p,r); 00614 p->next(r,n); r->prev(p,n); 00615 p=n; 00616 } 00617 if (r == &l) 00618 goto done; 00619 } 00620 } 00621 done: 00622 00623 // Remove remaining ranges 00624 while (r != &l) { 00625 h += r->width(); 00626 RangeList* n=r->next(p); 00627 p->next(r,n); n->prev(r,p); 00628 r->dispose(home); 00629 r=n; 00630 } 00631 00632 assert((r == &l) && !ri()); 00633 00634 // New first and last ranges 00635 RangeList* fn = f.next(NULL); 00636 RangeList* ln = l.prev(NULL); 00637 00638 // All ranges pruned? 00639 assert(fn != &l); 00640 00641 // Only a single range left? 00642 assert(fn != ln); 00643 00644 // The number of removed values 00645 holes += h; 00646 // Unlink sentinel ranges 00647 fn->prev(&f,NULL); ln->next(&l,NULL); 00648 // How many values where removed at the bounds 00649 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) + 00650 static_cast<unsigned int>(dom.max()-ln->max())); 00651 // Set new first and last ranges 00652 fst(fn); lst(ln); 00653 00654 if (b > 0) { 00655 assert((dom.min() != fn->min()) || (dom.max() != ln->max())); 00656 dom.min(fn->min()); dom.max(ln->max()); 00657 holes -= b; 00658 me = ME_INT_BND; goto notify; 00659 } 00660 00661 if (h > 0) { 00662 assert((dom.min() == fn->min()) && (dom.max() == ln->max())); 00663 me = ME_INT_DOM; goto notify; 00664 } 00665 return ME_INT_NONE; 00666 } 00667 notify: 00668 IntDelta d; 00669 return notify(home,me,d); 00670 } 00671 00672 template<class I> 00673 forceinline ModEvent 00674 IntVarImp::inter_r(Space& home, I& i, bool) { 00675 Iter::Ranges::IsRangeIter<I>(); 00676 IntVarImpFwd j(this); 00677 Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j); 00678 return narrow_r(home,ij,true); 00679 } 00680 00681 template<class I> 00682 forceinline ModEvent 00683 IntVarImp::minus_r(Space& home, I& i, bool depends) { 00684 Iter::Ranges::IsRangeIter<I>(); 00685 if (depends) { 00686 IntVarImpFwd j(this); 00687 Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i); 00688 return narrow_r(home,ij,true); 00689 } 00690 00691 // Skip all ranges that are too small 00692 while (i() && (i.max() < dom.min())) 00693 ++i; 00694 00695 // Is there no range left or all are too large? 00696 if (!i() || (i.min() > dom.max())) 00697 return ME_INT_NONE; 00698 00699 int i_min = i.min(); 00700 int i_max = i.max(); 00701 ++i; 00702 00703 if ((i_min <= dom.min()) && (i_max >= dom.max())) 00704 return ME_INT_FAILED; 00705 00706 if ((i_min > dom.min()) && (i_max >= dom.max())) 00707 return lq(home,i_min-1); 00708 00709 if ((i_min <= dom.min()) && (i_max < dom.max()) && 00710 (!i() || (i.min() > dom.max()))) 00711 return gq(home,i_max+1); 00712 00713 // Set up two sentinel elements 00714 RangeList f, l; 00715 // Put all ranges between sentinels 00716 if (range()) { 00717 // Create a new rangelist just for simplicity 00718 RangeList* n = new (home) RangeList(min(),max(),&f,&l); 00719 f.prevnext(NULL,n); l.prevnext(n,NULL); 00720 } else { 00721 // Link the two sentinel elements 00722 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL); 00723 fst()->prev(NULL,&f); lst()->next(NULL,&l); 00724 } 00725 00726 // Number of values removed (potential holes) 00727 unsigned int h = 0; 00728 // The previous range 00729 RangeList* p = &f; 00730 // The current range 00731 RangeList* r = f.next(NULL); 00732 00733 while (true) { 00734 assert((r != &f) && (r != &l)); 00735 if (i_min > r->max()) { 00736 RangeList* n=r->next(p); p=r; r=n; 00737 if (r == &l) 00738 break; 00739 } else if (i_max < r->min()) { 00740 if (!i()) 00741 break; 00742 i_min = i.min(); 00743 i_max = i.max(); 00744 ++i; 00745 } else if ((i_min <= r->min()) && (r->max() <= i_max)) { 00746 // r is included in i: remove entire range r 00747 h += r->width(); 00748 RangeList* n=r->next(p); 00749 p->next(r,n); n->prev(r,p); 00750 r->dispose(home); 00751 r=n; 00752 if (r == &l) 00753 break; 00754 } else if ((i_min > r->min()) && (i_max < r->max())) { 00755 // i is included in r: create new range before the current one 00756 h += static_cast<unsigned int>(i_max - i_min) + 1; 00757 RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r); 00758 r->min(i_max+1); 00759 p->next(r,n); r->prev(p,n); 00760 p=n; 00761 if (!i()) 00762 break; 00763 i_min = i.min(); 00764 i_max = i.max(); 00765 ++i; 00766 } else if (i_max < r->max()) { 00767 assert(i_min <= r->min()); 00768 // i ends before r: adjust minimum of r 00769 h += i_max-r->min()+1; 00770 r->min(i_max+1); 00771 if (!i()) 00772 break; 00773 i_min = i.min(); 00774 i_max = i.max(); 00775 ++i; 00776 } else { 00777 assert((i_max >= r->max()) && (r->min() < i_min)); 00778 // r ends before i: adjust maximum of r 00779 h += r->max()-i_min+1; 00780 r->max(i_min-1); 00781 RangeList* n=r->next(p); p=r; r=n; 00782 if (r == &l) 00783 break; 00784 } 00785 } 00786 00787 // New first and last ranges 00788 RangeList* fn = f.next(NULL); 00789 RangeList* ln = l.prev(NULL); 00790 00791 // All ranges pruned? 00792 if (fn == &l) { 00793 fst(NULL); lst(NULL); holes=0; 00794 return ME_INT_FAILED; 00795 } 00796 00797 ModEvent me; 00798 unsigned int b; 00799 00800 // Only a single range left? 00801 if (fn == ln) { 00802 assert(h > 0); 00803 dom.min(fn->min()); dom.max(fn->max()); 00804 fn->dispose(home); 00805 fst(NULL); lst(NULL); 00806 holes = 0; 00807 me = assigned() ? ME_INT_VAL : ME_INT_BND; 00808 goto notify; 00809 } 00810 00811 // The number of removed values 00812 holes += h; 00813 // Unlink sentinel ranges 00814 fn->prev(&f,NULL); ln->next(&l,NULL); 00815 // How many values where removed at the bounds 00816 b = (static_cast<unsigned int>(fn->min()-dom.min()) + 00817 static_cast<unsigned int>(dom.max()-ln->max())); 00818 // Set new first and last ranges 00819 fst(fn); lst(ln); 00820 00821 if (b > 0) { 00822 assert((dom.min() != fn->min()) || (dom.max() != ln->max())); 00823 dom.min(fn->min()); dom.max(ln->max()); 00824 holes -= b; 00825 me = ME_INT_BND; goto notify; 00826 } 00827 00828 if (h > 0) { 00829 assert((dom.min() == fn->min()) && (dom.max() == ln->max())); 00830 me = ME_INT_DOM; goto notify; 00831 } 00832 00833 return ME_INT_NONE; 00834 notify: 00835 IntDelta d; 00836 return notify(home,me,d); 00837 } 00838 00839 template<class I> 00840 forceinline ModEvent 00841 IntVarImp::narrow_v(Space& home, I& i, bool depends) { 00842 Iter::Values::IsValueIter<I>(); 00843 Iter::Values::ToRanges<I> r(i); 00844 return narrow_r(home,r,depends); 00845 } 00846 00847 template<class I> 00848 forceinline ModEvent 00849 IntVarImp::inter_v(Space& home, I& i, bool depends) { 00850 Iter::Values::IsValueIter<I>(); 00851 Iter::Values::ToRanges<I> r(i); 00852 return inter_r(home,r,depends); 00853 } 00854 00855 template<class I> 00856 forceinline ModEvent 00857 IntVarImp::minus_v(Space& home, I& i, bool depends) { 00858 Iter::Values::IsValueIter<I>(); 00859 if (depends) { 00860 Iter::Values::ToRanges<I> r(i); 00861 return minus_r(home, r, true); 00862 } 00863 00864 // Skip all values that are too small 00865 while (i() && (i.val() < dom.min())) 00866 ++i; 00867 00868 // Is there no value left or all are too large? 00869 if (!i() || (i.val() > dom.max())) 00870 return ME_INT_NONE; 00871 00872 int v = i.val(); 00873 // Skip values that are the same 00874 do { 00875 ++i; 00876 } while (i() && (i.val() == v)); 00877 00878 // Is there only a single value to be pruned? 00879 if (!i() || (i.val() > dom.max())) 00880 return nq_full(home,v); 00881 00882 // Set up two sentinel elements 00883 RangeList f, l; 00884 // Put all ranges between sentinels 00885 if (range()) { 00886 // Create a new rangelist just for simplicity 00887 RangeList* n = new (home) RangeList(min(),max(),&f,&l); 00888 f.prevnext(NULL,n); l.prevnext(n,NULL); 00889 } else { 00890 // Link the two sentinel elements 00891 f.prevnext(NULL,fst()); l.prevnext(lst(),NULL); 00892 fst()->prev(NULL,&f); lst()->next(NULL,&l); 00893 } 00894 00895 // Number of values removed (potential holes) 00896 unsigned int h = 0; 00897 // The previous range 00898 RangeList* p = &f; 00899 // The current range 00900 RangeList* r = f.next(NULL); 00901 00902 while (true) { 00903 assert((r != &f) && (r != &l)); 00904 if (v > r->max()) { 00905 // Move to next range 00906 RangeList* n=r->next(p); p=r; r=n; 00907 if (r == &l) 00908 break; 00909 } else { 00910 if ((v == r->min()) && (v == r->max())) { 00911 // Remove range 00912 h++; 00913 RangeList* n=r->next(p); 00914 p->next(r,n); n->prev(r,p); 00915 r->dispose(home); 00916 r=n; 00917 if (r == &l) 00918 break; 00919 } else if (v == r->min()) { 00920 h++; r->min(v+1); 00921 } else if (v == r->max()) { 00922 h++; r->max(v-1); 00923 RangeList* n=r->next(p); p=r; r=n; 00924 if (r == &l) 00925 break; 00926 } else if (v > r->min()) { 00927 // Create new range before the current one 00928 assert(v < r->max()); 00929 h++; 00930 RangeList* n = new (home) RangeList(r->min(),v-1,p,r); 00931 r->min(v+1); 00932 p->next(r,n); r->prev(p,n); 00933 p=n; 00934 } 00935 if (!i()) 00936 break; 00937 // Move to next value 00938 v = i.val(); ++i; 00939 } 00940 } 00941 assert((r == &l) || !i()); 00942 00943 // New first and last ranges 00944 RangeList* fn = f.next(NULL); 00945 RangeList* ln = l.prev(NULL); 00946 00947 // All ranges pruned? 00948 if (fn == &l) { 00949 fst(NULL); lst(NULL); holes=0; 00950 return ME_INT_FAILED; 00951 } 00952 00953 IntDelta d; 00954 00955 // Only a single range left? 00956 if (fn == ln) { 00957 assert(h > 0); 00958 dom.min(fn->min()); dom.max(fn->max()); 00959 fn->dispose(home); 00960 fst(NULL); lst(NULL); 00961 holes = 0; 00962 if (assigned()) 00963 return notify(home,ME_INT_VAL,d); 00964 else 00965 return notify(home,ME_INT_BND,d); 00966 } 00967 00968 // The number of removed values 00969 holes += h; 00970 // Unlink sentinel ranges 00971 fn->prev(&f,NULL); ln->next(&l,NULL); 00972 // How many values where removed at the bounds 00973 unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) + 00974 static_cast<unsigned int>(dom.max()-ln->max())); 00975 // Set new first and last ranges 00976 fst(fn); lst(ln); 00977 00978 if (b > 0) { 00979 assert((dom.min() != fn->min()) || (dom.max() != ln->max())); 00980 dom.min(fn->min()); dom.max(ln->max()); 00981 holes -= b; 00982 return notify(home,ME_INT_BND,d); 00983 } 00984 00985 if (h > 0) { 00986 assert((dom.min() == fn->min()) && (dom.max() == ln->max())); 00987 return notify(home,ME_INT_DOM,d); 00988 } 00989 00990 return ME_INT_NONE; 00991 } 00992 00993 00994 /* 00995 * Copying a variable 00996 * 00997 */ 00998 00999 forceinline IntVarImp* 01000 IntVarImp::copy(Space& home, bool share) { 01001 return copied() ? static_cast<IntVarImp*>(forward()) 01002 : perform_copy(home,share); 01003 } 01004 01005 01006 /* 01007 * Dependencies 01008 * 01009 */ 01010 forceinline void 01011 IntVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) { 01012 IntVarImpBase::subscribe(home,p,pc,dom.min()==dom.max(),schedule); 01013 } 01014 forceinline void 01015 IntVarImp::cancel(Space& home, Propagator& p, PropCond pc) { 01016 IntVarImpBase::cancel(home,p,pc,dom.min()==dom.max()); 01017 } 01018 01019 forceinline void 01020 IntVarImp::subscribe(Space& home, Advisor& a) { 01021 IntVarImpBase::subscribe(home,a,dom.min()==dom.max()); 01022 } 01023 forceinline void 01024 IntVarImp::cancel(Space& home, Advisor& a) { 01025 IntVarImpBase::cancel(home,a,dom.min()==dom.max()); 01026 } 01027 01028 forceinline ModEventDelta 01029 IntVarImp::med(ModEvent me) { 01030 return IntVarImpBase::med(me); 01031 } 01032 01033 }} 01034 01035 // STATISTICS: int-var