Generated on Wed Jan 4 17:49:15 2006 for Gecode by doxygen 1.4.6

integerset.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Gabor Szokoli <szokoli@gecode.org>
00005  *     Christian Schulte <schulte@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Guido Tack, 2004
00009  *     Christian Schulte, 2004
00010  *     Gabor Szokoli, 2004
00011  *
00012  *  Last modified:
00013  *     $Date: 2005-10-11 17:57:38 +0200 (Tue, 11 Oct 2005) $ by $Author: tack $
00014  *     $Revision: 2334 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  See the file "LICENSE" for information on usage and
00021  *  redistribution of this file, and for a
00022  *     DISCLAIMER OF ALL WARRANTIES.
00023  *
00024  */
00025 
00026 namespace Gecode { namespace Set {
00027 
00028   /*
00029    * Range lists
00030    *
00031    */
00032 
00033 #define RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
00034 #define PD2RL(p) reinterpret_cast<RangeList*>(p)
00035 
00036   forceinline
00037   RangeList::RangeList(void) {}
00038 
00039   forceinline
00040   RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
00041     : _min(min), _max(max) {
00042     _next = PD2RL(RL2PD(p)^RL2PD(n));     
00043   }
00044 
00045   forceinline RangeList*
00046   RangeList::next(const RangeList* p) const {
00047     return PD2RL(RL2PD(_next)^RL2PD(p));
00048   }
00049   forceinline RangeList*
00050   RangeList::prev(const RangeList* n) const {
00051     return PD2RL(RL2PD(_next)^RL2PD(n));
00052   }
00053   forceinline void
00054   RangeList::prevnext(RangeList* p, RangeList* n) {
00055     _next = PD2RL(RL2PD(p)^RL2PD(n));
00056   }
00057   forceinline void
00058   RangeList::next(RangeList* o, RangeList* n) {
00059     _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00060   }
00061   forceinline void
00062   RangeList::prev(RangeList* o, RangeList* n) {
00063     _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00064   }
00065   forceinline void
00066   RangeList::fix(RangeList* n) {
00067     _next = n;
00068   }
00069 
00070   forceinline void
00071   RangeList::min(int n) {
00072     _min = n;
00073   }
00074   forceinline void
00075   RangeList::max(int n) {
00076     _max = n;
00077   }
00078 
00079   forceinline int
00080   RangeList::min(void) const {
00081     return _min;
00082   }
00083   forceinline int
00084   RangeList::max(void) const {
00085     return _max;
00086   }
00087   forceinline unsigned int
00088   RangeList::width(void) const {
00089     return _max - _min + 1;
00090   }
00091 
00092 
00093   forceinline void
00094   RangeList::operator delete(void*) {}
00095 
00096   forceinline void
00097   RangeList::operator delete(void*, Space* home) {
00098     assert(false);
00099   }
00100 
00101   forceinline void*
00102   RangeList::operator new(size_t s, Space* home) {
00103     assert(s == sizeof(RangeList));
00104     return home->fl_alloc<sizeof(RangeList)>();
00105   }
00106 
00107   forceinline void
00108   RangeList::dispose(Space* home, RangeList* p, RangeList* l) {
00109     RangeList* c = this;
00110     while (c != l) {
00111       RangeList* n = c->next(p);
00112       c->fix(n);
00113       p=c; c=n;
00114     }
00115     home->fl_dispose<sizeof(RangeList)>(this,l);
00116   }
00117 
00118 #undef RL2PD
00119 #undef PD2RL
00120 
00121 
00122   /*
00123    * BndSet
00124    *
00125    */
00126 
00127   forceinline
00128   BndSet::BndSet(void) :
00129     first(NULL), last(NULL), _size(0) {}
00130 
00131   forceinline RangeList*
00132   BndSet::fst(void) const {
00133     return first;
00134   }
00135 
00136   forceinline RangeList*
00137   BndSet::lst(void) const {
00138     return last;
00139   }
00140 
00141   forceinline void
00142   BndSet::dispose(Space* home) {
00143     if (fst()!=NULL)
00144       fst()->dispose(home,NULL,lst());
00145   }
00146 
00147   forceinline void
00148   BndSet::fst(RangeList* f) {
00149     first = f;
00150   }
00151 
00152   forceinline void
00153   BndSet::lst(RangeList* l) {
00154     last = l;
00155   }
00156 
00157   forceinline
00158   BndSet::BndSet(Space* home, int mn, int mx) {
00159     RangeList* p = 
00160       new (home) RangeList(mn,mx,NULL,NULL);
00161     fst(p); lst(p);
00162     _size = mx-mn+1;
00163   }
00164 
00165   forceinline RangeList*
00166   BndSet::ranges(void) const {
00167     return fst();
00168   }
00169 
00170   forceinline unsigned int
00171   BndSet::size(void) const {
00172     return _size;
00173   }
00174 
00175   forceinline bool
00176   BndSet::empty(void) const {
00177     return (_size==0);
00178   }
00179 
00180   forceinline int
00181   BndSet::min(void) const {
00182     if (fst()==NULL) { return MIN_OF_EMPTY; }
00183     else { return fst()->min(); }
00184   }
00185 
00186   forceinline int
00187   BndSet::max(void) const {
00188     if (lst()==NULL) { return MAX_OF_EMPTY; }
00189     else { return lst()->max(); }
00190   }
00191 
00192   // nth smallest element
00193   forceinline int
00194   BndSet::minN(unsigned int n) const {
00195     RangeList* p=NULL;
00196     RangeList* c=fst();
00197     while (c!=NULL){
00198       if (c->width() >= n){
00199         return(c->min()+n);
00200       } else {
00201         n-=c->width();
00202         RangeList* nc=c->next(p);
00203         p=c; c=nc;
00204       }
00205     }
00206     return MIN_OF_EMPTY;
00207   }
00208 
00209   // nth largest element
00210   forceinline int
00211   BndSet::maxN(unsigned int n) const {
00212     RangeList* p=NULL;
00213     RangeList* c=lst();
00214     while (c!=NULL){
00215       if (c->width() >= n){
00216         return(c->max()-n);
00217       } else {
00218         n-=c->width();
00219         RangeList* nc=c->next(p);
00220         p=c; c=nc;
00221       }
00222     }
00223     return MAX_OF_EMPTY;
00224   }
00225 
00226   forceinline void
00227   BndSet::update(Space* home, BndSet& d) {
00228     if ( d.fst() == fst()) { return; }
00229     if (fst()!=NULL) { fst()->dispose(home,NULL,lst()); }
00230     _size = d.size();
00231     if (_size==0) { fst(NULL); lst(NULL); return ; }
00232 
00233     int n=0;
00234     {
00235       RangeList* p = NULL;
00236       RangeList* c = d.fst();
00237       while (c!=NULL) {
00238         RangeList* nc=c->next(p);
00239         p=c; c=nc; n++;
00240       }
00241     }
00242 
00243     RangeList* r = reinterpret_cast<RangeList*>
00244       (home->alloc(sizeof(RangeList)*n));
00245     fst(r); lst(r+n-1);
00246 
00247     {
00248       RangeList* p = NULL;
00249       RangeList* c = d.lst();
00250       for (int i=n; i--; ) {
00251         r[i].min(c->min());
00252         r[i].max(c->max());
00253         r[i].prevnext(&r[i-1],&r[i+1]);
00254 
00255         RangeList* nc=c->next(p);
00256         p=c; c=nc;
00257       }
00258       r[0].prev(&r[-1],NULL); 
00259       r[n-1].next(&r[n],NULL);
00260     }
00261 
00262   }
00263 
00264   template <class I> forceinline bool
00265   BndSet::overwrite(Space* home, I& ri) {
00266     // Is new domain empty?
00267     if (!ri()) {
00268       //Was it empty?
00269       if (fst()==NULL)
00270         return false;
00271       fst()->dispose(home,NULL,lst());
00272       _size=0; fst(NULL); lst(NULL);
00273       return true;
00274     }
00275 
00276     RangeList* f =
00277       new (home) RangeList(ri.min(),ri.max(),NULL,NULL);
00278     RangeList* l = f;
00279     unsigned int s = ri.width();
00280 
00281     ++ri;
00282     
00283     while (ri()){
00284       RangeList *n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
00285       l->next(NULL,n);
00286       l=n;
00287       s += ri.width();
00288       ++ri;
00289     }
00290 
00291     if (fst() != NULL)
00292       fst()->dispose(home,NULL,lst());
00293     fst(f); lst(l);
00294 
00295     // If the size did not change, nothing changed, as overwriting
00296     // must not at the same time include and exclude elements.
00297     if (size() == s)
00298       return false;
00299 
00300     _size = s;
00301     return true;
00302   }
00303 
00304   forceinline void
00305   BndSet::linkTo(Space* home, const BndSet& that){
00306     if (fst()!=NULL){
00307       assert(lst()!=NULL);
00308       assert(fst()!= that.fst());
00309       fst()->dispose(home,NULL,lst());
00310     }
00311     fst(that.fst());
00312     lst(that.lst());
00313     _size = that.size();
00314     assert(isConsistent());
00315   }
00316 
00317   forceinline bool
00318   BndSet::in(int i) const {
00319     RangeList *p = NULL;
00320     RangeList *c = fst();
00321     while (c) {
00322       if (c->min() <= i && c->max() >= i)
00323         return true;
00324       if (c->min() > i)
00325         return false;
00326       RangeList* nc = c->next(p);
00327       p=c; c=nc;
00328     }
00329     return false;
00330   }
00331 
00332   /*
00333    * Forward range iterator for BndSets
00334    *
00335    */
00336 
00337   forceinline
00338   BndSetRanges::BndSetRanges(void) {}
00339 
00340   forceinline
00341   BndSetRanges::BndSetRanges(const BndSet& s) :
00342     p(NULL), c(s.ranges()) {}
00343 
00344   forceinline void
00345   BndSetRanges::init(const BndSet& s) {
00346     p = NULL;
00347     c = s.ranges();
00348   }
00349 
00350   forceinline bool
00351   BndSetRanges::operator()(void) const {
00352     return c != NULL;
00353   }
00354   forceinline void
00355   BndSetRanges::operator++(void) {
00356     const RangeList* n=c->next(p); p=c; c=n;
00357   }
00358 
00359   forceinline int
00360   BndSetRanges::min(void) const {
00361     return c->min();
00362   }
00363   forceinline int
00364   BndSetRanges::max(void) const {
00365     return c->max();
00366   }
00367   forceinline unsigned int
00368   BndSetRanges::width(void) const {
00369     return c->width();
00370   }
00371 
00372   /*
00373    * GLBndSet
00374    *
00375    */
00376 
00377   forceinline
00378   GLBndSet::GLBndSet(Space* home) {}
00379 
00380   forceinline
00381   GLBndSet::GLBndSet(Space* home, int mi, int ma)
00382     : BndSet(home,mi,ma) { assert(mi<=ma); }
00383 
00384   forceinline
00385   GLBndSet::GLBndSet(Space* home, const IntSet& s)
00386     : BndSet(home,s) {}
00387 
00388   forceinline void
00389   GLBndSet::init(Space* home) { fst(NULL); lst(NULL); _size = 0; }
00390 
00391   forceinline bool
00392   GLBndSet::include(Space* home, int mi, int ma) {
00393     assert(ma >= mi);
00394     if (fst()==NULL) {
00395       RangeList* p = new (home) RangeList(mi,ma,NULL,NULL);
00396       fst(p);
00397       lst(p);
00398       _size=ma-mi+1;
00399       return true;
00400     }
00401     bool ret = include_full(home, mi, ma);
00402     assert(isConsistent());
00403     return ret;
00404   }
00405 
00406   template <class I> bool
00407   GLBndSet::includeI(Space* home, I& i) {
00408     if (!i())
00409       return false;
00410     BndSetRanges j(*this);
00411     Iter::Ranges::Union<BndSetRanges,I> ij(j,i);
00412     bool me = overwrite(home, ij);
00413     assert(isConsistent());
00414     return me;
00415   }
00416 
00417 
00418   /*
00419    * LUBndSet
00420    *
00421    */
00422 
00423   forceinline
00424   LUBndSet::LUBndSet(void) {}
00425 
00426   forceinline
00427   LUBndSet::LUBndSet(Space* home)
00428     : BndSet(home,Limits::Set::int_min,Limits::Set::int_max) {}
00429 
00430   forceinline
00431   LUBndSet::LUBndSet(Space* home, int mi, int ma)
00432     : BndSet(home,mi,ma) { assert(mi<=ma); }
00433 
00434   forceinline
00435   LUBndSet::LUBndSet(Space* home, const IntSet& s)
00436     : BndSet(home,s) {}
00437 
00438   forceinline void
00439   LUBndSet::init(Space* home) {
00440     RangeList *p =
00441       new (home) RangeList(Limits::Set::int_min,
00442                            Limits::Set::int_max,
00443                            NULL,NULL);
00444     fst(p);
00445     lst(p);
00446     _size = Limits::Set::card_max;
00447   }
00448 
00449   forceinline bool
00450   LUBndSet::exclude(Space* home, int mi, int ma) {
00451     assert(ma >= mi);
00452     if ((mi > max()) || (ma < min())) { return false; }
00453     if (mi <= min() && ma >= max() ) { //the range covers the whole set
00454       fst()->dispose(home,NULL,lst()); fst(NULL); lst(NULL);
00455       _size=0;
00456       return true;
00457     }
00458     bool ret =  exclude_full(home, mi, ma);
00459     assert(isConsistent());
00460     return ret;
00461   }
00462 
00463   template <class I> bool
00464   LUBndSet::intersectI(Space* home, I& i) {
00465     if (fst()==NULL) { return false; }
00466     if (!i()) {
00467       fst()->dispose(home,NULL,lst()); fst(NULL); lst(NULL);
00468       _size=0;
00469       return true;
00470     }
00471     BndSetRanges j(*this);
00472     Iter::Ranges::Inter<BndSetRanges,I> ij(j,i);
00473     bool ret = overwrite(home, ij);
00474     assert(isConsistent());
00475     return ret;
00476   }
00477 
00478   template <class I> bool
00479   LUBndSet::excludeI(Space* home, I& i) {
00480     if (!i()) { return false; }
00481     BndSetRanges j(*this);
00482     Iter::Ranges::Diff<BndSetRanges,I> ij(j,i);
00483     bool ret = overwrite(home, ij);
00484     assert(isConsistent());
00485     return ret;
00486   }
00487 
00488   /*
00489    * A complement iterator spezialized for the BndSet limits
00490    *
00491    */
00492   template <class I>
00493   RangesCompl<I>::RangesCompl(void) {}
00494 
00495   template <class I>
00496   RangesCompl<I>::RangesCompl(I& i)
00497     : Iter::Ranges::Compl<Limits::Set::int_min,
00498                           Limits::Set::int_max,
00499                           I>(i) {}
00500 
00501   template <class I> void
00502   RangesCompl<I>::init(I& i) {
00503     Iter::Ranges::Compl<Limits::Set::int_min,
00504       Limits::Set::int_max,I>::init(i);
00505   }
00506 
00507 }}
00508 
00509 // STATISTICS: set-var
00510