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 #include <gecode/set/propagator.hpp>
00519
00520 namespace Gecode {
00538 class SetVarArgs : public VarArgArray<SetVar> {
00539 public:
00541
00542
00543 explicit SetVarArgs(int n) : VarArgArray<SetVar>(n) {}
00545 SetVarArgs(const SetVarArgs& a) : VarArgArray<SetVar>(a) {}
00547 SetVarArgs(const VarArray<SetVar>& a) : VarArgArray<SetVar>(a) {}
00549 };
00551
00567 class SetVarArray : public VarArray<SetVar> {
00568 public:
00569 SetVarArray(void);
00570 SetVarArray(const SetVarArray&);
00572 GECODE_SET_EXPORT SetVarArray(Space& home,int n);
00579 GECODE_SET_EXPORT
00580 SetVarArray(Space& home,int n,int glbMin,int glbMax,int lubMin,int lubMax,
00581 unsigned int minCard = 0,
00582 unsigned int maxCard = Set::Limits::card);
00589 GECODE_SET_EXPORT
00590 SetVarArray(Space& home,int n,const IntSet& glb, int lubMin, int lubMax,
00591 unsigned int minCard = 0,
00592 unsigned int maxCard = Set::Limits::card);
00599 GECODE_SET_EXPORT
00600 SetVarArray(Space& home,int n,int glbMin,int glbMax,const IntSet& lub,
00601 unsigned int minCard = 0,
00602 unsigned int maxCard = Set::Limits::card);
00609 GECODE_SET_EXPORT
00610 SetVarArray(Space& home,int n,
00611 const IntSet& glb,const IntSet& lub,
00612 unsigned int minCard = 0,
00613 unsigned int maxCard = Set::Limits::card);
00614 };
00615
00616 }
00617
00618 #include <gecode/set/array.hpp>
00619
00620 namespace Gecode {
00621
00626 enum SetRelType {
00627 SRT_EQ,
00628 SRT_NQ,
00629 SRT_SUB,
00630 SRT_SUP,
00631 SRT_DISJ,
00632 SRT_CMPL
00633 };
00634
00639 enum SetOpType {
00640 SOT_UNION,
00641 SOT_DUNION,
00642 SOT_INTER,
00643 SOT_MINUS
00644 };
00645
00653
00655 GECODE_SET_EXPORT void
00656 dom(Home home, SetVar x, SetRelType r, int i);
00657
00659 GECODE_SET_EXPORT void
00660 dom(Home home, SetVar x, SetRelType r, int i, int j);
00661
00663 GECODE_SET_EXPORT void
00664 dom(Home home, SetVar x, SetRelType r, const IntSet& s);
00665
00667 GECODE_SET_EXPORT void
00668 dom(Home home, SetVar x, SetRelType r, int i, BoolVar b);
00669
00671 GECODE_SET_EXPORT void
00672 dom(Home home, SetVar x, SetRelType r, int i, int j, BoolVar b);
00673
00675 GECODE_SET_EXPORT void
00676 dom(Home home, SetVar x, SetRelType r, const IntSet& s, BoolVar b);
00677
00679 GECODE_SET_EXPORT void
00680 cardinality(Home home, SetVar x, unsigned int i, unsigned int j);
00681
00683
00684
00692
00694 GECODE_SET_EXPORT void
00695 rel(Home home, SetVar x, SetRelType r, SetVar y);
00696
00698 GECODE_SET_EXPORT void
00699 rel(Home home, SetVar x, SetRelType r, SetVar y, BoolVar b);
00700
00702 GECODE_SET_EXPORT void
00703 rel(Home home, SetVar s, SetRelType r, IntVar x);
00704
00706 GECODE_SET_EXPORT void
00707 rel(Home home, IntVar x, SetRelType r, SetVar s);
00708
00710 GECODE_SET_EXPORT void
00711 rel(Home home, SetVar s, SetRelType r, IntVar x, BoolVar b);
00712
00714 GECODE_SET_EXPORT void
00715 rel(Home home, IntVar x, SetRelType r, SetVar s, BoolVar b);
00716
00718 GECODE_SET_EXPORT void
00719 rel(Home home, SetVar s, IntRelType r, IntVar x);
00720
00722 GECODE_SET_EXPORT void
00723 rel(Home home, IntVar x, IntRelType r, SetVar s);
00724
00726
00734
00736 GECODE_SET_EXPORT void
00737 rel(Home home, SetVar x, SetOpType op, SetVar y, SetRelType r, SetVar z);
00738
00740 GECODE_SET_EXPORT void
00741 rel(Home home, SetOpType op, const SetVarArgs& x, SetVar y);
00742
00744 GECODE_SET_EXPORT void
00745 rel(Home home, SetOpType op, const SetVarArgs& x, const IntSet& z, SetVar y);
00746
00748 GECODE_SET_EXPORT void
00749 rel(Home home, SetOpType op, const IntVarArgs& x, const IntSet& z, SetVar y);
00750
00752 GECODE_SET_EXPORT void
00753 rel(Home home, SetOpType op, const IntVarArgs& x, SetVar y);
00754
00756 GECODE_SET_EXPORT void
00757 rel(Home home, const IntSet& x, SetOpType op, SetVar y,
00758 SetRelType r, SetVar z);
00759
00761 GECODE_SET_EXPORT void
00762 rel(Home home, SetVar x, SetOpType op, const IntSet& y,
00763 SetRelType r, SetVar z);
00764
00766 GECODE_SET_EXPORT void
00767 rel(Home home, SetVar x, SetOpType op, SetVar y,
00768 SetRelType r, const IntSet& z);
00769
00771 GECODE_SET_EXPORT void
00772 rel(Home home, const IntSet& x, SetOpType op, SetVar y, SetRelType r,
00773 const IntSet& z);
00774
00776 GECODE_SET_EXPORT void
00777 rel(Home home, SetVar x, SetOpType op, const IntSet& y, SetRelType r,
00778 const IntSet& z);
00779
00781
00782
00789
00791 GECODE_SET_EXPORT void
00792 convex(Home home, SetVar x);
00793
00795 GECODE_SET_EXPORT void
00796 convex(Home home, SetVar x, SetVar y);
00797
00799
00806
00808 GECODE_SET_EXPORT void
00809 sequence(Home home, const SetVarArgs& x);
00810
00812 GECODE_SET_EXPORT void
00813 sequence(Home home, const SetVarArgs& y, SetVar x);
00814
00816
00823
00824
00826 GECODE_SET_EXPORT void
00827 atmostOne(Home home, const SetVarArgs& x, unsigned int c);
00828
00830
00838
00841 GECODE_SET_EXPORT void
00842 min(Home home, SetVar s, IntVar x);
00843
00846 GECODE_SET_EXPORT void
00847 notMin(Home home, SetVar s, IntVar x);
00848
00851 GECODE_SET_EXPORT void
00852 min(Home home, SetVar s, IntVar x, BoolVar b);
00853
00856 GECODE_SET_EXPORT void
00857 max(Home home, SetVar s, IntVar x);
00858
00861 GECODE_SET_EXPORT void
00862 notMax(Home home, SetVar s, IntVar x);
00863
00866 GECODE_SET_EXPORT void
00867 max(Home home, SetVar s, IntVar x, BoolVar b);
00868
00870 GECODE_SET_EXPORT void
00871 channel(Home home, const IntVarArgs& x, SetVar y);
00872
00874 GECODE_SET_EXPORT void
00875 channel(Home home, const IntVarArgs& x,const SetVarArgs& y);
00876
00878 GECODE_SET_EXPORT void
00879 channel(Home home, const BoolVarArgs& x, SetVar y);
00880
00882 GECODE_SET_EXPORT void
00883 cardinality(Home home, SetVar s, IntVar x);
00884
00885
00896 GECODE_SET_EXPORT void
00897 weights(Home home, const IntArgs& elements, const IntArgs& weights,
00898 SetVar x, IntVar y);
00899
00901
00915
00925 GECODE_SET_EXPORT void
00926 element(Home home, SetOpType op, const SetVarArgs& x, SetVar y, SetVar z,
00927 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00928
00938 GECODE_SET_EXPORT void
00939 element(Home home, SetOpType op, const IntSetArgs& x, SetVar y, SetVar z,
00940 const IntSet& u = IntSet(Set::Limits::min,Set::Limits::max));
00941
00947 GECODE_SET_EXPORT void
00948 element(Home home, const SetVarArgs& x, IntVar y, SetVar z);
00949
00955 GECODE_SET_EXPORT void
00956 element(Home home, const IntSetArgs& s, IntVar y, SetVar z);
00957
00963 GECODE_SET_EXPORT void
00964 element(Home home, const IntSetArgs& a,
00965 IntVar x, int w, IntVar y, int h, SetVar z);
00971 GECODE_SET_EXPORT void
00972 element(Home home, const SetVarArgs& a,
00973 IntVar x, int w, IntVar y, int h, SetVar z);
00975
00986
00987 GECODE_SET_EXPORT void
00988 wait(Home home, SetVar x, void (*c)(Space& home));
00990 GECODE_SET_EXPORT void
00991 wait(Home home, const SetVarArgs& x, void (*c)(Space& home));
00993
01000
01001 enum SetVarBranch {
01002 SET_VAR_NONE = 0,
01003 SET_VAR_RND,
01004 SET_VAR_DEGREE_MIN,
01005 SET_VAR_DEGREE_MAX,
01006 SET_VAR_AFC_MIN,
01007 SET_VAR_AFC_MAX,
01008 SET_VAR_MIN_MIN,
01009 SET_VAR_MIN_MAX,
01010 SET_VAR_MAX_MIN,
01011 SET_VAR_MAX_MAX,
01012 SET_VAR_SIZE_MIN,
01013 SET_VAR_SIZE_MAX,
01014 SET_VAR_SIZE_DEGREE_MIN,
01015 SET_VAR_SIZE_DEGREE_MAX,
01016 SET_VAR_SIZE_AFC_MIN,
01017 SET_VAR_SIZE_AFC_MAX
01018 };
01019
01021 enum SetValBranch {
01022 SET_VAL_MIN_INC,
01023 SET_VAL_MIN_EXC,
01024 SET_VAL_MED_INC,
01025 SET_VAL_MED_EXC,
01026 SET_VAL_MAX_INC,
01027 SET_VAL_MAX_EXC,
01028 SET_VAL_RND_INC,
01029 SET_VAL_RND_EXC
01030 };
01031
01033 GECODE_SET_EXPORT void
01034 branch(Home home, const SetVarArgs& x,
01035 SetVarBranch vars, SetValBranch vals,
01036 const VarBranchOptions& o_vars = VarBranchOptions::def,
01037 const ValBranchOptions& o_vals = ValBranchOptions::def);
01039 GECODE_SET_EXPORT void
01040 branch(Home home, const SetVarArgs& x,
01041 const TieBreakVarBranch<SetVarBranch>& vars, SetValBranch vals,
01042 const TieBreakVarBranchOptions& o_vars = TieBreakVarBranchOptions::def,
01043 const ValBranchOptions& o_vals = ValBranchOptions::def);
01045 GECODE_SET_EXPORT void
01046 branch(Home home, SetVar x, SetValBranch vals,
01047 const ValBranchOptions& o_vals = ValBranchOptions::def);
01049
01055
01056 enum SetAssign {
01057 SET_ASSIGN_MIN_INC,
01058 SET_ASSIGN_MIN_EXC,
01059 SET_ASSIGN_MED_INC,
01060 SET_ASSIGN_MED_EXC,
01061 SET_ASSIGN_MAX_INC,
01062 SET_ASSIGN_MAX_EXC,
01063 SET_ASSIGN_RND_INC,
01064 SET_ASSIGN_RND_EXC
01065 };
01066
01068 GECODE_SET_EXPORT void
01069 assign(Home home, const SetVarArgs& x, SetAssign vals,
01070 const ValBranchOptions& o_vals = ValBranchOptions::def);
01072 GECODE_SET_EXPORT void
01073 assign(Home home, SetVar x, SetAssign vals,
01074 const ValBranchOptions& o_vals = ValBranchOptions::def);
01075
01077
01078 }
01079
01080 #endif
01081
01082
01083