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,
00247 bool process) {
00248 if (process)
00249 schedule(home,p,ME_SET_VAL);
00250 }
00251 forceinline void
00252 ConstantView::cancel(Space&,Propagator&,PropCond) {}
00253
00254 forceinline void
00255 ConstantView::subscribe(Space&, Advisor&) {}
00256 forceinline void
00257 ConstantView::cancel(Space&,Advisor&) {}
00258
00259 forceinline void
00260 ConstantView::update(Space& home, bool, ConstantView& p) {
00261
00262 if (size > 0)
00263 home.free<int>(ranges, 2);
00264
00265 domSize = p.domSize;
00266 size = p.size;
00267 if (size == 0) {
00268 ranges = NULL;
00269 } else {
00270
00271 ranges = home.alloc<int>(2*size);
00272 for (int i=size; i--; ) {
00273 ranges[2*i] = p.ranges[2*i];
00274 ranges[2*i+1] = p.ranges[2*i+1];
00275 }
00276 }
00277 }
00278
00279
00280
00281
00282
00283
00284
00285 forceinline ModEvent
00286 ConstantView::modevent(const Delta&) {
00287 GECODE_NEVER;
00288 return ME_GEN_NONE;
00289 }
00290
00291 forceinline int
00292 ConstantView::glbMin(const Delta&) const {
00293 GECODE_NEVER;
00294 return 0;
00295 }
00296
00297 forceinline int
00298 ConstantView::glbMax(const Delta&) const {
00299 GECODE_NEVER;
00300 return 0;
00301 }
00302
00303 forceinline bool
00304 ConstantView::glbAny(const Delta&) const {
00305 GECODE_NEVER;
00306 return false;
00307 }
00308
00309 forceinline int
00310 ConstantView::lubMin(const Delta&) const {
00311 GECODE_NEVER;
00312 return 0;
00313 }
00314
00315 forceinline int
00316 ConstantView::lubMax(const Delta&) const {
00317 GECODE_NEVER;
00318 return 0;
00319 }
00320
00321 forceinline bool
00322 ConstantView::lubAny(const Delta&) const {
00323 GECODE_NEVER;
00324 return false;
00325 }
00326
00327 forceinline
00328 EmptyView::EmptyView(void) {}
00329
00330
00331
00332 forceinline bool
00333 EmptyView::assigned(void) const { return true; }
00334
00335 forceinline unsigned int
00336 EmptyView::glbSize(void) const { return 0; }
00337
00338 forceinline unsigned int
00339 EmptyView::lubSize(void) const { return 0; }
00340
00341 forceinline unsigned int
00342 EmptyView::unknownSize(void) const { return 0; }
00343
00344 forceinline bool
00345 EmptyView::contains(int) const { return false; }
00346
00347 forceinline bool
00348 EmptyView::notContains(int) const { return true; }
00349
00350 forceinline unsigned int
00351 EmptyView::cardMin(void) const { return 0; }
00352
00353 forceinline unsigned int
00354 EmptyView::cardMax(void) const { return 0; }
00355
00356 forceinline int
00357 EmptyView::lubMin(void) const { return 0; }
00358
00359 forceinline int
00360 EmptyView::lubMax(void) const { return 0; }
00361
00362 forceinline int
00363 EmptyView::glbMin(void) const { return 0; }
00364
00365 forceinline int
00366 EmptyView::glbMax(void) const { return 0; }
00367
00368 forceinline ModEvent
00369 EmptyView::cardMin(Space&,unsigned int c) {
00370 return c==0 ? ME_SET_NONE : ME_SET_FAILED;
00371 }
00372
00373 forceinline ModEvent
00374 EmptyView::cardMax(Space&,unsigned int) {
00375 return ME_SET_NONE;
00376 }
00377
00378
00379 forceinline ModEvent
00380 EmptyView::include(Space&,int) {
00381 return ME_SET_FAILED;
00382 }
00383
00384 forceinline ModEvent
00385 EmptyView::exclude(Space&,int) { return ME_SET_NONE; }
00386
00387 forceinline ModEvent
00388 EmptyView::intersect(Space&,int) { return ME_SET_NONE; }
00389
00390 forceinline ModEvent
00391 EmptyView::intersect(Space&,int,int) { return ME_SET_NONE; }
00392
00393 forceinline ModEvent
00394 EmptyView::include(Space&,int,int) {
00395 return ME_SET_FAILED; }
00396
00397 forceinline ModEvent
00398 EmptyView::exclude(Space&,int,int) { return ME_SET_NONE; }
00399
00400 template<class I> ModEvent
00401 EmptyView::excludeI(Space&,I&) {
00402 Iter::Ranges::IsRangeIter<I>();
00403 return ME_SET_NONE;
00404 }
00405
00406 template<class I> ModEvent
00407 EmptyView::includeI(Space&,I& i) {
00408 Iter::Ranges::IsRangeIter<I>();
00409 return i() ? ME_SET_FAILED : ME_SET_NONE;
00410 }
00411
00412 template<class I> ModEvent
00413 EmptyView::intersectI(Space&,I&) {
00414 Iter::Ranges::IsRangeIter<I>();
00415 return ME_SET_NONE;
00416 }
00417
00418 forceinline void
00419 EmptyView::schedule(Space& home, Propagator& p, ModEvent me) {
00420 return SetView::schedule(home,p,me);
00421 }
00422 forceinline ModEvent
00423 EmptyView::me(const ModEventDelta&) {
00424 return ME_SET_NONE;
00425 }
00426 forceinline ModEventDelta
00427 EmptyView::med(ModEvent me) {
00428 return SetVarImp::med(me);
00429 }
00430
00431 forceinline void
00432 EmptyView::subscribe(Space& home, Propagator& p, PropCond,
00433 bool process) {
00434 if (process)
00435 schedule(home,p,ME_SET_VAL);
00436 }
00437 forceinline void
00438 EmptyView::cancel(Space&,Propagator&,PropCond) {}
00439 forceinline void
00440 EmptyView::subscribe(Space&, Advisor&) {}
00441 forceinline void
00442 EmptyView::cancel(Space&,Advisor&) {}
00443
00444
00445 forceinline void
00446 EmptyView::update(Space&, bool, EmptyView&) {}
00447
00448
00449
00450
00451
00452
00453
00454 forceinline ModEvent
00455 EmptyView::modevent(const Delta&) {
00456 GECODE_NEVER;
00457 return ME_GEN_NONE;
00458 }
00459
00460 forceinline int
00461 EmptyView::glbMin(const Delta&) const {
00462 GECODE_NEVER;
00463 return 0;
00464 }
00465
00466 forceinline int
00467 EmptyView::glbMax(const Delta&) const {
00468 GECODE_NEVER;
00469 return 0;
00470 }
00471
00472 forceinline bool
00473 EmptyView::glbAny(const Delta&) const {
00474 GECODE_NEVER;
00475 return false;
00476 }
00477
00478 forceinline int
00479 EmptyView::lubMin(const Delta&) const {
00480 GECODE_NEVER;
00481 return 0;
00482 }
00483
00484 forceinline int
00485 EmptyView::lubMax(const Delta&) const {
00486 GECODE_NEVER;
00487 return 0;
00488 }
00489
00490 forceinline bool
00491 EmptyView::lubAny(const Delta&) const {
00492 GECODE_NEVER;
00493 return false;
00494 }
00495
00496
00497
00498 forceinline
00499 UniverseView::UniverseView(void) {}
00500
00501 forceinline bool
00502 UniverseView::assigned(void) const { return true; }
00503
00504 forceinline unsigned int
00505 UniverseView::glbSize(void) const { return Set::Limits::card; }
00506
00507 forceinline unsigned int
00508 UniverseView::lubSize(void) const { return Set::Limits::card; }
00509
00510 forceinline unsigned int
00511 UniverseView::unknownSize(void) const { return 0; }
00512
00513 forceinline bool
00514 UniverseView::contains(int) const { return true; }
00515
00516 forceinline bool
00517 UniverseView::notContains(int) const { return false; }
00518
00519 forceinline unsigned int
00520 UniverseView::cardMin(void) const { return Set::Limits::card; }
00521
00522 forceinline unsigned int
00523 UniverseView::cardMax(void) const { return Limits::card; }
00524
00525 forceinline int
00526 UniverseView::lubMin(void) const { return Limits::card; }
00527
00528 forceinline int
00529 UniverseView::lubMax(void) const { return Limits::card; }
00530
00531 forceinline int
00532 UniverseView::glbMin(void) const { return Limits::card; }
00533
00534 forceinline int
00535 UniverseView::glbMax(void) const { return Limits::card; }
00536
00537 forceinline ModEvent
00538 UniverseView::cardMin(Space&,unsigned int c) {
00539 return c>Limits::card ? ME_SET_FAILED : ME_SET_NONE;
00540 }
00541
00542 forceinline ModEvent
00543 UniverseView::cardMax(Space&,unsigned int c) {
00544 return c>=Limits::card ? ME_SET_NONE : ME_SET_FAILED;
00545 }
00546
00547
00548 forceinline ModEvent
00549 UniverseView::include(Space&,int) {
00550 return ME_SET_NONE;
00551 }
00552
00553 forceinline ModEvent
00554 UniverseView::exclude(Space&,int) { return ME_SET_FAILED; }
00555
00556 forceinline ModEvent
00557 UniverseView::intersect(Space&,int) { return ME_SET_FAILED; }
00558
00559 forceinline ModEvent
00560 UniverseView::include(Space&,int,int) { return ME_SET_NONE; }
00561
00562 forceinline ModEvent
00563 UniverseView::exclude(Space&,int,int) { return ME_SET_FAILED; }
00564
00565 template<class I> ModEvent
00566 UniverseView::excludeI(Space&,I& i) {
00567 Iter::Ranges::IsRangeIter<I>();
00568 return i() ? ME_SET_FAILED : ME_SET_NONE;
00569 }
00570
00571 template<class I> forceinline ModEvent
00572 UniverseView::includeI(Space&,I&) {
00573 Iter::Ranges::IsRangeIter<I>();
00574 return ME_SET_NONE;
00575 }
00576
00577 forceinline ModEvent
00578 UniverseView::intersect(Space&,int i,int j) {
00579 return (i>Limits::min ||
00580 j<Limits::max) ? ME_SET_FAILED : ME_SET_NONE;
00581 }
00582
00583 template<class I> forceinline ModEvent
00584 UniverseView::intersectI(Space&,I& i) {
00585 Iter::Ranges::IsRangeIter<I>();
00586 return (i() &&
00587 (i.min()>Limits::min ||
00588 i.max()<Limits::max) ) ?
00589 ME_SET_FAILED : ME_SET_NONE;
00590 }
00591
00592 forceinline void
00593 UniverseView::schedule(Space& home, Propagator& p, ModEvent me) {
00594 return SetView::schedule(home,p,me);
00595 }
00596 forceinline ModEvent
00597 UniverseView::me(const ModEventDelta&) {
00598 return ME_SET_NONE;
00599 }
00600 forceinline ModEventDelta
00601 UniverseView::med(ModEvent me) {
00602 return SetVarImp::med(me);
00603 }
00604 forceinline void
00605 UniverseView::subscribe(Space& home, Propagator& p, PropCond,
00606 bool process) {
00607 if (process)
00608 schedule(home,p,ME_SET_VAL);
00609 }
00610 forceinline void
00611 UniverseView::cancel(Space&,Propagator&,PropCond) {}
00612
00613 forceinline void
00614 UniverseView::subscribe(Space&,Advisor&) {}
00615 forceinline void
00616 UniverseView::cancel(Space&,Advisor&) {}
00617
00618
00619 forceinline void
00620 UniverseView::update(Space&, bool, UniverseView&) {}
00621
00622
00623
00624
00625
00626
00627
00628 forceinline ModEvent
00629 UniverseView::modevent(const Delta&) {
00630 GECODE_NEVER;
00631 return ME_GEN_NONE;
00632 }
00633
00634 forceinline int
00635 UniverseView::glbMin(const Delta&) const {
00636 GECODE_NEVER;
00637 return 0;
00638 }
00639
00640 forceinline int
00641 UniverseView::glbMax(const Delta&) const {
00642 GECODE_NEVER;
00643 return 0;
00644 }
00645
00646 forceinline bool
00647 UniverseView::glbAny(const Delta&) const {
00648 GECODE_NEVER;
00649 return false;
00650 }
00651
00652 forceinline int
00653 UniverseView::lubMin(const Delta&) const {
00654 GECODE_NEVER;
00655 return 0;
00656 }
00657
00658 forceinline int
00659 UniverseView::lubMax(const Delta&) const {
00660 GECODE_NEVER;
00661 return 0;
00662 }
00663
00664 forceinline bool
00665 UniverseView::lubAny(const Delta&) const {
00666 GECODE_NEVER;
00667 return false;
00668 }
00669
00670
00671
00672
00673
00674
00679 template<>
00680 class LubRanges<EmptyView> : public Iter::Ranges::Empty {
00681 public:
00683
00684
00685 LubRanges(void) {}
00687 LubRanges(const EmptyView& x) { (void)x; }
00689 void init(const EmptyView& x) { (void)x; }
00691 };
00692
00697 template<>
00698 class GlbRanges<EmptyView> : public Iter::Ranges::Empty {
00699 public:
00701
00702
00703 GlbRanges(void) {}
00705 GlbRanges(const EmptyView& x) { (void)x; }
00707 void init(const EmptyView& x) { (void)x; }
00709 };
00710
00715 template<>
00716 class LubRanges<UniverseView> : public Iter::Ranges::Singleton {
00717 public:
00719
00720
00721 LubRanges(void)
00722 : Iter::Ranges::Singleton(Limits::min,
00723 Limits::max) {}
00725 LubRanges(const UniverseView& x)
00726 : Iter::Ranges::Singleton(Limits::min,
00727 Limits::max) {
00728 (void)x;
00729 }
00731 void init(const UniverseView& x) { (void)x; }
00733 };
00734
00739 template<>
00740 class GlbRanges<UniverseView> : public Iter::Ranges::Singleton {
00741 public:
00743
00744
00745 GlbRanges(void)
00746 : Iter::Ranges::Singleton(Limits::min,
00747 Limits::max) {}
00749 GlbRanges(const UniverseView& x)
00750 : Iter::Ranges::Singleton(Limits::min,
00751 Limits::max) {
00752 (void)x;
00753 }
00755 void init(const UniverseView& x) { (void)x; }
00757 };
00758
00759
00764 template<>
00765 class LubRanges<ConstantView> {
00766 private:
00767 ArrayRanges ar;
00768 public:
00770
00771
00772 LubRanges(void) {}
00774 LubRanges(const ConstantView& x) : ar(x.ranges,x.size) {}
00776 void init(const ConstantView& x) {
00777 ar.init(x.ranges,x.size);
00778 }
00780
00782
00783
00784 bool operator ()(void) const { return ar(); }
00786 void operator ++(void) { ++ar; }
00788
00790
00791
00792 int min(void) const { return ar.min(); }
00794 int max(void) const { return ar.max(); }
00796 unsigned int width(void) const { return ar.width(); }
00798 };
00799
00804 template<>
00805 class GlbRanges<ConstantView> : public LubRanges<ConstantView> {
00806 public:
00808
00809
00810 GlbRanges(void) {}
00812 GlbRanges(const ConstantView& x) : LubRanges<ConstantView>(x) {}
00814 void init(const ConstantView& x) {
00815 LubRanges<ConstantView>::init(x);
00816 }
00818 };
00819 }
00820
00821
00822
00823
00824
00825
00826 forceinline bool
00827 same(const Set::ConstantView& x, const Set::ConstantView& y) {
00828 if ((x.size != y.size) || (x.domSize != y.domSize))
00829 return false;
00830 for (int i=x.size; i--; )
00831 if (x.ranges[2*i] != y.ranges[2*i] ||
00832 x.ranges[2*i+1] != y.ranges[2*i+1])
00833 return false;
00834 return true;
00835 }
00836 forceinline bool
00837 before(const Set::ConstantView& x, const Set::ConstantView& y) {
00838 if (x.size < y.size)
00839 return true;
00840 if (x.domSize < y.domSize)
00841 return true;
00842 for (int i=x.size; i--; )
00843 if (x.ranges[2*i] < y.ranges[2*i] ||
00844 x.ranges[2*i+1] < y.ranges[2*i+1])
00845 return true;
00846 return false;
00847 }
00848
00849
00850 forceinline bool
00851 same(const Set::EmptyView&, const Set::EmptyView&) {
00852 return true;
00853 }
00854 forceinline bool
00855 before(const Set::EmptyView&, const Set::EmptyView&) {
00856 return false;
00857 }
00858
00859 forceinline bool
00860 same(const Set::UniverseView&, const Set::UniverseView&) {
00861 return true;
00862 }
00863 forceinline bool
00864 before(const Set::UniverseView&, const Set::UniverseView&) {
00865 return false;
00866 }
00867
00868 }
00869
00870
00871