Generated on Mon Nov 30 23:53:34 2009 for Gecode by doxygen 1.6.1

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: 2009-10-13 21:12:58 +0200 (Tue, 13 Oct 2009) $ by $Author: schulte $
00017  *     $Revision: 9897 $
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 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 // IFDEF: GECODE_HAS_SET_VARS
01083 // STATISTICS: set-post