Generated on Wed Jul 27 2011 15:08:52 for Gecode by doxygen 1.7.4
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