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 namespace Gecode { namespace Set {
00027
00028
00029
00030
00031
00032
00033 #define RL2PD(r) reinterpret_cast<ptrdiff_t>(r)
00034 #define PD2RL(p) reinterpret_cast<RangeList*>(p)
00035
00036 forceinline
00037 RangeList::RangeList(void) {}
00038
00039 forceinline
00040 RangeList::RangeList(int min, int max, RangeList* p, RangeList* n)
00041 : _min(min), _max(max) {
00042 _next = PD2RL(RL2PD(p)^RL2PD(n));
00043 }
00044
00045 forceinline RangeList*
00046 RangeList::next(const RangeList* p) const {
00047 return PD2RL(RL2PD(_next)^RL2PD(p));
00048 }
00049 forceinline RangeList*
00050 RangeList::prev(const RangeList* n) const {
00051 return PD2RL(RL2PD(_next)^RL2PD(n));
00052 }
00053 forceinline void
00054 RangeList::prevnext(RangeList* p, RangeList* n) {
00055 _next = PD2RL(RL2PD(p)^RL2PD(n));
00056 }
00057 forceinline void
00058 RangeList::next(RangeList* o, RangeList* n) {
00059 _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00060 }
00061 forceinline void
00062 RangeList::prev(RangeList* o, RangeList* n) {
00063 _next = PD2RL(RL2PD(_next)^(RL2PD(o)^RL2PD(n)));
00064 }
00065 forceinline void
00066 RangeList::fix(RangeList* n) {
00067 _next = n;
00068 }
00069
00070 forceinline void
00071 RangeList::min(int n) {
00072 _min = n;
00073 }
00074 forceinline void
00075 RangeList::max(int n) {
00076 _max = n;
00077 }
00078
00079 forceinline int
00080 RangeList::min(void) const {
00081 return _min;
00082 }
00083 forceinline int
00084 RangeList::max(void) const {
00085 return _max;
00086 }
00087 forceinline unsigned int
00088 RangeList::width(void) const {
00089 return _max - _min + 1;
00090 }
00091
00092
00093 forceinline void
00094 RangeList::operator delete(void*) {}
00095
00096 forceinline void
00097 RangeList::operator delete(void*, Space* home) {
00098 assert(false);
00099 }
00100
00101 forceinline void*
00102 RangeList::operator new(size_t s, Space* home) {
00103 assert(s == sizeof(RangeList));
00104 return home->fl_alloc<sizeof(RangeList)>();
00105 }
00106
00107 forceinline void
00108 RangeList::dispose(Space* home, RangeList* p, RangeList* l) {
00109 RangeList* c = this;
00110 while (c != l) {
00111 RangeList* n = c->next(p);
00112 c->fix(n);
00113 p=c; c=n;
00114 }
00115 home->fl_dispose<sizeof(RangeList)>(this,l);
00116 }
00117
00118 #undef RL2PD
00119 #undef PD2RL
00120
00121
00122
00123
00124
00125
00126
00127 forceinline
00128 BndSet::BndSet(void) :
00129 first(NULL), last(NULL), _size(0) {}
00130
00131 forceinline RangeList*
00132 BndSet::fst(void) const {
00133 return first;
00134 }
00135
00136 forceinline RangeList*
00137 BndSet::lst(void) const {
00138 return last;
00139 }
00140
00141 forceinline void
00142 BndSet::dispose(Space* home) {
00143 if (fst()!=NULL)
00144 fst()->dispose(home,NULL,lst());
00145 }
00146
00147 forceinline void
00148 BndSet::fst(RangeList* f) {
00149 first = f;
00150 }
00151
00152 forceinline void
00153 BndSet::lst(RangeList* l) {
00154 last = l;
00155 }
00156
00157 forceinline
00158 BndSet::BndSet(Space* home, int mn, int mx) {
00159 RangeList* p =
00160 new (home) RangeList(mn,mx,NULL,NULL);
00161 fst(p); lst(p);
00162 _size = mx-mn+1;
00163 }
00164
00165 forceinline RangeList*
00166 BndSet::ranges(void) const {
00167 return fst();
00168 }
00169
00170 forceinline unsigned int
00171 BndSet::size(void) const {
00172 return _size;
00173 }
00174
00175 forceinline bool
00176 BndSet::empty(void) const {
00177 return (_size==0);
00178 }
00179
00180 forceinline int
00181 BndSet::min(void) const {
00182 if (fst()==NULL) { return MIN_OF_EMPTY; }
00183 else { return fst()->min(); }
00184 }
00185
00186 forceinline int
00187 BndSet::max(void) const {
00188 if (lst()==NULL) { return MAX_OF_EMPTY; }
00189 else { return lst()->max(); }
00190 }
00191
00192
00193 forceinline int
00194 BndSet::minN(unsigned int n) const {
00195 RangeList* p=NULL;
00196 RangeList* c=fst();
00197 while (c!=NULL){
00198 if (c->width() >= n){
00199 return(c->min()+n);
00200 } else {
00201 n-=c->width();
00202 RangeList* nc=c->next(p);
00203 p=c; c=nc;
00204 }
00205 }
00206 return MIN_OF_EMPTY;
00207 }
00208
00209
00210 forceinline int
00211 BndSet::maxN(unsigned int n) const {
00212 RangeList* p=NULL;
00213 RangeList* c=lst();
00214 while (c!=NULL){
00215 if (c->width() >= n){
00216 return(c->max()-n);
00217 } else {
00218 n-=c->width();
00219 RangeList* nc=c->next(p);
00220 p=c; c=nc;
00221 }
00222 }
00223 return MAX_OF_EMPTY;
00224 }
00225
00226 forceinline void
00227 BndSet::update(Space* home, BndSet& d) {
00228 if ( d.fst() == fst()) { return; }
00229 if (fst()!=NULL) { fst()->dispose(home,NULL,lst()); }
00230 _size = d.size();
00231 if (_size==0) { fst(NULL); lst(NULL); return ; }
00232
00233 int n=0;
00234 {
00235 RangeList* p = NULL;
00236 RangeList* c = d.fst();
00237 while (c!=NULL) {
00238 RangeList* nc=c->next(p);
00239 p=c; c=nc; n++;
00240 }
00241 }
00242
00243 RangeList* r = reinterpret_cast<RangeList*>
00244 (home->alloc(sizeof(RangeList)*n));
00245 fst(r); lst(r+n-1);
00246
00247 {
00248 RangeList* p = NULL;
00249 RangeList* c = d.lst();
00250 for (int i=n; i--; ) {
00251 r[i].min(c->min());
00252 r[i].max(c->max());
00253 r[i].prevnext(&r[i-1],&r[i+1]);
00254
00255 RangeList* nc=c->next(p);
00256 p=c; c=nc;
00257 }
00258 r[0].prev(&r[-1],NULL);
00259 r[n-1].next(&r[n],NULL);
00260 }
00261
00262 }
00263
00264 template <class I> forceinline bool
00265 BndSet::overwrite(Space* home, I& ri) {
00266
00267 if (!ri()) {
00268
00269 if (fst()==NULL)
00270 return false;
00271 fst()->dispose(home,NULL,lst());
00272 _size=0; fst(NULL); lst(NULL);
00273 return true;
00274 }
00275
00276 RangeList* f =
00277 new (home) RangeList(ri.min(),ri.max(),NULL,NULL);
00278 RangeList* l = f;
00279 unsigned int s = ri.width();
00280
00281 ++ri;
00282
00283 while (ri()){
00284 RangeList *n = new (home) RangeList(ri.min(),ri.max(),l,NULL);
00285 l->next(NULL,n);
00286 l=n;
00287 s += ri.width();
00288 ++ri;
00289 }
00290
00291 if (fst() != NULL)
00292 fst()->dispose(home,NULL,lst());
00293 fst(f); lst(l);
00294
00295
00296
00297 if (size() == s)
00298 return false;
00299
00300 _size = s;
00301 return true;
00302 }
00303
00304 forceinline void
00305 BndSet::linkTo(Space* home, const BndSet& that){
00306 if (fst()!=NULL){
00307 assert(lst()!=NULL);
00308 assert(fst()!= that.fst());
00309 fst()->dispose(home,NULL,lst());
00310 }
00311 fst(that.fst());
00312 lst(that.lst());
00313 _size = that.size();
00314 assert(isConsistent());
00315 }
00316
00317 forceinline bool
00318 BndSet::in(int i) const {
00319 RangeList *p = NULL;
00320 RangeList *c = fst();
00321 while (c) {
00322 if (c->min() <= i && c->max() >= i)
00323 return true;
00324 if (c->min() > i)
00325 return false;
00326 RangeList* nc = c->next(p);
00327 p=c; c=nc;
00328 }
00329 return false;
00330 }
00331
00332
00333
00334
00335
00336
00337 forceinline
00338 BndSetRanges::BndSetRanges(void) {}
00339
00340 forceinline
00341 BndSetRanges::BndSetRanges(const BndSet& s) :
00342 p(NULL), c(s.ranges()) {}
00343
00344 forceinline void
00345 BndSetRanges::init(const BndSet& s) {
00346 p = NULL;
00347 c = s.ranges();
00348 }
00349
00350 forceinline bool
00351 BndSetRanges::operator()(void) const {
00352 return c != NULL;
00353 }
00354 forceinline void
00355 BndSetRanges::operator++(void) {
00356 const RangeList* n=c->next(p); p=c; c=n;
00357 }
00358
00359 forceinline int
00360 BndSetRanges::min(void) const {
00361 return c->min();
00362 }
00363 forceinline int
00364 BndSetRanges::max(void) const {
00365 return c->max();
00366 }
00367 forceinline unsigned int
00368 BndSetRanges::width(void) const {
00369 return c->width();
00370 }
00371
00372
00373
00374
00375
00376
00377 forceinline
00378 GLBndSet::GLBndSet(Space* home) {}
00379
00380 forceinline
00381 GLBndSet::GLBndSet(Space* home, int mi, int ma)
00382 : BndSet(home,mi,ma) { assert(mi<=ma); }
00383
00384 forceinline
00385 GLBndSet::GLBndSet(Space* home, const IntSet& s)
00386 : BndSet(home,s) {}
00387
00388 forceinline void
00389 GLBndSet::init(Space* home) { fst(NULL); lst(NULL); _size = 0; }
00390
00391 forceinline bool
00392 GLBndSet::include(Space* home, int mi, int ma) {
00393 assert(ma >= mi);
00394 if (fst()==NULL) {
00395 RangeList* p = new (home) RangeList(mi,ma,NULL,NULL);
00396 fst(p);
00397 lst(p);
00398 _size=ma-mi+1;
00399 return true;
00400 }
00401 bool ret = include_full(home, mi, ma);
00402 assert(isConsistent());
00403 return ret;
00404 }
00405
00406 template <class I> bool
00407 GLBndSet::includeI(Space* home, I& i) {
00408 if (!i())
00409 return false;
00410 BndSetRanges j(*this);
00411 Iter::Ranges::Union<BndSetRanges,I> ij(j,i);
00412 bool me = overwrite(home, ij);
00413 assert(isConsistent());
00414 return me;
00415 }
00416
00417
00418
00419
00420
00421
00422
00423 forceinline
00424 LUBndSet::LUBndSet(void) {}
00425
00426 forceinline
00427 LUBndSet::LUBndSet(Space* home)
00428 : BndSet(home,Limits::Set::int_min,Limits::Set::int_max) {}
00429
00430 forceinline
00431 LUBndSet::LUBndSet(Space* home, int mi, int ma)
00432 : BndSet(home,mi,ma) { assert(mi<=ma); }
00433
00434 forceinline
00435 LUBndSet::LUBndSet(Space* home, const IntSet& s)
00436 : BndSet(home,s) {}
00437
00438 forceinline void
00439 LUBndSet::init(Space* home) {
00440 RangeList *p =
00441 new (home) RangeList(Limits::Set::int_min,
00442 Limits::Set::int_max,
00443 NULL,NULL);
00444 fst(p);
00445 lst(p);
00446 _size = Limits::Set::card_max;
00447 }
00448
00449 forceinline bool
00450 LUBndSet::exclude(Space* home, int mi, int ma) {
00451 assert(ma >= mi);
00452 if ((mi > max()) || (ma < min())) { return false; }
00453 if (mi <= min() && ma >= max() ) {
00454 fst()->dispose(home,NULL,lst()); fst(NULL); lst(NULL);
00455 _size=0;
00456 return true;
00457 }
00458 bool ret = exclude_full(home, mi, ma);
00459 assert(isConsistent());
00460 return ret;
00461 }
00462
00463 template <class I> bool
00464 LUBndSet::intersectI(Space* home, I& i) {
00465 if (fst()==NULL) { return false; }
00466 if (!i()) {
00467 fst()->dispose(home,NULL,lst()); fst(NULL); lst(NULL);
00468 _size=0;
00469 return true;
00470 }
00471 BndSetRanges j(*this);
00472 Iter::Ranges::Inter<BndSetRanges,I> ij(j,i);
00473 bool ret = overwrite(home, ij);
00474 assert(isConsistent());
00475 return ret;
00476 }
00477
00478 template <class I> bool
00479 LUBndSet::excludeI(Space* home, I& i) {
00480 if (!i()) { return false; }
00481 BndSetRanges j(*this);
00482 Iter::Ranges::Diff<BndSetRanges,I> ij(j,i);
00483 bool ret = overwrite(home, ij);
00484 assert(isConsistent());
00485 return ret;
00486 }
00487
00488
00489
00490
00491
00492 template <class I>
00493 RangesCompl<I>::RangesCompl(void) {}
00494
00495 template <class I>
00496 RangesCompl<I>::RangesCompl(I& i)
00497 : Iter::Ranges::Compl<Limits::Set::int_min,
00498 Limits::Set::int_max,
00499 I>(i) {}
00500
00501 template <class I> void
00502 RangesCompl<I>::init(I& i) {
00503 Iter::Ranges::Compl<Limits::Set::int_min,
00504 Limits::Set::int_max,I>::init(i);
00505 }
00506
00507 }}
00508
00509
00510