Generated on Thu Jul 6 07:06:40 2006 for Gecode by doxygen 1.4.7

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-06-20 02:34:31 +0200 (Tue, 20 Jun 2006) $ by $Author: schulte $
00015  *     $Revision: 3308 $
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 #define GECODE_INT_EXPORT
00066 
00067 #endif
00068 
00069 #include <iostream>
00070 
00071 #include "gecode/iter.hh"
00072 #include "gecode/support/shared-array.hh"
00073 
00074 #include "gecode/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 "gecode/int/int-set.icc"
00240 
00241 
00242 #include "gecode/int/var.icc"
00243 #include "gecode/int/view.icc"
00244 #include "gecode/int/propagator.icc"
00245 #include "gecode/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 
00451   GECODE_INT_EXPORT void
00452   distinct(Space* home, const IntVarArgs& x, 
00453            IntConLevel icl=ICL_DEF);
00465   GECODE_INT_EXPORT void
00466   distinct(Space* home, const IntArgs& n, const IntVarArgs& x,
00467            IntConLevel icl=ICL_DEF);
00469 
00470 
00486   GECODE_INT_EXPORT void
00487   channel(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00488            IntConLevel icl=ICL_DEF);
00490 
00491 
00535   GECODE_INT_EXPORT void
00536   cumulatives(Space* home, const IntVarArgs& machine, 
00537               const IntVarArgs& start, const IntVarArgs& duration, 
00538               const IntVarArgs& end, const IntVarArgs& height, 
00539               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00544   GECODE_INT_EXPORT void
00545   cumulatives(Space* home, const IntArgs& machine, 
00546               const IntVarArgs& start, const IntVarArgs& duration, 
00547               const IntVarArgs& end, const IntVarArgs& height, 
00548               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00553   GECODE_INT_EXPORT void
00554   cumulatives(Space* home, const IntVarArgs& machine, 
00555               const IntVarArgs& start, const IntArgs& duration, 
00556               const IntVarArgs& end, const IntVarArgs& height, 
00557               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00562   GECODE_INT_EXPORT void
00563   cumulatives(Space* home, const IntArgs& machine, 
00564               const IntVarArgs& start, const IntArgs& duration, 
00565               const IntVarArgs& end, const IntVarArgs& height, 
00566               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00571    GECODE_INT_EXPORT void
00572   cumulatives(Space* home, const IntVarArgs& machine, 
00573               const IntVarArgs& start, const IntVarArgs& duration, 
00574               const IntVarArgs& end, const IntArgs& height, 
00575               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00580   GECODE_INT_EXPORT void
00581   cumulatives(Space* home, const IntArgs& machine, 
00582               const IntVarArgs& start, const IntVarArgs& duration, 
00583               const IntVarArgs& end, const IntArgs& height, 
00584               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00589   GECODE_INT_EXPORT void
00590   cumulatives(Space* home, const IntVarArgs& machine, 
00591               const IntVarArgs& start, const IntArgs& duration, 
00592               const IntVarArgs& end, const IntArgs& height, 
00593               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00598   GECODE_INT_EXPORT void
00599   cumulatives(Space* home, const IntArgs& machine, 
00600               const IntVarArgs& start, const IntArgs& duration, 
00601               const IntVarArgs& end, const IntArgs& height, 
00602               const IntArgs& limit, bool at_most, IntConLevel icl=ICL_DEF);
00604 
00605 
00611   class DFA;
00612 
00614 
00615   class GECODE_INT_EXPORT REG {
00616     friend class DFA;
00617   private:
00619     class Exp;
00621     Exp* e;
00623     REG(Exp* e);
00624   public:
00626     REG(const REG& r);
00628     const REG& operator=(const REG& r);
00629 
00631     REG(void);
00633     REG(int);
00635     REG operator()(unsigned int n, unsigned int m);
00637     REG operator()(unsigned int n);
00639     REG operator|(const REG& r);
00641     REG operator+(const REG& r);
00643     REG operator*(void);
00647     REG operator+(void);
00649     std::ostream& print(std::ostream&) const;
00651     ~REG(void);
00652   };
00653 
00661   class DFA {
00662   public:
00664     class Transition {
00665     public:
00666       int i_state; 
00667       int symbol;  
00668       int o_state; 
00669     };
00671     class Transitions;
00672   private:
00674     class DFAI;
00676     DFAI* dfai;
00677   protected:
00678     GECODE_INT_EXPORT
00686     void init(int start, Transition t_spec[], int f_spec[], 
00687               bool minimize);
00688   public:
00689     friend class Transitions;
00691     DFA(void);
00702     DFA(int s, Transition t[], int f[], bool minimize=true);
00703     GECODE_INT_EXPORT 
00705     DFA(REG& r);
00707     DFA(const DFA& d);
00709     const DFA& operator=(const DFA&);
00711     ~DFA(void);
00718     void update(bool share, DFA& d);
00720     unsigned int n_states(void) const;
00722     unsigned int n_transitions(void) const;
00724     int final_fst(void) const;
00726     int final_lst(void) const;
00728     int symbol_min(void) const;
00730     int symbol_max(void) const;
00731   };
00732 
00739   GECODE_INT_EXPORT void
00740   regular(Space* home, const IntVarArgs& x, DFA& d, 
00741           IntConLevel=ICL_DEF);
00742 
00744 
00745 }
00746 
00747 #include "gecode/int/regular/dfa.icc"
00748 
00749 namespace Gecode {
00750 
00777   GECODE_INT_EXPORT void 
00778   sortedness(Space* home, const IntVarArgs& x, const IntVarArgs& y,
00779              IntConLevel icl=ICL_DEF);
00780 
00797   GECODE_INT_EXPORT void 
00798   sortedness(Space*, const IntVarArgs& x, const IntVarArgs& y,
00799              const IntVarArgs& z,  
00800              IntConLevel icl=ICL_DEF);
00802 
00822   GECODE_INT_EXPORT void
00823   count(Space* home, const IntVarArgs& x, int n, IntRelType r, int m,   
00824         IntConLevel icl=ICL_DEF);
00830   GECODE_INT_EXPORT void
00831   count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, int m,   
00832         IntConLevel icl=ICL_DEF);
00838   GECODE_INT_EXPORT void
00839   count(Space* home, const IntVarArgs& x, int n, IntRelType r, IntVar z, 
00840         IntConLevel icl=ICL_DEF);
00846   GECODE_INT_EXPORT void
00847   count(Space* home, const IntVarArgs& x, IntVar y, IntRelType r, IntVar z, 
00848         IntConLevel icl=ICL_DEF);
00849 
00850 
00892   GECODE_INT_EXPORT void 
00893   gcc(Space* home, const IntVarArgs& x, const IntArgs& c, 
00894       int m, int unspec_low, int unspec_up, int min, int max, 
00895       IntConLevel icl);
00896   
00931   GECODE_INT_EXPORT void 
00932   gcc(Space* home, const IntVarArgs& x, const IntArgs& c, 
00933       int m, int unspec, int min, int max,
00934       IntConLevel icl);
00935 
00957   GECODE_INT_EXPORT void 
00958   gcc(Space* home, const IntVarArgs& x, int lb, int ub, IntConLevel icl);
00959 
00980   GECODE_INT_EXPORT void 
00981   gcc(Space* home, const IntVarArgs& x, int ub, IntConLevel icl);
00982 
00983 
01006   GECODE_INT_EXPORT void 
01007   gcc(Space* home,  const IntVarArgs& x, const IntVarArgs& c, 
01008       int min, int max, 
01009       IntConLevel icl);
01010   
01042   GECODE_INT_EXPORT void
01043   gcc(Space* home, 
01044       const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c, 
01045       int m, int unspec_low, int unspec_up, bool all, int min, int max, 
01046       IntConLevel icl);
01047 
01076   GECODE_INT_EXPORT void
01077   gcc(Space* home, 
01078       const IntVarArgs& x, const IntArgs& v, const IntVarArgs& c, 
01079       int m, int unspec, bool all, int min, int max, 
01080       IntConLevel icl);
01082 
01089 
01090   GECODE_INT_EXPORT void
01091   bool_not(Space* home, BoolVar b0, BoolVar b1,
01092            IntConLevel=ICL_DEF);
01093 
01095   GECODE_INT_EXPORT void
01096   bool_eq(Space* home, BoolVar b0, BoolVar b1,
01097           IntConLevel=ICL_DEF);
01098 
01100   GECODE_INT_EXPORT void
01101   bool_and(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01102            IntConLevel=ICL_DEF);
01104   GECODE_INT_EXPORT void
01105   bool_and(Space* home, BoolVar b0, BoolVar b1, bool b2,
01106            IntConLevel=ICL_DEF);
01108   GECODE_INT_EXPORT void
01109   bool_and(Space* home, const BoolVarArgs& b, BoolVar c,
01110            IntConLevel=ICL_DEF);
01112   GECODE_INT_EXPORT void
01113   bool_and(Space* home, const BoolVarArgs& b, bool c,
01114            IntConLevel=ICL_DEF);
01115 
01117   GECODE_INT_EXPORT void
01118   bool_or(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01119           IntConLevel=ICL_DEF);
01121   GECODE_INT_EXPORT void
01122   bool_or(Space* home, BoolVar b0, BoolVar b1, bool b2,
01123           IntConLevel=ICL_DEF);
01125   GECODE_INT_EXPORT void
01126   bool_or(Space* home, const BoolVarArgs& b, BoolVar c,
01127           IntConLevel=ICL_DEF);
01129   GECODE_INT_EXPORT void
01130   bool_or(Space* home, const BoolVarArgs& b, bool c,
01131           IntConLevel=ICL_DEF);
01132 
01134   GECODE_INT_EXPORT void
01135   bool_imp(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01136            IntConLevel=ICL_DEF);
01138   GECODE_INT_EXPORT void
01139   bool_imp(Space* home, BoolVar b0, BoolVar b1, bool b2,
01140            IntConLevel=ICL_DEF);
01141 
01143   GECODE_INT_EXPORT void
01144   bool_eqv(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01145            IntConLevel=ICL_DEF);
01147   GECODE_INT_EXPORT void
01148   bool_eqv(Space* home, BoolVar b0, BoolVar b1, bool b2,
01149            IntConLevel=ICL_DEF);
01151   GECODE_INT_EXPORT void
01152   bool_xor(Space* home, BoolVar b0, BoolVar b1, BoolVar b2,
01153            IntConLevel=ICL_DEF);
01155   GECODE_INT_EXPORT void
01156   bool_xor(Space* home, BoolVar b0, BoolVar b1, bool b2,
01157            IntConLevel=ICL_DEF);
01158 
01160 
01171   GECODE_INT_EXPORT void
01172   min(Space* home, IntVar x0, IntVar x1, IntVar x2,
01173       IntConLevel=ICL_DEF);
01178   GECODE_INT_EXPORT void
01179   min(Space* home, const IntVarArgs& x, IntVar y,
01180       IntConLevel=ICL_DEF);
01186   GECODE_INT_EXPORT void
01187   max(Space* home, IntVar x0, IntVar x1, IntVar x2,
01188       IntConLevel=ICL_DEF);
01194   GECODE_INT_EXPORT void
01195   max(Space* home, const IntVarArgs& x, IntVar y,
01196       IntConLevel=ICL_DEF);
01197 
01202   GECODE_INT_EXPORT void
01203   abs(Space* home, IntVar x0, IntVar x1,
01204       IntConLevel=ICL_DEF);
01205 
01211   GECODE_INT_EXPORT void
01212   mult(Space* home, IntVar x0, IntVar x1, IntVar x2,
01213        IntConLevel=ICL_DEF);
01215 
01245 
01246   GECODE_INT_EXPORT void
01247   linear(Space* home, const IntVarArgs& x, 
01248          IntRelType r, int c,
01249          IntConLevel=ICL_DEF);
01251   GECODE_INT_EXPORT void
01252   linear(Space* home, const IntVarArgs& x, 
01253          IntRelType r, IntVar y,
01254          IntConLevel=ICL_DEF);
01256   GECODE_INT_EXPORT void
01257   linear(Space* home, const IntVarArgs& x, 
01258          IntRelType r, int c, BoolVar b, IntConLevel=ICL_DEF);
01260   GECODE_INT_EXPORT void
01261   linear(Space* home, const IntVarArgs& x, 
01262          IntRelType r, IntVar y, BoolVar b, IntConLevel=ICL_DEF);
01268   GECODE_INT_EXPORT void
01269   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01270          IntRelType r, int c,
01271          IntConLevel=ICL_DEF);
01277   GECODE_INT_EXPORT void
01278   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01279          IntRelType r, IntVar y,
01280          IntConLevel=ICL_DEF);
01286   GECODE_INT_EXPORT void
01287   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01288          IntRelType r, int c, BoolVar b, 
01289          IntConLevel=ICL_DEF);
01295   GECODE_INT_EXPORT void
01296   linear(Space* home, const IntArgs& a, const IntVarArgs& x, 
01297          IntRelType r, IntVar y, BoolVar b, 
01298          IntConLevel=ICL_DEF);
01299 
01301   GECODE_INT_EXPORT void
01302   linear(Space* home, const BoolVarArgs& x, 
01303          IntRelType r, int c,
01304          IntConLevel=ICL_DEF);
01305 
01307   GECODE_INT_EXPORT void
01308   linear(Space* home, const BoolVarArgs& x, 
01309          IntRelType r, IntVar y,
01310          IntConLevel=ICL_DEF);
01311 
01313 
01314 
01321 
01322   enum BvarSel {
01323     BVAR_NONE,          
01324     BVAR_MIN_MIN,       
01325     BVAR_MIN_MAX,       
01326     BVAR_MAX_MIN,       
01327     BVAR_MAX_MAX,       
01328     BVAR_SIZE_MIN,      
01329     BVAR_SIZE_MAX,      
01330 
01336     BVAR_DEGREE_MIN,
01343     BVAR_DEGREE_MAX,
01349     BVAR_REGRET_MIN_MIN,
01355     BVAR_REGRET_MIN_MAX,
01361     BVAR_REGRET_MAX_MIN,
01367     BVAR_REGRET_MAX_MAX
01368   };
01369 
01371   enum BvalSel {
01372     BVAL_MIN,      
01373     BVAL_MED,      
01374     BVAL_MAX,      
01375     BVAL_SPLIT_MIN, 
01376     BVAL_SPLIT_MAX  
01377   };
01378 
01380   GECODE_INT_EXPORT void
01381   branch(Space* home, const IntVarArgs& x, BvarSel vars, BvalSel vals);
01383 
01389 
01390   enum AvalSel {
01391     AVAL_MIN, 
01392     AVAL_MED, 
01393     AVAL_MAX  
01394   };
01395 
01397   GECODE_INT_EXPORT void
01398   assign(Space* home, const IntVarArgs& x, AvalSel vals);
01399 
01401 
01402 }
01403 
01407 GECODE_INT_EXPORT std::ostream&
01408 operator<<(std::ostream&, const Gecode::REG& r);
01409 
01413 GECODE_INT_EXPORT std::ostream&
01414 operator<<(std::ostream&, const Gecode::DFA& d);
01415 
01416 #endif
01417 
01418 // STATISTICS: int-post
01419