00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 namespace Gecode { namespace Set {
00043
00044
00045
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
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
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
00249 if (!ri()) {
00250
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
00278
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
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
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
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() ) {
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() ) {
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
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
00519