Generated on Thu Jul 6 07:06:47 2006 for Gecode by doxygen 1.4.7

imp.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Contributing authors:
00006  *     Guido Tack <tack@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Christian Schulte, 2003
00010  *     Guido Tack, 2004
00011  *
00012  *  Last modified:
00013  *     $Date: 2005-10-31 11:02:00 +0100 (Mon, 31 Oct 2005) $ by $Author: schulte $
00014  *     $Revision: 2428 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  See the file "LICENSE" for information on usage and
00021  *  redistribution of this file, and for a
00022  *     DISCLAIMER OF ALL WARRANTIES.
00023  *
00024  */
00025 
00026 namespace Gecode { namespace Int {
00027 
00028   /*
00029    * Range lists
00030    *
00031    */
00032 
00033 #define RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
00034 #define PD2RL(p) reinterpret_cast<RangeList*>(p)
00035 
00036   forceinline
00037   IntVarImp::RangeList::RangeList(void) {}
00038 
00039   forceinline
00040   IntVarImp::RangeList::RangeList(int min, int max)
00041     : _min(min), _max(max) {}
00042 
00043   forceinline
00044   IntVarImp::RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
00045     : _min(min), _max(max) {
00046     _next = PD2RL(RL2PD(p)^RL2PD(n)); 
00047   }
00048 
00049   forceinline IntVarImp::RangeList*
00050   IntVarImp::RangeList::next(const RangeList* p) const {
00051     return PD2RL(RL2PD(_next)^RL2PD(p));
00052   }
00053   forceinline IntVarImp::RangeList*
00054   IntVarImp::RangeList::prev(const RangeList* n) const {
00055     return PD2RL(RL2PD(_next)^RL2PD(n));
00056   }
00057   forceinline void
00058   IntVarImp::RangeList::prevnext(RangeList* p, RangeList* n) {
00059     _next = PD2RL(RL2PD(p)^RL2PD(n));
00060   }
00061   forceinline void
00062   IntVarImp::RangeList::next(RangeList* o, RangeList* n) {
00063     _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00064   }
00065   forceinline void
00066   IntVarImp::RangeList::prev(RangeList* o, RangeList* n) {
00067     _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00068   }
00069   forceinline void
00070   IntVarImp::RangeList::fix(RangeList* n) {
00071     _next = n;
00072   }
00073 
00074   forceinline void
00075   IntVarImp::RangeList::min(int n) {
00076     _min = n;
00077   }
00078   forceinline void
00079   IntVarImp::RangeList::max(int n) {
00080     _max = n;
00081   }
00082 
00083   forceinline int
00084   IntVarImp::RangeList::min(void) const {
00085     return _min;
00086   }
00087   forceinline int
00088   IntVarImp::RangeList::max(void) const {
00089     return _max;
00090   }
00091   forceinline unsigned int
00092   IntVarImp::RangeList::width(void) const {
00093     return _max - _min + 1;
00094   }
00095 
00096 
00097   forceinline void
00098   IntVarImp::RangeList::operator delete(void*) {}
00099 
00100   forceinline void
00101   IntVarImp::RangeList::operator delete(void*, Space*) {
00102     assert(false);
00103   }
00104 
00105   forceinline void*
00106   IntVarImp::RangeList::operator new(size_t s, Space* home) {
00107     assert(s == sizeof(RangeList));
00108     return home->fl_alloc<sizeof(RangeList)>();
00109   }
00110 
00111   forceinline void
00112   IntVarImp::RangeList::dispose(Space* home, RangeList* p, RangeList* l) {
00113     RangeList* c = this;
00114     while (c != l) {
00115       RangeList* n = c->next(p);
00116       c->fix(n);
00117       p=c; c=n;
00118     }
00119     home->fl_dispose<sizeof(RangeList)>(this,l);
00120   }
00121 
00122   forceinline void
00123   IntVarImp::RangeList::dispose(Space* home, RangeList* l) {
00124     home->fl_dispose<sizeof(RangeList)>(this,l);
00125   }
00126 
00127   forceinline void
00128   IntVarImp::RangeList::dispose(Space* home) {
00129     home->fl_dispose<sizeof(RangeList)>(this,this);
00130   }
00131 
00132 #undef RL2PD
00133 #undef PD2RL
00134 
00135   /*
00136    * Mainitaining range lists for variable domain
00137    *
00138    */
00139 
00140   forceinline IntVarImp::RangeList*
00141   IntVarImp::fst(void) const {
00142     return dom.next(NULL);
00143   }
00144 
00145   forceinline void
00146   IntVarImp::fst(IntVarImp::RangeList* f) {
00147     dom.prevnext(NULL,f);
00148   }
00149 
00150   forceinline IntVarImp::RangeList*
00151   IntVarImp::lst(void) const {
00152     return _lst;
00153   }
00154 
00155   forceinline void
00156   IntVarImp::lst(IntVarImp::RangeList* l) {
00157     _lst = l;
00158   }
00159 
00160   /*
00161    * Creation of new variable implementations
00162    *
00163    */
00164 
00165   forceinline
00166   IntVarImp::IntVarImp(Space* home, int min, int max)
00167     : Variable<VTI_INT,PC_INT_DOM>(home),
00168       dom(min,max,NULL,NULL), holes(0) {}
00169 
00170   forceinline
00171   IntVarImp::IntVarImp(Space* home, const IntSet& d)
00172     : Variable<VTI_INT,PC_INT_DOM>(home),
00173       dom(d.min(),d.max()) {
00174     if (d.size() > 1) {
00175       int n = d.size();
00176       RangeList* r = reinterpret_cast<RangeList*>
00177         (home->alloc(sizeof(RangeList)*n));
00178       fst(r); lst(r+n-1);
00179       unsigned int h = d.max()-d.min()+1;
00180       for (int i = n; i--; ) {
00181         h -= d.width(i);
00182         r[i].min(d.min(i)); r[i].max(d.max(i));
00183         r[i].prevnext(&r[i-1],&r[i+1]);
00184       }
00185       r[0].prev(&r[-1],NULL); 
00186       r[n-1].next(&r[n],NULL);
00187       holes = h;
00188     } else {
00189       fst(NULL); holes = 0;
00190     }
00191   }
00192 
00193 
00194   /*
00195    * Operations on integer variable implementations
00196    *
00197    */
00198 
00199   forceinline int
00200   IntVarImp::min(void) const {
00201     return dom.min();
00202   }
00203   forceinline int
00204   IntVarImp::max(void) const {
00205     return dom.max();
00206   }
00207   forceinline int
00208   IntVarImp::val(void) const {
00209     assert(dom.min() == dom.max());
00210     return dom.min();
00211   }
00212 
00213   forceinline bool
00214   IntVarImp::range(void) const {
00215     return fst() == NULL;
00216   }
00217   forceinline bool
00218   IntVarImp::assigned(void) const {
00219     return dom.min() == dom.max();
00220   }
00221 
00222 
00223   forceinline unsigned int
00224   IntVarImp::width(void) const {
00225     return dom.width();
00226   }
00227 
00228   forceinline unsigned int
00229   IntVarImp::size(void) const {
00230     return dom.width() - holes;
00231   }
00232 
00233   forceinline unsigned int
00234   IntVarImp::regret_min(void) const {
00235     if (fst() == NULL) {
00236       return (dom.min() == dom.max()) ? 0 : 1;
00237     } else if (dom.min() == fst()->max()) {
00238       return fst()->next(NULL)->min()-dom.min();
00239     } else {
00240       return 1;
00241     }
00242   }
00243   forceinline unsigned int
00244   IntVarImp::regret_max(void) const {
00245     if (lst() == NULL) {
00246       return (dom.min() == dom.max()) ? 0 : 1;
00247     } else if (dom.max() == lst()->min()) {
00248       return dom.max()-lst()->prev(NULL)->max();
00249     } else {
00250       return 1;
00251     }
00252   }
00253 
00254 
00255 
00256   /*
00257    * Tests
00258    *
00259    */
00260 
00261   forceinline bool
00262   IntVarImp::in(int n) const {
00263     if ((n < dom.min()) || (n > dom.max()))
00264       return false;
00265     return (fst() == NULL) || in_full(n);
00266   }
00267   forceinline bool
00268   IntVarImp::in(double n) const {
00269     if ((n < dom.min()) || (n > dom.max()))
00270       return false;
00271     return (fst() == NULL) || in_full(static_cast<int>(n));
00272   }
00273 
00274 
00275   /*
00276    * Accessing rangelists for iteration
00277    *
00278    */
00279 
00280   forceinline const IntVarImp::RangeList*
00281   IntVarImp::ranges_fwd(void) const {
00282     return (fst() == NULL) ? &dom : fst();
00283   }
00284 
00285   forceinline const IntVarImp::RangeList*
00286   IntVarImp::ranges_bwd(void) const {
00287     return (fst() == NULL) ? &dom : lst();
00288   }
00289 
00290 
00291 
00292   /*
00293    * Tell operations (to be inlined: performing bounds checks first)
00294    *
00295    */
00296 
00297   forceinline ModEvent
00298   IntVarImp::gq(Space* home, int n) {
00299     if (n <= dom.min()) return ME_INT_NONE;
00300     if (n > dom.max())  return ME_INT_FAILED;
00301     gq_full(home,n);
00302     if (assigned())
00303       return ME_INT_VAL;
00304     return ME_INT_BND;
00305   }
00306   forceinline ModEvent
00307   IntVarImp::gq(Space* home, double n) {
00308     if (n <= dom.min()) return ME_INT_NONE;
00309     if (n > dom.max())  return ME_INT_FAILED;
00310     gq_full(home,static_cast<int>(n));
00311     if (assigned())
00312       return ME_INT_VAL;
00313     return ME_INT_BND;
00314   }
00315 
00316 
00317   forceinline ModEvent
00318   IntVarImp::lq(Space* home, int n) {
00319     if (n >= dom.max()) return ME_INT_NONE;
00320     if (n < dom.min())  return ME_INT_FAILED;
00321     lq_full(home,n);
00322     if (dom.min() == n)
00323       return ME_INT_VAL;
00324     return ME_INT_BND;
00325   }
00326   forceinline ModEvent
00327   IntVarImp::lq(Space* home, double n) {
00328     if (n >= dom.max()) return ME_INT_NONE;
00329     if (n < dom.min())  return ME_INT_FAILED;
00330     lq_full(home,static_cast<int>(n));
00331     if (dom.max() == n)
00332       return ME_INT_VAL;
00333     return ME_INT_BND;
00334   }
00335 
00336 
00337   forceinline ModEvent
00338   IntVarImp::eq(Space* home, int n) {
00339     if ((n < dom.min()) || (n > dom.max())) 
00340       return ME_INT_FAILED;
00341     if ((n == dom.min()) && (n == dom.max()))
00342       return ME_INT_NONE;
00343     eq_full(home,n);
00344     if (dom.min() == Limits::Int::int_max+1)
00345       return ME_INT_FAILED;
00346     return ME_INT_VAL;
00347   }
00348   forceinline ModEvent
00349   IntVarImp::eq(Space* home, double n) {
00350     if ((n < dom.min()) || (n > dom.max())) 
00351       return ME_INT_FAILED;
00352     if ((n == dom.min()) && (n == dom.max()))
00353       return ME_INT_NONE;
00354     eq_full(home,static_cast<int>(n));
00355     if (dom.min() == Limits::Int::int_max+1)
00356       return ME_INT_FAILED;
00357     return ME_INT_VAL;
00358   }
00359 
00360 
00361   forceinline ModEvent
00362   IntVarImp::nq(Space* home, int n) {
00363     if ((n < dom.min()) || (n > dom.max())) return ME_INT_NONE;
00364     return nq_full(home,n);
00365   }
00366   forceinline ModEvent
00367   IntVarImp::nq(Space* home, double d) {
00368     if ((d < dom.min()) || (d > dom.max())) return ME_INT_NONE;
00369     return nq_full(home,static_cast<int>(d));
00370   }
00371 
00372 
00373   /*
00374    * Tell operations with respect to iterators
00375    *
00376    */
00377 
00378   template <class I>
00379   forceinline ModEvent
00380   IntVarImp::narrow(Space* home, I& ri) {
00381     // Is new domain empty?
00382     if (!ri())
00383       return ME_INT_FAILED;
00384     int min0 = ri.min();
00385     int max0 = ri.max();
00386     ++ri;
00387     // Is new domain range?
00388     if (!ri()) {
00389       // Remove possible rangelist (if it was not a range, the domain
00390       // must have been narrowed!)
00391       if (fst()) {
00392         fst()->dispose(home,NULL,lst());
00393         fst(NULL); holes = 0;
00394       }
00395       const int min1 = dom.min(); dom.min(min0);
00396       const int max1 = dom.max(); dom.max(max0);
00397       if ((min0 == min1) && (max0 == max1))
00398         return ME_INT_NONE;
00399       if (min0 == max0) {
00400         notify(home,ME_INT_VAL);
00401         return ME_INT_VAL;
00402       }
00403     } else {
00404       // Construct new rangelist
00405       RangeList*   f = new (home) RangeList(min0,max0,NULL,NULL);
00406       RangeList*   l = f;
00407       unsigned int s = max0-min0+1;
00408       do {
00409         RangeList* n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
00410         l->next(NULL,n);
00411         l = n;
00412         s += ri.width();
00413         ++ri;
00414       } while (ri());
00415       if (fst() != NULL)
00416         fst()->dispose(home,NULL,lst());
00417       fst(f); lst(l);
00418       // Check for modification
00419       if (size() == s)
00420         return ME_INT_NONE;
00421       const int min1 = dom.min(); min0 = f->min(); dom.min(min0);
00422       const int max1 = dom.max(); max0 = l->max(); dom.max(max0);
00423       holes = width() - s;
00424       if ((min0 == min1) && (max0 == max1)) {
00425         notify(home,ME_INT_DOM);
00426         return ME_INT_DOM;
00427       }
00428     }
00429     notify(home,ME_INT_BND);
00430     return ME_INT_BND;
00431   }
00432 
00433   /*
00434    * Copying a variable
00435    *
00436    */
00437 
00438   forceinline IntVarImp*
00439   IntVarImp::copy(Space* home, bool share) {
00440     return copied() ? static_cast<IntVarImp*>(forward())
00441       : perform_copy(home,share);
00442   }
00443 
00444 
00445 
00446   /*
00447    * Boolean tell operations (assume not yet assigned 0/1 variable)
00448    *
00449    */
00450 
00451   forceinline void
00452   IntVarImp::t_zero_none(Space* home) {
00453     assert((dom.min() == 0) && (dom.max() == 1));
00454     dom.max(0);
00455     notify_unmodified(home,ME_INT_VAL);
00456   }
00457 
00458   forceinline void
00459   IntVarImp::t_one_none(Space* home) {
00460     assert((dom.min() == 0) && (dom.max() == 1));
00461     dom.min(1);
00462     notify_unmodified(home,ME_INT_VAL);
00463   }
00464 
00465 
00466   /*
00467    * Forward range iterator for rangelists
00468    *
00469    */
00470 
00471   forceinline
00472   IntVarImpFwd::IntVarImpFwd(void) {}
00473   forceinline
00474   IntVarImpFwd::IntVarImpFwd(const IntVarImp* x) 
00475     : p(NULL), c(x->ranges_fwd()) {}
00476   forceinline void
00477   IntVarImpFwd::init(const IntVarImp* x) {
00478     p=NULL; c=x->ranges_fwd();
00479   }
00480 
00481   forceinline bool
00482   IntVarImpFwd::operator()(void) const {
00483     return c != NULL;
00484   }
00485   forceinline void
00486   IntVarImpFwd::operator++(void) {
00487     const IntVarImp::RangeList* n=c->next(p); p=c; c=n;
00488   }
00489 
00490   forceinline int
00491   IntVarImpFwd::min(void) const {
00492     return c->min();
00493   }
00494   forceinline int
00495   IntVarImpFwd::max(void) const {
00496     return c->max();
00497   }
00498   forceinline unsigned int
00499   IntVarImpFwd::width(void) const {
00500     return c->width();
00501   }
00502 
00503 
00504   /*
00505    * Backward range iterator for rangelists
00506    *
00507    */
00508 
00509   forceinline
00510   IntVarImpBwd::IntVarImpBwd(void) {}
00511   forceinline
00512   IntVarImpBwd::IntVarImpBwd(const IntVarImp* x) 
00513     : n(NULL), c(x->ranges_bwd()) {}
00514   forceinline void
00515   IntVarImpBwd::init(const IntVarImp* x) {
00516     n=NULL; c=x->ranges_bwd();
00517   }
00518 
00519   forceinline bool
00520   IntVarImpBwd::operator()(void) const {
00521     return c != NULL;
00522   }
00523   forceinline void
00524   IntVarImpBwd::operator++(void) {
00525     const IntVarImp::RangeList* p=c->prev(n); n=c; c=p;
00526   }
00527 
00528   forceinline int
00529   IntVarImpBwd::min(void) const {
00530     return c->min();
00531   }
00532   forceinline int
00533   IntVarImpBwd::max(void) const {
00534     return c->max();
00535   }
00536   forceinline unsigned int
00537   IntVarImpBwd::width(void) const {
00538     return c->width();
00539   }
00540 
00541 
00542   /*
00543    * More domain operations
00544    *
00545    */
00546   template <class I>
00547   forceinline ModEvent
00548   IntVarImp::inter(Space* home, I& i) {
00549     IntVarImpFwd j(this);
00550     Iter::Ranges::Inter<I,IntVarImpFwd> ij(i,j);
00551     return narrow(home,ij);
00552   }
00553 
00554   template <class I>
00555   forceinline ModEvent
00556   IntVarImp::minus(Space* home, I& i) {
00557     IntVarImpFwd j(this);
00558     Iter::Ranges::Diff<IntVarImpFwd,I> ij(j,i);
00559     return narrow(home,ij);
00560   }
00561 
00562 }}
00563 
00564 // STATISTICS: int-var
00565