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,bool) {}
00206 forceinline void
00207 ConstantView::cancel(Space* home, 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
00240 EmptyView::EmptyView(void) {}
00241
00242
00243 forceinline bool
00244 EmptyView::assigned(void) const { return true; }
00245
00246 forceinline unsigned int
00247 EmptyView::glbSize(void) const { return 0; }
00248
00249 forceinline unsigned int
00250 EmptyView::lubSize(void) const { return 0; }
00251
00252 forceinline unsigned int
00253 EmptyView::unknownSize(void) const { return 0; }
00254
00255 forceinline bool
00256 EmptyView::contains(int) const { return false; }
00257
00258 forceinline bool
00259 EmptyView::notContains(int) const { return true; }
00260
00261 forceinline unsigned int
00262 EmptyView::cardMin() const { return 0; }
00263
00264 forceinline unsigned int
00265 EmptyView::cardMax() const { return 0; }
00266
00267 forceinline int
00268 EmptyView::lubMin() const { return 0; }
00269
00270 forceinline int
00271 EmptyView::lubMax() const { return 0; }
00272
00273 forceinline int
00274 EmptyView::glbMin() const { return 0; }
00275
00276 forceinline int
00277 EmptyView::glbMax() const { return 0; }
00278
00279 forceinline ModEvent
00280 EmptyView::cardMin(Space* home,unsigned int c) {
00281 return c==0 ? ME_SET_NONE : ME_SET_FAILED;
00282 }
00283
00284 forceinline ModEvent
00285 EmptyView::cardMax(Space* home,unsigned int c) {
00286 return ME_SET_NONE;
00287 }
00288
00289
00290 forceinline ModEvent
00291 EmptyView::include(Space* home,int) {
00292 return ME_SET_FAILED;
00293 }
00294
00295 forceinline ModEvent
00296 EmptyView::exclude(Space* home,int) { return ME_SET_NONE; }
00297
00298 forceinline ModEvent
00299 EmptyView::intersect(Space* home,int) { return ME_SET_NONE; }
00300
00301 forceinline ModEvent
00302 EmptyView::intersect(Space* home,int,int) { return ME_SET_NONE; }
00303
00304 forceinline ModEvent
00305 EmptyView::include(Space* home,int,int) {
00306 return ME_SET_FAILED; }
00307
00308 forceinline ModEvent
00309 EmptyView::exclude(Space* home,int,int) { return ME_SET_NONE; }
00310
00311 template <class I> ModEvent
00312 EmptyView::excludeI(Space* home,I&) { return ME_SET_NONE; }
00313
00314 template <class I> ModEvent
00315 EmptyView::includeI(Space* home,I& i) {
00316 return i() ? ME_SET_FAILED : ME_SET_NONE;
00317 }
00318
00319 template <class I> ModEvent
00320 EmptyView::intersectI(Space* home,I&) {
00321 return ME_SET_NONE;
00322 }
00323
00324 forceinline void
00325 EmptyView::subscribe(Space* home,Propagator*,PropCond,bool) {}
00326 forceinline void
00327 EmptyView::cancel(Space* home, Propagator*,PropCond) {}
00328
00329 forceinline ModEvent
00330 EmptyView::pme(const Propagator*) {
00331 return ME_SET_NONE;
00332 }
00333 forceinline PropModEvent
00334 EmptyView::pme(ModEvent me) {
00335 return SetVarImp::pme(me);
00336 }
00337
00338 forceinline void
00339 EmptyView::update(Space* home, bool, EmptyView&) {}
00340
00341
00342
00343
00344
00345 forceinline
00346 UniverseView::UniverseView(void) {}
00347
00348 forceinline bool
00349 UniverseView::assigned(void) const { return true; }
00350
00351 forceinline unsigned int
00352 UniverseView::glbSize(void) const { return Limits::Set::card_max; }
00353
00354 forceinline unsigned int
00355 UniverseView::lubSize(void) const { return Limits::Set::card_max; }
00356
00357 forceinline unsigned int
00358 UniverseView::unknownSize(void) const { return 0; }
00359
00360 forceinline bool
00361 UniverseView::contains(int) const { return true; }
00362
00363 forceinline bool
00364 UniverseView::notContains(int) const { return false; }
00365
00366 forceinline unsigned int
00367 UniverseView::cardMin() const { return Limits::Set::card_max; }
00368
00369 forceinline unsigned int
00370 UniverseView::cardMax() const { return Limits::Set::card_max; }
00371
00372 forceinline int
00373 UniverseView::lubMin() const { return Limits::Set::card_max; }
00374
00375 forceinline int
00376 UniverseView::lubMax() const { return Limits::Set::card_max; }
00377
00378 forceinline int
00379 UniverseView::glbMin() const { return Limits::Set::card_max; }
00380
00381 forceinline int
00382 UniverseView::glbMax() const { return Limits::Set::card_max; }
00383
00384 forceinline ModEvent
00385 UniverseView::cardMin(Space* home,unsigned int c) {
00386 return c>Limits::Set::card_max ? ME_SET_FAILED : ME_SET_NONE;
00387 }
00388
00389 forceinline ModEvent
00390 UniverseView::cardMax(Space* home,unsigned int c) {
00391 return c>=Limits::Set::card_max ? ME_SET_NONE : ME_SET_FAILED;
00392 }
00393
00394
00395 forceinline ModEvent
00396 UniverseView::include(Space* home,int) {
00397 return ME_SET_NONE;
00398 }
00399
00400 forceinline ModEvent
00401 UniverseView::exclude(Space* home,int) { return ME_SET_FAILED; }
00402
00403 forceinline ModEvent
00404 UniverseView::intersect(Space* home,int) { return ME_SET_FAILED; }
00405
00406 forceinline ModEvent
00407 UniverseView::include(Space* home,int,int) { return ME_SET_NONE; }
00408
00409 forceinline ModEvent
00410 UniverseView::exclude(Space* home,int,int) { return ME_SET_FAILED; }
00411
00412 template <class I> ModEvent
00413 UniverseView::excludeI(Space* home,I& i) {
00414 return i() ? ME_SET_FAILED : ME_SET_NONE;
00415 }
00416
00417 template <class I> forceinline ModEvent
00418 UniverseView::includeI(Space* home,I&) { return ME_SET_NONE; }
00419
00420 forceinline ModEvent
00421 UniverseView::intersect(Space* home,int i,int j) {
00422 return (i>Limits::Set::int_min ||
00423 i<Limits::Set::int_max) ? ME_SET_FAILED : ME_SET_NONE;
00424 }
00425
00426 template <class I> forceinline ModEvent
00427 UniverseView::intersectI(Space* home,I& i) {
00428 return (i() &&
00429 (i.min()>Limits::Set::int_min ||
00430 i.max()<Limits::Set::int_max) ) ?
00431 ME_SET_FAILED : ME_SET_NONE;
00432 }
00433
00434 forceinline void
00435 UniverseView::subscribe(Space* home,Propagator*,PropCond,bool) {}
00436 forceinline void
00437 UniverseView::cancel(Space* home, Propagator*,PropCond) {}
00438
00439 forceinline ModEvent
00440 UniverseView::pme(const Propagator*) {
00441 return ME_SET_NONE;
00442 }
00443 forceinline PropModEvent
00444 UniverseView::pme(ModEvent me) {
00445 return SetVarImp::pme(me);
00446 }
00447
00448 forceinline void
00449 UniverseView::update(Space* home, bool, UniverseView&) {}
00450
00451
00452
00453
00454
00455
00456
00457
00458
00463 template <>
00464 class LubRanges<EmptyView> : public Iter::Ranges::Empty {
00465 public:
00467
00468
00469 LubRanges(void) {}
00471 LubRanges(const EmptyView& x) {}
00473 void init(const EmptyView& x) {}
00475 };
00476
00481 template <>
00482 class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
00483 public:
00485
00486
00487 GlbRanges(void) {}
00489 GlbRanges(const EmptyView& x) {}
00491 void init(const EmptyView& x) {}
00493 };
00494
00499 template <>
00500 class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
00501 public:
00503
00504
00505 LubRanges(void)
00506 : Iter::Ranges::Singleton(Limits::Set::int_min,
00507 Limits::Set::int_max) {}
00509 LubRanges(const UniverseView& x)
00510 : Iter::Ranges::Singleton(Limits::Set::int_min,
00511 Limits::Set::int_max) {}
00513 void init(const UniverseView& x) {}
00515 };
00516
00521 template <>
00522 class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
00523 public:
00525
00526
00527 GlbRanges(void)
00528 : Iter::Ranges::Singleton(Limits::Set::int_min,
00529 Limits::Set::int_max) {}
00531 GlbRanges(const UniverseView& x)
00532 : Iter::Ranges::Singleton(Limits::Set::int_min,
00533 Limits::Set::int_max) {}
00535 void init(const UniverseView& x) {}
00537 };
00538
00539
00544 template <>
00545 class LubRanges<ConstantView> {
00546 private:
00547 ArrayRanges ar;
00548 public:
00550
00551
00552 LubRanges(void) {}
00554 LubRanges(const ConstantView& x) : ar(x.ranges,x.size) {}
00556 void init(const ConstantView& x) {
00557 ar.init(x.ranges,x.size);
00558 }
00560
00562
00563
00564 bool operator()(void) const { return ar(); }
00566 void operator++(void) { ++ar; }
00568
00570
00571
00572 int min(void) const { return ar.min(); }
00574 int max(void) const { return ar.max(); }
00576 unsigned int width(void) const { return ar.width(); }
00578 };
00579
00584 template <>
00585 class GlbRanges<ConstantView> : public LubRanges<ConstantView> {
00586 public:
00588
00589
00590 GlbRanges(void) {}
00592 GlbRanges(const ConstantView& x) : LubRanges<ConstantView>(x) {}
00594 void init(const ConstantView& x) {
00595 LubRanges<ConstantView>::init(x);
00596 }
00598 };
00599 }
00600
00601
00602
00603
00604
00605
00606 forceinline bool
00607 same(const Set::ConstantView& x, const Set::ConstantView& y) {
00608 if ((x.size != y.size) || (x.domSize != y.domSize))
00609 return false;
00610 for (int i=x.size; i--; )
00611 if (x.ranges[2*i] != y.ranges[2*i] ||
00612 x.ranges[2*i+1] != y.ranges[2*i+1])
00613 return false;
00614 return true;
00615 }
00616 forceinline bool
00617 before(const Set::ConstantView& x, const Set::ConstantView& y) {
00618 if (x.size < y.size)
00619 return true;
00620 if (x.domSize < y.domSize)
00621 return true;
00622 for (int i=x.size; i--; )
00623 if (x.ranges[2*i] < y.ranges[2*i] ||
00624 x.ranges[2*i+1] < y.ranges[2*i+1])
00625 return true;
00626 return false;
00627 }
00628
00629
00630 forceinline bool
00631 same(const Set::EmptyView&, const Set::EmptyView&) {
00632 return true;
00633 }
00634 forceinline bool
00635 before(const Set::EmptyView&, const Set::EmptyView&) {
00636 return false;
00637 }
00638
00639 forceinline bool
00640 same(const Set::UniverseView&, const Set::UniverseView&) {
00641 return true;
00642 }
00643 forceinline bool
00644 before(const Set::UniverseView&, const Set::UniverseView&) {
00645 return false;
00646 }
00647
00648 }
00649
00650
00651