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 #include "support/shared-array.hh"
00029
00030 #include <iostream>
00031 #include "iter.hh"
00032
00033 namespace Gecode { namespace Set {
00034
00041
00043 const ModEvent ME_SET_FAILED = ME_GEN_FAILED;
00045 const ModEvent ME_SET_NONE = ME_GEN_NONE;
00047 const ModEvent ME_SET_VAL = ME_GEN_ASSIGNED;
00048
00054 const ModEvent ME_SET_CARD = ME_SET_VAL + 1;
00062 const ModEvent ME_SET_LUB = ME_SET_CARD + 1;
00070 const ModEvent ME_SET_GLB = ME_SET_LUB + 1;
00078 const ModEvent ME_SET_BB = ME_SET_GLB + 1;
00085 const ModEvent ME_SET_CLUB = ME_SET_BB + 1;
00092 const ModEvent ME_SET_CGLB = ME_SET_CLUB + 1;
00099 const ModEvent ME_SET_CBB = ME_SET_CGLB + 1;
00100
00101
00102
00110 const PropCond PC_SET_VAL = PC_GEN_ASSIGNED;
00119 const PropCond PC_SET_CARD = PC_SET_VAL + 1;
00130 const PropCond PC_SET_CGLB = PC_SET_CARD + 1;
00141 const PropCond PC_SET_CLUB = PC_SET_CGLB + 1;
00151 const PropCond PC_SET_ANY = PC_SET_CLUB + 1;
00153
00154
00159 class RangeList : public FreeList {
00160 protected:
00162 int _min;
00164 int _max;
00165 public:
00167
00168
00169 RangeList(void);
00171 RangeList(int min, int max, RangeList* p, RangeList* n);
00173
00175
00176
00177 int min(void) const;
00179 int max(void) const;
00181 unsigned int width(void) const;
00182
00184 RangeList* next(const RangeList* p) const;
00186 RangeList* prev(const RangeList* n) const;
00188
00190
00191
00192 void min(int n);
00194 void max(int n);
00195
00197 void prevnext(RangeList* p, RangeList* n);
00199 void next(RangeList* o, RangeList* n);
00201 void prev(RangeList* o, RangeList* n);
00203 void fix(RangeList* n);
00205
00207
00208
00213 void dispose(Space* home, RangeList* p, RangeList* l);
00214
00216 static void* operator new(size_t s, Space* home);
00218 static void operator delete(void*);
00220 static void operator delete(void*, Space* home);
00222 };
00223
00224
00228 class BndSet {
00229 private:
00230 RangeList* first;
00231 RangeList* last;
00232 protected:
00234 unsigned int _size;
00236 void fst(RangeList* r);
00238 void lst(RangeList* r);
00239
00241 RangeList* fst(void) const;
00243 RangeList* lst(void) const;
00244
00245 public:
00247 static const int MAX_OF_EMPTY = Limits::Set::int_min-1;
00249 static const int MIN_OF_EMPTY = Limits::Set::int_max+1;
00250
00252
00253
00254 BndSet(void);
00256 BndSet(Space* home, int i, int j);
00258 BndSet(Space* home, const IntSet& s);
00260
00262
00263
00264 void dispose(Space* home);
00266
00268
00269
00270 int min(void) const;
00272 int max(void) const;
00274 int minN(unsigned int n) const;
00276 int maxN(unsigned int n) const;
00278 unsigned int size(void) const;
00280
00282
00283
00284 bool empty(void) const;
00286 bool in(int i) const;
00288
00290
00291
00292 void linkTo(Space* home, const BndSet& s);
00294
00296
00297
00298 RangeList* ranges(void) const;
00300
00301 protected:
00303 template <class I> bool overwrite(Space* home,I& i);
00304
00305 public:
00307
00308
00309 void update(Space* home, BndSet& x);
00311
00312 #ifndef NDEBUG
00313
00314 GECODE_SET_EXPORT bool isConsistent(void) const;
00315 #endif
00316 };
00317
00322 class BndSetRanges {
00323 private:
00325 const RangeList* p;
00327 const RangeList* c;
00328 public:
00330
00331
00332 BndSetRanges(void);
00334 BndSetRanges(const BndSet& s);
00336 void init(const BndSet& s);
00338
00340
00341
00342 bool operator()(void) const;
00344 void operator++(void);
00346
00348
00349
00350 int min(void) const;
00352 int max(void) const;
00354 unsigned int width(void) const;
00356 };
00357
00365 class GLBndSet : public BndSet {
00366 private:
00368 GECODE_SET_EXPORT bool include_full(Space* home,int,int);
00369 public:
00371
00372
00373 GLBndSet(Space* =NULL);
00375 GLBndSet(Space* home, int i, int j);
00377 GLBndSet(Space* home, const IntSet& s);
00379 void init(Space* home);
00381
00383
00384
00385 bool include(Space* home,int i,int j);
00387 template <class I> bool includeI(Space* home,I& i);
00389 private:
00390 GLBndSet(const GLBndSet&);
00391 const GLBndSet& operator=(const GLBndSet&);
00392 };
00393
00401 class LUBndSet: public BndSet{
00402 private:
00403 GECODE_SET_EXPORT bool exclude_full(Space* home, int, int);
00404 public:
00406
00407
00408 LUBndSet(void);
00410 LUBndSet(Space* home);
00412 LUBndSet(Space* home, int i, int j);
00414 LUBndSet(Space* home, const IntSet& s);
00416 void init(Space* home);
00418
00420
00421
00422 bool exclude(Space* home, int i, int j);
00424 template <class I> bool intersectI(Space* home, I& i);
00426 template <class I> bool excludeI(Space* home, I& i);
00428 private:
00429 LUBndSet(const LUBndSet&);
00430 const LUBndSet& operator=(const LUBndSet&);
00431 };
00432
00433
00434
00435
00436
00437
00438
00444 template <class I>
00445 class RangesCompl :
00446 public Iter::Ranges::Compl<Limits::Set::int_min, Limits::Set::int_max, I> {
00447 public:
00449
00450
00451 RangesCompl(void);
00453 RangesCompl(I& i);
00455 void init(I& i);
00457 };
00458
00470 template <class T> class LubRanges {
00471 public:
00473
00474
00475 LubRanges(void);
00477 LubRanges(const T& x);
00479 void init(const T& x);
00481
00483
00484
00485 bool operator()(void) const;
00487 void operator++(void);
00489
00491
00492
00493 int min(void) const;
00495 int max(void) const;
00497 unsigned int width(void) const;
00499 };
00500
00512 template <class T> class GlbRanges {
00513 public:
00515
00516
00517 GlbRanges(void);
00519 GlbRanges(const T& x);
00521 void init(const T& x);
00523
00525
00526
00527 bool operator()(void) const;
00529 void operator++(void);
00531
00533
00534
00535 int min(void) const;
00537 int max(void) const;
00539 unsigned int width(void) const;
00541 };
00542
00554 template <class T>
00555 class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
00556 private:
00557 LubRanges<T> i1;
00558 GlbRanges<T> i2;
00559 public:
00561
00562
00563 UnknownRanges(void);
00565 UnknownRanges(const T& x);
00567 void init(const T& x);
00569 };
00570
00571 }}
00572
00573 #include "set/var/integerset.icc"
00574 #include "set/var/iter.icc"
00575
00576 namespace Gecode { namespace Set {
00577
00583 class SetVarImp : public Variable<VTI_SET,PC_SET_ANY> {
00584 friend class LubRanges<SetVarImp*>;
00585 friend class GlbRanges<SetVarImp*>;
00586 private:
00588 LUBndSet lub;
00590 GLBndSet glb;
00592 unsigned int _cardMin;
00594 unsigned int _cardMax;
00595
00597 class Processor : public VarTypeProcessor<VTI_SET,PC_SET_ANY> {
00598 public:
00600 Processor(void);
00601 };
00603 GECODE_SET_EXPORT static Processor svp;
00604
00605 protected:
00607 SetVarImp(Space* home, bool share, SetVarImp& x);
00608 public:
00610
00611
00612 SetVarImp(Space* home);
00621 SetVarImp(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00622 unsigned int cardMin = 0,
00623 unsigned int cardMax = Limits::Set::card_max);
00632 SetVarImp(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00633 unsigned int cardMin,unsigned int cardMax);
00642 SetVarImp(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00643 unsigned int cardMin,unsigned int cardMax);
00652 SetVarImp(Space* home,const IntSet& glbD,const IntSet& lubD,
00653 unsigned int cardMin,unsigned int cardMax);
00655
00657
00658
00659 unsigned int cardMin(void) const;
00661 unsigned int cardMax(void) const;
00663 int lubMin(void) const;
00665 int lubMax(void) const;
00667 int lubMinN(int n) const;
00669 int lubMaxN(int n) const;
00671 int glbMin(void) const;
00673 int glbMax(void) const;
00675 unsigned int glbSize(void) const;
00677 unsigned int lubSize(void) const;
00679
00681
00682
00683 bool assigned(void) const;
00685 bool knownIn(int n) const;
00687 bool knownOut(int) const;
00689
00690 private:
00692
00693
00694 GECODE_SET_EXPORT ModEvent processLubChange(Space* home);
00696 GECODE_SET_EXPORT ModEvent processGlbChange(Space* home);
00703 ModEvent checkLubCardAssigned(Space* home,ModEvent me);
00710 ModEvent checkGlbCardAssigned(Space* home,ModEvent me);
00712
00714
00715
00716 GECODE_SET_EXPORT ModEvent cardMin_full(Space* home,unsigned int n);
00718 GECODE_SET_EXPORT ModEvent cardMax_full(Space* home,unsigned int n);
00720
00722 bool boundsConsistent(void) const;
00723 public:
00724
00726
00727
00728 ModEvent include(Space* home,int n);
00730 ModEvent include(Space* home,int i,int j);
00732 ModEvent exclude(Space* home,int n);
00734 ModEvent exclude(Space* home,int i,int j);
00736 ModEvent intersect(Space* home,int n);
00738 ModEvent intersect(Space* home,int i,int j);
00740 ModEvent cardMin(Space* home,unsigned int n);
00742 ModEvent cardMax(Space* home,unsigned int n);
00744
00746
00747
00748 template <class I> ModEvent includeI(Space* home,I& i);
00750 template <class I> ModEvent excludeI(Space* home,I& i);
00752 template <class I> ModEvent intersectI(Space* home,I& i);
00754
00755 public:
00757
00758
00759 GECODE_SET_EXPORT void subscribe(Space* home,Propagator* p,PropCond pc);
00761
00762 private:
00764 GECODE_SET_EXPORT SetVarImp* perform_copy(Space* home, bool share);
00765
00766 public:
00768
00769
00770 SetVarImp* copy(Space* home, bool share);
00772
00773 };
00774
00775 }}
00776
00777 #include "set/var/imp.icc"
00778
00779 namespace Gecode {
00780
00786 class SetVar {
00787 private:
00789 Set::SetVarImp* x;
00790 public:
00792
00793
00794 GECODE_SET_EXPORT SetVar(void);
00795
00797 GECODE_SET_EXPORT SetVar(Space* home);
00799 void init(Space* home);
00800
00818 GECODE_SET_EXPORT
00819 SetVar(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00820 unsigned int cardMin = 0,
00821 unsigned int cardMax = Limits::Set::card_max);
00839 void init(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00840 unsigned int cardMin = 0,
00841 unsigned int cardMax = Limits::Set::card_max);
00842
00860 GECODE_SET_EXPORT
00861 SetVar(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00862 unsigned int cardMin = 0,
00863 unsigned int cardMax = Limits::Set::card_max);
00881 void init(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00882 unsigned int cardMin = 0,
00883 unsigned int cardMax = Limits::Set::card_max);
00884
00902 GECODE_SET_EXPORT
00903 SetVar(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00904 unsigned int cardMin = 0,
00905 unsigned int cardMax = Limits::Set::card_max);
00923 void init(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00924 unsigned int cardMin = 0,
00925 unsigned int cardMax = Limits::Set::card_max);
00926
00944 GECODE_SET_EXPORT
00945 SetVar(Space* home,const IntSet& glbD,const IntSet& lubD,
00946 unsigned int cardMin = 0,
00947 unsigned int cardMax = Limits::Set::card_max);
00965 void init(Space* home,const IntSet& glbD,const IntSet& lubD,
00966 unsigned int cardMin = 0,
00967 unsigned int cardMax = Limits::Set::card_max);
00969
00971
00972
00973 Set::SetVarImp* variable(void) const;
00975
00977
00978
00979 unsigned int glbSize(void) const;
00981 unsigned int lubSize(void) const;
00983 unsigned int unknownSize(void) const;
00985 unsigned int cardMin(void) const;
00987 unsigned int cardMax(void) const;
00989 int lubMin(void) const;
00991 int lubMax(void) const;
00993 int glbMin(void) const;
00995 int glbMax(void) const;
00997
00999
01000
01001 bool contains(int i) const;
01003 bool notContains(int i) const;
01005 bool assigned(void) const;
01006
01008
01009
01010 void update(Space* home, bool, SetVar& x);
01012 };
01013
01019
01021 class SetVarGlbRanges {
01022 private:
01023 Set::GlbRanges<Set::SetVarImp*> iter;
01024 public:
01026
01027
01028 SetVarGlbRanges(void);
01030 SetVarGlbRanges(const SetVar& x);
01032
01034
01035
01036 bool operator()(void) const;
01038 void operator++(void);
01040
01042
01043
01044 int min(void) const;
01046 int max(void) const;
01048 unsigned int width(void) const;
01050 };
01051
01053 class SetVarLubRanges {
01054 private:
01055 Set::LubRanges<Set::SetVarImp*> iter;
01056 public:
01058
01059
01060 SetVarLubRanges(void);
01062 SetVarLubRanges(const SetVar& x);
01064
01066
01067
01068 bool operator()(void) const;
01070 void operator++(void);
01072
01074
01075
01076 int min(void) const;
01078 int max(void) const;
01080 unsigned int width(void) const;
01082 };
01083
01085 class SetVarUnknownRanges {
01086 private:
01087 Set::UnknownRanges<Set::SetVarImp*> iter;
01088 public:
01090
01091
01092 SetVarUnknownRanges(void);
01094 SetVarUnknownRanges(const SetVar& x);
01096
01098
01099
01100 bool operator()(void) const;
01102 void operator++(void);
01104
01106
01107
01108 int min(void) const;
01110 int max(void) const;
01112 unsigned int width(void) const;
01114 };
01115
01117 class SetVarGlbValues {
01118 private:
01119 Iter::Ranges::ToValues<SetVarGlbRanges> iter;
01120 public:
01122
01123
01124 SetVarGlbValues(void);
01126 SetVarGlbValues(const SetVar& x);
01128
01130
01131
01132 bool operator()(void) const;
01134 void operator++(void);
01136
01138
01139
01140 int val(void) const;
01142 };
01143
01145 class SetVarLubValues {
01146 private:
01147 Iter::Ranges::ToValues<SetVarLubRanges> iter;
01148 public:
01150
01151
01152 SetVarLubValues(void);
01154 SetVarLubValues(const SetVar& x);
01156
01158
01159
01160 bool operator()(void) const;
01162 void operator++(void);
01164
01166
01167
01168 int val(void) const;
01170 };
01171
01173 class SetVarUnknownValues {
01174 private:
01175 Iter::Ranges::ToValues<SetVarUnknownRanges> iter;
01176 public:
01178
01179
01180 SetVarUnknownValues(void);
01182 SetVarUnknownValues(const SetVar& x);
01184
01186
01187
01188 bool operator()(void) const;
01190 void operator++(void);
01192
01194
01195
01196 int val(void) const;
01198 };
01199
01201 }
01202
01203 #include "set/var/set.icc"
01204
01209 GECODE_SET_EXPORT std::ostream&
01210 operator<<(std::ostream&, const Gecode::SetVar& x);
01211
01212
01213