00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 namespace Gecode { namespace Set {
00023
00028 class ArrayRanges {
00029 private:
00030 int *_ranges;
00031 int _size;
00032 int _pos;
00033 public:
00035
00036
00037 ArrayRanges() : _ranges(NULL), _size(0), _pos(0) {}
00039 ArrayRanges(int *ranges, int size)
00040 : _ranges(ranges), _size(size), _pos(0) {}
00042 void init(int* ranges, int size) {
00043 _ranges = ranges; _size = size; _pos = 0;
00044 }
00046
00048
00049
00050 bool operator()(void) const { return _pos<_size; }
00052 void operator++(void) { _pos++; }
00054
00056
00057
00058 int min(void) const { return _ranges[_pos*2]; }
00060 int max(void) const { return _ranges[_pos*2+1]; }
00062 unsigned int width(void) const {
00063 return _ranges[_pos*2+1]-_ranges[_pos*2]+1;
00064 }
00066 };
00067
00068 forceinline
00069 ConstantView::ConstantView(void) : ranges(NULL), size(0), domSize(0) {}
00070
00071 forceinline
00072 ConstantView::ConstantView(Space* home, const IntSet& dom)
00073 : ranges(NULL), size(dom.size()), domSize(0) {
00074 if (size > 0) {
00075 ranges = static_cast<int*>(home->alloc(2*size*sizeof(int)));
00076 IntSetRanges dr(dom);
00077 for (int i=0; dr(); ++dr, i+=2) {
00078 int min = dr.min(); int max = dr.max();
00079 ranges[i] = min;
00080 ranges[i+1] = max;
00081 domSize += (max-min+1);
00082 }
00083 }
00084 }
00085
00086 forceinline bool
00087 ConstantView::assigned(void) const { return true; }
00088
00089 forceinline unsigned int
00090 ConstantView::glbSize(void) const { return domSize; }
00091
00092 forceinline unsigned int
00093 ConstantView::lubSize(void) const { return domSize; }
00094
00095 forceinline unsigned int
00096 ConstantView::unknownSize(void) const { return 0; }
00097
00098 forceinline bool
00099 ConstantView::contains(int i) const {
00100 for (unsigned int j=size; j--; ) {
00101 if (ranges[2*j+1] < i)
00102 return false;
00103 if (ranges[2*j] >= i)
00104 return true;
00105 }
00106 return false;
00107 }
00108
00109 forceinline bool
00110 ConstantView::notContains(int i) const {
00111 return !contains(i);
00112 }
00113
00114 forceinline unsigned int
00115 ConstantView::cardMin() const { return domSize; }
00116
00117 forceinline unsigned int
00118 ConstantView::cardMax() const { return domSize; }
00119
00120 forceinline int
00121 ConstantView::lubMin() const {
00122 return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0];
00123 }
00124
00125 forceinline int
00126 ConstantView::lubMax() const {
00127 return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1];
00128 }
00129
00130 forceinline int
00131 ConstantView::glbMin() const { return lubMin(); }
00132
00133 forceinline int
00134 ConstantView::glbMax() const { return lubMax(); }
00135
00136 forceinline ModEvent
00137 ConstantView::cardMin(Space* home,unsigned int c) {
00138 return c<=domSize ? ME_SET_NONE : ME_SET_FAILED;
00139 }
00140
00141 forceinline ModEvent
00142 ConstantView::cardMax(Space* home,unsigned int c) {
00143 return c>=domSize ? ME_SET_NONE : ME_SET_FAILED;
00144 }
00145
00146 forceinline ModEvent
00147 ConstantView::include(Space* home,int c) {
00148 return contains(c) ? ME_SET_NONE : ME_SET_FAILED;
00149 }
00150
00151 forceinline ModEvent
00152 ConstantView::exclude(Space* home,int c) {
00153 return contains(c) ? ME_SET_FAILED : ME_SET_NONE;
00154 }
00155
00156 forceinline ModEvent
00157 ConstantView::intersect(Space* home,int c) {
00158 return (size==0 ||
00159 (size==1 &&
00160 ranges[0]==ranges[1] && ranges[0]==c)) ?
00161 ME_SET_NONE : ME_SET_FAILED;
00162 }
00163
00164 forceinline ModEvent
00165 ConstantView::intersect(Space* home,int i,int j) {
00166 return (glbMin()>=i && glbMax()<=j) ?
00167 ME_SET_NONE : ME_SET_FAILED;
00168 }
00169
00170 forceinline ModEvent
00171 ConstantView::include(Space* home,int i,int j) {
00172 Iter::Ranges::Singleton single(i,j);
00173 ArrayRanges ar(ranges, size);
00174 return (single() && Iter::Ranges::subset(single, ar)) ?
00175 ME_SET_NONE : ME_SET_FAILED;
00176 }
00177
00178 forceinline ModEvent
00179 ConstantView::exclude(Space* home,int i,int j) {
00180 Iter::Ranges::Singleton single(i,j);
00181 ArrayRanges ar(ranges, size);
00182 return (single() && Iter::Ranges::subset(single, ar)) ?
00183 ME_SET_FAILED : ME_SET_NONE;
00184 }
00185
00186 template <class I> ModEvent
00187 ConstantView::excludeI(Space* home,I& i) {
00188 ArrayRanges ar(ranges, size);
00189 return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE;
00190 }
00191
00192 template <class I> ModEvent
00193 ConstantView::includeI(Space* home,I& i) {
00194 ArrayRanges ar(ranges, size);
00195 return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED;
00196 }
00197
00198 template <class I> ModEvent
00199 ConstantView::intersectI(Space* home,I& i) {
00200 ArrayRanges ar(ranges, size);
00201 return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED;
00202 }
00203
00204 forceinline void
00205 ConstantView::subscribe(Space* home,Propagator*,PropCond) {}
00206 forceinline void
00207 ConstantView::cancel(Propagator*,PropCond) {}
00208
00209 forceinline ModEvent
00210 ConstantView::pme(const Propagator*) {
00211 return ME_SET_NONE;
00212 }
00213 forceinline PropModEvent
00214 ConstantView::pme(ModEvent me) {
00215 return SetVarImp::pme(me);
00216 }
00217
00218 forceinline void
00219 ConstantView::update(Space* home, bool share, ConstantView& p) {
00220
00221 if (size>0) {
00222 home->reuse(ranges, 2*size*sizeof(int));
00223 }
00224
00225 domSize = p.domSize;
00226 size = p.size;
00227 if (size == 0) {
00228 ranges = NULL;
00229 } else {
00230
00231 ranges = static_cast<int*>(home->alloc(2*size*sizeof(int)));
00232 for (unsigned int i=size; i--; ) {
00233 ranges[2*i] = p.ranges[2*i];
00234 ranges[2*i+1] = p.ranges[2*i+1];
00235 }
00236 }
00237 }
00238
00239 forceinline bool
00240 ConstantView::destruct(void) { return true; }
00241
00242 forceinline
00243 EmptyView::EmptyView(void) {}
00244
00245
00246 forceinline bool
00247 EmptyView::assigned(void) const { return true; }
00248
00249 forceinline unsigned int
00250 EmptyView::glbSize(void) const { return 0; }
00251
00252 forceinline unsigned int
00253 EmptyView::lubSize(void) const { return 0; }
00254
00255 forceinline unsigned int
00256 EmptyView::unknownSize(void) const { return 0; }
00257
00258 forceinline bool
00259 EmptyView::contains(int) const { return false; }
00260
00261 forceinline bool
00262 EmptyView::notContains(int) const { return true; }
00263
00264 forceinline unsigned int
00265 EmptyView::cardMin() const { return 0; }
00266
00267 forceinline unsigned int
00268 EmptyView::cardMax() const { return 0; }
00269
00270 forceinline int
00271 EmptyView::lubMin() const { return 0; }
00272
00273 forceinline int
00274 EmptyView::lubMax() const { return 0; }
00275
00276 forceinline int
00277 EmptyView::glbMin() const { return 0; }
00278
00279 forceinline int
00280 EmptyView::glbMax() const { return 0; }
00281
00282 forceinline ModEvent
00283 EmptyView::cardMin(Space* home,unsigned int c) {
00284 return c==0 ? ME_SET_NONE : ME_SET_FAILED;
00285 }
00286
00287 forceinline ModEvent
00288 EmptyView::cardMax(Space* home,unsigned int c) {
00289 return ME_SET_NONE;
00290 }
00291
00292
00293 forceinline ModEvent
00294 EmptyView::include(Space* home,int) {
00295 return ME_SET_FAILED;
00296 }
00297
00298 forceinline ModEvent
00299 EmptyView::exclude(Space* home,int) { return ME_SET_NONE; }
00300
00301 forceinline ModEvent
00302 EmptyView::intersect(Space* home,int) { return ME_SET_NONE; }
00303
00304 forceinline ModEvent
00305 EmptyView::intersect(Space* home,int,int) { return ME_SET_NONE; }
00306
00307 forceinline ModEvent
00308 EmptyView::include(Space* home,int,int) {
00309 return ME_SET_FAILED; }
00310
00311 forceinline ModEvent
00312 EmptyView::exclude(Space* home,int,int) { return ME_SET_NONE; }
00313
00314 template <class I> ModEvent
00315 EmptyView::excludeI(Space* home,I&) { return ME_SET_NONE; }
00316
00317 template <class I> ModEvent
00318 EmptyView::includeI(Space* home,I& i) {
00319 return i() ? ME_SET_FAILED : ME_SET_NONE;
00320 }
00321
00322 template <class I> ModEvent
00323 EmptyView::intersectI(Space* home,I&) {
00324 return ME_SET_NONE;
00325 }
00326
00327 forceinline void
00328 EmptyView::subscribe(Space* home,Propagator*,PropCond) {}
00329 forceinline void
00330 EmptyView::cancel(Propagator*,PropCond) {}
00331
00332 forceinline ModEvent
00333 EmptyView::pme(const Propagator*) {
00334 return ME_SET_NONE;
00335 }
00336 forceinline PropModEvent
00337 EmptyView::pme(ModEvent me) {
00338 return SetVarImp::pme(me);
00339 }
00340
00341 forceinline void
00342 EmptyView::update(Space* home, bool, EmptyView&) {}
00343
00344 forceinline bool
00345 EmptyView::destruct(void) { return false; }
00346
00347
00348
00349
00350
00351
00352 forceinline
00353 UniverseView::UniverseView(void) {}
00354
00355 forceinline bool
00356 UniverseView::assigned(void) const { return true; }
00357
00358 forceinline unsigned int
00359 UniverseView::glbSize(void) const { return Limits::Set::card_max; }
00360
00361 forceinline unsigned int
00362 UniverseView::lubSize(void) const { return Limits::Set::card_max; }
00363
00364 forceinline unsigned int
00365 UniverseView::unknownSize(void) const { return 0; }
00366
00367 forceinline bool
00368 UniverseView::contains(int) const { return true; }
00369
00370 forceinline bool
00371 UniverseView::notContains(int) const { return false; }
00372
00373 forceinline unsigned int
00374 UniverseView::cardMin() const { return Limits::Set::card_max; }
00375
00376 forceinline unsigned int
00377 UniverseView::cardMax() const { return Limits::Set::card_max; }
00378
00379 forceinline int
00380 UniverseView::lubMin() const { return Limits::Set::card_max; }
00381
00382 forceinline int
00383 UniverseView::lubMax() const { return Limits::Set::card_max; }
00384
00385 forceinline int
00386 UniverseView::glbMin() const { return Limits::Set::card_max; }
00387
00388 forceinline int
00389 UniverseView::glbMax() const { return Limits::Set::card_max; }
00390
00391 forceinline ModEvent
00392 UniverseView::cardMin(Space* home,unsigned int c) {
00393 return c>Limits::Set::card_max ? ME_SET_FAILED : ME_SET_NONE;
00394 }
00395
00396 forceinline ModEvent
00397 UniverseView::cardMax(Space* home,unsigned int c) {
00398 return c>=Limits::Set::card_max ? ME_SET_NONE : ME_SET_FAILED;
00399 }
00400
00401
00402 forceinline ModEvent
00403 UniverseView::include(Space* home,int) {
00404 return ME_SET_NONE;
00405 }
00406
00407 forceinline ModEvent
00408 UniverseView::exclude(Space* home,int) { return ME_SET_FAILED; }
00409
00410 forceinline ModEvent
00411 UniverseView::intersect(Space* home,int) { return ME_SET_FAILED; }
00412
00413 forceinline ModEvent
00414 UniverseView::include(Space* home,int,int) { return ME_SET_NONE; }
00415
00416 forceinline ModEvent
00417 UniverseView::exclude(Space* home,int,int) { return ME_SET_FAILED; }
00418
00419 template <class I> ModEvent
00420 UniverseView::excludeI(Space* home,I& i) {
00421 return i() ? ME_SET_FAILED : ME_SET_NONE;
00422 }
00423
00424 template <class I> forceinline ModEvent
00425 UniverseView::includeI(Space* home,I&) { return ME_SET_NONE; }
00426
00427 forceinline ModEvent
00428 UniverseView::intersect(Space* home,int i,int j) {
00429 return (i>Limits::Set::int_min ||
00430 i<Limits::Set::int_max) ? ME_SET_FAILED : ME_SET_NONE;
00431 }
00432
00433 template <class I> forceinline ModEvent
00434 UniverseView::intersectI(Space* home,I& i) {
00435 return (i() &&
00436 (i.min()>Limits::Set::int_min ||
00437 i.max()<Limits::Set::int_max) ) ?
00438 ME_SET_FAILED : ME_SET_NONE;
00439 }
00440
00441 forceinline void
00442 UniverseView::subscribe(Space* home,Propagator*,PropCond) {}
00443 forceinline void
00444 UniverseView::cancel(Propagator*,PropCond) {}
00445
00446 forceinline ModEvent
00447 UniverseView::pme(const Propagator*) {
00448 return ME_SET_NONE;
00449 }
00450 forceinline PropModEvent
00451 UniverseView::pme(ModEvent me) {
00452 return SetVarImp::pme(me);
00453 }
00454
00455 forceinline void
00456 UniverseView::update(Space* home, bool, UniverseView&) {}
00457
00458 forceinline bool
00459 UniverseView::destruct(void) { return false; }
00460
00461
00462
00463
00464
00465
00466
00467
00468
00469
00474 template <>
00475 class LubRanges<EmptyView> : public Iter::Ranges::Empty {
00476 public:
00478
00479
00480 LubRanges(void) {}
00482 LubRanges(const EmptyView& x) {}
00484 void init(const EmptyView& x) {}
00486 };
00487
00492 template <>
00493 class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
00494 public:
00496
00497
00498 GlbRanges(void) {}
00500 GlbRanges(const EmptyView& x) {}
00502 void init(const EmptyView& x) {}
00504 };
00505
00510 template <>
00511 class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
00512 public:
00514
00515
00516 LubRanges(void)
00517 : Iter::Ranges::Singleton(Limits::Set::int_min,
00518 Limits::Set::int_max) {}
00520 LubRanges(const UniverseView& x)
00521 : Iter::Ranges::Singleton(Limits::Set::int_min,
00522 Limits::Set::int_max) {}
00524 void init(const UniverseView& x) {}
00526 };
00527
00532 template <>
00533 class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
00534 public:
00536
00537
00538 GlbRanges(void)
00539 : Iter::Ranges::Singleton(Limits::Set::int_min,
00540 Limits::Set::int_max) {}
00542 GlbRanges(const UniverseView& x)
00543 : Iter::Ranges::Singleton(Limits::Set::int_min,
00544 Limits::Set::int_max) {}
00546 void init(const UniverseView& x) {}
00548 };
00549
00550
00555 template <>
00556 class LubRanges<ConstantView> {
00557 private:
00558 ArrayRanges ar;
00559 public:
00561
00562
00563 LubRanges(void) {}
00565 LubRanges(const ConstantView& x) : ar(x.ranges,x.size) {}
00567 void init(const ConstantView& x) {
00568 ar.init(x.ranges,x.size);
00569 }
00571
00573
00574
00575 bool operator()(void) const { return ar(); }
00577 void operator++(void) { ++ar; }
00579
00581
00582
00583 int min(void) const { return ar.min(); }
00585 int max(void) const { return ar.max(); }
00587 unsigned int width(void) const { return ar.width(); }
00589 };
00590
00595 template <>
00596 class GlbRanges<ConstantView> : public LubRanges<ConstantView> {
00597 public:
00599
00600
00601 GlbRanges(void) {}
00603 GlbRanges(const ConstantView& x) : LubRanges<ConstantView>(x) {}
00605 void init(const ConstantView& x) {
00606 LubRanges<ConstantView>::init(x);
00607 }
00609 };
00610 }
00611
00612
00613
00614
00615
00616
00617 forceinline bool
00618 same(const Set::ConstantView& x, const Set::ConstantView& y) {
00619 if ((x.size != y.size) || (x.domSize != y.domSize))
00620 return false;
00621 for (int i=x.size; i--; )
00622 if (x.ranges[2*i] != y.ranges[2*i] ||
00623 x.ranges[2*i+1] != y.ranges[2*i+1])
00624 return false;
00625 return true;
00626 }
00627 forceinline bool
00628 before(const Set::ConstantView& x, const Set::ConstantView& y) {
00629 if (x.size < y.size)
00630 return true;
00631 if (x.domSize < y.domSize)
00632 return true;
00633 for (int i=x.size; i--; )
00634 if (x.ranges[2*i] < y.ranges[2*i] ||
00635 x.ranges[2*i+1] < y.ranges[2*i+1])
00636 return true;
00637 return false;
00638 }
00639
00640
00641 forceinline bool
00642 same(const Set::EmptyView&, const Set::EmptyView&) {
00643 return true;
00644 }
00645 forceinline bool
00646 before(const Set::EmptyView&, const Set::EmptyView&) {
00647 return false;
00648 }
00649
00650 forceinline bool
00651 same(const Set::UniverseView&, const Set::UniverseView&) {
00652 return true;
00653 }
00654 forceinline bool
00655 before(const Set::UniverseView&, const Set::UniverseView&) {
00656 return false;
00657 }
00658
00659 }
00660
00661
00662