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 "gecode/support/shared-array.hh"
00029
00030 #include <iostream>
00031 #include "gecode/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
00313 GECODE_SET_EXPORT bool isConsistent(void) const;
00314 };
00315
00320 class BndSetRanges {
00321 private:
00323 const RangeList* p;
00325 const RangeList* c;
00326 public:
00328
00329
00330 BndSetRanges(void);
00332 BndSetRanges(const BndSet& s);
00334 void init(const BndSet& s);
00336
00338
00339
00340 bool operator()(void) const;
00342 void operator++(void);
00344
00346
00347
00348 int min(void) const;
00350 int max(void) const;
00352 unsigned int width(void) const;
00354 };
00355
00363 class GLBndSet : public BndSet {
00364 private:
00366 GECODE_SET_EXPORT bool include_full(Space* home,int,int);
00367 public:
00369
00370
00371 GLBndSet(Space* =NULL);
00373 GLBndSet(Space* home, int i, int j);
00375 GLBndSet(Space* home, const IntSet& s);
00377 void init(Space* home);
00379
00381
00382
00383 bool include(Space* home,int i,int j);
00385 template <class I> bool includeI(Space* home,I& i);
00387 private:
00388 GLBndSet(const GLBndSet&);
00389 const GLBndSet& operator=(const GLBndSet&);
00390 };
00391
00399 class LUBndSet: public BndSet{
00400 private:
00401 GECODE_SET_EXPORT bool exclude_full(Space* home, int, int);
00402 public:
00404
00405
00406 LUBndSet(void);
00408 LUBndSet(Space* home);
00410 LUBndSet(Space* home, int i, int j);
00412 LUBndSet(Space* home, const IntSet& s);
00414 void init(Space* home);
00416
00418
00419
00420 bool exclude(Space* home, int i, int j);
00422 template <class I> bool intersectI(Space* home, I& i);
00424 template <class I> bool excludeI(Space* home, I& i);
00426 private:
00427 LUBndSet(const LUBndSet&);
00428 const LUBndSet& operator=(const LUBndSet&);
00429 };
00430
00431
00432
00433
00434
00435
00436
00442 template <class I>
00443 class RangesCompl :
00444 public Iter::Ranges::Compl<Limits::Set::int_min, Limits::Set::int_max, I> {
00445 public:
00447
00448
00449 RangesCompl(void);
00451 RangesCompl(I& i);
00453 void init(I& i);
00455 };
00456
00468 template <class T> class LubRanges {
00469 public:
00471
00472
00473 LubRanges(void);
00475 LubRanges(const T& x);
00477 void init(const T& x);
00479
00481
00482
00483 bool operator()(void) const;
00485 void operator++(void);
00487
00489
00490
00491 int min(void) const;
00493 int max(void) const;
00495 unsigned int width(void) const;
00497 };
00498
00510 template <class T> class GlbRanges {
00511 public:
00513
00514
00515 GlbRanges(void);
00517 GlbRanges(const T& x);
00519 void init(const T& x);
00521
00523
00524
00525 bool operator()(void) const;
00527 void operator++(void);
00529
00531
00532
00533 int min(void) const;
00535 int max(void) const;
00537 unsigned int width(void) const;
00539 };
00540
00552 template <class T>
00553 class UnknownRanges : public Iter::Ranges::Diff<LubRanges<T>, GlbRanges<T> >{
00554 private:
00555 LubRanges<T> i1;
00556 GlbRanges<T> i2;
00557 public:
00559
00560
00561 UnknownRanges(void);
00563 UnknownRanges(const T& x);
00565 void init(const T& x);
00567 };
00568
00569 }}
00570
00571 #include "gecode/set/var/integerset.icc"
00572 #include "gecode/set/var/iter.icc"
00573
00574 namespace Gecode { namespace Set {
00575
00581 class SetVarImp : public Variable<VTI_SET,PC_SET_ANY> {
00582 friend class LubRanges<SetVarImp*>;
00583 friend class GlbRanges<SetVarImp*>;
00584 private:
00586 LUBndSet lub;
00588 GLBndSet glb;
00590 unsigned int _cardMin;
00592 unsigned int _cardMax;
00593
00595 class Processor : public VarTypeProcessor<VTI_SET,PC_SET_ANY> {
00596 public:
00598 Processor(void);
00599 };
00601 GECODE_SET_EXPORT static Processor svp;
00602
00603 protected:
00605 SetVarImp(Space* home, bool share, SetVarImp& x);
00606 public:
00608
00609
00610 SetVarImp(Space* home);
00619 SetVarImp(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00620 unsigned int cardMin = 0,
00621 unsigned int cardMax = Limits::Set::card_max);
00630 SetVarImp(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00631 unsigned int cardMin,unsigned int cardMax);
00640 SetVarImp(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00641 unsigned int cardMin,unsigned int cardMax);
00650 SetVarImp(Space* home,const IntSet& glbD,const IntSet& lubD,
00651 unsigned int cardMin,unsigned int cardMax);
00653
00655
00656
00657 unsigned int cardMin(void) const;
00659 unsigned int cardMax(void) const;
00661 int lubMin(void) const;
00663 int lubMax(void) const;
00665 int lubMinN(int n) const;
00667 int lubMaxN(int n) const;
00669 int glbMin(void) const;
00671 int glbMax(void) const;
00673 unsigned int glbSize(void) const;
00675 unsigned int lubSize(void) const;
00677
00679
00680
00681 bool assigned(void) const;
00683 bool knownIn(int n) const;
00685 bool knownOut(int) const;
00687
00688 private:
00690
00691
00692 GECODE_SET_EXPORT ModEvent processLubChange(Space* home);
00694 GECODE_SET_EXPORT ModEvent processGlbChange(Space* home);
00701 ModEvent checkLubCardAssigned(Space* home,ModEvent me);
00708 ModEvent checkGlbCardAssigned(Space* home,ModEvent me);
00710
00712
00713
00714 GECODE_SET_EXPORT ModEvent cardMin_full(Space* home,unsigned int n);
00716 GECODE_SET_EXPORT ModEvent cardMax_full(Space* home,unsigned int n);
00718
00720 bool boundsConsistent(void) const;
00721 public:
00722
00724
00725
00726 ModEvent include(Space* home,int n);
00728 ModEvent include(Space* home,int i,int j);
00730 ModEvent exclude(Space* home,int n);
00732 ModEvent exclude(Space* home,int i,int j);
00734 ModEvent intersect(Space* home,int n);
00736 ModEvent intersect(Space* home,int i,int j);
00738 ModEvent cardMin(Space* home,unsigned int n);
00740 ModEvent cardMax(Space* home,unsigned int n);
00742
00744
00745
00746 template <class I> ModEvent includeI(Space* home,I& i);
00748 template <class I> ModEvent excludeI(Space* home,I& i);
00750 template <class I> ModEvent intersectI(Space* home,I& i);
00752
00753 public:
00755
00756
00757 GECODE_SET_EXPORT void subscribe(Space* home,Propagator* p,PropCond pc);
00759
00760 private:
00762 GECODE_SET_EXPORT SetVarImp* perform_copy(Space* home, bool share);
00763
00764 public:
00766
00767
00768 SetVarImp* copy(Space* home, bool share);
00770
00771 };
00772
00773 }}
00774
00775 #include "gecode/set/var/imp.icc"
00776
00777 namespace Gecode {
00778
00784 class SetVar {
00785 private:
00787 Set::SetVarImp* x;
00788 public:
00790
00791
00792 GECODE_SET_EXPORT SetVar(void);
00793
00795 GECODE_SET_EXPORT SetVar(Space* home);
00797 void init(Space* home);
00798
00816 GECODE_SET_EXPORT
00817 SetVar(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00818 unsigned int cardMin = 0,
00819 unsigned int cardMax = Limits::Set::card_max);
00837 void init(Space* home,int glbMin,int glbMax,int lubMin,int lubMax,
00838 unsigned int cardMin = 0,
00839 unsigned int cardMax = Limits::Set::card_max);
00840
00858 GECODE_SET_EXPORT
00859 SetVar(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00860 unsigned int cardMin = 0,
00861 unsigned int cardMax = Limits::Set::card_max);
00879 void init(Space* home,const IntSet& glbD,int lubMin,int lubMax,
00880 unsigned int cardMin = 0,
00881 unsigned int cardMax = Limits::Set::card_max);
00882
00900 GECODE_SET_EXPORT
00901 SetVar(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00902 unsigned int cardMin = 0,
00903 unsigned int cardMax = Limits::Set::card_max);
00921 void init(Space* home,int glbMin,int glbMax,const IntSet& lubD,
00922 unsigned int cardMin = 0,
00923 unsigned int cardMax = Limits::Set::card_max);
00924
00942 GECODE_SET_EXPORT
00943 SetVar(Space* home,const IntSet& glbD,const IntSet& lubD,
00944 unsigned int cardMin = 0,
00945 unsigned int cardMax = Limits::Set::card_max);
00963 void init(Space* home,const IntSet& glbD,const IntSet& lubD,
00964 unsigned int cardMin = 0,
00965 unsigned int cardMax = Limits::Set::card_max);
00967
00969
00970
00971 Set::SetVarImp* variable(void) const;
00973
00975
00976
00977 unsigned int glbSize(void) const;
00979 unsigned int lubSize(void) const;
00981 unsigned int unknownSize(void) const;
00983 unsigned int cardMin(void) const;
00985 unsigned int cardMax(void) const;
00987 int lubMin(void) const;
00989 int lubMax(void) const;
00991 int glbMin(void) const;
00993 int glbMax(void) const;
00995
00997
00998
00999 bool contains(int i) const;
01001 bool notContains(int i) const;
01003 bool assigned(void) const;
01004
01006
01007
01008 void update(Space* home, bool, SetVar& x);
01010 };
01011
01017
01019 class SetVarGlbRanges {
01020 private:
01021 Set::GlbRanges<Set::SetVarImp*> iter;
01022 public:
01024
01025
01026 SetVarGlbRanges(void);
01028 SetVarGlbRanges(const SetVar& x);
01030
01032
01033
01034 bool operator()(void) const;
01036 void operator++(void);
01038
01040
01041
01042 int min(void) const;
01044 int max(void) const;
01046 unsigned int width(void) const;
01048 };
01049
01051 class SetVarLubRanges {
01052 private:
01053 Set::LubRanges<Set::SetVarImp*> iter;
01054 public:
01056
01057
01058 SetVarLubRanges(void);
01060 SetVarLubRanges(const SetVar& x);
01062
01064
01065
01066 bool operator()(void) const;
01068 void operator++(void);
01070
01072
01073
01074 int min(void) const;
01076 int max(void) const;
01078 unsigned int width(void) const;
01080 };
01081
01083 class SetVarUnknownRanges {
01084 private:
01085 Set::UnknownRanges<Set::SetVarImp*> iter;
01086 public:
01088
01089
01090 SetVarUnknownRanges(void);
01092 SetVarUnknownRanges(const SetVar& x);
01094
01096
01097
01098 bool operator()(void) const;
01100 void operator++(void);
01102
01104
01105
01106 int min(void) const;
01108 int max(void) const;
01110 unsigned int width(void) const;
01112 };
01113
01115 class SetVarGlbValues {
01116 private:
01117 Iter::Ranges::ToValues<SetVarGlbRanges> iter;
01118 public:
01120
01121
01122 SetVarGlbValues(void);
01124 SetVarGlbValues(const SetVar& x);
01126
01128
01129
01130 bool operator()(void) const;
01132 void operator++(void);
01134
01136
01137
01138 int val(void) const;
01140 };
01141
01143 class SetVarLubValues {
01144 private:
01145 Iter::Ranges::ToValues<SetVarLubRanges> iter;
01146 public:
01148
01149
01150 SetVarLubValues(void);
01152 SetVarLubValues(const SetVar& x);
01154
01156
01157
01158 bool operator()(void) const;
01160 void operator++(void);
01162
01164
01165
01166 int val(void) const;
01168 };
01169
01171 class SetVarUnknownValues {
01172 private:
01173 Iter::Ranges::ToValues<SetVarUnknownRanges> iter;
01174 public:
01176
01177
01178 SetVarUnknownValues(void);
01180 SetVarUnknownValues(const SetVar& x);
01182
01184
01185
01186 bool operator()(void) const;
01188 void operator++(void);
01190
01192
01193
01194 int val(void) const;
01196 };
01197
01199 }
01200
01201 #include "gecode/set/var/set.icc"
01202
01207 GECODE_SET_EXPORT std::ostream&
01208 operator<<(std::ostream&, const Gecode::SetVar& x);
01209
01210
01211