int.hh

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Contributing authors:
00007  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00008  *
00009  *  Copyright:
00010  *     Christian Schulte, 2002
00011  *     Guido Tack, 2004
00012  *
00013  *  Last modified:
00014  *     $Date: 2006-08-31 17:36:38 +0200 (Thu, 31 Aug 2006) $ by $Author: schulte $
00015  *     $Revision: 3579 $
00016  *
00017  *  This file is part of Gecode, the generic constraint
00018  *  development environment:
00019  *     http://www.gecode.org
00020  *
00021  *  See the file "LICENSE" for information on usage and
00022  *  redistribution of this file, and for a
00023  *     DISCLAIMER OF ALL WARRANTIES.
00024  *
00025  */
00026 
00027 #ifndef __GECODE_INT_HH__
00028 #define __GECODE_INT_HH__
00029 
00030 namespace Gecode { namespace Int {
00031 
00043 }}
00044 
00045 #include "gecode/limits.hh"
00046 
00047 #include "gecode/kernel.hh"
00048 
00049 /*
00050  * Support for DLLs under Windows
00051  *
00052  */
00053 
00054 #if !defined(GECODE_STATIC_LIBS) && \
00055     (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00056 
00057 #ifdef GECODE_BUILD_INT
00058 #define GECODE_INT_EXPORT __declspec( dllexport )
00059 #else
00060 #define GECODE_INT_EXPORT __declspec( dllimport )
00061 #endif
00062 
00063 #else
00064 
00065 #ifdef GCC_HASCLASSVISIBILITY
00066 
00067 #define GECODE_INT_EXPORT __attribute__ ((visibility("default")))
00068 
00069 #else
00070 
00071 #define GECODE_INT_EXPORT
00072 
00073 #endif
00074 #endif
00075 
00076 #include <iostream>
00077 
00078 #include "gecode/iter.hh"
00079 #include "gecode/support/shared-array.hh"
00080 
00081 #include "gecode/int/exception.icc"
00082 
00083 namespace Gecode {
00084 
00085   class IntSetRanges;
00086 
00094   class IntSet {
00095     friend class IntSetRanges;
00096   private:
00098     class Range {
00099     public:
00100       int min, max;
00101     };
00103     Support::SharedArray<Range> sar;
00105     class MinInc;
00107     GECODE_INT_EXPORT void normalize(int n);
00108     GECODE_INT_EXPORT void init(int n, int m);
00109     GECODE_INT_EXPORT void init(const int r[], int n);
00110     GECODE_INT_EXPORT void init(const int r[][2], int n);
00111   public:
00113 
00114 
00115     IntSet(void);
00117     IntSet(const IntSet& is);
00122     IntSet(int n, int m);
00124     IntSet(const int r[],   int n);
00130     IntSet(const int r[][2], int n);
00132     template <class I>
00133     IntSet(I& i);
00135 
00137 
00138 
00139     int size(void) const;
00141 
00143 
00144 
00145     int min(int i) const;
00147     int max(int i) const;
00149     unsigned int width(int i) const;
00151 
00153 
00154 
00155     int min(void) const;
00157     int max(void) const;
00159 
00161 
00162 
00167     void update(bool share, IntSet& s);
00169 
00171 
00172 
00173     GECODE_INT_EXPORT static const IntSet empty;
00175   };
00176 
00182   class IntSetRanges {
00183   private:
00185     const IntSet::Range* i;
00187     const IntSet::Range* e;
00188   public:
00190 
00191 
00192     IntSetRanges(void);
00194     IntSetRanges(const IntSet& s);
00196     void init(const IntSet& s);
00198 
00200 
00201 
00202     bool operator()(void) const;
00204     void operator++(void);
00206 
00208 
00209 
00210     int min(void) const;
00212     int max(void) const;
00214     unsigned int width(void) const;
00216   };
00217 
00223   class IntSetValues
00224     : public Iter::Ranges::ToValues<IntSetRanges> {
00225   public:
00227 
00228 
00229     IntSetValues(void);
00231     IntSetValues(const IntSet& s);
00233     void init(const IntSet& s);
00235   };
00236 
00237 }
00238 
00243 GECODE_INT_EXPORT std::ostream&
00244 operator<<(std::ostream&, const Gecode::IntSet& s);
00245 
00246 #include "gecode/int/int-set.icc"
00247 
00248 
00249 #include "gecode/int/var.icc"
00250 #include "gecode/int/view.icc"
00251 #include "gecode/int/propagator.icc"
00252 #include "gecode/int/array.icc"
00253 
00254 
00255 namespace Gecode {
00256 
00261   enum IntRelType {
00262     IRT_EQ, 
00263     IRT_NQ, 
00264     IRT_LQ, 
00265     IRT_LE, 
00266     IRT_GQ, 
00267     IRT_GR  
00268   };
00269 
00283   enum IntConLevel {
00284     ICL_VAL, 
00285     ICL_BND, 
00286     ICL_DOM, 
00287     ICL_DEF  
00288   };
00289 
00290 
00291 
00299 
00300   GECODE_INT_EXPORT void
00301   dom(Space* home, IntVar x, int l, int m,
00302       IntConLevel=ICL_DEF);
00304   GECODE_INT_EXPORT void
00305   dom(Space* home, IntVarArgs& x, int l, int m,
00306       IntConLevel=ICL_DEF);
00307 
00309   GECODE_INT_EXPORT void
00310   dom(Space* home, IntVar x, const IntSet& s,
00311       IntConLevel=ICL_DEF);
00313   GECODE_INT_EXPORT void
00314   dom(Space* home, IntVarArgs& x, const IntSet& s,
00315       IntConLevel=ICL_DEF);
00316 
00318   GECODE_INT_EXPORT void
00319   dom(Space* home, IntVar x, int l, int m, BoolVar b,
00320       IntConLevel=ICL_DEF);
00322   GECODE_INT_EXPORT void
00323   dom(Space* home, IntVar x, const IntSet& s, BoolVar b,
00324       IntConLevel=ICL_DEF);
00326 
00327 
00334 
00335 
00341   GECODE_INT_EXPORT void
00342   rel(Space* home, IntVar x0, IntRelType r, IntVar x1,
00343       IntConLevel icl=ICL_DEF);
00345   GECODE_INT_EXPORT void
00346   rel(Space* home, IntVar x, IntRelType r, int c,
00347       IntConLevel icl=ICL_DEF);
00353   GECODE_INT_EXPORT void
00354   rel(Space* home, IntVar x0, IntRelType r, IntVar x1, BoolVar b,
00355       IntConLevel icl=ICL_DEF);
00361   GECODE_INT_EXPORT void
00362   rel(Space* home, IntVar x, IntRelType r, int c, BoolVar b,
00363       IntConLevel icl=ICL_DEF);
00364 
00376   GECODE_INT_EXPORT void
00377   rel(Space* home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
00378       IntConLevel icl=ICL_DEF);
00380 
00387 
00393   GECODE_INT_EXPORT void
00394   eq(Space* home, IntVar x0, IntVar x1, IntConLevel icl=ICL_DEF);
00396   GECODE_INT_EXPORT void
00397   eq(Space* home, IntVar x, int n, IntConLevel=ICL_DEF);
00403   GECODE_INT_EXPORT void
00404   eq(Space* home, IntVar x0, IntVar x1, BoolVar b, IntConLevel icl=ICL_DEF);
00410   GECODE_INT_EXPORT void
00411   eq(Space* home, IntVar x, int n, BoolVar b, IntConLevel icl=ICL_DEF);
00417   GECODE_INT_EXPORT void
00418   eq(Space* home, const IntVarArgs& x, IntConLevel icl=ICL_DEF);
00420 
00421 
00422 
00434   GECODE_INT_EXPORT void
00435   element(Space* home, const IntArgs& n, IntVar x0, IntVar x1,
00436           IntConLevel=ICL_DEF);
00442   GECODE_INT_EXPORT void
00443   element(Space* home, const IntVarArgs& x, IntVar y0, IntVar y1,
00444           IntConLevel icl=ICL_DEF);
00446 
00447 
00462   GECODE_INT_EXPORT void
00463   distinct(Space* home, const IntVarArgs& x,
00464            IntConLevel icl=ICL_DEF);
00476   GECODE_INT_EXPORT void
00477   distinct(Space* home, const IntArgs& n, const IntVarArgs& x,
00478            IntConLevel icl=ICL_DEF);
00480 
00481 
00497   GECODE_INT_EXPORT void
00498   channel(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00499            IntConLevel icl=ICL_DEF);
00501 
00502 
00546   GECODE_INT_EXPORT void
00547   cumulatives(Space* home, const IntVarArgs& machine,
00548               const IntVarArgs& start, const IntVarArgs& duration,
00549               const IntVarArgs& end, const IntVarArgs& height,
00550               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00555   GECODE_INT_EXPORT void
00556   cumulatives(Space* home, const IntArgs& machine,
00557               const IntVarArgs& start, const IntVarArgs& duration,
00558               const IntVarArgs& end, const IntVarArgs& height,
00559               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00564   GECODE_INT_EXPORT void
00565   cumulatives(Space* home, const IntVarArgs& machine,
00566               const IntVarArgs& start, const IntArgs& duration,
00567               const IntVarArgs& end, const IntVarArgs& height,
00568               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00573   GECODE_INT_EXPORT void
00574   cumulatives(Space* home, const IntArgs& machine,
00575               const IntVarArgs& start, const IntArgs& duration,
00576               const IntVarArgs& end, const IntVarArgs& height,
00577               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00582    GECODE_INT_EXPORT void
00583   cumulatives(Space* home, const IntVarArgs& machine,
00584               const IntVarArgs& start, const IntVarArgs& duration,
00585               const IntVarArgs& end, const IntArgs& height,
00586               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00591   GECODE_INT_EXPORT void
00592   cumulatives(Space* home, const IntArgs& machine,
00593               const IntVarArgs& start, const IntVarArgs& duration,
00594               const IntVarArgs& end, const IntArgs& height,
00595               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00600   GECODE_INT_EXPORT void
00601   cumulatives(Space* home, const IntVarArgs& machine,
00602               const IntVarArgs& start, const IntArgs& duration,
00603               const IntVarArgs& end, const IntArgs& height,
00604               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00609   GECODE_INT_EXPORT void
00610   cumulatives(Space* home, const IntArgs& machine,
00611               const IntVarArgs& start, const IntArgs& duration,
00612               const IntVarArgs& end, const IntArgs& height,
00613               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00615 
00616 
00622   class DFA;
00623 
00625 
00626   class GECODE_INT_EXPORT REG {
00627     friend class DFA;
00628   private:
00630     class Exp;
00632     Exp* e;
00634     REG(Exp* e);
00635   public:
00637     REG(const REG& r);
00639     const REG& operator=(const REG& r);
00640 
00642     REG(void);
00644     REG(int);
00646     REG operator()(unsigned int n, unsigned int m);
00648     REG operator()(unsigned int n);
00650     REG operator|(const REG& r);
00652     REG operator+(const REG& r);
00654     REG operator*(void);
00658     REG operator+(void);
00660     std::ostream& print(std::ostream&) const;
00662     ~REG(void);
00663   };
00664 
00672   class DFA {
00673   public:
00675     class Transition {
00676     public:
00677       int i_state; 
00678       int symbol;  
00679       int o_state; 
00680     };
00682     class Transitions;
00683   private:
00685     class DFAI;
00687     DFAI* dfai;
00688   protected:
00689     GECODE_INT_EXPORT
00697     void init(int start, Transition t_spec[], int f_spec[],
00698               bool minimize);
00699   public:
00700     friend class Transitions;
00702     DFA(void);
00713     DFA(int s, Transition t[], int f[], bool minimize=true);
00714     GECODE_INT_EXPORT
00716     DFA(REG& r);
00718     DFA(const DFA& d);
00720     const DFA& operator=(const DFA&);
00722     ~DFA(void);
00729     void update(bool share, DFA& d);
00731     unsigned int n_states(void) const;
00733     unsigned int n_transitions(void) const;
00735     int final_fst(void) const;
00737     int final_lst(void) const;
00739     int symbol_min(void) const;
00741     int symbol_max(void) const;
00742   };
00743 
00750   GECODE_INT_EXPORT void
00751   regular(Space* home, const IntVarArgs& x, DFA& d,
00752           IntConLevel=ICL_DEF);
00753 
00755 
00756 }
00757 
00758 #include "gecode/int/regular/dfa.icc"
00759 
00760 namespace Gecode {
00761 
00788   GECODE_INT_EXPORT void
00789   sortedness(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00790              IntConLevel icl=ICL_DEF);
00791 
00808   GECODE_INT_EXPORT void
00809   sortedness(Space*, const IntVarArgs& x, const IntVarArgs& y,
00810              const IntVarArgs& z,
00811              IntConLevel icl=ICL_DEF);
00813 
00832   GECODE_INT_EXPORT void
00833   count(Space* home, const IntVarArgs& x, int n, IntRelType r, int m,
00834         IntConLevel icl=ICL_DEF);
00839   GECODE_INT_EXPORT void
00840   count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, int m,
00841         IntConLevel icl=ICL_DEF);
00846   GECODE_INT_EXPORT void
00847   count(Space* home, const IntVarArgs& x, int n, IntRelType r, IntVar z,
00848         IntConLevel icl=ICL_DEF);
00853   GECODE_INT_EXPORT void
00854   count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, IntVar z,
00855         IntConLevel icl=ICL_DEF);
00856 
00857 
00899   GECODE_INT_EXPORT void
00900   gcc(Space* home, const IntVarArgs& x, const IntArgs& c,
00901       int m, int unspec_low, int unspec_up, int min, int max,
00902       IntConLevel icl);
00903 
00938   GECODE_INT_EXPORT void
00939   gcc(Space* home, const IntVarArgs& x, const IntArgs& c,
00940       int m, int unspec, int min, int max,
00941       IntConLevel icl);
00942 
00964   GECODE_INT_EXPORT void
00965   gcc(Space* home, const IntVarArgs& x, int lb, int ub, IntConLevel icl);
00966 
00987   GECODE_INT_EXPORT void
00988   gcc(Space* home, const IntVarArgs& x, int ub, IntConLevel icl);
00989 
00990 
01013   GECODE_INT_EXPORT void
01014   gcc(Space* home,  const IntVarArgs& x, const IntVarArgs& c,
01015       int min, int max,
01016       IntConLevel icl);
01017 
01049   GECODE_INT_EXPORT void
01050   gcc(Space* home,
01051       const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c,
01052       int m, int unspec_low, int unspec_up, bool all, int min, int max,
01053       IntConLevel icl);
01054 
01083   GECODE_INT_EXPORT void
01084   gcc(Space* home,
01085       const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c,
01086       int m, int unspec, bool all, int min, int max,
01087       IntConLevel icl);
01089 
01096 
01097   GECODE_INT_EXPORT void
01098   bool_not(Space* home, BoolVar b0, BoolVar b1,
01099            IntConLevel=ICL_DEF);
01100 
01102   GECODE_INT_EXPORT void
01103   bool_eq(Space* home, BoolVar b0, BoolVar b1,
01104           IntConLevel=ICL_DEF);
01105 
01107   GECODE_INT_EXPORT void
01108   bool_and(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01109            IntConLevel=ICL_DEF);
01111   GECODE_INT_EXPORT void
01112   bool_and(Space* home, BoolVar b0, BoolVar b1, bool b2,
01113            IntConLevel=ICL_DEF);
01115   GECODE_INT_EXPORT void
01116   bool_and(Space* home, const BoolVarArgs& b, BoolVar c,
01117            IntConLevel=ICL_DEF);
01119   GECODE_INT_EXPORT void
01120   bool_and(Space* home, const BoolVarArgs& b, bool c,
01121            IntConLevel=ICL_DEF);
01122 
01124   GECODE_INT_EXPORT void
01125   bool_or(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01126           IntConLevel=ICL_DEF);
01128   GECODE_INT_EXPORT void
01129   bool_or(Space* home, BoolVar b0, BoolVar b1, bool b2,
01130           IntConLevel=ICL_DEF);
01132   GECODE_INT_EXPORT void
01133   bool_or(Space* home, const BoolVarArgs& b, BoolVar c,
01134           IntConLevel=ICL_DEF);
01136   GECODE_INT_EXPORT void
01137   bool_or(Space* home, const BoolVarArgs& b, bool c,
01138           IntConLevel=ICL_DEF);
01139 
01141   GECODE_INT_EXPORT void
01142   bool_imp(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01143            IntConLevel=ICL_DEF);
01145   GECODE_INT_EXPORT void
01146   bool_imp(Space* home, BoolVar b0, BoolVar b1, bool b2,
01147            IntConLevel=ICL_DEF);
01148 
01150   GECODE_INT_EXPORT void
01151   bool_eqv(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01152            IntConLevel=ICL_DEF);
01154   GECODE_INT_EXPORT void
01155   bool_eqv(Space* home, BoolVar b0, BoolVar b1, bool b2,
01156            IntConLevel=ICL_DEF);
01158   GECODE_INT_EXPORT void
01159   bool_xor(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01160            IntConLevel=ICL_DEF);
01162   GECODE_INT_EXPORT void
01163   bool_xor(Space* home, BoolVar b0, BoolVar b1, bool b2,
01164            IntConLevel=ICL_DEF);
01165 
01167 
01178   GECODE_INT_EXPORT void
01179   min(Space* home, IntVar x0, IntVar x1, IntVar x2,
01180       IntConLevel=ICL_DEF);
01185   GECODE_INT_EXPORT void
01186   min(Space* home, const IntVarArgs& x, IntVar y,
01187       IntConLevel=ICL_DEF);
01193   GECODE_INT_EXPORT void
01194   max(Space* home, IntVar x0, IntVar x1, IntVar x2,
01195       IntConLevel=ICL_DEF);
01201   GECODE_INT_EXPORT void
01202   max(Space* home, const IntVarArgs& x, IntVar y,
01203       IntConLevel=ICL_DEF);
01204 
01209   GECODE_INT_EXPORT void
01210   abs(Space* home, IntVar x0, IntVar x1,
01211       IntConLevel=ICL_DEF);
01212 
01218   GECODE_INT_EXPORT void
01219   mult(Space* home, IntVar x0, IntVar x1, IntVar x2,
01220        IntConLevel=ICL_DEF);
01222 
01252 
01253   GECODE_INT_EXPORT void
01254   linear(Space* home, const IntVarArgs& x,
01255          IntRelType r, int c,
01256          IntConLevel=ICL_DEF);
01258   GECODE_INT_EXPORT void
01259   linear(Space* home, const IntVarArgs& x,
01260          IntRelType r, IntVar y,
01261          IntConLevel=ICL_DEF);
01263   GECODE_INT_EXPORT void
01264   linear(Space* home, const IntVarArgs& x,
01265          IntRelType r, int c, BoolVar b, IntConLevel=ICL_DEF);
01267   GECODE_INT_EXPORT void
01268   linear(Space* home, const IntVarArgs& x,
01269          IntRelType r, IntVar y, BoolVar b, IntConLevel=ICL_DEF);
01275   GECODE_INT_EXPORT void
01276   linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01277          IntRelType r, int c,
01278          IntConLevel=ICL_DEF);
01284   GECODE_INT_EXPORT void
01285   linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01286          IntRelType r, IntVar y,
01287          IntConLevel=ICL_DEF);
01293   GECODE_INT_EXPORT void
01294   linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01295          IntRelType r, int c, BoolVar b,
01296          IntConLevel=ICL_DEF);
01302   GECODE_INT_EXPORT void
01303   linear(Space* home, const IntArgs& a, const IntVarArgs& x,
01304          IntRelType r, IntVar y, BoolVar b,
01305          IntConLevel=ICL_DEF);
01306 
01308   GECODE_INT_EXPORT void
01309   linear(Space* home, const BoolVarArgs& x,
01310          IntRelType r, int c,
01311          IntConLevel=ICL_DEF);
01312 
01314   GECODE_INT_EXPORT void
01315   linear(Space* home, const BoolVarArgs& x,
01316          IntRelType r, IntVar y,
01317          IntConLevel=ICL_DEF);
01318 
01320 
01321 
01328 
01329   enum BvarSel {
01330     BVAR_NONE,          
01331     BVAR_MIN_MIN,       
01332     BVAR_MIN_MAX,       
01333     BVAR_MAX_MIN,       
01334     BVAR_MAX_MAX,       
01335     BVAR_SIZE_MIN,      
01336     BVAR_SIZE_MAX,      
01337 
01343     BVAR_DEGREE_MIN,
01350     BVAR_DEGREE_MAX,
01356     BVAR_REGRET_MIN_MIN,
01362     BVAR_REGRET_MIN_MAX,
01368     BVAR_REGRET_MAX_MIN,
01374     BVAR_REGRET_MAX_MAX
01375   };
01376 
01378   enum BvalSel {
01379     BVAL_MIN,      
01380     BVAL_MED,      
01381     BVAL_MAX,      
01382     BVAL_SPLIT_MIN, 
01383     BVAL_SPLIT_MAX  
01384   };
01385 
01387   GECODE_INT_EXPORT void
01388   branch(Space* home, const IntVarArgs& x, BvarSel vars, BvalSel vals);
01390 
01396 
01397   enum AvalSel {
01398     AVAL_MIN, 
01399     AVAL_MED, 
01400     AVAL_MAX  
01401   };
01402 
01404   GECODE_INT_EXPORT void
01405   assign(Space* home, const IntVarArgs& x, AvalSel vals);
01406 
01408 
01409 }
01410 
01414 GECODE_INT_EXPORT std::ostream&
01415 operator<<(std::ostream&, const Gecode::REG& r);
01416 
01420 GECODE_INT_EXPORT std::ostream&
01421 operator<<(std::ostream&, const Gecode::DFA& d);
01422 
01423 #endif
01424 
01425 // STATISTICS: int-post
01426