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 VarBase<Set::SetVarImp> {
00130 friend class SetVarArray;
00131 private:
00132 using VarBase<Set::SetVarImp>::varimp;
00134 void init(Space& home);
00143 void init(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
00144 unsigned int cardMin = 0,
00145 unsigned int cardMax = Set::Limits::card);
00154 void init(Space& home,const IntSet& glbD,int lubMin,int lubMax,
00155 unsigned int cardMin = 0,
00156 unsigned int cardMax = Set::Limits::card);
00165 void init(Space& home,int glbMin,int glbMax,const IntSet& lubD,
00166 unsigned int cardMin = 0,
00167 unsigned int cardMax = Set::Limits::card);
00176 void init(Space& home,const IntSet& glbD,const IntSet& lubD,
00177 unsigned int cardMin = 0,
00178 unsigned int cardMax = Set::Limits::card);
00179 public:
00181
00182
00183 SetVar(void);
00185 SetVar(const SetVar& x0);
00187 SetVar(const Set::SetView& x0);
00188
00190 GECODE_SET_EXPORT SetVar(Space& home);
00191
00209 GECODE_SET_EXPORT
00210 SetVar(Space& home,int glbMin,int glbMax,int lubMin,int lubMax,
00211 unsigned int cardMin = 0,
00212 unsigned int cardMax = Set::Limits::card);
00213
00231 GECODE_SET_EXPORT
00232 SetVar(Space& home,const IntSet& glbD,int lubMin,int lubMax,
00233 unsigned int cardMin = 0,
00234 unsigned int cardMax = Set::Limits::card);
00235
00253 GECODE_SET_EXPORT
00254 SetVar(Space& home,int glbMin,int glbMax,const IntSet& lubD,
00255 unsigned int cardMin = 0,
00256 unsigned int cardMax = Set::Limits::card);
00257
00275 GECODE_SET_EXPORT
00276 SetVar(Space& home,const IntSet& glbD,const IntSet& lubD,
00277 unsigned int cardMin = 0,
00278 unsigned int cardMax = Set::Limits::card);
00280
00282
00283
00284 unsigned int glbSize(void) const;
00286 unsigned int lubSize(void) const;
00288 unsigned int unknownSize(void) const;
00290 unsigned int cardMin(void) const;
00292 unsigned int cardMax(void) const;
00294 int lubMin(void) const;
00296 int lubMax(void) const;
00298 int glbMin(void) const;
00300 int glbMax(void) const;
00302
00304
00305
00306 bool contains(int i) const;
00308 bool notContains(int i) const;
00310 bool assigned(void) const;
00311
00313
00314
00315 void update(Space& home, bool, SetVar& x);
00317 };
00318
00324
00326 class SetVarGlbRanges {
00327 private:
00328 Set::GlbRanges<Set::SetVarImp*> iter;
00329 public:
00331
00332
00333 SetVarGlbRanges(void);
00335 SetVarGlbRanges(const SetVar& x);
00337
00339
00340
00341 bool operator ()(void) const;
00343 void operator ++(void);
00345
00347
00348
00349 int min(void) const;
00351 int max(void) const;
00353 unsigned int width(void) const;
00355 };
00356
00358 class SetVarLubRanges {
00359 private:
00360 Set::LubRanges<Set::SetVarImp*> iter;
00361 public:
00363
00364
00365 SetVarLubRanges(void);
00367 SetVarLubRanges(const SetVar& x);
00369
00371
00372
00373 bool operator ()(void) const;
00375 void operator ++(void);
00377
00379
00380
00381 int min(void) const;
00383 int max(void) const;
00385 unsigned int width(void) const;
00387 };
00388
00390 class SetVarUnknownRanges {
00391 private:
00392 Set::UnknownRanges<Set::SetVarImp*> iter;
00393 public:
00395
00396
00397 SetVarUnknownRanges(void);
00399 SetVarUnknownRanges(const SetVar& x);
00401
00403
00404
00405 bool operator ()(void) const;
00407 void operator ++(void);
00409
00411
00412
00413 int min(void) const;
00415 int max(void) const;
00417 unsigned int width(void) const;
00419 };
00420
00422 class SetVarGlbValues {
00423 private:
00424 Iter::Ranges::ToValues<SetVarGlbRanges> iter;
00425 public:
00427
00428
00429 SetVarGlbValues(void);
00431 SetVarGlbValues(const SetVar& x);
00433
00435
00436
00437 bool operator ()(void) const;
00439 void operator ++(void);
00441
00443
00444
00445 int val(void) const;
00447 };
00448
00450 class SetVarLubValues {
00451 private:
00452 Iter::Ranges::ToValues<SetVarLubRanges> iter;
00453 public:
00455
00456
00457 SetVarLubValues(void);
00459 SetVarLubValues(const SetVar& x);
00461
00463
00464
00465 bool operator ()(void) const;
00467 void operator ++(void);
00469
00471
00472
00473 int val(void) const;
00475 };
00476
00478 class SetVarUnknownValues {
00479 private:
00480 Iter::Ranges::ToValues<SetVarUnknownRanges> iter;
00481 public:
00483
00484
00485 SetVarUnknownValues(void);
00487 SetVarUnknownValues(const SetVar& x);
00489
00491
00492
00493 bool operator ()(void) const;
00495 void operator ++(void);
00497
00499
00500
00501 int val(void) const;
00503 };
00504
00506
00511 template<class Char, class Traits>
00512 std::basic_ostream<Char,Traits>&
00513 operator <<(std::basic_ostream<Char,Traits>& os, const SetVar& x);
00514
00515 }
00516
00517 #include <gecode/set/view.hpp>
00518
00519 namespace Gecode {
00537 class SetVarArgs : public VarArgArray<SetVar> {
00538 public:
00540
00541
00542 explicit SetVarArgs(int n) : VarArgArray<SetVar>(n) {}
00544 SetVarArgs(const SetVarArgs& a) : VarArgArray<SetVar>(a) {}
00546 SetVarArgs(const VarArray<SetVar>& a) : VarArgArray<SetVar>(a) {}
00548 };
00550
00566 class SetVarArray : public VarArray<SetVar> {
00567 public:
00568 SetVarArray(void);
00569 SetVarArray(const SetVarArray&);
00571 GECODE_SET_EXPORT SetVarArray(Space& home,int n);
00578 GECODE_SET_EXPORT
00579 SetVarArray(Space& home,int n,int glbMin,int glbMax,int lubMin,int lubMax,
00580 unsigned int minCard = 0,
00581 unsigned int maxCard = Set::Limits::card);
00588 GECODE_SET_EXPORT
00589 SetVarArray(Space& home,int n,const IntSet& glb, int lubMin, int lubMax,
00590 unsigned int minCard = 0,
00591 unsigned int maxCard = Set::Limits::card);
00598 GECODE_SET_EXPORT
00599 SetVarArray(Space& home,int n,int glbMin,int glbMax,const IntSet& lub,
00600 unsigned int minCard = 0,
00601 unsigned int maxCard = Set::Limits::card);
00608 GECODE_SET_EXPORT
00609 SetVarArray(Space& home,int n,
00610 const IntSet& glb,const IntSet& lub,
00611 unsigned int minCard = 0,
00612 unsigned int maxCard = Set::Limits::card);
00613 };
00614
00615 }
00616
00617 #include <gecode/set/array.hpp>
00618
00619 namespace Gecode {
00620
00625 enum SetRelType {
00626 SRT_EQ,
00627 SRT_NQ,
00628 SRT_SUB,
00629 SRT_SUP,
00630 SRT_DISJ,
00631 SRT_CMPL
00632 };
00633
00638 enum SetOpType {
00639 SOT_UNION,
00640 SOT_DUNION,
00641 SOT_INTER,
00642 SOT_MINUS
00643 };
00644
00652
00654 GECODE_SET_EXPORT void
00655 dom(Home home, SetVar x, SetRelType r, int i);
00656
00658 GECODE_SET_EXPORT void
00659 dom(Home home, SetVar x, SetRelType r, int i, int j);
00660
00662 GECODE_SET_EXPORT void
00663 dom(Home home, SetVar x, SetRelType r, const IntSet& s);
00664
00666 GECODE_SET_EXPORT void
00667 dom(Home home, SetVar x, SetRelType r, int i, BoolVar b);
00668
00670 GECODE_SET_EXPORT void
00671 dom(Home home, SetVar x, SetRelType r, int i, int j, BoolVar b);
00672
00674 GECODE_SET_EXPORT void
00675 dom(Home home, SetVar x, SetRelType r, const IntSet& s, BoolVar b);
00676
00678 GECODE_SET_EXPORT void
00679 cardinality(Home home, SetVar x, unsigned int i, unsigned int j);
00680
00682
00683
00691
00693 GECODE_SET_EXPORT void
00694 rel(Home home, SetVar x, SetRelType r, SetVar y);
00695
00697 GECODE_SET_EXPORT void
00698 rel(Home home, SetVar x, SetRelType r, SetVar y, BoolVar b);
00699
00701 GECODE_SET_EXPORT void
00702 rel(Home home, SetVar s, SetRelType r, IntVar x);
00703
00705 GECODE_SET_EXPORT void
00706 rel(Home home, IntVar x, SetRelType r, SetVar s);
00707
00709 GECODE_SET_EXPORT void
00710 rel(Home home, SetVar s, SetRelType r, IntVar x, BoolVar b);
00711
00713 GECODE_SET_EXPORT void
00714 rel(Home home, IntVar x, SetRelType r, SetVar s, BoolVar b);
00715
00717 GECODE_SET_EXPORT void
00718 rel(Home home, SetVar s, IntRelType r, IntVar x);
00719
00721 GECODE_SET_EXPORT void
00722 rel(Home home, IntVar x, IntRelType r, SetVar s);
00723
00725
00733
00735 GECODE_SET_EXPORT void
00736 rel(Home home, SetVar x, SetOpType op, SetVar y, SetRelType r, SetVar z);
00737
00739 GECODE_SET_EXPORT void
00740 rel(Home home, SetOpType op, const SetVarArgs& x, SetVar y);
00741
00743 GECODE_SET_EXPORT void
00744 rel(Home home, SetOpType op, const SetVarArgs& x, const IntSet& z, SetVar y);
00745
00747 GECODE_SET_EXPORT void
00748 rel(Home home, SetOpType op, const IntVarArgs& x, const IntSet& z, SetVar y);
00749
00751 GECODE_SET_EXPORT void
00752 rel(Home home, SetOpType op, const IntVarArgs& x, SetVar y);
00753
00755 GECODE_SET_EXPORT void
00756 rel(Home home, const IntSet& x, SetOpType op, SetVar y,
00757 SetRelType r, SetVar z);
00758
00760 GECODE_SET_EXPORT void
00761 rel(Home home, SetVar x, SetOpType op, const IntSet& y,
00762 SetRelType r, SetVar z);
00763
00765 GECODE_SET_EXPORT void
00766 rel(Home home, SetVar x, SetOpType op, SetVar y,
00767 SetRelType r, const IntSet& z);
00768
00770 GECODE_SET_EXPORT void
00771 rel(Home home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
00772 const IntSet& z);
00773
00775 GECODE_SET_EXPORT void
00776 rel(Home home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
00777 const IntSet& z);
00778
00780
00781
00788
00790 GECODE_SET_EXPORT void
00791 convex(Home home, SetVar x);
00792
00794 GECODE_SET_EXPORT void
00795 convex(Home home, SetVar x, SetVar y);
00796
00798
00805
00807 GECODE_SET_EXPORT void
00808 sequence(Home home, const SetVarArgs& x);
00809
00811 GECODE_SET_EXPORT void
00812 sequence(Home home, const SetVarArgs& y, SetVar x);
00813
00815
00822
00823
00825 GECODE_SET_EXPORT void
00826 atmostOne(Home home, const SetVarArgs& x, unsigned int c);
00827
00829
00837
00840 GECODE_SET_EXPORT void
00841 min(Home home, SetVar s, IntVar x);
00842
00845 GECODE_SET_EXPORT void
00846 notMin(Home home, SetVar s, IntVar x);
00847
00850 GECODE_SET_EXPORT void
00851 min(Home home, SetVar s, IntVar x, BoolVar b);
00852
00855 GECODE_SET_EXPORT void
00856 max(Home home, SetVar s, IntVar x);
00857
00860 GECODE_SET_EXPORT void
00861 notMax(Home home, SetVar s, IntVar x);
00862
00865 GECODE_SET_EXPORT void
00866 max(Home home, SetVar s, IntVar x, BoolVar b);
00867
00869 GECODE_SET_EXPORT void
00870 channel(Home home, const IntVarArgs& x, SetVar y);
00871
00873 GECODE_SET_EXPORT void
00874 channel(Home home, const IntVarArgs& x,const SetVarArgs& y);
00875
00877 GECODE_SET_EXPORT void
00878 channel(Home home, const BoolVarArgs& x, SetVar y);
00879
00881 GECODE_SET_EXPORT void
00882 cardinality(Home home, SetVar s, IntVar x);
00883
00884
00895 GECODE_SET_EXPORT void
00896 weights(Home home, const IntArgs& elements, const IntArgs& weights,
00897 SetVar x, IntVar y);
00898
00900
00914
00924 GECODE_SET_EXPORT void
00925 element(Home home, SetOpType op, const SetVarArgs& x, SetVar y, SetVar z,
00926 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00927
00937 GECODE_SET_EXPORT void
00938 element(Home home, SetOpType op, const IntSetArgs& x, SetVar y, SetVar z,
00939 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00940
00946 GECODE_SET_EXPORT void
00947 element(Home home, const SetVarArgs& x, IntVar y, SetVar z);
00948
00954 GECODE_SET_EXPORT void
00955 element(Home home, const IntSetArgs& s, IntVar y, SetVar z);
00956
00962 GECODE_SET_EXPORT void
00963 element(Home home, const IntSetArgs& a,
00964 IntVar x, int w, IntVar y, int h, SetVar z);
00970 GECODE_SET_EXPORT void
00971 element(Home home, const SetVarArgs& a,
00972 IntVar x, int w, IntVar y, int h, SetVar z);
00974
00985
00986 GECODE_SET_EXPORT void
00987 wait(Home home, SetVar x, void (*c)(Space& home));
00989 GECODE_SET_EXPORT void
00990 wait(Home home, const SetVarArgs& x, void (*c)(Space& home));
00992
00999
01000 enum SetVarBranch {
01001 SET_VAR_NONE = 0,
01002 SET_VAR_RND,
01003 SET_VAR_DEGREE_MIN,
01004 SET_VAR_DEGREE_MAX,
01005 SET_VAR_AFC_MIN,
01006 SET_VAR_AFC_MAX,
01007 SET_VAR_MIN_MIN,
01008 SET_VAR_MIN_MAX,
01009 SET_VAR_MAX_MIN,
01010 SET_VAR_MAX_MAX,
01011 SET_VAR_SIZE_MIN,
01012 SET_VAR_SIZE_MAX,
01013 SET_VAR_SIZE_DEGREE_MIN,
01014 SET_VAR_SIZE_DEGREE_MAX,
01015 SET_VAR_SIZE_AFC_MIN,
01016 SET_VAR_SIZE_AFC_MAX
01017 };
01018
01020 enum SetValBranch {
01021 SET_VAL_MIN_INC,
01022 SET_VAL_MIN_EXC,
01023 SET_VAL_MED_INC,
01024 SET_VAL_MED_EXC,
01025 SET_VAL_MAX_INC,
01026 SET_VAL_MAX_EXC,
01027 SET_VAL_RND_INC,
01028 SET_VAL_RND_EXC
01029 };
01030
01032 GECODE_SET_EXPORT void
01033 branch(Home home, const SetVarArgs& x,
01034 SetVarBranch vars, SetValBranch vals,
01035 const VarBranchOptions& o_vars = VarBranchOptions::def,
01036 const ValBranchOptions& o_vals = ValBranchOptions::def);
01038 GECODE_SET_EXPORT void
01039 branch(Home home, const SetVarArgs& x,
01040 const TieBreakVarBranch<SetVarBranch>& vars, SetValBranch vals,
01041 const TieBreakVarBranchOptions& o_vars = TieBreakVarBranchOptions::def,
01042 const ValBranchOptions& o_vals = ValBranchOptions::def);
01044 GECODE_SET_EXPORT void
01045 branch(Home home, SetVar x, SetValBranch vals,
01046 const ValBranchOptions& o_vals = ValBranchOptions::def);
01048
01054
01055 enum SetAssign {
01056 SET_ASSIGN_MIN_INC,
01057 SET_ASSIGN_MIN_EXC,
01058 SET_ASSIGN_MED_INC,
01059 SET_ASSIGN_MED_EXC,
01060 SET_ASSIGN_MAX_INC,
01061 SET_ASSIGN_MAX_EXC,
01062 SET_ASSIGN_RND_INC,
01063 SET_ASSIGN_RND_EXC
01064 };
01065
01067 GECODE_SET_EXPORT void
01068 assign(Home home, const SetVarArgs& x, SetAssign vals,
01069 const ValBranchOptions& o_vals = ValBranchOptions::def);
01071 GECODE_SET_EXPORT void
01072 assign(Home home, SetVar x, SetAssign vals,
01073 const ValBranchOptions& o_vals = ValBranchOptions::def);
01074
01076
01077 }
01078
01079 #endif
01080
01081
01082