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

set.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *     Gabor Szokoli <szokoli@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Christian Schulte <schulte@gecode.org>
00009  *
00010  *  Copyright:
00011  *     Guido Tack, 2004
00012  *     Christian Schulte, 2004
00013  *     Gabor Szokoli, 2004
00014  *
00015  *  Last modified:
00016  *     $Date: 2010-06-02 14:54:28 +0200 (Wed, 02 Jun 2010) $ by $Author: schulte $
00017  *     $Revision: 11005 $
00018  *
00019  *  This file is part of Gecode, the generic constraint
00020  *  development environment:
00021  *     http://www.gecode.org
00022  *
00023  *  Permission is hereby granted, free of charge, to any person obtaining
00024  *  a copy of this software and associated documentation files (the
00025  *  "Software"), to deal in the Software without restriction, including
00026  *  without limitation the rights to use, copy, modify, merge, publish,
00027  *  distribute, sublicense, and/or sell copies of the Software, and to
00028  *  permit persons to whom the Software is furnished to do so, subject to
00029  *  the following conditions:
00030  *
00031  *  The above copyright notice and this permission notice shall be
00032  *  included in all copies or substantial portions of the Software.
00033  *
00034  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00035  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00036  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00037  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00038  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00039  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00040  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00041  *
00042  */
00043 
00044 namespace Gecode { namespace Set {
00045 
00046   /*
00047    * Creation of new variable implementations
00048    *
00049    */
00050 
00051   forceinline
00052   SetVarImp::SetVarImp(Space& home)
00053     : SetVarImpBase(home), lub(home), glb(home) {
00054     lub.card(Limits::card);
00055     assert(lub.card()==lub.size());
00056   }
00057 
00058   forceinline
00059   SetVarImp::SetVarImp(Space& home,int lbMin,int lbMax,int ubMin,int ubMax,
00060                        unsigned int cardMin, unsigned int cardMax)
00061     : SetVarImpBase(home),
00062       lub(home,ubMin,ubMax), glb(home,lbMin,lbMax) {
00063     glb.card(std::max(cardMin, glb.size() ));
00064     lub.card(std::min(cardMax, lub.size() ));
00065   }
00066 
00067   forceinline
00068   SetVarImp::SetVarImp(Space& home,
00069                        const IntSet& theGlb,int ubMin,int ubMax,
00070                        unsigned int cardMin, unsigned int cardMax)
00071     : SetVarImpBase(home),
00072       lub(home,ubMin,ubMax), glb(home,theGlb) {
00073     glb.card(std::max(cardMin, glb.size() ));
00074     lub.card(std::min(cardMax, lub.size() ));
00075   }
00076 
00077   forceinline
00078   SetVarImp::SetVarImp(Space& home,
00079                        int lbMin,int lbMax,const IntSet& theLub,
00080                        unsigned int cardMin, unsigned int cardMax)
00081     : SetVarImpBase(home),
00082       lub(home,theLub), glb(home,lbMin,lbMax) {
00083     glb.card(std::max(cardMin, glb.size() ));
00084     lub.card(std::min(cardMax, lub.size() ));
00085   }
00086 
00087   forceinline
00088   SetVarImp::SetVarImp(Space& home,
00089                        const IntSet& theGlb,const IntSet& theLub,
00090                        unsigned int cardMin, unsigned int cardMax)
00091     : SetVarImpBase(home), lub(home,theLub), glb(home,theGlb) {
00092     glb.card(std::max(cardMin, glb.size() ));
00093     lub.card(std::min(cardMax, lub.size() ));
00094   }
00095 
00096 
00097   forceinline bool
00098   SetVarImp::assigned(void) const {
00099     return glb.size() == lub.size();
00100   }
00101 
00102   forceinline unsigned int
00103   SetVarImp::cardMin(void) const { return glb.card(); }
00104 
00105   forceinline unsigned int
00106   SetVarImp::cardMax(void) const { return lub.card(); }
00107 
00108   forceinline bool
00109   SetVarImp::knownIn(int i) const { return (glb.in(i)); }
00110 
00111   forceinline bool
00112   SetVarImp::knownOut(int i) const { return !(lub.in(i)); }
00113 
00114   forceinline int
00115   SetVarImp::lubMin(void) const { return lub.min(); }
00116 
00117   forceinline int
00118   SetVarImp::lubMax(void) const { return lub.max(); }
00119 
00120   forceinline int
00121   SetVarImp::lubMinN(unsigned int n) const { return lub.minN(n); }
00122 
00123   forceinline int
00124   SetVarImp::glbMin(void) const { return glb.min(); }
00125 
00126   forceinline int
00127   SetVarImp::glbMax(void) const { return glb.max(); }
00128 
00129   forceinline unsigned int
00130   SetVarImp::glbSize() const { return glb.size(); }
00131 
00132   forceinline unsigned int
00133   SetVarImp::lubSize() const { return lub.size(); }
00134 
00135   /*
00136    * Support for delta information
00137    *
00138    */
00139   forceinline int
00140   SetVarImp::glbMin(const Delta& d) {
00141     return static_cast<const SetDelta&>(d).glbMin();
00142   }
00143   forceinline int
00144   SetVarImp::glbMax(const Delta& d) {
00145     return static_cast<const SetDelta&>(d).glbMax();
00146   }
00147   forceinline bool
00148   SetVarImp::glbAny(const Delta& d) {
00149     return static_cast<const SetDelta&>(d).glbAny();
00150   }
00151   forceinline int
00152   SetVarImp::lubMin(const Delta& d) {
00153     return static_cast<const SetDelta&>(d).lubMin();
00154   }
00155   forceinline int
00156   SetVarImp::lubMax(const Delta& d) {
00157     return static_cast<const SetDelta&>(d).lubMax();
00158   }
00159   forceinline bool
00160   SetVarImp::lubAny(const Delta& d) {
00161     return static_cast<const SetDelta&>(d).lubAny();
00162   }
00163 
00164   forceinline ModEvent
00165   SetVarImp::cardMin(Space& home,unsigned int newMin) {
00166     if (cardMin() >= newMin)
00167       return ME_SET_NONE;
00168     if (newMin > cardMax())
00169       return ME_SET_FAILED;
00170     glb.card(newMin);
00171     return cardMin_full(home);
00172   }
00173 
00174   forceinline ModEvent
00175   SetVarImp::cardMax(Space& home,unsigned int newMax) {
00176     if (cardMax() <= newMax)
00177       return ME_SET_NONE;
00178     if (cardMin() > newMax)
00179       return ME_SET_FAILED;
00180     lub.card(newMax);
00181     return cardMax_full(home);
00182   }
00183 
00184   forceinline ModEvent
00185   SetVarImp::intersect(Space& home,int i, int j) {
00186     BndSetRanges lb(glb);
00187     Iter::Ranges::Singleton s(i,j);
00188     Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s);
00189     if (probe())
00190       return ME_SET_FAILED;
00191     if (assigned())
00192       return ME_SET_NONE;
00193     int oldMin = lub.min();
00194     int oldMax = lub.max();
00195     if (lub.intersect(home, i, j)) {
00196       SetDelta d;
00197       if (i == oldMin) {
00198         d._lubMin = lub.max()+1;
00199         d._lubMax = oldMax;
00200       } else if (j == oldMax) {
00201         d._lubMin = oldMin;
00202         d._lubMax = lub.min()-1;
00203       }
00204       return processLubChange(home, d);
00205     }
00206     return ME_SET_NONE;
00207   }
00208 
00209   forceinline ModEvent
00210   SetVarImp::intersect(Space& home,int i) {
00211     return intersect(home, i, i);
00212   }
00213 
00214   template<class I>
00215   inline ModEvent
00216   SetVarImp::intersectI(Space& home, I& iterator) {
00217     Iter::Ranges::IsRangeIter<I>();
00218     if (assigned()) {
00219       BndSetRanges lbi(glb);
00220       Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
00221       if (probe())
00222         return ME_SET_FAILED;
00223       return ME_SET_NONE;
00224     }
00225     if (!iterator()) {
00226       if (cardMin() > 0)
00227         return ME_SET_FAILED;
00228       lub.card(0);
00229       SetDelta d(1, 0, lub.min(), lub.max());
00230       lub.excludeAll(home);
00231       return notify(home, ME_SET_VAL, d);
00232     }
00233     int mi=iterator.min();
00234     int ma=iterator.max();
00235     ++iterator;
00236     if (iterator())
00237       return intersectI_full(home, mi, ma, iterator);
00238     else
00239       return intersect(home, mi, ma);
00240   }
00241 
00242   template<class I>
00243   ModEvent
00244   SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
00245     Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00246     if (lub.intersectI(home, si)) {
00247       BndSetRanges ub(lub);
00248       BndSetRanges lb(glb);
00249       if (!Iter::Ranges::subset(lb,ub)) {
00250         glb.become(home, lub);
00251         glb.card(glb.size());
00252         lub.card(glb.size());
00253         return ME_SET_FAILED;
00254       }
00255       ModEvent me = ME_SET_LUB;
00256       if (cardMax() > lub.size()) {
00257         lub.card(lub.size());
00258         if (cardMin() > cardMax()) {
00259           glb.become(home, lub);
00260           glb.card(glb.size());
00261           lub.card(glb.size());
00262           return ME_SET_FAILED;
00263         }
00264         me = ME_SET_CLUB;
00265       }
00266       if (cardMax() == lub.size() && cardMin() == cardMax()) {
00267         glb.become(home, lub);
00268         me = ME_SET_VAL;
00269       }
00270       SetDelta d;
00271       return notify(home, me, d);
00272     }
00273     return ME_SET_NONE;
00274   }
00275 
00276   forceinline ModEvent
00277   SetVarImp::include(Space& home, int i, int j) {
00278     if (j<i)
00279       return ME_SET_NONE;
00280     BndSetRanges ub(lub);
00281     Iter::Ranges::Singleton sij(i,j);
00282     if (!Iter::Ranges::subset(sij,ub)) {
00283       return ME_SET_FAILED;
00284     }
00285     SetDelta d;
00286     if (glb.include(home, i, j, d))
00287       return processGlbChange(home, d);
00288     return ME_SET_NONE;
00289   }
00290 
00291   forceinline ModEvent
00292   SetVarImp::include(Space& home, int i) {
00293     return include(home, i, i);
00294   }
00295 
00296   template<class I> forceinline ModEvent
00297   SetVarImp::includeI(Space& home, I& iterator) {
00298     Iter::Ranges::IsRangeIter<I>();
00299     if (!iterator()) {
00300       return ME_SET_NONE;
00301     }
00302     if (assigned()) {
00303       BndSetRanges lbi(glb);
00304       Iter::Ranges::Diff<I,BndSetRanges>
00305         probe(iterator,lbi);
00306       return probe() ? ME_SET_FAILED : ME_SET_NONE;
00307     }
00308     int mi=iterator.min();
00309     int ma=iterator.max();
00310     ++iterator;
00311     if (iterator())
00312       return includeI_full(home, mi, ma, iterator);
00313     else
00314       return include(home, mi, ma);
00315   }
00316 
00317   template<class I>
00318   ModEvent
00319   SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
00320     Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00321     if (glb.includeI(home, si)) {
00322       BndSetRanges ub(lub);
00323       BndSetRanges lb(glb);
00324       if (!Iter::Ranges::subset(lb,ub)) {
00325         glb.become(home, lub);
00326         glb.card(glb.size());
00327         lub.card(glb.size());
00328         return ME_SET_FAILED;
00329       }
00330       ModEvent me = ME_SET_GLB;
00331       if (cardMin() < glb.size()) {
00332         glb.card(glb.size());
00333         if (cardMin() > cardMax()) {
00334           glb.become(home, lub);
00335           glb.card(glb.size());
00336           lub.card(glb.size());
00337           return ME_SET_FAILED;
00338         }
00339         me = ME_SET_CGLB;
00340       }
00341       if (cardMin() == glb.size() && cardMin() == cardMax()) {
00342         lub.become(home, glb);
00343         me = ME_SET_VAL;
00344       }
00345       SetDelta d;
00346       return notify(home, me, d);
00347     }
00348     return ME_SET_NONE;
00349   }
00350 
00351   forceinline ModEvent
00352   SetVarImp::exclude(Space& home, int i, int j) {
00353     if (j<i)
00354       return ME_SET_NONE;
00355     Iter::Ranges::Singleton sij(i,j);
00356     BndSetRanges lb(glb);
00357     Iter::Ranges::Inter<Iter::Ranges::Singleton,BndSetRanges> probe(sij,lb);
00358     if (probe())
00359       return ME_SET_FAILED;
00360     SetDelta d;
00361     if (lub.exclude(home, i, j, d))
00362       return processLubChange(home, d);
00363     return ME_SET_NONE;
00364   }
00365 
00366   forceinline ModEvent
00367   SetVarImp::exclude(Space& home, int i) {
00368     return exclude(home, i, i);
00369   }
00370 
00371   template<class I>
00372   inline ModEvent
00373   SetVarImp::excludeI(Space& home, I& iterator) {
00374     Iter::Ranges::IsRangeIter<I>();
00375     if (!iterator())
00376       return ME_SET_NONE;
00377     if (assigned()) {
00378       BndSetRanges ubi(lub);
00379       Iter::Ranges::Inter<BndSetRanges,I> probe(ubi,iterator);
00380       return probe() ? ME_SET_FAILED : ME_SET_NONE;
00381     }
00382     int mi=iterator.min();
00383     int ma=iterator.max();
00384     ++iterator;
00385     if (iterator())
00386       return excludeI_full(home, mi, ma, iterator);
00387     else
00388       return exclude(home, mi, ma);
00389   }
00390 
00391   template<class I>
00392   ModEvent
00393   SetVarImp::excludeI_full(Space& home, int mi, int ma, I& iterator) {
00394     Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00395     if (lub.excludeI(home, si)) {
00396       BndSetRanges ub(lub);
00397       BndSetRanges lb(glb);
00398       if (!Iter::Ranges::subset(lb,ub)) {
00399         glb.become(home, lub);
00400         glb.card(glb.size());
00401         lub.card(glb.size());
00402         return ME_SET_FAILED;
00403       }
00404       ModEvent me = ME_SET_LUB;
00405       if (cardMax() > lub.size()) {
00406         lub.card(lub.size());
00407         if (cardMin() > cardMax()) {
00408           glb.become(home, lub);
00409           glb.card(glb.size());
00410           lub.card(glb.size());
00411           return ME_SET_FAILED;
00412         }
00413         me = ME_SET_CLUB;
00414       }
00415       if (cardMax() == lub.size() && cardMin() == cardMax()) {
00416         glb.become(home, lub);
00417         me = ME_SET_VAL;
00418       }
00419       SetDelta d;
00420       return notify(home, me, d);
00421     }
00422     return ME_SET_NONE;
00423   }
00424 
00425   /*
00426    * Copying a variable
00427    *
00428    */
00429 
00430   forceinline SetVarImp*
00431   SetVarImp::copy(Space& home, bool share) {
00432     return copied() ?
00433       static_cast<SetVarImp*>(forward()) :
00434       perform_copy(home,share);
00435   }
00436 
00437   /*
00438    * Iterator specializations
00439    *
00440    */
00441 
00450   template<>
00451   class LubRanges<SetVarImp*> : public BndSetRanges {
00452   public:
00454 
00455 
00456     LubRanges(void);
00458     LubRanges(const SetVarImp*);
00460     void init(const SetVarImp*);
00462   };
00463 
00464   forceinline
00465   LubRanges<SetVarImp*>::LubRanges(void) {}
00466 
00467   forceinline
00468   LubRanges<SetVarImp*>::LubRanges(const SetVarImp* x)
00469     : BndSetRanges(x->lub) {}
00470 
00471   forceinline void
00472   LubRanges<SetVarImp*>::init(const SetVarImp* x) {
00473     BndSetRanges::init(x->lub);
00474   }
00475 
00484   template<>
00485   class GlbRanges<SetVarImp*> : public BndSetRanges {
00486   public:
00488 
00489 
00490     GlbRanges(void);
00492     GlbRanges(const SetVarImp* x);
00494     void init(const SetVarImp*);
00496   };
00497 
00498   forceinline
00499   GlbRanges<SetVarImp*>::GlbRanges(void) {}
00500 
00501   forceinline
00502   GlbRanges<SetVarImp*>::GlbRanges(const SetVarImp* x)
00503     : BndSetRanges(x->glb) {}
00504 
00505   forceinline void
00506   GlbRanges<SetVarImp*>::init(const SetVarImp* x) {
00507     BndSetRanges::init(x->glb);
00508   }
00509 
00510 
00511   /*
00512    * Dependencies
00513    *
00514    */
00515   forceinline void
00516   SetVarImp::subscribe(Space& home, Propagator& p, PropCond pc, bool schedule) {
00517     SetVarImpBase::subscribe(home,p,pc,assigned(),schedule);
00518   }
00519   forceinline void
00520   SetVarImp::cancel(Space& home, Propagator& p, PropCond pc) {
00521     SetVarImpBase::cancel(home,p,pc,assigned());
00522   }
00523   forceinline void
00524   SetVarImp::subscribe(Space& home, Advisor& a) {
00525     SetVarImpBase::subscribe(home,a,assigned());
00526   }
00527   forceinline void
00528   SetVarImp::cancel(Space& home, Advisor& a) {
00529     SetVarImpBase::cancel(home,a,assigned());
00530   }
00531 
00532 }}
00533 
00534 // STATISTICS: set-var