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 #ifndef __GECODE_SET_HH__
00045 #define __GECODE_SET_HH__
00046
00047 #include <gecode/kernel.hh>
00048 #include <gecode/int.hh>
00049 #include <gecode/iter.hh>
00050
00051
00052
00053
00054
00055 #if !defined(GECODE_STATIC_LIBS) && \
00056 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00057
00058 #ifdef GECODE_BUILD_SET
00059 #define GECODE_SET_EXPORT __declspec( dllexport )
00060 #else
00061 #define GECODE_SET_EXPORT __declspec( dllimport )
00062 #endif
00063
00064 #else
00065
00066 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
00067 #define GECODE_SET_EXPORT __attribute__ ((visibility("default")))
00068 #else
00069 #define GECODE_SET_EXPORT
00070 #endif
00071
00072 #endif
00073
00074
00075 #ifndef GECODE_BUILD_SET
00076 #define GECODE_LIBRARY_NAME "Set"
00077 #include <gecode/support/auto-link.hpp>
00078 #endif
00079
00080
00092 #include <gecode/set/exception.hpp>
00093
00094 namespace Gecode { namespace Set {
00095
00097 namespace Limits {
00099 const int max = (Gecode::Int::Limits::max / 2) - 1;
00101 const int min = -max;
00103 const unsigned int card = max-min+1;
00105 void check(int n, const char* l);
00107 void check(unsigned int n, const char* l);
00109 void check(const IntSet& s, const char* l);
00110 }
00111
00112 }}
00113
00114 #include <gecode/set/limits.hpp>
00115
00116 #include <gecode/set/var-imp.hpp>
00117
00118 namespace Gecode {
00119
00120 namespace Set {
00121 class SetView;
00122 }
00123
00129 class SetVar : public VarImpVar<Set::SetVarImp> {
00130 friend class SetVarArray;
00131 friend class SetVarArgs;
00132 using VarImpVar<Set::SetVarImp>::x;
00133 public:
00135
00136
00137 SetVar(void);
00139 SetVar(const SetVar& y);
00141 SetVar(const Set::SetView& y);
00142
00144 GECODE_SET_EXPORT SetVar(Space& home);
00145
00163 GECODE_SET_EXPORT
00164 SetVar(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
00165 unsigned int cardMin = 0,
00166 unsigned int cardMax = Set::Limits::card);
00167
00184 GECODE_SET_EXPORT
00185 SetVar(Space& home,const IntSet& glbD,int lubMin,int lubMax,
00186 unsigned int cardMin = 0,
00187 unsigned int cardMax = Set::Limits::card);
00188
00206 GECODE_SET_EXPORT
00207 SetVar(Space& home,int glbMin,int glbMax,const IntSet& lubD,
00208 unsigned int cardMin = 0,
00209 unsigned int cardMax = Set::Limits::card);
00210
00228 GECODE_SET_EXPORT
00229 SetVar(Space& home,const IntSet& glbD,const IntSet& lubD,
00230 unsigned int cardMin = 0,
00231 unsigned int cardMax = Set::Limits::card);
00233
00235
00236
00237 unsigned int glbSize(void) const;
00239 unsigned int lubSize(void) const;
00241 unsigned int unknownSize(void) const;
00243 unsigned int cardMin(void) const;
00245 unsigned int cardMax(void) const;
00247 int lubMin(void) const;
00249 int lubMax(void) const;
00251 int glbMin(void) const;
00253 int glbMax(void) const;
00255
00257
00258
00259 bool contains(int i) const;
00261 bool notContains(int i) const;
00263 };
00264
00270
00272 class SetVarGlbRanges {
00273 private:
00274 Set::GlbRanges<Set::SetVarImp*> iter;
00275 public:
00277
00278
00279 SetVarGlbRanges(void);
00281 SetVarGlbRanges(const SetVar& x);
00283
00285
00286
00287 bool operator ()(void) const;
00289 void operator ++(void);
00291
00293
00294
00295 int min(void) const;
00297 int max(void) const;
00299 unsigned int width(void) const;
00301 };
00302
00304 class SetVarLubRanges {
00305 private:
00306 Set::LubRanges<Set::SetVarImp*> iter;
00307 public:
00309
00310
00311 SetVarLubRanges(void);
00313 SetVarLubRanges(const SetVar& x);
00315
00317
00318
00319 bool operator ()(void) const;
00321 void operator ++(void);
00323
00325
00326
00327 int min(void) const;
00329 int max(void) const;
00331 unsigned int width(void) const;
00333 };
00334
00336 class SetVarUnknownRanges {
00337 private:
00338 Set::UnknownRanges<Set::SetVarImp*> iter;
00339 public:
00341
00342
00343 SetVarUnknownRanges(void);
00345 SetVarUnknownRanges(const SetVar& x);
00347
00349
00350
00351 bool operator ()(void) const;
00353 void operator ++(void);
00355
00357
00358
00359 int min(void) const;
00361 int max(void) const;
00363 unsigned int width(void) const;
00365 };
00366
00368 class SetVarGlbValues {
00369 private:
00370 Iter::Ranges::ToValues<SetVarGlbRanges> iter;
00371 public:
00373
00374
00375 SetVarGlbValues(void);
00377 SetVarGlbValues(const SetVar& x);
00379
00381
00382
00383 bool operator ()(void) const;
00385 void operator ++(void);
00387
00389
00390
00391 int val(void) const;
00393 };
00394
00396 class SetVarLubValues {
00397 private:
00398 Iter::Ranges::ToValues<SetVarLubRanges> iter;
00399 public:
00401
00402
00403 SetVarLubValues(void);
00405 SetVarLubValues(const SetVar& x);
00407
00409
00410
00411 bool operator ()(void) const;
00413 void operator ++(void);
00415
00417
00418
00419 int val(void) const;
00421 };
00422
00424 class SetVarUnknownValues {
00425 private:
00426 Iter::Ranges::ToValues<SetVarUnknownRanges> iter;
00427 public:
00429
00430
00431 SetVarUnknownValues(void);
00433 SetVarUnknownValues(const SetVar& x);
00435
00437
00438
00439 bool operator ()(void) const;
00441 void operator ++(void);
00443
00445
00446
00447 int val(void) const;
00449 };
00450
00452
00457 template<class Char, class Traits>
00458 std::basic_ostream<Char,Traits>&
00459 operator <<(std::basic_ostream<Char,Traits>& os, const SetVar& x);
00460
00461 }
00462
00463 #include <gecode/set/view.hpp>
00464
00465 namespace Gecode {
00475
00476 }
00477
00478 #include <gecode/set/array-traits.hpp>
00479
00480 namespace Gecode {
00481
00490 class SetVarArgs : public VarArgArray<SetVar> {
00491 public:
00493
00494
00495 SetVarArgs(void) {}
00497 explicit SetVarArgs(int n) : VarArgArray<SetVar>(n) {}
00499 SetVarArgs(const SetVarArgs& a) : VarArgArray<SetVar>(a) {}
00501 SetVarArgs(const VarArray<SetVar>& a) : VarArgArray<SetVar>(a) {}
00508 GECODE_SET_EXPORT
00509 SetVarArgs(Space& home,int n,int glbMin,int glbMax,
00510 int lubMin,int lubMax,
00511 unsigned int minCard = 0,
00512 unsigned int maxCard = Set::Limits::card);
00519 GECODE_SET_EXPORT
00520 SetVarArgs(Space& home,int n,const IntSet& glb,
00521 int lubMin, int lubMax,
00522 unsigned int minCard = 0,
00523 unsigned int maxCard = Set::Limits::card);
00530 GECODE_SET_EXPORT
00531 SetVarArgs(Space& home,int n,int glbMin,int glbMax,
00532 const IntSet& lub,
00533 unsigned int minCard = 0,
00534 unsigned int maxCard = Set::Limits::card);
00541 GECODE_SET_EXPORT
00542 SetVarArgs(Space& home,int n,
00543 const IntSet& glb,const IntSet& lub,
00544 unsigned int minCard = 0,
00545 unsigned int maxCard = Set::Limits::card);
00547 };
00549
00565 class SetVarArray : public VarArray<SetVar> {
00566 public:
00568
00569
00570 SetVarArray(void);
00572 SetVarArray(const SetVarArray&);
00574 SetVarArray(Space& home, const SetVarArgs&);
00576 GECODE_SET_EXPORT SetVarArray(Space& home, int n);
00583 GECODE_SET_EXPORT
00584 SetVarArray(Space& home,int n,int glbMin,int glbMax,int lubMin,int lubMax,
00585 unsigned int minCard = 0,
00586 unsigned int maxCard = Set::Limits::card);
00593 GECODE_SET_EXPORT
00594 SetVarArray(Space& home,int n,const IntSet& glb, int lubMin, int lubMax,
00595 unsigned int minCard = 0,
00596 unsigned int maxCard = Set::Limits::card);
00603 GECODE_SET_EXPORT
00604 SetVarArray(Space& home,int n,int glbMin,int glbMax,const IntSet& lub,
00605 unsigned int minCard = 0,
00606 unsigned int maxCard = Set::Limits::card);
00613 GECODE_SET_EXPORT
00614 SetVarArray(Space& home,int n,
00615 const IntSet& glb,const IntSet& lub,
00616 unsigned int minCard = 0,
00617 unsigned int maxCard = Set::Limits::card);
00619 };
00620
00621 }
00622
00623 #include <gecode/set/array.hpp>
00624
00625 namespace Gecode {
00626
00638 enum SetRelType {
00639 SRT_EQ,
00640 SRT_NQ,
00641 SRT_SUB,
00642 SRT_SUP,
00643 SRT_DISJ,
00644 SRT_CMPL,
00645 SRT_LQ,
00646 SRT_LE,
00647 SRT_GQ,
00648 SRT_GR
00649 };
00650
00655 enum SetOpType {
00656 SOT_UNION,
00657 SOT_DUNION,
00658 SOT_INTER,
00659 SOT_MINUS
00660 };
00661
00669
00671 GECODE_SET_EXPORT void
00672 dom(Home home, SetVar x, SetRelType r, int i);
00673
00675 GECODE_SET_EXPORT void
00676 dom(Home home, SetVar x, SetRelType r, int i, int j);
00677
00679 GECODE_SET_EXPORT void
00680 dom(Home home, SetVar x, SetRelType r, const IntSet& s);
00681
00683 GECODE_SET_EXPORT void
00684 dom(Home home, SetVar x, SetRelType r, int i, BoolVar b);
00685
00687 GECODE_SET_EXPORT void
00688 dom(Home home, SetVar x, SetRelType r, int i, int j, BoolVar b);
00689
00691 GECODE_SET_EXPORT void
00692 dom(Home home, SetVar x, SetRelType r, const IntSet& s, BoolVar b);
00693
00695 GECODE_SET_EXPORT void
00696 cardinality(Home home, SetVar x, unsigned int i, unsigned int j);
00697
00699
00700
00708
00710 GECODE_SET_EXPORT void
00711 rel(Home home, SetVar x, SetRelType r, SetVar y);
00712
00714 GECODE_SET_EXPORT void
00715 rel(Home home, SetVar x, SetRelType r, SetVar y, BoolVar b);
00716
00718 GECODE_SET_EXPORT void
00719 rel(Home home, SetVar s, SetRelType r, IntVar x);
00720
00722 GECODE_SET_EXPORT void
00723 rel(Home home, IntVar x, SetRelType r, SetVar s);
00724
00726 GECODE_SET_EXPORT void
00727 rel(Home home, SetVar s, SetRelType r, IntVar x, BoolVar b);
00728
00730 GECODE_SET_EXPORT void
00731 rel(Home home, IntVar x, SetRelType r, SetVar s, BoolVar b);
00732
00734 GECODE_SET_EXPORT void
00735 rel(Home home, SetVar s, IntRelType r, IntVar x);
00736
00738 GECODE_SET_EXPORT void
00739 rel(Home home, IntVar x, IntRelType r, SetVar s);
00740
00742
00750
00752 GECODE_SET_EXPORT void
00753 rel(Home home, SetVar x, SetOpType op, SetVar y, SetRelType r, SetVar z);
00754
00756 GECODE_SET_EXPORT void
00757 rel(Home home, SetOpType op, const SetVarArgs& x, SetVar y);
00758
00760 GECODE_SET_EXPORT void
00761 rel(Home home, SetOpType op, const SetVarArgs& x, const IntSet& z, SetVar y);
00762
00764 GECODE_SET_EXPORT void
00765 rel(Home home, SetOpType op, const IntVarArgs& x, const IntSet& z, SetVar y);
00766
00768 GECODE_SET_EXPORT void
00769 rel(Home home, SetOpType op, const IntVarArgs& x, SetVar y);
00770
00772 GECODE_SET_EXPORT void
00773 rel(Home home, const IntSet& x, SetOpType op, SetVar y,
00774 SetRelType r, SetVar z);
00775
00777 GECODE_SET_EXPORT void
00778 rel(Home home, SetVar x, SetOpType op, const IntSet& y,
00779 SetRelType r, SetVar z);
00780
00782 GECODE_SET_EXPORT void
00783 rel(Home home, SetVar x, SetOpType op, SetVar y,
00784 SetRelType r, const IntSet& z);
00785
00787 GECODE_SET_EXPORT void
00788 rel(Home home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
00789 const IntSet& z);
00790
00792 GECODE_SET_EXPORT void
00793 rel(Home home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
00794 const IntSet& z);
00795
00797
00798
00805
00807 GECODE_SET_EXPORT void
00808 convex(Home home, SetVar x);
00809
00811 GECODE_SET_EXPORT void
00812 convex(Home home, SetVar x, SetVar y);
00813
00815
00822
00824 GECODE_SET_EXPORT void
00825 sequence(Home home, const SetVarArgs& x);
00826
00828 GECODE_SET_EXPORT void
00829 sequence(Home home, const SetVarArgs& y, SetVar x);
00830
00832
00839
00840
00842 GECODE_SET_EXPORT void
00843 atmostOne(Home home, const SetVarArgs& x, unsigned int c);
00844
00846
00854
00857 GECODE_SET_EXPORT void
00858 min(Home home, SetVar s, IntVar x);
00859
00862 GECODE_SET_EXPORT void
00863 notMin(Home home, SetVar s, IntVar x);
00864
00867 GECODE_SET_EXPORT void
00868 min(Home home, SetVar s, IntVar x, BoolVar b);
00869
00872 GECODE_SET_EXPORT void
00873 max(Home home, SetVar s, IntVar x);
00874
00877 GECODE_SET_EXPORT void
00878 notMax(Home home, SetVar s, IntVar x);
00879
00882 GECODE_SET_EXPORT void
00883 max(Home home, SetVar s, IntVar x, BoolVar b);
00884
00886 GECODE_SET_EXPORT void
00887 channelSorted(Home home, const IntVarArgs& x, SetVar y);
00888
00890 GECODE_SET_EXPORT void
00891 channel(Home home, const IntVarArgs& x,const SetVarArgs& y);
00892
00894 GECODE_SET_EXPORT void
00895 channel(Home home, const BoolVarArgs& x, SetVar y);
00896
00898 GECODE_SET_EXPORT void
00899 cardinality(Home home, SetVar s, IntVar x);
00900
00901
00912 GECODE_SET_EXPORT void
00913 weights(Home home, IntSharedArray elements, IntSharedArray weights,
00914 SetVar x, IntVar y);
00915
00917
00929 GECODE_SET_EXPORT void
00930 precede(Home home, const SetVarArgs& x, int s, int t);
00934 GECODE_SET_EXPORT void
00935 precede(Home home, const SetVarArgs& x, const IntArgs& c);
00936
00950
00960 GECODE_SET_EXPORT void
00961 element(Home home, SetOpType op, const SetVarArgs& x, SetVar y, SetVar z,
00962 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00963
00973 GECODE_SET_EXPORT void
00974 element(Home home, SetOpType op, const IntVarArgs& x, SetVar y, SetVar z,
00975 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00976
00986 GECODE_SET_EXPORT void
00987 element(Home home, SetOpType op, const IntSetArgs& x, SetVar y, SetVar z,
00988 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00989
00999 GECODE_SET_EXPORT void
01000 element(Home home, SetOpType op, const IntArgs& x, SetVar y, SetVar z,
01001 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
01002
01008 GECODE_SET_EXPORT void
01009 element(Home home, const SetVarArgs& x, IntVar y, SetVar z);
01010
01016 GECODE_SET_EXPORT void
01017 element(Home home, const IntSetArgs& s, IntVar y, SetVar z);
01018
01024 GECODE_SET_EXPORT void
01025 element(Home home, const IntSetArgs& a,
01026 IntVar x, int w, IntVar y, int h, SetVar z);
01032 GECODE_SET_EXPORT void
01033 element(Home home, const SetVarArgs& a,
01034 IntVar x, int w, IntVar y, int h, SetVar z);
01036
01047
01048 GECODE_SET_EXPORT void
01049 wait(Home home, SetVar x, void (*c)(Space& home));
01051 GECODE_SET_EXPORT void
01052 wait(Home home, const SetVarArgs& x, void (*c)(Space& home));
01054
01061
01062 enum SetVarBranch {
01063 SET_VAR_NONE = 0,
01064 SET_VAR_RND,
01065 SET_VAR_DEGREE_MIN,
01066 SET_VAR_DEGREE_MAX,
01067 SET_VAR_AFC_MIN,
01068 SET_VAR_AFC_MAX,
01069 SET_VAR_MIN_MIN,
01070 SET_VAR_MIN_MAX,
01071 SET_VAR_MAX_MIN,
01072 SET_VAR_MAX_MAX,
01073 SET_VAR_SIZE_MIN,
01074 SET_VAR_SIZE_MAX,
01075 SET_VAR_SIZE_DEGREE_MIN,
01076 SET_VAR_SIZE_DEGREE_MAX,
01077 SET_VAR_SIZE_AFC_MIN,
01078 SET_VAR_SIZE_AFC_MAX
01079 };
01080
01082 enum SetValBranch {
01083 SET_VAL_MIN_INC,
01084 SET_VAL_MIN_EXC,
01085 SET_VAL_MED_INC,
01086 SET_VAL_MED_EXC,
01087 SET_VAL_MAX_INC,
01088 SET_VAL_MAX_EXC,
01089 SET_VAL_RND_INC,
01090 SET_VAL_RND_EXC
01091 };
01092
01094 GECODE_SET_EXPORT void
01095 branch(Home home, const SetVarArgs& x,
01096 SetVarBranch vars, SetValBranch vals,
01097 const VarBranchOptions& o_vars = VarBranchOptions::def,
01098 const ValBranchOptions& o_vals = ValBranchOptions::def);
01100 GECODE_SET_EXPORT void
01101 branch(Home home, const SetVarArgs& x,
01102 const TieBreakVarBranch<SetVarBranch>& vars, SetValBranch vals,
01103 const TieBreakVarBranchOptions& o_vars = TieBreakVarBranchOptions::def,
01104 const ValBranchOptions& o_vals = ValBranchOptions::def);
01106 GECODE_SET_EXPORT void
01107 branch(Home home, SetVar x, SetValBranch vals,
01108 const ValBranchOptions& o_vals = ValBranchOptions::def);
01110
01116
01117 enum SetAssign {
01118 SET_ASSIGN_MIN_INC,
01119 SET_ASSIGN_MIN_EXC,
01120 SET_ASSIGN_MED_INC,
01121 SET_ASSIGN_MED_EXC,
01122 SET_ASSIGN_MAX_INC,
01123 SET_ASSIGN_MAX_EXC,
01124 SET_ASSIGN_RND_INC,
01125 SET_ASSIGN_RND_EXC
01126 };
01127
01129 GECODE_SET_EXPORT void
01130 assign(Home home, const SetVarArgs& x, SetAssign vals,
01131 const ValBranchOptions& o_vals = ValBranchOptions::def);
01133 GECODE_SET_EXPORT void
01134 assign(Home home, SetVar x, SetAssign vals,
01135 const ValBranchOptions& o_vals = ValBranchOptions::def);
01136
01138
01139 }
01140
01141 #endif
01142
01143
01144