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
00093 class BndSet {
00094 private:
00095 RangeList* first;
00096 RangeList* last;
00097 protected:
00099 unsigned int _size;
00101 unsigned int _card;
00103 void fst(RangeList* r);
00105 void lst(RangeList* r);
00106
00108 RangeList* fst(void) const;
00110 RangeList* lst(void) const;
00111
00112 public:
00114 static const int MAX_OF_EMPTY = Limits::min-1;
00116 static const int MIN_OF_EMPTY = Limits::max+1;
00117
00119
00120
00121 BndSet(void);
00123 BndSet(Space& home, int i, int j);
00125 GECODE_SET_EXPORT BndSet(Space& home, const IntSet& s);
00127
00129
00130
00131 void dispose(Space& home);
00133
00135
00136
00137 int min(void) const;
00139 int max(void) const;
00141 int minN(unsigned int n) const;
00143 unsigned int size(void) const;
00145 unsigned int card(void) const;
00147 void card(unsigned int c);
00149
00151
00152
00153 bool empty(void) const;
00155 bool in(int i) const;
00157
00159
00160
00161 void become(Space& home, const BndSet& s);
00163
00165
00166
00167 RangeList* ranges(void) const;
00169
00170 protected:
00172 template<class I> bool overwrite(Space& home,I& i);
00173
00174 public:
00176
00177
00178 void update(Space& home, BndSet& x);
00180
00182 GECODE_SET_EXPORT bool isConsistent(void) const;
00183 };
00184
00189 class BndSetRanges : public Iter::Ranges::RangeList {
00190 public:
00192
00193
00194 BndSetRanges(void);
00196 BndSetRanges(const BndSet& s);
00198 void init(const BndSet& s);
00200 };
00201
00209 class GLBndSet : public BndSet {
00210 private:
00212 GECODE_SET_EXPORT bool include_full(Space& home,int,int,SetDelta&);
00213 public:
00215
00216
00217 GLBndSet(void);
00219 GLBndSet(Space&);
00221 GLBndSet(Space& home, int i, int j);
00223 GLBndSet(Space& home, const IntSet& s);
00225 void init(Space& home);
00227
00229
00230
00231 bool include(Space& home,int i,int j,SetDelta& d);
00233 template<class I> bool includeI(Space& home,I& i);
00235 private:
00236 GLBndSet(const GLBndSet&);
00237 const GLBndSet& operator =(const GLBndSet&);
00238 };
00239
00247 class LUBndSet: public BndSet{
00248 private:
00249 GECODE_SET_EXPORT bool exclude_full(Space& home, int, int, SetDelta&);
00250 GECODE_SET_EXPORT bool intersect_full(Space& home, int i, int j);
00251 public:
00253
00254
00255 LUBndSet(void);
00257 LUBndSet(Space& home);
00259 LUBndSet(Space& home, int i, int j);
00261 LUBndSet(Space& home, const IntSet& s);
00263 void init(Space& home);
00265
00267
00268
00269 bool exclude(Space& home, int i, int j, SetDelta& d);
00271 bool intersect(Space& home, int i, int j);
00273 template<class I> bool intersectI(Space& home, I& i);
00275 template<class I> bool excludeI(Space& home, I& i);
00277 void excludeAll(Space& home);
00279 private:
00280 LUBndSet(const LUBndSet&);
00281 const LUBndSet& operator =(const LUBndSet&);
00282 };
00283
00284
00285
00286
00287
00288
00289
00295 template<class I>
00296 class RangesCompl :
00297 public Iter::Ranges::Compl<Limits::min, Limits::max, I> {
00298 public:
00300
00301
00302 RangesCompl(void);
00304 RangesCompl(I& i);
00306 void init(I& i);
00308 };
00309
00321 template<class T> class LubRanges {
00322 public:
00324
00325
00326 LubRanges(void);
00328 LubRanges(const T& x);
00330 void init(const T& x);
00332
00334
00335
00336 bool operator ()(void) const;
00338 void operator ++(void);
00340
00342
00343
00344 int min(void) const;
00346 int max(void) const;
00348 unsigned int width(void) const;
00350 };
00351
00363 template<class T> class GlbRanges {
00364 public:
00366
00367
00368 GlbRanges(void);
00370 GlbRanges(const T& x);
00372 void init(const T& x);
00374
00376
00377
00378 bool operator ()(void) const;
00380 void operator ++(void);
00382
00384
00385
00386 int min(void) const;
00388 int max(void) const;
00390 unsigned int width(void) const;
00392 };
00393
00405 template<class T>
00406 class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
00407 private:
00408 LubRanges<T> i1;
00409 GlbRanges<T> i2;
00410 public:
00412
00413
00414 UnknownRanges(void);
00416 UnknownRanges(const T& x);
00418 void init(const T& x);
00420 };
00421
00422 }}
00423
00424 #include <gecode/set/var-imp/integerset.hpp>
00425 #include <gecode/set/var-imp/iter.hpp>
00426
00427 namespace Gecode { namespace Set {
00428
00434 class SetVarImp : public SetVarImpBase {
00435 friend class LubRanges<SetVarImp*>;
00436 friend class GlbRanges<SetVarImp*>;
00437 private:
00439 LUBndSet lub;
00441 GLBndSet glb;
00442
00443 protected:
00445 SetVarImp(Space& home, bool share, SetVarImp& x);
00446 public:
00448
00449
00450 SetVarImp(Space& home);
00459 SetVarImp(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
00460 unsigned int cardMin = 0,
00461 unsigned int cardMax = Limits::card);
00470 SetVarImp(Space& home,const IntSet& glbD,int lubMin,int lubMax,
00471 unsigned int cardMin,unsigned int cardMax);
00480 SetVarImp(Space& home,int glbMin,int glbMax,const IntSet& lubD,
00481 unsigned int cardMin,unsigned int cardMax);
00490 SetVarImp(Space& home,const IntSet& glbD,const IntSet& lubD,
00491 unsigned int cardMin,unsigned int cardMax);
00493
00495
00496
00497 unsigned int cardMin(void) const;
00499 unsigned int cardMax(void) const;
00501 int lubMin(void) const;
00503 int lubMax(void) const;
00505 int lubMinN(unsigned int n) const;
00507 int glbMin(void) const;
00509 int glbMax(void) const;
00511 unsigned int glbSize(void) const;
00513 unsigned int lubSize(void) const;
00515
00517
00518
00519 bool assigned(void) const;
00521 bool knownIn(int n) const;
00523 bool knownOut(int) const;
00525
00526 private:
00528
00529
00530 template<class I> ModEvent includeI_full(Space& home,int mi, int ma, I& i);
00532 template<class I> ModEvent excludeI_full(Space& home,int mi, int ma, I& i);
00534 template<class I> ModEvent intersectI_full(Space& home,int mi, int ma, I& i);
00536
00537 GECODE_SET_EXPORT ModEvent processLubChange(Space& home, SetDelta& d);
00538 GECODE_SET_EXPORT ModEvent processGlbChange(Space& home, SetDelta& d);
00539
00541
00542
00543 GECODE_SET_EXPORT ModEvent cardMin_full(Space& home);
00545 GECODE_SET_EXPORT ModEvent cardMax_full(Space& home);
00547
00548 public:
00549
00551
00552
00553 ModEvent include(Space& home,int n);
00555 ModEvent include(Space& home,int i,int j);
00557 ModEvent exclude(Space& home,int n);
00559 ModEvent exclude(Space& home,int i,int j);
00561 ModEvent intersect(Space& home,int n);
00563 ModEvent intersect(Space& home,int i,int j);
00565 ModEvent cardMin(Space& home,unsigned int n);
00567 ModEvent cardMax(Space& home,unsigned int n);
00569
00571
00572
00573 template<class I> ModEvent includeI(Space& home,I& i);
00575 template<class I> ModEvent excludeI(Space& home,I& i);
00577 template<class I> ModEvent intersectI(Space& home,I& i);
00579
00580 public:
00582
00583
00590 void subscribe(Space& home, Propagator& p, PropCond pc, bool schedule=true);
00592 void cancel(Space& home, Propagator& p, PropCond pc);
00594 void subscribe(Space& home, Advisor& a);
00596 void cancel(Space& home, Advisor& a);
00598
00599 private:
00601 GECODE_SET_EXPORT SetVarImp* perform_copy(Space& home, bool share);
00602
00603 public:
00605
00606
00607 SetVarImp* copy(Space& home, bool share);
00609
00611
00612
00613 static int glbMin(const Delta& d);
00615 static int glbMax(const Delta& d);
00617 static bool glbAny(const Delta& d);
00619 static int lubMin(const Delta& d);
00621 static int lubMax(const Delta& d);
00623 static bool lubAny(const Delta& d);
00625
00626 };
00627
00628 class SetView;
00629
00630 }}
00631
00632 #include <gecode/set/var-imp/set.hpp>
00633
00634