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

integerset.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  *     Christian Schulte <schulte@gecode.org>
00007  *
00008  *  Copyright:
00009  *     Guido Tack, 2004
00010  *     Christian Schulte, 2004
00011  *     Gabor Szokoli, 2004
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Set {
00039 
00040   /*
00041    * BndSet
00042    *
00043    */
00044 
00045   forceinline
00046   BndSet::BndSet(void) :
00047     first(NULL), last(NULL), _size(0), _card(0) {}
00048 
00049   forceinline RangeList*
00050   BndSet::fst(void) const {
00051     return first;
00052   }
00053 
00054   forceinline RangeList*
00055   BndSet::lst(void) const {
00056     return last;
00057   }
00058 
00059   forceinline void
00060   BndSet::dispose(Space& home) {
00061     if (fst()!=NULL)
00062       fst()->dispose(home,lst());
00063   }
00064 
00065   forceinline void
00066   BndSet::fst(RangeList* f) {
00067     first = f;
00068   }
00069 
00070   forceinline void
00071   BndSet::lst(RangeList* l) {
00072     last = l;
00073   }
00074 
00075   forceinline
00076   BndSet::BndSet(Space& home, int mn, int mx) {
00077     if (mn>mx) {
00078       fst(NULL); lst(NULL); _size = 0;
00079     } else {
00080       RangeList* p =
00081         new (home) RangeList(mn,mx,NULL);
00082       fst(p); lst(p);
00083       _size = static_cast<unsigned int>(mx-mn+1);
00084     }
00085   }
00086 
00087   forceinline RangeList*
00088   BndSet::ranges(void) const {
00089     return fst();
00090   }
00091 
00092   forceinline unsigned int
00093   BndSet::size(void) const {
00094     return _size;
00095   }
00096 
00097   forceinline bool
00098   BndSet::empty(void) const {
00099     return (_size==0);
00100   }
00101 
00102   forceinline int
00103   BndSet::min(void) const {
00104     if (fst()==NULL)
00105       return MIN_OF_EMPTY;
00106     else
00107       return fst()->min();
00108   }
00109 
00110   forceinline int
00111   BndSet::max(void) const {
00112     if (lst()==NULL)
00113       return MAX_OF_EMPTY;
00114     else
00115       return lst()->max();
00116   }
00117 
00118   // nth smallest element
00119   forceinline int
00120   BndSet::minN(unsigned int n) const {
00121     for (RangeList* c = fst(); c != NULL; c = c->next()) {
00122       if (c->width() > n)
00123         return static_cast<int>(c->min() + n);
00124       n -= c->width();
00125     }
00126     return MIN_OF_EMPTY;
00127   }
00128 
00129   forceinline unsigned int
00130   BndSet::card(void) const {
00131     return _card;
00132   }
00133 
00134   forceinline void
00135   BndSet::card(unsigned int c) {
00136     _card = c;
00137   }
00138 
00139   forceinline void
00140   BndSet::update(Space& home, BndSet& d) {
00141     if (d.fst() == fst())
00142       return;
00143     if (fst() != NULL)
00144       fst()->dispose(home,lst());
00145     _size = d.size();
00146     if (_size == 0) {
00147       fst(NULL); lst(NULL);
00148       return;
00149     }
00150 
00151     int n=0;
00152     for (RangeList* c = d.fst(); c != NULL; c = c->next())
00153       n++;
00154 
00155     RangeList* r = home.alloc<RangeList>(n);
00156     fst(r); lst(r+n-1);
00157 
00158     {
00159       RangeList* c = d.fst();
00160       for (int i=0; i<n; i++) {
00161         r[i].min(c->min());
00162         r[i].max(c->max());
00163         r[i].next(&r[i+1]);
00164         c = c->next();
00165       }
00166     }
00167     r[n-1].next(NULL);
00168   }
00169 
00170   template<class I> forceinline bool
00171   BndSet::overwrite(Space& home, I& ri) {
00172     // Is new domain empty?
00173     if (!ri()) {
00174       //Was it empty?
00175       if (fst()==NULL)
00176         return false;
00177       fst()->dispose(home,lst());
00178       _size=0; fst(NULL); lst(NULL);
00179       return true;
00180     }
00181 
00182     RangeList* f =
00183       new (home) RangeList(ri.min(),ri.max(),NULL);
00184     RangeList* l = f;
00185     unsigned int s = ri.width();
00186 
00187     ++ri;
00188 
00189     while (ri()) {
00190       RangeList *n = new (home) RangeList(ri.min(),ri.max(),NULL);
00191       l->next(n);
00192       l=n;
00193       s += ri.width();
00194       ++ri;
00195     }
00196 
00197     if (fst() != NULL)
00198       fst()->dispose(home,lst());
00199     fst(f); lst(l);
00200 
00201     // If the size did not change, nothing changed, as overwriting
00202     // must not at the same time include and exclude elements.
00203     if (size() == s)
00204       return false;
00205 
00206     _size = s;
00207     return true;
00208   }
00209 
00210   forceinline void
00211   BndSet::become(Space& home, const BndSet& that) {
00212     if (fst()!=NULL) {
00213       assert(lst()!=NULL);
00214       assert(fst()!= that.fst());
00215       fst()->dispose(home,lst());
00216     }
00217     fst(that.fst());
00218     lst(that.lst());
00219     _size = that.size();
00220     assert(isConsistent());
00221   }
00222 
00223   forceinline bool
00224   BndSet::in(int i) const {
00225     for (RangeList* c = fst(); c != NULL; c = c->next()) {
00226       if (c->min() <= i && c->max() >= i)
00227         return true;
00228       if (c->min() > i)
00229         return false;
00230     }
00231     return false;
00232   }
00233 
00234   /*
00235    * Range iterator for BndSets
00236    *
00237    */
00238 
00239   forceinline
00240   BndSetRanges::BndSetRanges(void) {}
00241 
00242   forceinline
00243   BndSetRanges::BndSetRanges(const BndSet& s)
00244     : Iter::Ranges::RangeList(s.ranges()) {}
00245 
00246   forceinline void
00247   BndSetRanges::init(const BndSet& s) {
00248     Iter::Ranges::RangeList::init(s.ranges());
00249   }
00250 
00251   /*
00252    * GLBndSet
00253    *
00254    */
00255 
00256   forceinline
00257   GLBndSet::GLBndSet(void) {}
00258 
00259   forceinline
00260   GLBndSet::GLBndSet(Space&) {}
00261 
00262   forceinline
00263   GLBndSet::GLBndSet(Space& home, int mi, int ma)
00264     : BndSet(home,mi,ma) {}
00265 
00266   forceinline
00267   GLBndSet::GLBndSet(Space& home, const IntSet& s)
00268     : BndSet(home,s) {}
00269 
00270   forceinline void
00271   GLBndSet::init(Space& home) {
00272     dispose(home);
00273     fst(NULL);
00274     lst(NULL);
00275     _size = 0;
00276   }
00277 
00278   forceinline bool
00279   GLBndSet::include(Space& home, int mi, int ma, SetDelta& d) {
00280     assert(ma >= mi);
00281     if (fst()==NULL) {
00282       RangeList* p = new (home) RangeList(mi,ma,NULL);
00283       fst(p);
00284       lst(p);
00285       _size=static_cast<unsigned int>(ma-mi+1);
00286       d._glbMin = mi;
00287       d._glbMax = ma;
00288       return true;
00289     }
00290     bool ret = include_full(home, mi, ma, d);
00291     assert(isConsistent());
00292     return ret;
00293   }
00294 
00295   template<class I> bool
00296   GLBndSet::includeI(Space& home, I& i) {
00297     if (!i())
00298       return false;
00299     BndSetRanges j(*this);
00300     Iter::Ranges::Union<BndSetRanges,I> ij(j,i);
00301     bool me = overwrite(home, ij);
00302     assert(isConsistent());
00303     return me;
00304   }
00305 
00306 
00307   /*
00308    * LUBndSet
00309    *
00310    */
00311 
00312   forceinline
00313   LUBndSet::LUBndSet(void) {}
00314 
00315   forceinline
00316   LUBndSet::LUBndSet(Space& home)
00317     : BndSet(home,Limits::min,Limits::max) {}
00318 
00319   forceinline
00320   LUBndSet::LUBndSet(Space& home, int mi, int ma)
00321     : BndSet(home,mi,ma) {}
00322 
00323   forceinline
00324   LUBndSet::LUBndSet(Space& home, const IntSet& s)
00325     : BndSet(home,s) {}
00326 
00327   forceinline void
00328   LUBndSet::init(Space& home) {
00329     RangeList *p =
00330       new (home) RangeList(Limits::min,
00331                            Limits::max,
00332                            NULL);
00333     fst(p);
00334     lst(p);
00335     _size = Limits::card;
00336   }
00337 
00338   forceinline bool
00339   LUBndSet::exclude(Space& home, int mi, int ma, SetDelta& d) {
00340     assert(ma >= mi);
00341     if ((mi > max()) || (ma < min())) { return false; }
00342     if (mi <= min() && ma >= max() ) { //the range covers the whole set
00343       d._lubMin = min();
00344       d._lubMax = max();
00345       fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00346       _size=0;
00347       return true;
00348     }
00349     bool ret =  exclude_full(home, mi, ma, d);
00350     assert(isConsistent());
00351     return ret;
00352   }
00353 
00354   forceinline bool
00355   LUBndSet::intersect(Space& home, int mi, int ma) {
00356     assert(ma >= mi);
00357     if ((mi <= min()) && (ma >= max())) { return false; }
00358     if (_size == 0) return false;
00359     if (ma < min() || mi > max() ) { // empty the whole set
00360      fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00361      _size=0;
00362      return true;
00363     }
00364     bool ret = intersect_full(home, mi, ma);
00365     assert(isConsistent());
00366     return ret;
00367   }
00368 
00369   template<class I> bool
00370   LUBndSet::intersectI(Space& home, I& i) {
00371     if (fst()==NULL) { return false; }
00372     if (!i()) {
00373       fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00374       _size=0;
00375       return true;
00376     }
00377     BndSetRanges j(*this);
00378     Iter::Ranges::Inter<BndSetRanges,I> ij(j,i);
00379     bool ret = overwrite(home, ij);
00380     assert(isConsistent());
00381     return ret;
00382   }
00383 
00384   template<class I> bool
00385   LUBndSet::excludeI(Space& home, I& i) {
00386     if (!i()) { return false; }
00387     BndSetRanges j(*this);
00388     Iter::Ranges::Diff<BndSetRanges,I> ij(j,i);
00389     bool ret = overwrite(home, ij);
00390     assert(isConsistent());
00391     return ret;
00392   }
00393 
00394   forceinline void
00395   LUBndSet::excludeAll(Space& home) {
00396     fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00397     _size=0;
00398   }
00399 
00400   /*
00401    * A complement iterator spezialized for the BndSet limits
00402    *
00403    */
00404   template<class I>
00405   RangesCompl<I>::RangesCompl(void) {}
00406 
00407   template<class I>
00408   RangesCompl<I>::RangesCompl(I& i)
00409     : Iter::Ranges::Compl<Limits::min,
00410                           Limits::max,
00411                           I>(i) {}
00412 
00413   template<class I> void
00414   RangesCompl<I>::init(I& i) {
00415     Iter::Ranges::Compl<Limits::min,
00416       Limits::max,I>::init(i);
00417   }
00418 
00419 }}
00420 
00421 // STATISTICS: set-var
00422