cpltset.hh

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00005  *
00006  *  Copyright:
00007  *     Patrick Pekczynski, 2006
00008  *
00009  *  Last modified:
00010  *     $Date: 2008-08-06 10:39:34 +0200 (Wed, 06 Aug 2008) $ by $Author: raphael $
00011  *     $Revision: 7494 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #ifndef __GECODE_CPLTSET_HH__
00039 #define __GECODE_CPLTSET_HH__
00040 
00041 #include "gecode/kernel.hh"
00042 #include "gecode/iter.hh"
00043 #include "gecode/int.hh"
00044 #include "gecode/set.hh"
00045 
00046 /*
00047  * Configure linking
00048  *
00049  */
00050 #if !defined(GECODE_STATIC_LIBS) && \
00051     (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00052 
00053 #ifdef GECODE_BUILD_CPLTSET
00054 #define GECODE_CPLTSET_EXPORT __declspec( dllexport )
00055 #else
00056 #define GECODE_CPLTSET_EXPORT __declspec( dllimport )
00057 #endif
00058 
00059 #else
00060 
00061 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
00062 #define GECODE_CPLTSET_EXPORT __attribute__ ((visibility("default")))
00063 #else
00064 #define GECODE_CPLTSET_EXPORT
00065 #endif
00066 
00067 #endif
00068 
00069 #include "gecode/cpltset/exception.icc"
00070 
00085 #include "gecode/cpltset/bddmanager.icc"
00086 
00087 #include "gecode/cpltset/support.icc"
00088 #include "gecode/cpltset/var-imp.icc"
00089 
00090 namespace Gecode { 
00097   class CpltSetVar : public VarBase<CpltSet::CpltSetVarImp> {
00098   private:
00099     using VarBase<CpltSet::CpltSetVarImp>::varimp;  
00100   public:
00102     CpltSetVar(void);
00103 
00105     void dispose(Space* home);
00106 
00124     GECODE_CPLTSET_EXPORT 
00125     CpltSetVar(Space* home,
00126                int glbMin,int glbMax,int lubMin,int lubMax,
00127                unsigned int cardMin = 0,
00128                unsigned int cardMax = Set::Limits::card);
00146     void init(Space* home,
00147               int glbMin,int glbMax,int lubMin,int lubMax,
00148               unsigned int cardMin = 0,
00149               unsigned int cardMax = Set::Limits::card);
00150 
00168     GECODE_CPLTSET_EXPORT 
00169     CpltSetVar(Space* home,
00170                const IntSet& glbD,int lubMin,int lubMax,
00171                unsigned int cardMin = 0,
00172                unsigned int cardMax = Set::Limits::card);
00190     void init(Space* home,
00191               const IntSet& glbD,int lubMin,int lubMax,
00192               unsigned int cardMin = 0,
00193               unsigned int cardMax = Set::Limits::card);
00194 
00212     GECODE_CPLTSET_EXPORT 
00213     CpltSetVar(Space* home,
00214                int glbMin,int glbMax,const IntSet& lubD,
00215                unsigned int cardMin = 0,
00216                unsigned int cardMax = Set::Limits::card);
00234     void init(Space* home,
00235               int glbMin,int glbMax,const IntSet& lubD,
00236               unsigned int cardMin = 0,
00237               unsigned int cardMax = Set::Limits::card);
00238 
00256     GECODE_CPLTSET_EXPORT 
00257     CpltSetVar(Space* home,
00258                const IntSet& glbD,const IntSet& lubD,
00259                unsigned int cardMin = 0,
00260                unsigned int cardMax = Set::Limits::card);
00277     void init(Space* home,
00278               const IntSet& glbD,const IntSet& lubD,
00279               unsigned int cardMin = 0,
00280               unsigned int cardMax = Set::Limits::card);
00282 
00284 
00285 
00286     unsigned int glbSize(void) const;
00288     unsigned int lubSize(void) const;
00290     unsigned int unknownSize(void) const;
00292     unsigned int cardMin(void) const;
00294     unsigned int cardMax(void) const;
00296     int lubMin(void) const;
00298     int lubMax(void) const;
00300     int glbMin(void) const;
00302     int glbMax(void) const;
00304 
00306 
00307 
00308     bool contains(int i) const;
00310     bool notContains(int i) const;
00312     bool assigned(void) const;
00314     
00316 
00317 
00318     void update(Space* home, bool share, CpltSetVar& x);
00320 
00321   };
00322 
00328   class CpltSetVarGlbRanges {
00329   private:
00330     Set::GlbRanges<CpltSet::CpltSetVarImp*> iter;
00331   public:
00332     CpltSetVarGlbRanges(void);
00333     CpltSetVarGlbRanges(const CpltSetVar& x);
00334     bool operator()(void) const;
00335     void operator++(void);
00336     int min(void) const;
00337     int max(void) const;
00338   };
00339 
00345   class CpltSetVarGlbValues {
00346   private:
00347     CpltSet::GlbValues<CpltSet::CpltSetVarImp*> iter;
00348   public:
00349     CpltSetVarGlbValues(void);
00350     CpltSetVarGlbValues(const CpltSetVar& x);
00351     bool operator()(void) const;
00352     void operator++(void);
00353     int val(void) const;
00354   };
00355 
00361   class CpltSetVarLubRanges {
00362   private:
00363     Set::LubRanges<CpltSet::CpltSetVarImp*> iter;
00364   public:
00365     CpltSetVarLubRanges(void);
00366     CpltSetVarLubRanges(const CpltSetVar& x);
00367     bool operator()(void) const;
00368     void operator++(void);
00369     int min(void) const;
00370     int max(void) const;
00371   };
00372 
00378   class CpltSetVarLubValues {
00379   private:
00380     CpltSet::LubValues<CpltSet::CpltSetVarImp*> iter;
00381   public:
00382     CpltSetVarLubValues(void);
00383     CpltSetVarLubValues(const CpltSetVar& x);
00384     bool operator()(void) const;
00385     void operator++(void);
00386     int val(void) const;
00387   };
00388 
00394   class CpltSetVarUnknownRanges {
00395   private:
00396     Set::UnknownRanges<CpltSet::CpltSetVarImp*> iter;
00397   public:
00398     CpltSetVarUnknownRanges(void);
00399     CpltSetVarUnknownRanges(const CpltSetVar& x);
00400     bool operator()(void) const;
00401     void operator++(void);
00402     int min(void) const;
00403     int max(void) const;
00404   };
00405 
00406 }
00407 
00412 GECODE_CPLTSET_EXPORT std::ostream&
00413 operator<<(std::ostream&, const Gecode::CpltSetVar& x);
00414 
00415 #include "gecode/cpltset/view.icc"
00416 
00417 namespace Gecode {
00427 
00428   typedef VarArgArray<CpltSetVar>  CpltSetVarArgs;
00430 
00446   class CpltSetVarArray : public VarArray<CpltSetVar> {
00447   public:
00448     CpltSetVarArray(void);
00449     CpltSetVarArray(const CpltSetVarArray&);
00451     GECODE_CPLTSET_EXPORT CpltSetVarArray(Space* home, int n);
00458     GECODE_CPLTSET_EXPORT 
00459     CpltSetVarArray(Space* home,
00460                     int n,int glbMin,int glbMax,int lubMin,int lubMax,
00461                     unsigned int minCard = 0,
00462                     unsigned int maxCard = Set::Limits::card);
00469     GECODE_CPLTSET_EXPORT 
00470     CpltSetVarArray(Space* home,
00471                     int n,const IntSet& glb, int lubMin, int lubMax,
00472                     unsigned int minCard = 0,
00473                     unsigned int maxCard = Set::Limits::card);
00480     GECODE_CPLTSET_EXPORT 
00481     CpltSetVarArray(Space* home,
00482                     int n,int glbMin,int glbMax,const IntSet& lub,
00483                     unsigned int minCard = 0,
00484                     unsigned int maxCard = Set::Limits::card);
00491     GECODE_CPLTSET_EXPORT 
00492     CpltSetVarArray(Space* home, int n,
00493                     const IntSet& glb,const IntSet& lub,
00494                     unsigned int minCard = 0,
00495                     unsigned int maxCard = Set::Limits::card);
00496   };
00497 }
00498 
00499 #include "gecode/cpltset/array.icc"
00500 
00501 
00502 namespace Gecode {
00503 
00508   enum CpltSetRelType {
00510     SRT_LE,    
00512     SRT_GR,
00514     SRT_LQ,
00516     SRT_GQ,
00518     SRT_LE_REV,
00520     SRT_GR_REV,
00522     SRT_LQ_REV,
00524     SRT_GQ_REV
00525   };
00526 
00531   enum CpltSetOpType {
00532     SOT_SYMDIFF,  
00533   };
00534 
00541 
00543   GECODE_CPLTSET_EXPORT void
00544   dom(Space* home, CpltSetVar x, SetRelType r, int i);
00545 
00547   GECODE_CPLTSET_EXPORT void
00548   dom(Space* home, CpltSetVar x, SetRelType r, int i, int j);
00549 
00551   GECODE_CPLTSET_EXPORT void
00552   dom(Space* home, CpltSetVar x, SetRelType r, const IntSet& s);
00553 
00555   GECODE_CPLTSET_EXPORT void
00556   cardinality(Space* home, CpltSetVar x, unsigned int l, unsigned int u);
00557 
00559   GECODE_CPLTSET_EXPORT void
00560   cardinality(Space* home, CpltSetVar x, unsigned int c);
00561   
00563 
00571   
00573   GECODE_CPLTSET_EXPORT void
00574   rel(Space* home, CpltSetVar x, CpltSetRelType r, CpltSetVar y);
00575 
00577   GECODE_CPLTSET_EXPORT void
00578   rel(Space* home, CpltSetVar x, SetRelType r, CpltSetVar y);
00579 
00581 
00589 
00591   GECODE_CPLTSET_EXPORT void
00592   rel(Space* home, CpltSetVar x, CpltSetOpType o, CpltSetVar y, 
00593       CpltSetRelType r, CpltSetVar z);
00594 
00596   GECODE_CPLTSET_EXPORT void
00597   rel(Space* home, CpltSetVar x, CpltSetOpType o, CpltSetVar y, 
00598       SetRelType r, CpltSetVar z);
00599 
00601   GECODE_CPLTSET_EXPORT void
00602   rel(Space* home, CpltSetVar x, SetOpType o, CpltSetVar y, 
00603       CpltSetRelType r, CpltSetVar z);
00604 
00606   GECODE_CPLTSET_EXPORT void
00607   rel(Space* home, CpltSetVar x, SetOpType o, CpltSetVar y, 
00608       SetRelType r, CpltSetVar z);
00609 
00611 
00619     
00621   GECODE_CPLTSET_EXPORT void
00622   singleton(Space* home, IntVar x, CpltSetVar s);
00623   
00625 
00633   
00635   GECODE_CPLTSET_EXPORT void
00636   exactly(Space* home, CpltSetVar x, IntSet& is, unsigned int c);
00637 
00639   GECODE_CPLTSET_EXPORT void
00640   atmost(Space* home, CpltSetVar x, IntSet& is, unsigned int c);
00641 
00643   GECODE_CPLTSET_EXPORT void
00644   atmost(Space* home, CpltSetVar x, CpltSetVar y, unsigned int c);
00645 
00647   GECODE_CPLTSET_EXPORT void
00648   atmostLex(Space* home, CpltSetVar x, CpltSetVar y, unsigned int c, 
00649             CpltSetRelType lex);
00650 
00655   GECODE_CPLTSET_EXPORT void
00656   atmostLexCard(Space* home, CpltSetVar x, CpltSetVar y, int c, 
00657                 CpltSetRelType lex, int d);
00658 
00660   GECODE_CPLTSET_EXPORT void
00661   atmostCard(Space* home, CpltSetVar x, CpltSetVar y, int c, int d);
00662 
00664   GECODE_CPLTSET_EXPORT void
00665   atmost(Space* home, CpltSetVar x, CpltSetVar y, CpltSetVar z, int c);
00666 
00672   GECODE_CPLTSET_EXPORT void
00673   atmostOne(Space* home, const CpltSetVarArgs& x, int c);
00674 
00676   GECODE_CPLTSET_EXPORT void
00677   partition(Space* home, const CpltSetVarArgs& x);
00678 
00680   GECODE_CPLTSET_EXPORT void
00681   partition(Space* home, const CpltSetVarArgs& x, const CpltSetVar& y);
00682 
00689   GECODE_CPLTSET_EXPORT void
00690   partitionLex(Space* home, const CpltSetVarArgs& x, CpltSetRelType lex);
00697   GECODE_CPLTSET_EXPORT void
00698   partitionLexCard(Space* home, const CpltSetVarArgs& x, CpltSetRelType lex, 
00699                    unsigned int c);
00700 
00705   GECODE_CPLTSET_EXPORT void
00706   partitionCard(Space* home, const CpltSetVarArgs& x, unsigned int c);
00707 
00709   
00717   
00719   GECODE_CPLTSET_EXPORT void
00720   selectUnion(Space* home, const CpltSetVarArgs& x, CpltSetVar s,
00721               CpltSetVar t);
00722 
00724   GECODE_CPLTSET_EXPORT void
00725   selectNonEmptySub(Space* home, const CpltSetVarArgs& x,
00726                     CpltSetVar s, CpltSetVar t);
00727 
00729   GECODE_CPLTSET_EXPORT void
00730   range(Space* home, const CpltSetVarArgs& x, CpltSetVar s, CpltSetVar t);
00731 
00733   GECODE_CPLTSET_EXPORT void
00734   roots(Space* home, const CpltSetVarArgs& x, CpltSetVar s, CpltSetVar t, 
00735         const CpltSetVarArgs& allvars);
00736 
00740   GECODE_CPLTSET_EXPORT void
00741   alldifferent(Space* home, const CpltSetVarArgs& x, CpltSetVar s,
00742                CpltSetVar t, const CpltSetVarArgs& allvars);
00743 
00748   GECODE_CPLTSET_EXPORT void
00749   nvalue(Space* home, const CpltSetVarArgs& x, CpltSetVar s, CpltSetVar t,
00750          unsigned int n, const CpltSetVarArgs& allvars);
00751 
00757   GECODE_CPLTSET_EXPORT void
00758   uses(Space* home, const IntVarArgs& x, CpltSetVar s, CpltSetVar t,
00759        const CpltSetVarArgs& y, CpltSetVar u, CpltSetVar v);
00761 
00762 
00768   
00770   enum CpltSetVarBranch {
00771     CPLTSET_VAR_NONE,             
00772     CPLTSET_VAR_MIN_CARD,         
00773     CPLTSET_VAR_MAX_CARD,         
00774     CPLTSET_VAR_MIN_UNKNOWN_ELEM, 
00775     CPLTSET_VAR_MAX_UNKNOWN_ELEM  
00776   };
00777   
00779   enum CpltSetValBranch { 
00780     CPLTSET_VAL_MIN_UNKNOWN,          
00781     CPLTSET_VAL_MAX_UNKNOWN,          
00782     CPLTSET_VAL_MIN_UNKNOWN_EX_FIRST, 
00783     CPLTSET_VAL_MAX_UNKNOWN_EX_FIRST  
00784   };
00785 
00787   GECODE_CPLTSET_EXPORT void
00788   branch(Space* home, const CpltSetVarArgs& x, 
00789          CpltSetVarBranch vars, CpltSetValBranch vals);
00791 
00792 }
00793 
00794 #endif
00795 
00796 // IFDEF: GECODE_HAS_CPLTSET_VARS
00797 // STATISTICS: set-post