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 namespace Gecode { namespace Set {
00039
00044 class ArrayRanges {
00045 private:
00046 int *_ranges;
00047 int _size;
00048 int _pos;
00049 public:
00051
00052
00053 ArrayRanges(void) : _ranges(NULL), _size(0), _pos(0) {}
00055 ArrayRanges(int *ranges, int size)
00056 : _ranges(ranges), _size(size), _pos(0) {}
00058 void init(int* ranges, int size) {
00059 _ranges = ranges; _size = size; _pos = 0;
00060 }
00062
00064
00065
00066 bool operator ()(void) const { return _pos<_size; }
00068 void operator ++(void) { _pos++; }
00070
00072
00073
00074 int min(void) const { return _ranges[_pos*2]; }
00076 int max(void) const { return _ranges[_pos*2+1]; }
00078 unsigned int width(void) const {
00079 return static_cast<unsigned int>(_ranges[_pos*2+1]-_ranges[_pos*2]+1);
00080 }
00082 };
00083
00084 forceinline
00085 ConstantView::ConstantView(void) : ranges(NULL), size(0), domSize(0) {}
00086
00087 forceinline
00088 void
00089 ConstantView::init(Space& home, const IntSet& dom) {
00090 size = dom.ranges();
00091 domSize = 0;
00092 if (size > 0) {
00093 ranges = home.alloc<int>(2*size);
00094 IntSetRanges dr(dom);
00095 for (int i=0; dr(); ++dr, i+=2) {
00096 int min = dr.min(); int max = dr.max();
00097 ranges[i] = min;
00098 ranges[i+1] = max;
00099 domSize += static_cast<unsigned int>(max-min+1);
00100 }
00101 } else {
00102 ranges = NULL;
00103 }
00104 }
00105
00106 forceinline
00107 ConstantView::ConstantView(Space& home, const IntSet& dom) {
00108 init(home, dom);
00109 }
00110
00111 forceinline bool
00112 ConstantView::assigned(void) const { return true; }
00113
00114 forceinline unsigned int
00115 ConstantView::glbSize(void) const { return domSize; }
00116
00117 forceinline unsigned int
00118 ConstantView::lubSize(void) const { return domSize; }
00119
00120 forceinline unsigned int
00121 ConstantView::unknownSize(void) const { return 0; }
00122
00123 forceinline bool
00124 ConstantView::contains(int i) const {
00125 for (int j=size; j--; ) {
00126 if (ranges[2*j+1] < i)
00127 return false;
00128 if (ranges[2*j] >= i)
00129 return true;
00130 }
00131 return false;
00132 }
00133
00134 forceinline bool
00135 ConstantView::notContains(int i) const {
00136 return !contains(i);
00137 }
00138
00139 forceinline unsigned int
00140 ConstantView::cardMin(void) const { return domSize; }
00141
00142 forceinline unsigned int
00143 ConstantView::cardMax(void) const { return domSize; }
00144
00145 forceinline int
00146 ConstantView::lubMin(void) const {
00147 return size==0 ? BndSet::MIN_OF_EMPTY : ranges[0];
00148 }
00149
00150 forceinline int
00151 ConstantView::lubMax(void) const {
00152 return size==0 ? BndSet::MAX_OF_EMPTY : ranges[size*2-1];
00153 }
00154
00155 forceinline int
00156 ConstantView::glbMin(void) const { return lubMin(); }
00157
00158 forceinline int
00159 ConstantView::glbMax(void) const { return lubMax(); }
00160
00161 forceinline ModEvent
00162 ConstantView::cardMin(Space&,unsigned int c) {
00163 return c<=domSize ? ME_SET_NONE : ME_SET_FAILED;
00164 }
00165
00166 forceinline ModEvent
00167 ConstantView::cardMax(Space&,unsigned int c) {
00168 return c>=domSize ? ME_SET_NONE : ME_SET_FAILED;
00169 }
00170
00171 forceinline ModEvent
00172 ConstantView::include(Space&,int c) {
00173 return contains(c) ? ME_SET_NONE : ME_SET_FAILED;
00174 }
00175
00176 forceinline ModEvent
00177 ConstantView::exclude(Space&,int c) {
00178 return contains(c) ? ME_SET_FAILED : ME_SET_NONE;
00179 }
00180
00181 forceinline ModEvent
00182 ConstantView::intersect(Space&,int c) {
00183 return (size==0 ||
00184 (size==1 &&
00185 ranges[0]==ranges[1] && ranges[0]==c)) ?
00186 ME_SET_NONE : ME_SET_FAILED;
00187 }
00188
00189 forceinline ModEvent
00190 ConstantView::intersect(Space&,int i,int j) {
00191 return (glbMin()>=i && glbMax()<=j) ?
00192 ME_SET_NONE : ME_SET_FAILED;
00193 }
00194
00195 forceinline ModEvent
00196 ConstantView::include(Space&,int i,int j) {
00197 Iter::Ranges::Singleton single(i,j);
00198 ArrayRanges ar(ranges, size);
00199 return (single() && Iter::Ranges::subset(single, ar)) ?
00200 ME_SET_NONE : ME_SET_FAILED;
00201 }
00202
00203 forceinline ModEvent
00204 ConstantView::exclude(Space&,int i,int j) {
00205 Iter::Ranges::Singleton single(i,j);
00206 ArrayRanges ar(ranges, size);
00207 return (single() && Iter::Ranges::subset(single, ar)) ?
00208 ME_SET_FAILED : ME_SET_NONE;
00209 }
00210
00211 template<class I> ModEvent
00212 ConstantView::excludeI(Space&,I& i) {
00213 Iter::Ranges::IsRangeIter<I>();
00214 ArrayRanges ar(ranges, size);
00215 return (i() && Iter::Ranges::subset(i, ar)) ? ME_SET_FAILED : ME_SET_NONE;
00216 }
00217
00218 template<class I> ModEvent
00219 ConstantView::includeI(Space&,I& i) {
00220 Iter::Ranges::IsRangeIter<I>();
00221 ArrayRanges ar(ranges, size);
00222 return Iter::Ranges::subset(i, ar) ? ME_SET_NONE : ME_SET_FAILED;
00223 }
00224
00225 template<class I> ModEvent
00226 ConstantView::intersectI(Space&,I& i) {
00227 Iter::Ranges::IsRangeIter<I>();
00228 ArrayRanges ar(ranges, size);
00229 return Iter::Ranges::subset(ar, i) ? ME_SET_NONE : ME_SET_FAILED;
00230 }
00231
00232 forceinline void
00233 ConstantView::schedule(Space& home, Propagator& p, ModEvent me) {
00234 return SetView::schedule(home,p,me);
00235 }
00236 forceinline ModEvent
00237 ConstantView::me(const ModEventDelta&) {
00238 return ME_SET_NONE;
00239 }
00240 forceinline ModEventDelta
00241 ConstantView::med(ModEvent me) {
00242 return SetVarImp::med(me);
00243 }
00244
00245 forceinline void
00246 ConstantView::subscribe(Space& home, Propagator& p, PropCond,bool) {
00247 schedule(home,p,ME_SET_VAL);
00248 }
00249 forceinline void
00250 ConstantView::cancel(Space&,Propagator&,PropCond) {}
00251
00252 forceinline void
00253 ConstantView::subscribe(Space&, Advisor&) {}
00254 forceinline void
00255 ConstantView::cancel(Space&,Advisor&) {}
00256
00257 forceinline void
00258 ConstantView::update(Space& home, bool, ConstantView& p) {
00259
00260 if (size > 0)
00261 home.free<int>(ranges, 2);
00262
00263 domSize = p.domSize;
00264 size = p.size;
00265 if (size == 0) {
00266 ranges = NULL;
00267 } else {
00268
00269 ranges = home.alloc<int>(2*size);
00270 for (int i=size; i--; ) {
00271 ranges[2*i] = p.ranges[2*i];
00272 ranges[2*i+1] = p.ranges[2*i+1];
00273 }
00274 }
00275 }
00276
00277
00278
00279
00280
00281
00282
00283 forceinline ModEvent
00284 ConstantView::modevent(const Delta&) {
00285 GECODE_NEVER;
00286 return ME_GEN_NONE;
00287 }
00288
00289 forceinline int
00290 ConstantView::glbMin(const Delta&) const {
00291 GECODE_NEVER;
00292 return 0;
00293 }
00294
00295 forceinline int
00296 ConstantView::glbMax(const Delta&) const {
00297 GECODE_NEVER;
00298 return 0;
00299 }
00300
00301 forceinline bool
00302 ConstantView::glbAny(const Delta&) const {
00303 GECODE_NEVER;
00304 return false;
00305 }
00306
00307 forceinline int
00308 ConstantView::lubMin(const Delta&) const {
00309 GECODE_NEVER;
00310 return 0;
00311 }
00312
00313 forceinline int
00314 ConstantView::lubMax(const Delta&) const {
00315 GECODE_NEVER;
00316 return 0;
00317 }
00318
00319 forceinline bool
00320 ConstantView::lubAny(const Delta&) const {
00321 GECODE_NEVER;
00322 return false;
00323 }
00324
00325 forceinline
00326 EmptyView::EmptyView(void) {}
00327
00328
00329
00330 forceinline bool
00331 EmptyView::assigned(void) const { return true; }
00332
00333 forceinline unsigned int
00334 EmptyView::glbSize(void) const { return 0; }
00335
00336 forceinline unsigned int
00337 EmptyView::lubSize(void) const { return 0; }
00338
00339 forceinline unsigned int
00340 EmptyView::unknownSize(void) const { return 0; }
00341
00342 forceinline bool
00343 EmptyView::contains(int) const { return false; }
00344
00345 forceinline bool
00346 EmptyView::notContains(int) const { return true; }
00347
00348 forceinline unsigned int
00349 EmptyView::cardMin(void) const { return 0; }
00350
00351 forceinline unsigned int
00352 EmptyView::cardMax(void) const { return 0; }
00353
00354 forceinline int
00355 EmptyView::lubMin(void) const { return 0; }
00356
00357 forceinline int
00358 EmptyView::lubMax(void) const { return 0; }
00359
00360 forceinline int
00361 EmptyView::glbMin(void) const { return 0; }
00362
00363 forceinline int
00364 EmptyView::glbMax(void) const { return 0; }
00365
00366 forceinline ModEvent
00367 EmptyView::cardMin(Space&,unsigned int c) {
00368 return c==0 ? ME_SET_NONE : ME_SET_FAILED;
00369 }
00370
00371 forceinline ModEvent
00372 EmptyView::cardMax(Space&,unsigned int) {
00373 return ME_SET_NONE;
00374 }
00375
00376
00377 forceinline ModEvent
00378 EmptyView::include(Space&,int) {
00379 return ME_SET_FAILED;
00380 }
00381
00382 forceinline ModEvent
00383 EmptyView::exclude(Space&,int) { return ME_SET_NONE; }
00384
00385 forceinline ModEvent
00386 EmptyView::intersect(Space&,int) { return ME_SET_NONE; }
00387
00388 forceinline ModEvent
00389 EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; }
00390
00391 forceinline ModEvent
00392 EmptyView::include(Space&,int,int) {
00393 return ME_SET_FAILED; }
00394
00395 forceinline ModEvent
00396 EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; }
00397
00398 template<class I> ModEvent
00399 EmptyView::excludeI(Space&,I&) {
00400 Iter::Ranges::IsRangeIter<I>();
00401 return ME_SET_NONE;
00402 }
00403
00404 template<class I> ModEvent
00405 EmptyView::includeI(Space&,I& i) {
00406 Iter::Ranges::IsRangeIter<I>();
00407 return i() ? ME_SET_FAILED : ME_SET_NONE;
00408 }
00409
00410 template<class I> ModEvent
00411 EmptyView::intersectI(Space&,I&) {
00412 Iter::Ranges::IsRangeIter<I>();
00413 return ME_SET_NONE;
00414 }
00415
00416 forceinline void
00417 EmptyView::schedule(Space& home, Propagator& p, ModEvent me) {
00418 return SetView::schedule(home,p,me);
00419 }
00420 forceinline ModEvent
00421 EmptyView::me(const ModEventDelta&) {
00422 return ME_SET_NONE;
00423 }
00424 forceinline ModEventDelta
00425 EmptyView::med(ModEvent me) {
00426 return SetVarImp::med(me);
00427 }
00428
00429 forceinline void
00430 EmptyView::subscribe(Space& home, Propagator& p, PropCond,bool) {
00431 schedule(home,p,ME_SET_VAL);
00432 }
00433 forceinline void
00434 EmptyView::cancel(Space&,Propagator&,PropCond) {}
00435 forceinline void
00436 EmptyView::subscribe(Space&, Advisor&) {}
00437 forceinline void
00438 EmptyView::cancel(Space&,Advisor&) {}
00439
00440
00441 forceinline void
00442 EmptyView::update(Space&, bool, EmptyView&) {}
00443
00444
00445
00446
00447
00448
00449
00450 forceinline ModEvent
00451 EmptyView::modevent(const Delta&) {
00452 GECODE_NEVER;
00453 return ME_GEN_NONE;
00454 }
00455
00456 forceinline int
00457 EmptyView::glbMin(const Delta&) const {
00458 GECODE_NEVER;
00459 return 0;
00460 }
00461
00462 forceinline int
00463 EmptyView::glbMax(const Delta&) const {
00464 GECODE_NEVER;
00465 return 0;
00466 }
00467
00468 forceinline bool
00469 EmptyView::glbAny(const Delta&) const {
00470 GECODE_NEVER;
00471 return false;
00472 }
00473
00474 forceinline int
00475 EmptyView::lubMin(const Delta&) const {
00476 GECODE_NEVER;
00477 return 0;
00478 }
00479
00480 forceinline int
00481 EmptyView::lubMax(const Delta&) const {
00482 GECODE_NEVER;
00483 return 0;
00484 }
00485
00486 forceinline bool
00487 EmptyView::lubAny(const Delta&) const {
00488 GECODE_NEVER;
00489 return false;
00490 }
00491
00492
00493
00494 forceinline
00495 UniverseView::UniverseView(void) {}
00496
00497 forceinline bool
00498 UniverseView::assigned(void) const { return true; }
00499
00500 forceinline unsigned int
00501 UniverseView::glbSize(void) const { return Set::Limits::card; }
00502
00503 forceinline unsigned int
00504 UniverseView::lubSize(void) const { return Set::Limits::card; }
00505
00506 forceinline unsigned int
00507 UniverseView::unknownSize(void) const { return 0; }
00508
00509 forceinline bool
00510 UniverseView::contains(int) const { return true; }
00511
00512 forceinline bool
00513 UniverseView::notContains(int) const { return false; }
00514
00515 forceinline unsigned int
00516 UniverseView::cardMin(void) const { return Set::Limits::card; }
00517
00518 forceinline unsigned int
00519 UniverseView::cardMax(void) const { return Limits::card; }
00520
00521 forceinline int
00522 UniverseView::lubMin(void) const { return Limits::card; }
00523
00524 forceinline int
00525 UniverseView::lubMax(void) const { return Limits::card; }
00526
00527 forceinline int
00528 UniverseView::glbMin(void) const { return Limits::card; }
00529
00530 forceinline int
00531 UniverseView::glbMax(void) const { return Limits::card; }
00532
00533 forceinline ModEvent
00534 UniverseView::cardMin(Space&,unsigned int c) {
00535 return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE;
00536 }
00537
00538 forceinline ModEvent
00539 UniverseView::cardMax(Space&,unsigned int c) {
00540 return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED;
00541 }
00542
00543
00544 forceinline ModEvent
00545 UniverseView::include(Space&,int) {
00546 return ME_SET_NONE;
00547 }
00548
00549 forceinline ModEvent
00550 UniverseView::exclude(Space&,int) { return ME_SET_FAILED; }
00551
00552 forceinline ModEvent
00553 UniverseView::intersect(Space&,int) { return ME_SET_FAILED; }
00554
00555 forceinline ModEvent
00556 UniverseView::include(Space&,int,int) { return ME_SET_NONE; }
00557
00558 forceinline ModEvent
00559 UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; }
00560
00561 template<class I> ModEvent
00562 UniverseView::excludeI(Space&,I& i) {
00563 Iter::Ranges::IsRangeIter<I>();
00564 return i() ? ME_SET_FAILED : ME_SET_NONE;
00565 }
00566
00567 template<class I> forceinline ModEvent
00568 UniverseView::includeI(Space&,I&) {
00569 Iter::Ranges::IsRangeIter<I>();
00570 return ME_SET_NONE;
00571 }
00572
00573 forceinline ModEvent
00574 UniverseView::intersect(Space&,int i,int j) {
00575 return (i>Limits::min ||
00576 j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE;
00577 }
00578
00579 template<class I> forceinline ModEvent
00580 UniverseView::intersectI(Space&,I& i) {
00581 Iter::Ranges::IsRangeIter<I>();
00582 return (i() &&
00583 (i.min()>Limits::min ||
00584 i.max()<Limits::max) ) ?
00585 ME_SET_FAILED : ME_SET_NONE;
00586 }
00587
00588 forceinline void
00589 UniverseView::schedule(Space& home, Propagator& p, ModEvent me) {
00590 return SetView::schedule(home,p,me);
00591 }
00592 forceinline ModEvent
00593 UniverseView::me(const ModEventDelta&) {
00594 return ME_SET_NONE;
00595 }
00596 forceinline ModEventDelta
00597 UniverseView::med(ModEvent me) {
00598 return SetVarImp::med(me);
00599 }
00600 forceinline void
00601 UniverseView::subscribe(Space& home, Propagator& p, PropCond,bool) {
00602 schedule(home,p,ME_SET_VAL);
00603 }
00604 forceinline void
00605 UniverseView::cancel(Space&,Propagator&,PropCond) {}
00606
00607 forceinline void
00608 UniverseView::subscribe(Space&,Advisor&) {}
00609 forceinline void
00610 UniverseView::cancel(Space&,Advisor&) {}
00611
00612
00613 forceinline void
00614 UniverseView::update(Space&, bool, UniverseView&) {}
00615
00616
00617
00618
00619
00620
00621
00622 forceinline ModEvent
00623 UniverseView::modevent(const Delta&) {
00624 GECODE_NEVER;
00625 return ME_GEN_NONE;
00626 }
00627
00628 forceinline int
00629 UniverseView::glbMin(const Delta&) const {
00630 GECODE_NEVER;
00631 return 0;
00632 }
00633
00634 forceinline int
00635 UniverseView::glbMax(const Delta&) const {
00636 GECODE_NEVER;
00637 return 0;
00638 }
00639
00640 forceinline bool
00641 UniverseView::glbAny(const Delta&) const {
00642 GECODE_NEVER;
00643 return false;
00644 }
00645
00646 forceinline int
00647 UniverseView::lubMin(const Delta&) const {
00648 GECODE_NEVER;
00649 return 0;
00650 }
00651
00652 forceinline int
00653 UniverseView::lubMax(const Delta&) const {
00654 GECODE_NEVER;
00655 return 0;
00656 }
00657
00658 forceinline bool
00659 UniverseView::lubAny(const Delta&) const {
00660 GECODE_NEVER;
00661 return false;
00662 }
00663
00664
00665
00666
00667
00668
00673 template<>
00674 class LubRanges<EmptyView> : public Iter::Ranges::Empty {
00675 public:
00677
00678
00679 LubRanges(void) {}
00681 LubRanges(const EmptyView& x) { (void)x; }
00683 void init(const EmptyView& x) { (void)x; }
00685 };
00686
00691 template<>
00692 class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
00693 public:
00695
00696
00697 GlbRanges(void) {}
00699 GlbRanges(const EmptyView& x) { (void)x; }
00701 void init(const EmptyView& x) { (void)x; }
00703 };
00704
00709 template<>
00710 class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
00711 public:
00713
00714
00715 LubRanges(void)
00716 : Iter::Ranges::Singleton(Limits::min,
00717 Limits::max) {}
00719 LubRanges(const UniverseView& x)
00720 : Iter::Ranges::Singleton(Limits::min,
00721 Limits::max) {
00722 (void)x;
00723 }
00725 void init(const UniverseView& x) { (void)x; }
00727 };
00728
00733 template<>
00734 class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
00735 public:
00737
00738
00739 GlbRanges(void)
00740 : Iter::Ranges::Singleton(Limits::min,
00741 Limits::max) {}
00743 GlbRanges(const UniverseView& x)
00744 : Iter::Ranges::Singleton(Limits::min,
00745 Limits::max) {
00746 (void)x;
00747 }
00749 void init(const UniverseView& x) { (void)x; }
00751 };
00752
00753
00758 template<>
00759 class LubRanges<ConstantView> {
00760 private:
00761 ArrayRanges ar;
00762 public:
00764
00765
00766 LubRanges(void) {}
00768 LubRanges(const ConstantView& x) : ar(x.ranges,x.size) {}
00770 void init(const ConstantView& x) {
00771 ar.init(x.ranges,x.size);
00772 }
00774
00776
00777
00778 bool operator ()(void) const { return ar(); }
00780 void operator ++(void) { ++ar; }
00782
00784
00785
00786 int min(void) const { return ar.min(); }
00788 int max(void) const { return ar.max(); }
00790 unsigned int width(void) const { return ar.width(); }
00792 };
00793
00798 template<>
00799 class GlbRanges<ConstantView> : public LubRanges<ConstantView> {
00800 public:
00802
00803
00804 GlbRanges(void) {}
00806 GlbRanges(const ConstantView& x) : LubRanges<ConstantView>(x) {}
00808 void init(const ConstantView& x) {
00809 LubRanges<ConstantView>::init(x);
00810 }
00812 };
00813 }
00814
00815
00816
00817
00818
00819
00820 forceinline bool
00821 same(const Set::ConstantView& x, const Set::ConstantView& y) {
00822 if ((x.size != y.size) || (x.domSize != y.domSize))
00823 return false;
00824 for (int i=x.size; i--; )
00825 if (x.ranges[2*i] != y.ranges[2*i] ||
00826 x.ranges[2*i+1] != y.ranges[2*i+1])
00827 return false;
00828 return true;
00829 }
00830 forceinline bool
00831 before(const Set::ConstantView& x, const Set::ConstantView& y) {
00832 if (x.size < y.size)
00833 return true;
00834 if (x.domSize < y.domSize)
00835 return true;
00836 for (int i=x.size; i--; )
00837 if (x.ranges[2*i] < y.ranges[2*i] ||
00838 x.ranges[2*i+1] < y.ranges[2*i+1])
00839 return true;
00840 return false;
00841 }
00842
00843
00844 forceinline bool
00845 same(const Set::EmptyView&, const Set::EmptyView&) {
00846 return true;
00847 }
00848 forceinline bool
00849 before(const Set::EmptyView&, const Set::EmptyView&) {
00850 return false;
00851 }
00852
00853 forceinline bool
00854 same(const Set::UniverseView&, const Set::UniverseView&) {
00855 return true;
00856 }
00857 forceinline bool
00858 before(const Set::UniverseView&, const Set::UniverseView&) {
00859 return false;
00860 }
00861
00862 }
00863
00864
00865