Generated on Tue Jul 27 2010 21:59:12 for Gecode by doxygen 1.7.1

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