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
00631 enum SetRelType {
00632 SRT_EQ,
00633 SRT_NQ,
00634 SRT_SUB,
00635 SRT_SUP,
00636 SRT_DISJ,
00637 SRT_CMPL
00638 };
00639
00644 enum SetOpType {
00645 SOT_UNION,
00646 SOT_DUNION,
00647 SOT_INTER,
00648 SOT_MINUS
00649 };
00650
00658
00660 GECODE_SET_EXPORT void
00661 dom(Home home, SetVar x, SetRelType r, int i);
00662
00664 GECODE_SET_EXPORT void
00665 dom(Home home, SetVar x, SetRelType r, int i, int j);
00666
00668 GECODE_SET_EXPORT void
00669 dom(Home home, SetVar x, SetRelType r, const IntSet& s);
00670
00672 GECODE_SET_EXPORT void
00673 dom(Home home, SetVar x, SetRelType r, int i, BoolVar b);
00674
00676 GECODE_SET_EXPORT void
00677 dom(Home home, SetVar x, SetRelType r, int i, int j, BoolVar b);
00678
00680 GECODE_SET_EXPORT void
00681 dom(Home home, SetVar x, SetRelType r, const IntSet& s, BoolVar b);
00682
00684 GECODE_SET_EXPORT void
00685 cardinality(Home home, SetVar x, unsigned int i, unsigned int j);
00686
00688
00689
00697
00699 GECODE_SET_EXPORT void
00700 rel(Home home, SetVar x, SetRelType r, SetVar y);
00701
00703 GECODE_SET_EXPORT void
00704 rel(Home home, SetVar x, SetRelType r, SetVar y, BoolVar b);
00705
00707 GECODE_SET_EXPORT void
00708 rel(Home home, SetVar s, SetRelType r, IntVar x);
00709
00711 GECODE_SET_EXPORT void
00712 rel(Home home, IntVar x, SetRelType r, SetVar s);
00713
00715 GECODE_SET_EXPORT void
00716 rel(Home home, SetVar s, SetRelType r, IntVar x, BoolVar b);
00717
00719 GECODE_SET_EXPORT void
00720 rel(Home home, IntVar x, SetRelType r, SetVar s, BoolVar b);
00721
00723 GECODE_SET_EXPORT void
00724 rel(Home home, SetVar s, IntRelType r, IntVar x);
00725
00727 GECODE_SET_EXPORT void
00728 rel(Home home, IntVar x, IntRelType r, SetVar s);
00729
00731
00739
00741 GECODE_SET_EXPORT void
00742 rel(Home home, SetVar x, SetOpType op, SetVar y, SetRelType r, SetVar z);
00743
00745 GECODE_SET_EXPORT void
00746 rel(Home home, SetOpType op, const SetVarArgs& x, SetVar y);
00747
00749 GECODE_SET_EXPORT void
00750 rel(Home home, SetOpType op, const SetVarArgs& x, const IntSet& z, SetVar y);
00751
00753 GECODE_SET_EXPORT void
00754 rel(Home home, SetOpType op, const IntVarArgs& x, const IntSet& z, SetVar y);
00755
00757 GECODE_SET_EXPORT void
00758 rel(Home home, SetOpType op, const IntVarArgs& x, SetVar y);
00759
00761 GECODE_SET_EXPORT void
00762 rel(Home home, const IntSet& x, SetOpType op, SetVar y,
00763 SetRelType r, SetVar z);
00764
00766 GECODE_SET_EXPORT void
00767 rel(Home home, SetVar x, SetOpType op, const IntSet& y,
00768 SetRelType r, SetVar z);
00769
00771 GECODE_SET_EXPORT void
00772 rel(Home home, SetVar x, SetOpType op, SetVar y,
00773 SetRelType r, const IntSet& z);
00774
00776 GECODE_SET_EXPORT void
00777 rel(Home home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
00778 const IntSet& z);
00779
00781 GECODE_SET_EXPORT void
00782 rel(Home home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
00783 const IntSet& z);
00784
00786
00787
00794
00796 GECODE_SET_EXPORT void
00797 convex(Home home, SetVar x);
00798
00800 GECODE_SET_EXPORT void
00801 convex(Home home, SetVar x, SetVar y);
00802
00804
00811
00813 GECODE_SET_EXPORT void
00814 sequence(Home home, const SetVarArgs& x);
00815
00817 GECODE_SET_EXPORT void
00818 sequence(Home home, const SetVarArgs& y, SetVar x);
00819
00821
00828
00829
00831 GECODE_SET_EXPORT void
00832 atmostOne(Home home, const SetVarArgs& x, unsigned int c);
00833
00835
00843
00846 GECODE_SET_EXPORT void
00847 min(Home home, SetVar s, IntVar x);
00848
00851 GECODE_SET_EXPORT void
00852 notMin(Home home, SetVar s, IntVar x);
00853
00856 GECODE_SET_EXPORT void
00857 min(Home home, SetVar s, IntVar x, BoolVar b);
00858
00861 GECODE_SET_EXPORT void
00862 max(Home home, SetVar s, IntVar x);
00863
00866 GECODE_SET_EXPORT void
00867 notMax(Home home, SetVar s, IntVar x);
00868
00871 GECODE_SET_EXPORT void
00872 max(Home home, SetVar s, IntVar x, BoolVar b);
00873
00875 GECODE_SET_EXPORT void
00876 channel(Home home, const IntVarArgs& x, SetVar y);
00877
00879 GECODE_SET_EXPORT void
00880 channel(Home home, const IntVarArgs& x,const SetVarArgs& y);
00881
00883 GECODE_SET_EXPORT void
00884 channel(Home home, const BoolVarArgs& x, SetVar y);
00885
00887 GECODE_SET_EXPORT void
00888 cardinality(Home home, SetVar s, IntVar x);
00889
00890
00901 GECODE_SET_EXPORT void
00902 weights(Home home, const IntArgs& elements, const IntArgs& weights,
00903 SetVar x, IntVar y);
00904
00906
00920
00930 GECODE_SET_EXPORT void
00931 element(Home home, SetOpType op, const SetVarArgs& x, SetVar y, SetVar z,
00932 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00933
00943 GECODE_SET_EXPORT void
00944 element(Home home, SetOpType op, const IntSetArgs& x, SetVar y, SetVar z,
00945 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00946
00952 GECODE_SET_EXPORT void
00953 element(Home home, const SetVarArgs& x, IntVar y, SetVar z);
00954
00960 GECODE_SET_EXPORT void
00961 element(Home home, const IntSetArgs& s, IntVar y, SetVar z);
00962
00968 GECODE_SET_EXPORT void
00969 element(Home home, const IntSetArgs& a,
00970 IntVar x, int w, IntVar y, int h, SetVar z);
00976 GECODE_SET_EXPORT void
00977 element(Home home, const SetVarArgs& a,
00978 IntVar x, int w, IntVar y, int h, SetVar z);
00980
00991
00992 GECODE_SET_EXPORT void
00993 wait(Home home, SetVar x, void (*c)(Space& home));
00995 GECODE_SET_EXPORT void
00996 wait(Home home, const SetVarArgs& x, void (*c)(Space& home));
00998
01005
01006 enum SetVarBranch {
01007 SET_VAR_NONE = 0,
01008 SET_VAR_RND,
01009 SET_VAR_DEGREE_MIN,
01010 SET_VAR_DEGREE_MAX,
01011 SET_VAR_AFC_MIN,
01012 SET_VAR_AFC_MAX,
01013 SET_VAR_MIN_MIN,
01014 SET_VAR_MIN_MAX,
01015 SET_VAR_MAX_MIN,
01016 SET_VAR_MAX_MAX,
01017 SET_VAR_SIZE_MIN,
01018 SET_VAR_SIZE_MAX,
01019 SET_VAR_SIZE_DEGREE_MIN,
01020 SET_VAR_SIZE_DEGREE_MAX,
01021 SET_VAR_SIZE_AFC_MIN,
01022 SET_VAR_SIZE_AFC_MAX
01023 };
01024
01026 enum SetValBranch {
01027 SET_VAL_MIN_INC,
01028 SET_VAL_MIN_EXC,
01029 SET_VAL_MED_INC,
01030 SET_VAL_MED_EXC,
01031 SET_VAL_MAX_INC,
01032 SET_VAL_MAX_EXC,
01033 SET_VAL_RND_INC,
01034 SET_VAL_RND_EXC
01035 };
01036
01038 GECODE_SET_EXPORT void
01039 branch(Home home, const SetVarArgs& x,
01040 SetVarBranch vars, SetValBranch vals,
01041 const VarBranchOptions& o_vars = VarBranchOptions::def,
01042 const ValBranchOptions& o_vals = ValBranchOptions::def);
01044 GECODE_SET_EXPORT void
01045 branch(Home home, const SetVarArgs& x,
01046 const TieBreakVarBranch<SetVarBranch>& vars, SetValBranch vals,
01047 const TieBreakVarBranchOptions& o_vars = TieBreakVarBranchOptions::def,
01048 const ValBranchOptions& o_vals = ValBranchOptions::def);
01050 GECODE_SET_EXPORT void
01051 branch(Home home, SetVar x, SetValBranch vals,
01052 const ValBranchOptions& o_vals = ValBranchOptions::def);
01054
01060
01061 enum SetAssign {
01062 SET_ASSIGN_MIN_INC,
01063 SET_ASSIGN_MIN_EXC,
01064 SET_ASSIGN_MED_INC,
01065 SET_ASSIGN_MED_EXC,
01066 SET_ASSIGN_MAX_INC,
01067 SET_ASSIGN_MAX_EXC,
01068 SET_ASSIGN_RND_INC,
01069 SET_ASSIGN_RND_EXC
01070 };
01071
01073 GECODE_SET_EXPORT void
01074 assign(Home home, const SetVarArgs& x, SetAssign vals,
01075 const ValBranchOptions& o_vals = ValBranchOptions::def);
01077 GECODE_SET_EXPORT void
01078 assign(Home home, SetVar x, SetAssign vals,
01079 const ValBranchOptions& o_vals = ValBranchOptions::def);
01080
01082
01083 }
01084
01085 #endif
01086
01087
01088