Generated on Fri May 13 2011 22:41:23 for Gecode by doxygen 1.7.1

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