Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

int.hh (Revision: 2696)

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: 2005-12-06 07:46:40 +0100 (Tue, 06 Dec 2005) $ by $Author: pekczynski $
00015  *     $Revision: 2696 $
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 "./limits.hh"
00046 
00047 #include "./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 #define GECODE_INT_EXPORT
00066 
00067 #endif
00068 
00069 #include <iostream>
00070 
00071 #include "iter.hh"
00072 #include "support/shared-array.hh"
00073 
00074 #include "int/exception.icc"
00075 
00076 namespace Gecode {
00077 
00078   class IntSetRanges;
00079 
00087   class IntSet {
00088     friend class IntSetRanges;
00089   private:
00091     class Range {
00092     public:
00093       int min, max;
00094     };
00096     Support::SharedArray<Range> sar;
00098     class MinInc;
00100     GECODE_INT_EXPORT void normalize(int n);
00101     GECODE_INT_EXPORT void init(int n, int m);
00102     GECODE_INT_EXPORT void init(const int r[], int n);
00103     GECODE_INT_EXPORT void init(const int r[][2], int n);
00104   public:
00106 
00107 
00108     IntSet(void);
00110     IntSet(const IntSet& is);
00115     IntSet(int n, int m);
00117     IntSet(const int r[],   int n);
00123     IntSet(const int r[][2], int n);
00125     template <class I>
00126     IntSet(I& i);
00128 
00130 
00131 
00132     int size(void) const;
00134 
00136 
00137 
00138     int min(int i) const;
00140     int max(int i) const;
00142     unsigned int width(int i) const;
00144     
00146 
00147 
00148     int min(void) const;
00150     int max(void) const;
00152     
00154 
00155 
00160     void update(bool share, IntSet& s);
00162     
00164 
00165 
00166     GECODE_INT_EXPORT static const IntSet empty;
00168   };
00169 
00175   class IntSetRanges {
00176   private:
00178     const IntSet::Range* i; 
00180     const IntSet::Range* e;
00181   public:
00183 
00184 
00185     IntSetRanges(void);
00187     IntSetRanges(const IntSet& s);
00189     void init(const IntSet& s);
00191     
00193 
00194 
00195     bool operator()(void) const;
00197     void operator++(void);
00199     
00201 
00202 
00203     int min(void) const;
00205     int max(void) const;
00207     unsigned int width(void) const;
00209   };
00210   
00216   class IntSetValues
00217     : public Iter::Ranges::ToValues<IntSetRanges> {
00218   public:
00220 
00221 
00222     IntSetValues(void);
00224     IntSetValues(const IntSet& s);
00226     void init(const IntSet& s);
00228   };
00229 
00230 }
00231 
00236 GECODE_INT_EXPORT std::ostream&
00237 operator<<(std::ostream&, const Gecode::IntSet& s);
00238 
00239 #include "int/int-set.icc"
00240 
00241 
00242 #include "int/var.icc"
00243 #include "int/view.icc"
00244 #include "int/propagator.icc"
00245 #include "int/array.icc"
00246 
00247 
00248 namespace Gecode {
00249 
00254   enum IntRelType {
00255     IRT_EQ, 
00256     IRT_NQ, 
00257     IRT_LQ, 
00258     IRT_LE, 
00259     IRT_GQ, 
00260     IRT_GR  
00261   };
00262 
00276   enum IntConLevel {
00277     ICL_VAL, 
00278     ICL_BND, 
00279     ICL_DOM, 
00280     ICL_DEF  
00281   };
00282   
00283 
00284 
00292 
00293   GECODE_INT_EXPORT void
00294   dom(Space* home, IntVar x, int l, int m,
00295       IntConLevel=ICL_DEF);
00297   GECODE_INT_EXPORT void
00298   dom(Space* home, IntVarArgs& x, int l, int m,
00299       IntConLevel=ICL_DEF);
00300 
00302   GECODE_INT_EXPORT void
00303   dom(Space* home, IntVar x, const IntSet& s,
00304       IntConLevel=ICL_DEF);
00306   GECODE_INT_EXPORT void
00307   dom(Space* home, IntVarArgs& x, const IntSet& s,
00308       IntConLevel=ICL_DEF);
00309 
00311   GECODE_INT_EXPORT void
00312   dom(Space* home, IntVar x, int l, int m, BoolVar b,
00313       IntConLevel=ICL_DEF);
00315   GECODE_INT_EXPORT void
00316   dom(Space* home, IntVar x, const IntSet& s, BoolVar b,
00317       IntConLevel=ICL_DEF);
00319   
00320   
00327   
00328 
00334   GECODE_INT_EXPORT void
00335   rel(Space* home, IntVar x0, IntRelType r, IntVar x1,
00336       IntConLevel icl=ICL_DEF);
00338   GECODE_INT_EXPORT void
00339   rel(Space* home, IntVar x, IntRelType r, int c,
00340       IntConLevel icl=ICL_DEF);
00346   GECODE_INT_EXPORT void
00347   rel(Space* home, IntVar x0, IntRelType r, IntVar x1, BoolVar b,
00348       IntConLevel icl=ICL_DEF);
00354   GECODE_INT_EXPORT void
00355   rel(Space* home, IntVar x, IntRelType r, int c, BoolVar b,
00356       IntConLevel icl=ICL_DEF);
00357 
00365   GECODE_INT_EXPORT void
00366   lex(Space* home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
00367       IntConLevel icl=ICL_DEF);
00369 
00376   
00382   GECODE_INT_EXPORT void
00383   eq(Space* home, IntVar x0, IntVar x1, IntConLevel icl=ICL_DEF);
00385   GECODE_INT_EXPORT void
00386   eq(Space* home, IntVar x, int n, IntConLevel=ICL_DEF);
00392   GECODE_INT_EXPORT void
00393   eq(Space* home, IntVar x0, IntVar x1, BoolVar b, IntConLevel icl=ICL_DEF);
00399   GECODE_INT_EXPORT void
00400   eq(Space* home, IntVar x, int n, BoolVar b, IntConLevel icl=ICL_DEF);
00406   GECODE_INT_EXPORT void
00407   eq(Space* home, const IntVarArgs& x, IntConLevel icl=ICL_DEF);  
00409 
00410 
00411 
00423   GECODE_INT_EXPORT void
00424   element(Space* home, const IntArgs& n, IntVar x0, IntVar x1,
00425           IntConLevel=ICL_DEF);
00431   GECODE_INT_EXPORT void
00432   element(Space* home, const IntVarArgs& x, IntVar y0, IntVar y1,
00433           IntConLevel icl=ICL_DEF);
00435 
00436 
00448   GECODE_INT_EXPORT void
00449   distinct(Space* home, const IntVarArgs& x, 
00450            IntConLevel icl=ICL_DEF);
00460   GECODE_INT_EXPORT void
00461   distinct(Space* home, const IntArgs& n, const IntVarArgs& x,
00462            IntConLevel icl=ICL_DEF);
00464 
00465 
00509   GECODE_INT_EXPORT void
00510   cumulatives(Space* home, const IntVarArgs& machine, 
00511               const IntVarArgs& start, const IntVarArgs& duration, 
00512               const IntVarArgs& end, const IntVarArgs& height, 
00513               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00518   GECODE_INT_EXPORT void
00519   cumulatives(Space* home, const IntArgs& machine, 
00520               const IntVarArgs& start, const IntVarArgs& duration, 
00521               const IntVarArgs& end, const IntVarArgs& height, 
00522               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00527   GECODE_INT_EXPORT void
00528   cumulatives(Space* home, const IntVarArgs& machine, 
00529               const IntVarArgs& start, const IntArgs& duration, 
00530               const IntVarArgs& end, const IntVarArgs& height, 
00531               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00536   GECODE_INT_EXPORT void
00537   cumulatives(Space* home, const IntArgs& machine, 
00538               const IntVarArgs& start, const IntArgs& duration, 
00539               const IntVarArgs& end, const IntVarArgs& height, 
00540               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00545    GECODE_INT_EXPORT void
00546   cumulatives(Space* home, const IntVarArgs& machine, 
00547               const IntVarArgs& start, const IntVarArgs& duration, 
00548               const IntVarArgs& end, const IntArgs& height, 
00549               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00554   GECODE_INT_EXPORT void
00555   cumulatives(Space* home, const IntArgs& machine, 
00556               const IntVarArgs& start, const IntVarArgs& duration, 
00557               const IntVarArgs& end, const IntArgs& height, 
00558               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00563   GECODE_INT_EXPORT void
00564   cumulatives(Space* home, const IntVarArgs& machine, 
00565               const IntVarArgs& start, const IntArgs& duration, 
00566               const IntVarArgs& end, const IntArgs& height, 
00567               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00572   GECODE_INT_EXPORT void
00573   cumulatives(Space* home, const IntArgs& machine, 
00574               const IntVarArgs& start, const IntArgs& duration, 
00575               const IntVarArgs& end, const IntArgs& height, 
00576               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00578 
00579 
00585   class DFA;
00586 
00588 
00589   class GECODE_INT_EXPORT REG {
00590     friend class DFA;
00591   private:
00593     class Exp;
00595     Exp* e;
00597     REG(Exp* e);
00598   public:
00600     REG(const REG& r);
00602     const REG& operator=(const REG& r);
00603 
00605     REG(void);
00607     REG(int);
00609     REG operator()(unsigned int n, unsigned int m);
00611     REG operator()(unsigned int n);
00613     REG operator|(const REG& r);
00615     REG operator+(const REG& r);
00617     REG operator*(void);
00621     REG operator+(void);
00623     std::ostream& print(std::ostream&) const;
00625     ~REG(void);
00626   };
00627 
00635   class DFA {
00636   public:
00638     class Transition {
00639     public:
00640       int i_state; 
00641       int symbol;  
00642       int o_state; 
00643     };
00645     class Transitions;
00646   private:
00648     class DFAI;
00650     DFAI* dfai;
00651   protected:
00652     GECODE_INT_EXPORT
00660     void init(int start, Transition t_spec[], int f_spec[], 
00661               bool minimize);
00662   public:
00663     friend class Transitions;
00665     DFA(void);
00676     DFA(int s, Transition t[], int f[], bool minimize=true);
00677     GECODE_INT_EXPORT 
00679     DFA(REG& r);
00681     DFA(const DFA& d);
00683     const DFA& operator=(const DFA&);
00685     ~DFA(void);
00692     void update(bool share, DFA& d);
00694     unsigned int n_states(void) const;
00696     unsigned int n_transitions(void) const;
00698     int final_fst(void) const;
00700     int final_lst(void) const;
00702     int symbol_min(void) const;
00704     int symbol_max(void) const;
00705   };
00706 
00713   GECODE_INT_EXPORT void
00714   regular(Space* home, const IntVarArgs& x, DFA& d, 
00715           IntConLevel=ICL_DEF);
00716 
00718 
00719 }
00720 
00721 #include "int/regular/dfa.icc"
00722 
00723 namespace Gecode {
00724 
00746   GECODE_INT_EXPORT void 
00747   sortedness(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00748              IntConLevel icl=ICL_DEF);
00760   GECODE_INT_EXPORT void 
00761   sortedness(Space*, const IntVarArgs& x, const IntVarArgs& y,
00762              const IntVarArgs& z,  
00763              IntConLevel icl=ICL_DEF);
00765 
00777   GECODE_INT_EXPORT void
00778   count(Space* home, const IntVarArgs& x, int n, IntRelType r, int m,   
00779         IntConLevel icl=ICL_DEF);
00785   GECODE_INT_EXPORT void
00786   count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, int m,   
00787         IntConLevel icl=ICL_DEF);
00793   GECODE_INT_EXPORT void
00794   count(Space* home, const IntVarArgs& x, int n, IntRelType r, IntVar z, 
00795         IntConLevel icl=ICL_DEF);
00801   GECODE_INT_EXPORT void
00802   count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, IntVar z, 
00803         IntConLevel icl=ICL_DEF);
00804 
00829   GECODE_INT_EXPORT void 
00830   gcc(Space* home, const IntVarArgs& x, const IntArgs& c, int m, int unspec,
00831       int min, int max,
00832       IntConLevel icl);
00833 
00865   GECODE_INT_EXPORT void 
00866   gcc(Space* home, const IntVarArgs& x, const IntArgs& c, int m, 
00867       int unspec_low, int unspec_up, int min, int max, 
00868       IntConLevel icl);
00869   
00881   GECODE_INT_EXPORT void 
00882   gcc(Space* home, const IntVarArgs& x, int ub, IntConLevel cl);
00883 
00898   GECODE_INT_EXPORT void 
00899   gcc(Space* home, const IntVarArgs& x, int lb, int ub, IntConLevel cl);
00900 
00912   GECODE_INT_EXPORT void 
00913   gcc(Space* home,  const IntVarArgs& x, const IntVarArgs& c, 
00914       int min, int max, 
00915       IntConLevel cl);
00916   
00929   GECODE_INT_EXPORT void
00930   gcc(Space* home, const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c, 
00931       int m, int unspec, bool all, int min, int max, 
00932       IntConLevel icl);
00933 
00947   GECODE_INT_EXPORT void
00948   gcc(Space* home, const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c, 
00949       int m, int unspec_low, int unspec_up, bool all, int min, int max, 
00950       IntConLevel icl);
00951 
00953 
00960 
00961   GECODE_INT_EXPORT void
00962   bool_not(Space* home, BoolVar b0, BoolVar b1,
00963            IntConLevel=ICL_DEF);
00964 
00966   GECODE_INT_EXPORT void
00967   bool_eq(Space* home, BoolVar b0, BoolVar b1,
00968           IntConLevel=ICL_DEF);
00969 
00971   GECODE_INT_EXPORT void
00972   bool_and(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00973            IntConLevel=ICL_DEF);
00975   GECODE_INT_EXPORT void
00976   bool_and(Space* home, const BoolVarArgs& b, BoolVar c,
00977            IntConLevel=ICL_DEF);
00978 
00980   GECODE_INT_EXPORT void
00981   bool_or(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00982           IntConLevel=ICL_DEF);
00984   GECODE_INT_EXPORT void
00985   bool_or(Space* home, const BoolVarArgs& b, BoolVar c,
00986           IntConLevel=ICL_DEF);
00987 
00989   GECODE_INT_EXPORT void
00990   bool_imp(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00991            IntConLevel=ICL_DEF);
00992 
00994   GECODE_INT_EXPORT void
00995   bool_eqv(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
00996            IntConLevel=ICL_DEF);
00998   GECODE_INT_EXPORT void
00999   bool_xor(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01000            IntConLevel=ICL_DEF);
01001 
01003 
01014   GECODE_INT_EXPORT void
01015   min(Space* home, IntVar x0, IntVar x1, IntVar x2,
01016       IntConLevel=ICL_DEF);
01021   GECODE_INT_EXPORT void
01022   min(Space* home, const IntVarArgs& x, IntVar y,
01023       IntConLevel=ICL_DEF);
01029   GECODE_INT_EXPORT void
01030   max(Space* home, IntVar x0, IntVar x1, IntVar x2,
01031       IntConLevel=ICL_DEF);
01037   GECODE_INT_EXPORT void
01038   max(Space* home, const IntVarArgs& x, IntVar y,
01039       IntConLevel=ICL_DEF);
01040 
01045   GECODE_INT_EXPORT void
01046   abs(Space* home, IntVar x0, IntVar x1,
01047       IntConLevel=ICL_DEF);
01048 
01054   GECODE_INT_EXPORT void
01055   mult(Space* home, IntVar x0, IntVar x1, IntVar x2,
01056        IntConLevel=ICL_DEF);
01058 
01082 
01083   GECODE_INT_EXPORT void
01084   linear(Space* home, const IntVarArgs& x, 
01085          IntRelType r, int c,
01086          IntConLevel=ICL_DEF);
01088   GECODE_INT_EXPORT void
01089   linear(Space* home, const IntVarArgs& x, 
01090          IntRelType r, IntVar y,
01091          IntConLevel=ICL_DEF);
01093   GECODE_INT_EXPORT void
01094   linear(Space* home, const IntVarArgs& x, 
01095          IntRelType r, int c, BoolVar b, IntConLevel=ICL_DEF);
01097   GECODE_INT_EXPORT void
01098   linear(Space* home, const IntVarArgs& x, 
01099          IntRelType r, IntVar y, BoolVar b, IntConLevel=ICL_DEF);
01105   GECODE_INT_EXPORT void
01106   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01107          IntRelType r, int c,
01108          IntConLevel=ICL_DEF);
01114   GECODE_INT_EXPORT void
01115   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01116          IntRelType r, IntVar y,
01117          IntConLevel=ICL_DEF);
01123   GECODE_INT_EXPORT void
01124   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01125          IntRelType r, int c, BoolVar b, 
01126          IntConLevel=ICL_DEF);
01132   GECODE_INT_EXPORT void
01133   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01134          IntRelType r, IntVar y, BoolVar b, 
01135          IntConLevel=ICL_DEF);
01136 
01138   GECODE_INT_EXPORT void
01139   linear(Space* home, const BoolVarArgs& x, 
01140          IntRelType r, int c,
01141          IntConLevel=ICL_DEF);
01142 
01144   GECODE_INT_EXPORT void
01145   linear(Space* home, const BoolVarArgs& x, 
01146          IntRelType r, IntVar y,
01147          IntConLevel=ICL_DEF);
01148 
01150 
01151 
01158 
01159   enum BvarSel {
01160     BVAR_NONE,          
01161     BVAR_MIN_MIN,       
01162     BVAR_MIN_MAX,       
01163     BVAR_MAX_MIN,       
01164     BVAR_MAX_MAX,       
01165     BVAR_SIZE_MIN,      
01166     BVAR_SIZE_MAX,      
01167 
01173     BVAR_DEGREE_MIN,
01180     BVAR_DEGREE_MAX,
01186     BVAR_REGRET_MIN_MIN,
01192     BVAR_REGRET_MIN_MAX,
01198     BVAR_REGRET_MAX_MIN,
01204     BVAR_REGRET_MAX_MAX
01205   };
01206 
01208   enum BvalSel {
01209     BVAL_MIN,      
01210     BVAL_MED,      
01211     BVAL_MAX,      
01212     BVAL_SPLIT_MIN, 
01213     BVAL_SPLIT_MAX  
01214   };
01215 
01217   GECODE_INT_EXPORT void
01218   branch(Space* home, const IntVarArgs& x, BvarSel vars, BvalSel vals);
01220 
01226 
01227   enum AvalSel {
01228     AVAL_MIN, 
01229     AVAL_MED, 
01230     AVAL_MAX  
01231   };
01232 
01234   GECODE_INT_EXPORT void
01235   assign(Space* home, const IntVarArgs& x, AvalSel vals);
01236 
01238 
01239 }
01240 
01244 GECODE_INT_EXPORT std::ostream&
01245 operator<<(std::ostream&, const Gecode::REG& r);
01246 
01250 GECODE_INT_EXPORT std::ostream&
01251 operator<<(std::ostream&, const Gecode::DFA& d);
01252 
01253 #endif
01254 
01255 // STATISTICS: int-post
01256