Generated on Thu Apr 11 13:59:07 2019 for Gecode by doxygen 1.6.3

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