Generated on Mon Nov 30 23:53:37 2009 for Gecode by doxygen 1.6.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: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
00017  *     $Revision: 9692 $
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 ModEvent
00140   SetVarImp::modevent(const Delta& d) {
00141     return d.modevent();
00142   }
00143   forceinline int
00144   SetVarImp::glbMin(const Delta& d) {
00145     return static_cast<const SetDelta&>(d).glbMin();
00146   }
00147   forceinline int
00148   SetVarImp::glbMax(const Delta& d) {
00149     return static_cast<const SetDelta&>(d).glbMax();
00150   }
00151   forceinline bool
00152   SetVarImp::glbAny(const Delta& d) {
00153     return static_cast<const SetDelta&>(d).glbAny();
00154   }
00155   forceinline int
00156   SetVarImp::lubMin(const Delta& d) {
00157     return static_cast<const SetDelta&>(d).lubMin();
00158   }
00159   forceinline int
00160   SetVarImp::lubMax(const Delta& d) {
00161     return static_cast<const SetDelta&>(d).lubMax();
00162   }
00163   forceinline bool
00164   SetVarImp::lubAny(const Delta& d) {
00165     return static_cast<const SetDelta&>(d).lubAny();
00166   }
00167 
00168   forceinline ModEvent
00169   SetVarImp::cardMin(Space& home,unsigned int newMin) {
00170     if (cardMin() >= newMin)
00171       return ME_SET_NONE;
00172     if (newMin > cardMax())
00173       return ME_SET_FAILED;
00174     glb.card(newMin);
00175     return cardMin_full(home);
00176   }
00177 
00178   forceinline ModEvent
00179   SetVarImp::cardMax(Space& home,unsigned int newMax) {
00180     if (cardMax() <= newMax)
00181       return ME_SET_NONE;
00182     if (cardMin() > newMax)
00183       return ME_SET_FAILED;
00184     lub.card(newMax);
00185     return cardMax_full(home);
00186   }
00187 
00188   forceinline ModEvent
00189   SetVarImp::intersect(Space& home,int i, int j) {
00190     BndSetRanges lb(glb);
00191     Iter::Ranges::Singleton s(i,j);
00192     Iter::Ranges::Diff<BndSetRanges, Iter::Ranges::Singleton> probe(lb, s);
00193     if (probe())
00194       return ME_SET_FAILED;
00195     if (assigned())
00196       return ME_SET_NONE;
00197     int oldMin = lub.min();
00198     int oldMax = lub.max();
00199     if (lub.intersect(home, i, j)) {
00200       SetDelta d;
00201       if (i == oldMin) {
00202         d._lubMin = lub.max()+1;
00203         d._lubMax = oldMax;
00204       } else if (j == oldMax) {
00205         d._lubMin = oldMin;
00206         d._lubMax = lub.min()-1;
00207       }
00208       return processLubChange(home, d);
00209     }
00210     return ME_SET_NONE;
00211   }
00212 
00213   forceinline ModEvent
00214   SetVarImp::intersect(Space& home,int i) {
00215     return intersect(home, i, i);
00216   }
00217 
00218   template<class I>
00219   inline ModEvent
00220   SetVarImp::intersectI(Space& home, I& iterator) {
00221     Iter::Ranges::IsRangeIter<I>();
00222     if (assigned()) {
00223       BndSetRanges lbi(glb);
00224       Iter::Ranges::Diff<BndSetRanges,I> probe(lbi,iterator);
00225       if (probe())
00226         return ME_SET_FAILED;
00227       return ME_SET_NONE;
00228     }
00229     if (!iterator()) {
00230       if (cardMin() > 0)
00231         return ME_SET_FAILED;
00232       lub.card(0);
00233       SetDelta d(1, 0, lub.min(), lub.max());
00234       lub.excludeAll(home);
00235       return notify(home, ME_SET_VAL, d);
00236     }
00237     int mi=iterator.min();
00238     int ma=iterator.max();
00239     ++iterator;
00240     if (iterator())
00241       return intersectI_full(home, mi, ma, iterator);
00242     else
00243       return intersect(home, mi, ma);
00244   }
00245 
00246   template<class I>
00247   ModEvent
00248   SetVarImp::intersectI_full(Space& home, int mi, int ma, I& iterator) {
00249     Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00250     if (lub.intersectI(home, si)) {
00251       BndSetRanges ub(lub);
00252       BndSetRanges lb(glb);
00253       if (!Iter::Ranges::subset(lb,ub)) {
00254         glb.become(home, lub);
00255         glb.card(glb.size());
00256         lub.card(glb.size());
00257         return ME_SET_FAILED;
00258       }
00259       ModEvent me = ME_SET_LUB;
00260       if (cardMax() > lub.size()) {
00261         lub.card(lub.size());
00262         if (cardMin() > cardMax()) {
00263           glb.become(home, lub);
00264           glb.card(glb.size());
00265           lub.card(glb.size());
00266           return ME_SET_FAILED;
00267         }
00268         me = ME_SET_CLUB;
00269       }
00270       if (cardMax() == lub.size() && cardMin() == cardMax()) {
00271         glb.become(home, lub);
00272         me = ME_SET_VAL;
00273       }
00274       SetDelta d;
00275       return notify(home, me, d);
00276     }
00277     return ME_SET_NONE;
00278   }
00279 
00280   forceinline ModEvent
00281   SetVarImp::include(Space& home, int i, int j) {
00282     BndSetRanges ub(lub);
00283     Iter::Ranges::Singleton sij(i,j);
00284     if (!Iter::Ranges::subset(sij,ub)) {
00285       return ME_SET_FAILED;
00286     }
00287     SetDelta d;
00288     if (glb.include(home, i, j, d))
00289       return processGlbChange(home, d);
00290     return ME_SET_NONE;
00291   }
00292 
00293   forceinline ModEvent
00294   SetVarImp::include(Space& home, int i) {
00295     return include(home, i, i);
00296   }
00297 
00298   template<class I> forceinline ModEvent
00299   SetVarImp::includeI(Space& home, I& iterator) {
00300     Iter::Ranges::IsRangeIter<I>();
00301     if (!iterator()) {
00302       return ME_SET_NONE;
00303     }
00304     if (assigned()) {
00305       BndSetRanges lbi(glb);
00306       Iter::Ranges::Diff<I,BndSetRanges>
00307         probe(iterator,lbi);
00308       return probe() ? ME_SET_FAILED : ME_SET_NONE;
00309     }
00310     int mi=iterator.min();
00311     int ma=iterator.max();
00312     ++iterator;
00313     if (iterator())
00314       return includeI_full(home, mi, ma, iterator);
00315     else
00316       return include(home, mi, ma);
00317   }
00318 
00319   template<class I>
00320   ModEvent
00321   SetVarImp::includeI_full(Space& home, int mi, int ma, I& iterator) {
00322     Iter::Ranges::SingletonAppend<I> si(mi,ma,iterator);
00323     if (glb.includeI(home, si)) {
00324       BndSetRanges ub(lub);
00325       BndSetRanges lb(glb);
00326       if (!Iter::Ranges::subset(lb,ub)) {
00327         glb.become(home, lub);
00328         glb.card(glb.size());
00329         lub.card(glb.size());
00330         return ME_SET_FAILED;
00331       }
00332       ModEvent me = ME_SET_GLB;
00333       if (cardMin() < glb.size()) {
00334         glb.card(glb.size());
00335         if (cardMin() > cardMax()) {
00336           glb.become(home, lub);
00337           glb.card(glb.size());
00338           lub.card(glb.size());
00339           return ME_SET_FAILED;
00340         }
00341         me = ME_SET_CGLB;
00342       }
00343       if (cardMin() == glb.size() && cardMin() == cardMax()) {
00344         lub.become(home, glb);
00345         me = ME_SET_VAL;
00346       }
00347       SetDelta d;
00348       return notify(home, me, d);
00349     }
00350     return ME_SET_NONE;
00351   }
00352 
00353   forceinline ModEvent
00354   SetVarImp::exclude(Space& home, int i, int j) {
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 process) {
00517     SetVarImpBase::subscribe(home,p,pc,assigned(),process);
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