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