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