set.hh
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Guido Tack <tack@gecode.org> 00005 * Christian Schulte <schulte@gecode.org> 00006 * 00007 * Contributing authors: 00008 * Gabor Szokoli <szokoli@gecode.org> 00009 * 00010 * Copyright: 00011 * Guido Tack, 2004 00012 * Christian Schulte, 2004 00013 * Gabor Szokoli, 2004 00014 * 00015 * Last modified: 00016 * $Date: 2010-08-31 16:19:34 +0200 (Tue, 31 Aug 2010) $ by $Author: schulte $ 00017 * $Revision: 11366 $ 00018 * 00019 * This file is part of Gecode, the generic constraint 00020 * development environment: 00021 * http://www.gecode.org 00022 * 00023 * Permission is hereby granted, free of charge, to any person obtaining 00024 * a copy of this software and associated documentation files (the 00025 * "Software"), to deal in the Software without restriction, including 00026 * without limitation the rights to use, copy, modify, merge, publish, 00027 * distribute, sublicense, and/or sell copies of the Software, and to 00028 * permit persons to whom the Software is furnished to do so, subject to 00029 * the following conditions: 00030 * 00031 * The above copyright notice and this permission notice shall be 00032 * included in all copies or substantial portions of the Software. 00033 * 00034 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00035 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00036 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00037 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00038 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00039 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00040 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 * Configure linking 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 // Configure auto-linking 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 // IFDEF: GECODE_HAS_SET_VARS 01088 // STATISTICS: set-post