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
00248 if (!ri()) {
00249
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
00277
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
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
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
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() ) {
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() ) {
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
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
00515