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
00039
00040
00041
00042
00043
00044 #include <iostream>
00045
00046 namespace Gecode { namespace Set {
00047
00048 class SetVarImp;
00049 class LUBndSet;
00050 class GLBndSet;
00051
00056 class SetDelta : public Delta {
00057 friend class SetVarImp;
00058 friend class LUBndSet;
00059 friend class GLBndSet;
00060 private:
00061 int _glbMin;
00062 int _glbMax;
00063 int _lubMin;
00064 int _lubMax;
00065 public:
00067 SetDelta(void);
00069 SetDelta(int glbMin, int glbMax, int lubMin, int lubMax);
00071 int glbMin(void) const;
00073 int glbMax(void) const;
00075 int lubMin(void) const;
00077 int lubMax(void) const;
00079 bool glbAny(void) const;
00081 bool lubAny(void) const;
00082 };
00083
00084 }}
00085
00086 #include <gecode/set/var-imp/delta.hpp>
00087
00088 namespace Gecode { namespace Set {
00089
00094 class RangeList : public FreeList {
00095 protected:
00097 int _min;
00099 int _max;
00100 public:
00102
00103
00104 RangeList(void);
00106 RangeList(int min, int max, RangeList* n);
00108
00110
00111
00112 int min(void) const;
00114 int max(void) const;
00116 unsigned int width(void) const;
00117
00119 RangeList* next(void) const;
00121
00123
00124
00125 void min(int n);
00127 void max(int n);
00129 void next(RangeList* n);
00131
00133
00134
00137 void dispose(Space& home, RangeList* l);
00138
00140 static void* operator new(size_t s, Space& home);
00142 static void* operator new(size_t s, void* p);
00144 static void operator delete(void*);
00146 static void operator delete(void*, Space& home);
00148 static void operator delete(void*, void*);
00150 };
00151
00152
00156 class BndSet {
00157 private:
00158 RangeList* first;
00159 RangeList* last;
00160 protected:
00162 unsigned int _size;
00164 unsigned int _card;
00166 void fst(RangeList* r);
00168 void lst(RangeList* r);
00169
00171 RangeList* fst(void) const;
00173 RangeList* lst(void) const;
00174
00175 public:
00177 static const int MAX_OF_EMPTY = Limits::min-1;
00179 static const int MIN_OF_EMPTY = Limits::max+1;
00180
00182
00183
00184 BndSet(void);
00186 BndSet(Space& home, int i, int j);
00188 BndSet(Space& home, const IntSet& s);
00190
00192
00193
00194 void dispose(Space& home);
00196
00198
00199
00200 int min(void) const;
00202 int max(void) const;
00204 int minN(unsigned int n) const;
00206 unsigned int size(void) const;
00208 unsigned int card(void) const;
00210 void card(unsigned int c);
00212
00214
00215
00216 bool empty(void) const;
00218 bool in(int i) const;
00220
00222
00223
00224 void become(Space& home, const BndSet& s);
00226
00228
00229
00230 RangeList* ranges(void) const;
00232
00233 protected:
00235 template<class I> bool overwrite(Space& home,I& i);
00236
00237 public:
00239
00240
00241 void update(Space& home, BndSet& x);
00243
00245 GECODE_SET_EXPORT bool isConsistent(void) const;
00246 };
00247
00252 class BndSetRanges {
00253 private:
00255 const RangeList* c;
00256 public:
00258
00259
00260 BndSetRanges(void);
00262 BndSetRanges(const BndSet& s);
00264 void init(const BndSet& s);
00266
00268
00269
00270 bool operator ()(void) const;
00272 void operator ++(void);
00274
00276
00277
00278 int min(void) const;
00280 int max(void) const;
00282 unsigned int width(void) const;
00284 };
00285
00293 class GLBndSet : public BndSet {
00294 private:
00296 GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&);
00297 public:
00299
00300
00301 GLBndSet(void);
00303 GLBndSet(Space&);
00305 GLBndSet(Space& home, int i, int j);
00307 GLBndSet(Space& home, const IntSet& s);
00309 void init(Space& home);
00311
00313
00314
00315 bool include(Space& home,int i,int j,SetDelta& d);
00317 template<class I> bool includeI(Space& home,I& i);
00319 private:
00320 GLBndSet(const GLBndSet&);
00321 const GLBndSet& operator =(const GLBndSet&);
00322 };
00323
00331 class LUBndSet: public BndSet{
00332 private:
00333 GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&);
00334 GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j);
00335 public:
00337
00338
00339 LUBndSet(void);
00341 LUBndSet(Space& home);
00343 LUBndSet(Space& home, int i, int j);
00345 LUBndSet(Space& home, const IntSet& s);
00347 void init(Space& home);
00349
00351
00352
00353 bool exclude(Space& home, int i, int j, SetDelta& d);
00355 bool intersect(Space& home, int i, int j);
00357 template<class I> bool intersectI(Space& home, I& i);
00359 template<class I> bool excludeI(Space& home, I& i);
00361 void excludeAll(Space& home);
00363 private:
00364 LUBndSet(const LUBndSet&);
00365 const LUBndSet& operator =(const LUBndSet&);
00366 };
00367
00368
00369
00370
00371
00372
00373
00379 template<class I>
00380 class RangesCompl :
00381 public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
00382 public:
00384
00385
00386 RangesCompl(void);
00388 RangesCompl(I& i);
00390 void init(I& i);
00392 };
00393
00405 template<class T> class LubRanges {
00406 public:
00408
00409
00410 LubRanges(void);
00412 LubRanges(const T& x);
00414 void init(const T& x);
00416
00418
00419
00420 bool operator ()(void) const;
00422 void operator ++(void);
00424
00426
00427
00428 int min(void) const;
00430 int max(void) const;
00432 unsigned int width(void) const;
00434 };
00435
00447 template<class T> class GlbRanges {
00448 public:
00450
00451
00452 GlbRanges(void);
00454 GlbRanges(const T& x);
00456 void init(const T& x);
00458
00460
00461
00462 bool operator ()(void) const;
00464 void operator ++(void);
00466
00468
00469
00470 int min(void) const;
00472 int max(void) const;
00474 unsigned int width(void) const;
00476 };
00477
00489 template<class T>
00490 class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
00491 private:
00492 LubRanges<T> i1;
00493 GlbRanges<T> i2;
00494 public:
00496
00497
00498 UnknownRanges(void);
00500 UnknownRanges(const T& x);
00502 void init(const T& x);
00504 };
00505
00506 }}
00507
00508 #include <gecode/set/var-imp/integerset.hpp>
00509 #include <gecode/set/var-imp/iter.hpp>
00510
00511 namespace Gecode { namespace Set {
00512
00518 class SetVarImp : public SetVarImpBase {
00519 friend class LubRanges<SetVarImp*>;
00520 friend class GlbRanges<SetVarImp*>;
00521 private:
00523 LUBndSet lub;
00525 GLBndSet glb;
00526
00527 protected:
00529 SetVarImp(Space& home, bool share, SetVarImp& x);
00530 public:
00532
00533
00534 SetVarImp(Space& home);
00543 SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
00544 unsigned int cardMin = 0,
00545 unsigned int cardMax = Limits::card);
00554 SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax,
00555 unsigned int cardMin,unsigned int cardMax);
00564 SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD,
00565 unsigned int cardMin,unsigned int cardMax);
00574 SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD,
00575 unsigned int cardMin,unsigned int cardMax);
00577
00579
00580
00581 unsigned int cardMin(void) const;
00583 unsigned int cardMax(void) const;
00585 int lubMin(void) const;
00587 int lubMax(void) const;
00589 int lubMinN(unsigned int n) const;
00591 int glbMin(void) const;
00593 int glbMax(void) const;
00595 unsigned int glbSize(void) const;
00597 unsigned int lubSize(void) const;
00599
00601
00602
00603 bool assigned(void) const;
00605 bool knownIn(int n) const;
00607 bool knownOut(int) const;
00609
00610 private:
00612
00613
00614 template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i);
00616 template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i);
00618 template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i);
00620
00621 GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d);
00622 GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d);
00623
00625
00626
00627 GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
00629 GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
00631
00632 public:
00633
00635
00636
00637 ModEvent include(Space& home,int n);
00639 ModEvent include(Space& home,int i,int j);
00641 ModEvent exclude(Space& home,int n);
00643 ModEvent exclude(Space& home,int i,int j);
00645 ModEvent intersect(Space& home,int n);
00647 ModEvent intersect(Space& home,int i,int j);
00649 ModEvent cardMin(Space& home,unsigned int n);
00651 ModEvent cardMax(Space& home,unsigned int n);
00653
00655
00656
00657 template<class I> ModEvent includeI(Space& home,I& i);
00659 template<class I> ModEvent excludeI(Space& home,I& i);
00661 template<class I> ModEvent intersectI(Space& home,I& i);
00663
00664 public:
00666
00667
00674 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00676 void cancel(Space& home, Propagator& p, PropCond pc);
00678 void subscribe(Space& home, Advisor& a);
00680 void cancel(Space& home, Advisor& a);
00682
00683 private:
00685 GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home, bool share);
00686
00687 public:
00689
00690
00691 SetVarImp* copy(Space& home, bool share);
00693
00695
00696
00697 static int glbMin(const Delta& d);
00699 static int glbMax(const Delta& d);
00701 static bool glbAny(const Delta& d);
00703 static int lubMin(const Delta& d);
00705 static int lubMax(const Delta& d);
00707 static bool lubAny(const Delta& d);
00709
00710 };
00711
00712 class SetView;
00713
00714 }}
00715
00716 #include <gecode/set/var-imp/set.hpp>
00717
00718