Generated on Fri Oct 19 11:25:05 2018 for Gecode by doxygen 1.6.3

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  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Int {
00039 
00040   /*
00041    * Range lists
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    * Mainitaining range lists for variable domain
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    * Creation of new variable implementations
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    * Operations on integer variable implementations
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    * Tests
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    * Accessing rangelists for iteration
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    * Support for delta information
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    * 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 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    * Forward range iterator for rangelists
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    * Backward range iterator for rangelists
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    * Iterator-based domain operations
00499    *
00500    */
00501   template<class I>
00502   forceinline ModEvent
00503   IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
00504     // Is new domain empty?
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     // Is new domain range?
00515     if (!ri()) {
00516       // Remove possible rangelist (if it was not a range, the domain
00517       // must have been narrowed!)
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       // Construct new rangelist
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       // Check for modification
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       // Set up two sentinel elements
00558       RangeList f, l;
00559       // Put all ranges between sentinels
00560       f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00561       fst()->prev(NULL,&f);   lst()->next(NULL,&l);
00562 
00563       // Number of values removed (potential holes)
00564       unsigned int h = 0;
00565       // The previous range
00566       RangeList* p = &f;
00567       // The current range
00568       RangeList* r = f.next(NULL);
00569 
00570       while (true) {
00571         assert((r != &f) && (r != &l));
00572         if (r->max() < min0) {
00573           // Entire range removed
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           // Range unchanged
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           // Range might have been split into many small ranges
00591           assert((r->min() <= min0) && (max0 <= r->max()));
00592           h += r->width();
00593           int end = r->max();
00594           // Copy first range
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       // Remove remaining ranges
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       // New first and last ranges
00631       RangeList* fn = f.next(NULL);
00632       RangeList* ln = l.prev(NULL);
00633 
00634       // All ranges pruned?
00635       assert(fn != &l);
00636 
00637       // Only a single range left?
00638       assert(fn != ln);
00639 
00640       // The number of removed values
00641       holes += h;
00642       // Unlink sentinel ranges
00643       fn->prev(&f,NULL); ln->next(&l,NULL);
00644       // How many values where removed at the bounds
00645       unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00646                         static_cast<unsigned int>(dom.max()-ln->max()));
00647       // Set new first and last ranges
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     // Skip all ranges that are too small
00686     while (i() && (i.max() < dom.min()))
00687       ++i;
00688 
00689     // Is there no range left or all are too large?
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     // Set up two sentinel elements
00708     RangeList f, l;
00709     // Put all ranges between sentinels
00710     if (range()) {
00711       // Create a new rangelist just for simplicity
00712       RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00713       f.prevnext(NULL,n); l.prevnext(n,NULL);
00714     } else {
00715       // Link the two sentinel elements
00716       f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00717       fst()->prev(NULL,&f);   lst()->next(NULL,&l);
00718     }
00719 
00720     // Number of values removed (potential holes)
00721     unsigned int h = 0;
00722     // The previous range
00723     RangeList* p = &f;
00724     // The current range
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         // r is included in i: remove entire range r
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         // i is included in r: create new range before the current one
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         // i ends before r: adjust minimum of r
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         // r ends before i: adjust maximum of r
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     // New first and last ranges
00782     RangeList* fn = f.next(NULL);
00783     RangeList* ln = l.prev(NULL);
00784 
00785     // All ranges pruned?
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     // Only a single range left?
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     // The number of removed values
00806     holes += h;
00807     // Unlink sentinel ranges
00808     fn->prev(&f,NULL); ln->next(&l,NULL);
00809     // How many values where removed at the bounds
00810     b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00811          static_cast<unsigned int>(dom.max()-ln->max()));
00812     // Set new first and last ranges
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     // Skip all values that are too small
00856     while (i() && (i.val() < dom.min()))
00857       ++i;
00858 
00859     // Is there no value left or all are too large?
00860     if (!i() || (i.val() > dom.max()))
00861       return ME_INT_NONE;
00862 
00863     int v = i.val();
00864     // Skip values that are the same
00865     do {
00866       ++i;
00867     } while (i() && (i.val() == v));
00868 
00869     // Is there only a single value to be pruned?
00870     if (!i() || (i.val() > dom.max()))
00871       return nq_full(home,v);
00872 
00873     // Set up two sentinel elements
00874     RangeList f, l;
00875     // Put all ranges between sentinels
00876     if (range()) {
00877       // Create a new rangelist just for simplicity
00878       RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00879       f.prevnext(NULL,n); l.prevnext(n,NULL);
00880     } else {
00881       // Link the two sentinel elements
00882       f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00883       fst()->prev(NULL,&f);   lst()->next(NULL,&l);
00884     }
00885 
00886     // Number of values removed (potential holes)
00887     unsigned int h = 0;
00888     // The previous range
00889     RangeList* p = &f;
00890     // The current range
00891     RangeList* r = f.next(NULL);
00892 
00893     while (true) {
00894       assert((r != &f) && (r != &l));
00895       if (v > r->max()) {
00896         // Move to next range
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           // Remove range
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           // Create new range before the current one
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         // Move to next value
00929         v = i.val(); ++i;
00930       }
00931     }
00932     assert((r == &l) || !i());
00933 
00934     // New first and last ranges
00935     RangeList* fn = f.next(NULL);
00936     RangeList* ln = l.prev(NULL);
00937 
00938     // All ranges pruned?
00939     if (fn == &l) {
00940       fst(NULL); lst(NULL); holes=0;
00941       return fail(home);
00942     }
00943 
00944     IntDelta d;
00945 
00946     // Only a single range left?
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     // The number of removed values
00960     holes += h;
00961     // Unlink sentinel ranges
00962     fn->prev(&f,NULL); ln->next(&l,NULL);
00963     // How many values where removed at the bounds
00964     unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00965                       static_cast<unsigned int>(dom.max()-ln->max()));
00966     // Set new first and last ranges
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    * Copying a variable
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 // STATISTICS: int-var