Generated on Mon Nov 30 23:53:24 2009 for Gecode by doxygen 1.6.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: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
00015  *     $Revision: 9692 $
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 ModEvent
00325   IntVarImp::modevent(const Delta& d) {
00326     return d.modevent();
00327   }
00328   forceinline int
00329   IntVarImp::min(const Delta& d) {
00330     return static_cast<const IntDelta&>(d).min();
00331   }
00332   forceinline int
00333   IntVarImp::max(const Delta& d) {
00334     return static_cast<const IntDelta&>(d).max();
00335   }
00336   forceinline bool
00337   IntVarImp::any(const Delta& d) {
00338     return static_cast<const IntDelta&>(d).any();
00339   }
00340 
00341 
00342   /*
00343    * Tell operations (to be inlined: performing bounds checks first)
00344    *
00345    */
00346 
00347   forceinline ModEvent
00348   IntVarImp::gq(Space& home, int n) {
00349     if (n <= dom.min()) return ME_INT_NONE;
00350     if (n > dom.max())  return ME_INT_FAILED;
00351     ModEvent me = gq_full(home,n);
00352     GECODE_ASSUME((me == ME_INT_FAILED) |
00353                   (me == ME_INT_VAL) |
00354                   (me == ME_INT_BND));
00355     return me;
00356   }
00357   forceinline ModEvent
00358   IntVarImp::gq(Space& home, double n) {
00359     if (n <= dom.min()) return ME_INT_NONE;
00360     if (n > dom.max())  return ME_INT_FAILED;
00361     ModEvent me = gq_full(home,static_cast<int>(n));
00362     GECODE_ASSUME((me == ME_INT_FAILED) |
00363                   (me == ME_INT_VAL) |
00364                   (me == ME_INT_BND));
00365     return me;
00366   }
00367 
00368 
00369   forceinline ModEvent
00370   IntVarImp::lq(Space& home, int n) {
00371     if (n >= dom.max()) return ME_INT_NONE;
00372     if (n < dom.min())  return ME_INT_FAILED;
00373     ModEvent me = lq_full(home,n);
00374     GECODE_ASSUME((me == ME_INT_FAILED) |
00375                   (me == ME_INT_VAL) |
00376                   (me == ME_INT_BND));
00377     return me;
00378   }
00379   forceinline ModEvent
00380   IntVarImp::lq(Space& home, double n) {
00381     if (n >= dom.max()) return ME_INT_NONE;
00382     if (n < dom.min())  return ME_INT_FAILED;
00383     ModEvent me = lq_full(home,static_cast<int>(n));
00384     GECODE_ASSUME((me == ME_INT_FAILED) |
00385                   (me == ME_INT_VAL) |
00386                   (me == ME_INT_BND));
00387     return me;
00388   }
00389 
00390 
00391   forceinline ModEvent
00392   IntVarImp::eq(Space& home, int n) {
00393     if ((n < dom.min()) || (n > dom.max()))
00394       return ME_INT_FAILED;
00395     if ((n == dom.min()) && (n == dom.max()))
00396       return ME_INT_NONE;
00397     ModEvent me = eq_full(home,n);
00398     GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
00399     return me;
00400   }
00401   forceinline ModEvent
00402   IntVarImp::eq(Space& home, double m) {
00403     if ((m < dom.min()) || (m > dom.max()))
00404       return ME_INT_FAILED;
00405     int n = static_cast<int>(m);
00406     if ((n == dom.min()) && (n == dom.max()))
00407       return ME_INT_NONE;
00408     ModEvent me = eq_full(home,n);
00409     GECODE_ASSUME((me == ME_INT_FAILED) | (me == ME_INT_VAL));
00410     return me;
00411   }
00412 
00413 
00414   forceinline ModEvent
00415   IntVarImp::nq(Space& home, int n) {
00416     if ((n < dom.min()) || (n > dom.max()))
00417       return ME_INT_NONE;
00418     return nq_full(home,n);
00419   }
00420   forceinline ModEvent
00421   IntVarImp::nq(Space& home, double d) {
00422     if ((d < dom.min()) || (d > dom.max()))
00423       return ME_INT_NONE;
00424     return nq_full(home,static_cast<int>(d));
00425   }
00426 
00427 
00428   /*
00429    * Forward range iterator for rangelists
00430    *
00431    */
00432 
00433   forceinline
00434   IntVarImpFwd::IntVarImpFwd(void) {}
00435   forceinline
00436   IntVarImpFwd::IntVarImpFwd(const IntVarImp* x)
00437     : p(NULL), c(x->ranges_fwd()) {}
00438   forceinline void
00439   IntVarImpFwd::init(const IntVarImp* x) {
00440     p=NULL; c=x->ranges_fwd();
00441   }
00442 
00443   forceinline bool
00444   IntVarImpFwd::operator ()(void) const {
00445     return c != NULL;
00446   }
00447   forceinline void
00448   IntVarImpFwd::operator ++(void) {
00449     const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
00450   }
00451 
00452   forceinline int
00453   IntVarImpFwd::min(void) const {
00454     return c->min();
00455   }
00456   forceinline int
00457   IntVarImpFwd::max(void) const {
00458     return c->max();
00459   }
00460   forceinline unsigned int
00461   IntVarImpFwd::width(void) const {
00462     return c->width();
00463   }
00464 
00465 
00466   /*
00467    * Backward range iterator for rangelists
00468    *
00469    */
00470 
00471   forceinline
00472   IntVarImpBwd::IntVarImpBwd(void) {}
00473   forceinline
00474   IntVarImpBwd::IntVarImpBwd(const IntVarImp* x)
00475     : n(NULL), c(x->ranges_bwd()) {}
00476   forceinline void
00477   IntVarImpBwd::init(const IntVarImp* x) {
00478     n=NULL; c=x->ranges_bwd();
00479   }
00480 
00481   forceinline bool
00482   IntVarImpBwd::operator ()(void) const {
00483     return c != NULL;
00484   }
00485   forceinline void
00486   IntVarImpBwd::operator ++(void) {
00487     const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
00488   }
00489 
00490   forceinline int
00491   IntVarImpBwd::min(void) const {
00492     return c->min();
00493   }
00494   forceinline int
00495   IntVarImpBwd::max(void) const {
00496     return c->max();
00497   }
00498   forceinline unsigned int
00499   IntVarImpBwd::width(void) const {
00500     return c->width();
00501   }
00502 
00503 
00504   /*
00505    * Iterator-based domain operations
00506    *
00507    */
00508   template<class I>
00509   forceinline ModEvent
00510   IntVarImp::narrow_r(Space& home, I& ri, bool depends) {
00511     Iter::Ranges::IsRangeIter<I>();
00512     // Is new domain empty?
00513     if (!ri())
00514       return ME_INT_FAILED;
00515 
00516     int min0 = ri.min();
00517     int max0 = ri.max();
00518     ++ri;
00519 
00520     ModEvent me;
00521 
00522     // Is new domain range?
00523     if (!ri()) {
00524       // Remove possible rangelist (if it was not a range, the domain
00525       // must have been narrowed!)
00526       if (fst()) {
00527         fst()->dispose(home,NULL,lst());
00528         fst(NULL); holes = 0;
00529       }
00530       const int min1 = dom.min(); dom.min(min0);
00531       const int max1 = dom.max(); dom.max(max0);
00532       if ((min0 == min1) && (max0 == max1))
00533         return ME_INT_NONE;
00534       me = (min0 == max0) ? ME_INT_VAL : ME_INT_BND;
00535       goto notify;
00536     }
00537 
00538     if (depends || range()) {
00539       // Construct new rangelist
00540       RangeList*   f = new (home) RangeList(min0,max0,NULL,NULL);
00541       RangeList*   l = f;
00542       unsigned int s = static_cast<unsigned int>(max0-min0+1);
00543       do {
00544         RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
00545         l->next(NULL,n);
00546         l = n;
00547         s += ri.width();
00548         ++ri;
00549       } while (ri());
00550       if (fst() != NULL)
00551         fst()->dispose(home,NULL,lst());
00552       fst(f); lst(l);
00553 
00554       // Check for modification
00555       if (size() == s)
00556         return ME_INT_NONE;
00557 
00558       const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
00559       const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
00560       holes = width() - s;
00561 
00562       me = ((min0 == min1) && (max0 == max1)) ? ME_INT_DOM : ME_INT_BND;
00563       goto notify;
00564     } else {
00565       // Set up two sentinel elements
00566       RangeList f, l;
00567       // Put all ranges between sentinels
00568       f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00569       fst()->prev(NULL,&f);   lst()->next(NULL,&l);
00570 
00571       // Number of values removed (potential holes)
00572       unsigned int h = 0;
00573       // The previous range
00574       RangeList* p = &f;
00575       // The current range
00576       RangeList* r = f.next(NULL);
00577 
00578       while (true) {
00579         assert((r != &f) && (r != &l));
00580         if (r->max() < min0) {
00581           // Entire range removed
00582           h += r->width();
00583           RangeList* n=r->next(p);
00584           p->next(r,n); n->prev(r,p);
00585           r->dispose(home);
00586           r=n;
00587           if (r == &l)
00588             goto done;
00589         } else if ((r->min() == min0) && (r->max() == max0)) {
00590           // Range unchanged
00591           RangeList* n=r->next(p); p=r; r=n;
00592           if (r == &l)
00593             goto done;
00594           if (!ri())
00595             goto done;
00596           min0=ri.min(); max0=ri.max(); ++ri;
00597         } else {
00598           // Range might have been split into many small ranges
00599           assert((r->min() <= min0) && (max0 <= r->max()));
00600           h += r->width();
00601           int end = r->max();
00602           // Copy first range
00603           r->min(min0); r->max(max0);
00604           assert(h > r->width());
00605           h -= r->width();
00606           {
00607             RangeList* n=r->next(p); p=r; r=n;
00608           }
00609           while (true) {
00610             if (!ri())
00611               goto done;
00612             min0=ri.min(); max0=ri.max(); ++ri;
00613             if (max0 > end)
00614               break;
00615             assert(h > static_cast<unsigned int>(max0-min0+1));
00616             h -= max0-min0+1;
00617             RangeList* n = new (home) RangeList(min0,max0,p,r);
00618             p->next(r,n); r->prev(p,n);
00619             p=n;
00620           }
00621           if (r == &l)
00622             goto done;
00623         }
00624       }
00625     done:
00626 
00627       // Remove remaining ranges
00628       while (r != &l) {
00629         h += r->width();
00630         RangeList* n=r->next(p);
00631         p->next(r,n); n->prev(r,p);
00632         r->dispose(home);
00633         r=n;
00634       }
00635 
00636       assert((r == &l) && !ri());
00637 
00638       // New first and last ranges
00639       RangeList* fn = f.next(NULL);
00640       RangeList* ln = l.prev(NULL);
00641 
00642       // All ranges pruned?
00643       assert(fn != &l);
00644 
00645       // Only a single range left?
00646       assert(fn != ln);
00647 
00648       // The number of removed values
00649       holes += h;
00650       // Unlink sentinel ranges
00651       fn->prev(&f,NULL); ln->next(&l,NULL);
00652       // How many values where removed at the bounds
00653       unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00654                         static_cast<unsigned int>(dom.max()-ln->max()));
00655       // Set new first and last ranges
00656       fst(fn); lst(ln);
00657 
00658       if (b > 0) {
00659         assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00660         dom.min(fn->min()); dom.max(ln->max());
00661         holes -= b;
00662         me = ME_INT_BND; goto notify;
00663       }
00664 
00665       if (h > 0) {
00666         assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00667         me = ME_INT_DOM; goto notify;
00668       }
00669       return ME_INT_NONE;
00670     }
00671   notify:
00672     IntDelta d;
00673     return notify(home,me,d);
00674   }
00675 
00676   template<class I>
00677   forceinline ModEvent
00678   IntVarImp::inter_r(Space& home, I& i, bool) {
00679     Iter::Ranges::IsRangeIter<I>();
00680     IntVarImpFwd j(this);
00681     Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
00682     return narrow_r(home,ij,true);
00683   }
00684 
00685   template<class I>
00686   forceinline ModEvent
00687   IntVarImp::minus_r(Space& home, I& i, bool depends) {
00688     Iter::Ranges::IsRangeIter<I>();
00689     if (depends) {
00690       IntVarImpFwd j(this);
00691       Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
00692       return narrow_r(home,ij,true);
00693     }
00694 
00695     // Skip all ranges that are too small
00696     while (i() && (i.max() < dom.min()))
00697       ++i;
00698 
00699     // Is there no range left or all are too large?
00700     if (!i() || (i.min() > dom.max()))
00701       return ME_INT_NONE;
00702 
00703     int i_min = i.min();
00704     int i_max = i.max();
00705     ++i;
00706 
00707     if ((i_min <= dom.min()) && (i_max >= dom.max()))
00708       return ME_INT_FAILED;
00709 
00710     if ((i_min > dom.min()) && (i_max >= dom.max()))
00711       return lq(home,i_min-1);
00712     
00713     if ((i_min <= dom.min()) && (i_max < dom.max()) &&
00714         (!i() || (i.min() > dom.max())))
00715       return gq(home,i_max+1);
00716 
00717     // Set up two sentinel elements
00718     RangeList f, l;
00719     // Put all ranges between sentinels
00720     if (range()) {
00721       // Create a new rangelist just for simplicity
00722       RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00723       f.prevnext(NULL,n); l.prevnext(n,NULL);
00724     } else {
00725       // Link the two sentinel elements
00726       f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00727       fst()->prev(NULL,&f);   lst()->next(NULL,&l);
00728     }
00729 
00730     // Number of values removed (potential holes)
00731     unsigned int h = 0;
00732     // The previous range
00733     RangeList* p = &f;
00734     // The current range
00735     RangeList* r = f.next(NULL);
00736 
00737     while (true) {
00738       assert((r != &f) && (r != &l));
00739       if (i_min > r->max()) {
00740         RangeList* n=r->next(p); p=r; r=n;
00741         if (r == &l)
00742           break;
00743       } else if (i_max < r->min()) {
00744         if (!i())
00745           break;
00746         i_min = i.min();
00747         i_max = i.max();
00748         ++i;
00749       } else if ((i_min <= r->min()) && (r->max() <= i_max)) {
00750         // r is included in i: remove entire range r
00751         h += r->width();
00752         RangeList* n=r->next(p);
00753         p->next(r,n); n->prev(r,p);
00754         r->dispose(home);
00755         r=n;
00756         if (r == &l)
00757           break;
00758       } else if ((i_min > r->min()) && (i_max < r->max())) {
00759         // i is included in r: create new range before the current one
00760         h += static_cast<unsigned int>(i_max - i_min) + 1;
00761         RangeList* n = new (home) RangeList(r->min(),i_min-1,p,r);
00762         r->min(i_max+1);
00763         p->next(r,n); r->prev(p,n);
00764         p=n;
00765         if (!i())
00766           break;
00767         i_min = i.min();
00768         i_max = i.max();
00769         ++i;
00770       } else if (i_max < r->max()) {
00771         assert(i_min <= r->min());
00772         // i ends before r: adjust minimum of r
00773         h += i_max-r->min()+1;
00774         r->min(i_max+1);
00775         if (!i())
00776           break;
00777         i_min = i.min();
00778         i_max = i.max();
00779         ++i;
00780       } else {
00781         assert((i_max >= r->max()) && (r->min() < i_min));
00782         // r ends before i: adjust maximum of r
00783         h += r->max()-i_min+1;
00784         r->max(i_min-1);
00785         RangeList* n=r->next(p); p=r; r=n;
00786         if (r == &l)
00787           break;
00788       }
00789     }
00790 
00791     // New first and last ranges
00792     RangeList* fn = f.next(NULL);
00793     RangeList* ln = l.prev(NULL);
00794 
00795     // All ranges pruned?
00796     if (fn == &l) {
00797       fst(NULL); lst(NULL); holes=0;
00798       return ME_INT_FAILED;
00799     }
00800 
00801     ModEvent me;
00802     unsigned int b;
00803 
00804     // Only a single range left?
00805     if (fn == ln) {
00806       assert(h > 0);
00807       dom.min(fn->min()); dom.max(fn->max());
00808       fn->dispose(home);
00809       fst(NULL); lst(NULL);
00810       holes = 0;
00811       me = assigned() ? ME_INT_VAL : ME_INT_BND;
00812       goto notify;
00813     }
00814 
00815     // The number of removed values
00816     holes += h;
00817     // Unlink sentinel ranges
00818     fn->prev(&f,NULL); ln->next(&l,NULL);
00819     // How many values where removed at the bounds
00820     b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00821          static_cast<unsigned int>(dom.max()-ln->max()));
00822     // Set new first and last ranges
00823     fst(fn); lst(ln);
00824 
00825     if (b > 0) {
00826       assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00827       dom.min(fn->min()); dom.max(ln->max());
00828       holes -= b;
00829       me = ME_INT_BND; goto notify;
00830     }
00831 
00832     if (h > 0) {
00833       assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00834       me = ME_INT_DOM; goto notify;
00835     }
00836 
00837     return ME_INT_NONE;
00838   notify:
00839     IntDelta d;
00840     return notify(home,me,d);
00841   }
00842 
00843   template<class I>
00844   forceinline ModEvent
00845   IntVarImp::narrow_v(Space& home, I& i, bool depends) {
00846     Iter::Values::IsValueIter<I>();
00847     Iter::Values::ToRanges<I> r(i);
00848     return narrow_r(home,r,depends);
00849   }
00850 
00851   template<class I>
00852   forceinline ModEvent
00853   IntVarImp::inter_v(Space& home, I& i, bool depends) {
00854     Iter::Values::IsValueIter<I>();
00855     Iter::Values::ToRanges<I> r(i);
00856     return inter_r(home,r,depends);
00857   }
00858 
00859   template<class I>
00860   forceinline ModEvent
00861   IntVarImp::minus_v(Space& home, I& i, bool depends) {
00862     Iter::Values::IsValueIter<I>();
00863     if (depends) {
00864       Iter::Values::ToRanges<I> r(i);
00865       return minus_r(home, r, true);
00866     }
00867 
00868     // Skip all values that are too small
00869     while (i() && (i.val() < dom.min()))
00870       ++i;
00871 
00872     // Is there no value left or all are too large?
00873     if (!i() || (i.val() > dom.max()))
00874       return ME_INT_NONE;
00875 
00876     int v = i.val();
00877     // Skip values that are the same
00878     do {
00879       ++i;
00880     } while (i() && (i.val() == v));
00881 
00882     // Is there only a single value to be pruned?
00883     if (!i() || (i.val() > dom.max()))
00884       return nq_full(home,v);
00885 
00886     // Set up two sentinel elements
00887     RangeList f, l;
00888     // Put all ranges between sentinels
00889     if (range()) {
00890       // Create a new rangelist just for simplicity
00891       RangeList* n = new (home) RangeList(min(),max(),&f,&l);
00892       f.prevnext(NULL,n); l.prevnext(n,NULL);
00893     } else {
00894       // Link the two sentinel elements
00895       f.prevnext(NULL,fst()); l.prevnext(lst(),NULL);
00896       fst()->prev(NULL,&f);   lst()->next(NULL,&l);
00897     }
00898 
00899     // Number of values removed (potential holes)
00900     unsigned int h = 0;
00901     // The previous range
00902     RangeList* p = &f;
00903     // The current range
00904     RangeList* r = f.next(NULL);
00905 
00906     while (true) {
00907       assert((r != &f) && (r != &l));
00908       if (v > r->max()) {
00909         // Move to next range
00910         RangeList* n=r->next(p); p=r; r=n;
00911         if (r == &l)
00912           break;
00913       } else {
00914         if ((v == r->min()) && (v == r->max())) {
00915           // Remove range
00916           h++;
00917           RangeList* n=r->next(p);
00918           p->next(r,n); n->prev(r,p);
00919           r->dispose(home);
00920           r=n;
00921           if (r == &l)
00922             break;
00923         } else if (v == r->min()) {
00924           h++; r->min(v+1);
00925         } else if (v == r->max()) {
00926           h++; r->max(v-1);
00927           RangeList* n=r->next(p); p=r; r=n;
00928           if (r == &l)
00929             break;
00930         } else if (v > r->min()) {
00931           // Create new range before the current one
00932           assert(v < r->max());
00933           h++;
00934           RangeList* n = new (home) RangeList(r->min(),v-1,p,r);
00935           r->min(v+1);
00936           p->next(r,n); r->prev(p,n);
00937           p=n;
00938         }
00939         if (!i())
00940           break;
00941         // Move to next value
00942         v = i.val(); ++i;
00943       }
00944     }
00945     assert((r == &l) || !i());
00946 
00947     // New first and last ranges
00948     RangeList* fn = f.next(NULL);
00949     RangeList* ln = l.prev(NULL);
00950 
00951     // All ranges pruned?
00952     if (fn == &l) {
00953       fst(NULL); lst(NULL); holes=0;
00954       return ME_INT_FAILED;
00955     }
00956 
00957     IntDelta d;
00958 
00959     // Only a single range left?
00960     if (fn == ln) {
00961       assert(h > 0);
00962       dom.min(fn->min()); dom.max(fn->max());
00963       fn->dispose(home);
00964       fst(NULL); lst(NULL);
00965       holes = 0;
00966       if (assigned())
00967         return notify(home,ME_INT_VAL,d);
00968       else
00969         return notify(home,ME_INT_BND,d);
00970     }
00971 
00972     // The number of removed values
00973     holes += h;
00974     // Unlink sentinel ranges
00975     fn->prev(&f,NULL); ln->next(&l,NULL);
00976     // How many values where removed at the bounds
00977     unsigned int b = (static_cast<unsigned int>(fn->min()-dom.min()) +
00978                       static_cast<unsigned int>(dom.max()-ln->max()));
00979     // Set new first and last ranges
00980     fst(fn); lst(ln);
00981 
00982     if (b > 0) {
00983       assert((dom.min() != fn->min()) || (dom.max() != ln->max()));
00984       dom.min(fn->min()); dom.max(ln->max());
00985       holes -= b;
00986       return notify(home,ME_INT_BND,d);
00987     }
00988 
00989     if (h > 0) {
00990       assert((dom.min() == fn->min()) && (dom.max() == ln->max()));
00991       return notify(home,ME_INT_DOM,d);
00992     }
00993 
00994     return ME_INT_NONE;
00995   }
00996 
00997 
00998   /*
00999    * Copying a variable
01000    *
01001    */
01002 
01003   forceinline IntVarImp*
01004   IntVarImp::copy(Space& home, bool share) {
01005     return copied() ? static_cast<IntVarImp*>(forward())
01006       : perform_copy(home,share);
01007   }
01008 
01009 
01010   /*
01011    * Dependencies
01012    *
01013    */
01014   forceinline void
01015   IntVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool process) {
01016     IntVarImpBase::subscribe(home,p,pc,dom.min()==dom.max(),process);
01017   }
01018   forceinline void
01019   IntVarImp::cancel(Space& home, Propagator& p, PropCond pc) {
01020     IntVarImpBase::cancel(home,p,pc,dom.min()==dom.max());
01021   }
01022 
01023   forceinline void
01024   IntVarImp::subscribe(Space& home, Advisor& a) {
01025     IntVarImpBase::subscribe(home,a,dom.min()==dom.max());
01026   }
01027   forceinline void
01028   IntVarImp::cancel(Space& home, Advisor& a) {
01029     IntVarImpBase::cancel(home,a,dom.min()==dom.max());
01030   }
01031 
01032   forceinline ModEventDelta
01033   IntVarImp::med(ModEvent me) {
01034     return IntVarImpBase::med(me);
01035   }
01036 
01037 }}
01038 
01039 // STATISTICS: int-var