Generated on Tue Jul 27 2010 21:59:19 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: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
00015  *     $Revision: 9692 $
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     Iter::Ranges::IsRangeIter<I>();
00248     // Is new domain empty?
00249     if (!ri()) {
00250       //Was it empty?
00251       if (fst()==NULL)
00252         return false;
00253       fst()->dispose(home,lst());
00254       _size=0; fst(NULL); lst(NULL);
00255       return true;
00256     }
00257 
00258     RangeList* f =
00259       new (home) RangeList(ri.min(),ri.max(),NULL);
00260     RangeList* l = f;
00261     unsigned int s = ri.width();
00262 
00263     ++ri;
00264 
00265     while (ri()){
00266       RangeList *n = new (home) RangeList(ri.min(),ri.max(),NULL);
00267       l->next(n);
00268       l=n;
00269       s += ri.width();
00270       ++ri;
00271     }
00272 
00273     if (fst() != NULL)
00274       fst()->dispose(home,lst());
00275     fst(f); lst(l);
00276 
00277     // If the size did not change, nothing changed, as overwriting
00278     // must not at the same time include and exclude elements.
00279     if (size() == s)
00280       return false;
00281 
00282     _size = s;
00283     return true;
00284   }
00285 
00286   forceinline void
00287   BndSet::become(Space& home, const BndSet& that){
00288     if (fst()!=NULL){
00289       assert(lst()!=NULL);
00290       assert(fst()!= that.fst());
00291       fst()->dispose(home,lst());
00292     }
00293     fst(that.fst());
00294     lst(that.lst());
00295     _size = that.size();
00296     assert(isConsistent());
00297   }
00298 
00299   forceinline bool
00300   BndSet::in(int i) const {
00301     for (RangeList* c = fst(); c != NULL; c = c->next()) {
00302       if (c->min() <= i && c->max() >= i)
00303         return true;
00304       if (c->min() > i)
00305         return false;
00306     }
00307     return false;
00308   }
00309 
00310   /*
00311    * Range iterator for BndSets
00312    *
00313    */
00314 
00315   forceinline
00316   BndSetRanges::BndSetRanges(void) {}
00317 
00318   forceinline
00319   BndSetRanges::BndSetRanges(const BndSet& s) : c(s.ranges()) {}
00320 
00321   forceinline void
00322   BndSetRanges::init(const BndSet& s) { c = s.ranges(); }
00323 
00324   forceinline bool
00325   BndSetRanges::operator ()(void) const { return c != NULL; }
00326 
00327   forceinline void
00328   BndSetRanges::operator ++(void) {
00329     c = c->next();
00330   }
00331 
00332   forceinline int
00333   BndSetRanges::min(void) const {
00334     return c->min();
00335   }
00336   forceinline int
00337   BndSetRanges::max(void) const {
00338     return c->max();
00339   }
00340   forceinline unsigned int
00341   BndSetRanges::width(void) const {
00342     return c->width();
00343   }
00344 
00345   /*
00346    * GLBndSet
00347    *
00348    */
00349 
00350   forceinline
00351   GLBndSet::GLBndSet(void) {}
00352 
00353   forceinline
00354   GLBndSet::GLBndSet(Space&) {}
00355 
00356   forceinline
00357   GLBndSet::GLBndSet(Space& home, int mi, int ma)
00358     : BndSet(home,mi,ma) {}
00359 
00360   forceinline
00361   GLBndSet::GLBndSet(Space& home, const IntSet& s)
00362     : BndSet(home,s) {}
00363 
00364   forceinline void
00365   GLBndSet::init(Space& home) {
00366     dispose(home);
00367     fst(NULL);
00368     lst(NULL);
00369     _size = 0;
00370   }
00371 
00372   forceinline bool
00373   GLBndSet::include(Space& home, int mi, int ma, SetDelta& d) {
00374     assert(ma >= mi);
00375     if (fst()==NULL) {
00376       RangeList* p = new (home) RangeList(mi,ma,NULL);
00377       fst(p);
00378       lst(p);
00379       _size=static_cast<unsigned int>(ma-mi+1);
00380       d._glbMin = mi;
00381       d._glbMax = ma;
00382       return true;
00383     }
00384     bool ret = include_full(home, mi, ma, d);
00385     assert(isConsistent());
00386     return ret;
00387   }
00388 
00389   template<class I> bool
00390   GLBndSet::includeI(Space& home, I& i) {
00391     Iter::Ranges::IsRangeIter<I>();
00392     if (!i())
00393       return false;
00394     BndSetRanges j(*this);
00395     Iter::Ranges::Union<BndSetRanges,I> ij(j,i);
00396     bool me = overwrite(home, ij);
00397     assert(isConsistent());
00398     return me;
00399   }
00400 
00401 
00402   /*
00403    * LUBndSet
00404    *
00405    */
00406 
00407   forceinline
00408   LUBndSet::LUBndSet(void) {}
00409 
00410   forceinline
00411   LUBndSet::LUBndSet(Space& home)
00412     : BndSet(home,Limits::min,Limits::max) {}
00413 
00414   forceinline
00415   LUBndSet::LUBndSet(Space& home, int mi, int ma)
00416     : BndSet(home,mi,ma) {}
00417 
00418   forceinline
00419   LUBndSet::LUBndSet(Space& home, const IntSet& s)
00420     : BndSet(home,s) {}
00421 
00422   forceinline void
00423   LUBndSet::init(Space& home) {
00424     RangeList *p =
00425       new (home) RangeList(Limits::min,
00426                            Limits::max,
00427                            NULL);
00428     fst(p);
00429     lst(p);
00430     _size = Limits::card;
00431   }
00432 
00433   forceinline bool
00434   LUBndSet::exclude(Space& home, int mi, int ma, SetDelta& d) {
00435     assert(ma >= mi);
00436     if ((mi > max()) || (ma < min())) { return false; }
00437     if (mi <= min() && ma >= max() ) { //the range covers the whole set
00438       d._lubMin = min();
00439       d._lubMax = max();
00440       fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00441       _size=0;
00442       return true;
00443     }
00444     bool ret =  exclude_full(home, mi, ma, d);
00445     assert(isConsistent());
00446     return ret;
00447   }
00448 
00449   forceinline bool
00450   LUBndSet::intersect(Space& home, int mi, int ma) {
00451     assert(ma >= mi);
00452     if ((mi <= min()) && (ma >= max())) { return false; }
00453     if (_size == 0) return false;
00454     if (ma < min() || mi > max() ) { // empty the whole set
00455      fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00456      _size=0;
00457      return true;
00458     }
00459     bool ret = intersect_full(home, mi, ma);
00460     assert(isConsistent());
00461     return ret;
00462   }
00463 
00464   template<class I> bool
00465   LUBndSet::intersectI(Space& home, I& i) {
00466     Iter::Ranges::IsRangeIter<I>();
00467     if (fst()==NULL) { return false; }
00468     if (!i()) {
00469       fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00470       _size=0;
00471       return true;
00472     }
00473     BndSetRanges j(*this);
00474     Iter::Ranges::Inter<BndSetRanges,I> ij(j,i);
00475     bool ret = overwrite(home, ij);
00476     assert(isConsistent());
00477     return ret;
00478   }
00479 
00480   template<class I> bool
00481   LUBndSet::excludeI(Space& home, I& i) {
00482     Iter::Ranges::IsRangeIter<I>();
00483     if (!i()) { return false; }
00484     BndSetRanges j(*this);
00485     Iter::Ranges::Diff<BndSetRanges,I> ij(j,i);
00486     bool ret = overwrite(home, ij);
00487     assert(isConsistent());
00488     return ret;
00489   }
00490 
00491   forceinline void
00492   LUBndSet::excludeAll(Space& home) {
00493     fst()->dispose(home,lst()); fst(NULL); lst(NULL);
00494     _size=0;
00495   }
00496 
00497   /*
00498    * A complement iterator spezialized for the BndSet limits
00499    *
00500    */
00501   template<class I>
00502   RangesCompl<I>::RangesCompl(void) {}
00503 
00504   template<class I>
00505   RangesCompl<I>::RangesCompl(I& i)
00506     : Iter::Ranges::Compl<Limits::min,
00507                           Limits::max,
00508                           I>(i) {}
00509 
00510   template<class I> void
00511   RangesCompl<I>::init(I& i) {
00512     Iter::Ranges::Compl<Limits::min,
00513       Limits::max,I>::init(i);
00514   }
00515 
00516 }}
00517 
00518 // STATISTICS: set-var
00519