minimodel.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  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00006  *
00007  *  Copyright:
00008  *     Christian Schulte, 2004
00009  *     Guido Tack, 2004
00010  *     Mikael Lagerkvist, 2005
00011  *
00012  *  Last modified:
00013  *     $Date: 2006-08-31 17:36:38 +0200 (Thu, 31 Aug 2006) $ by $Author: schulte $
00014  *     $Revision: 3579 $
00015  *
00016  *  This file is part of Gecode, the generic constraint
00017  *  development environment:
00018  *     http://www.gecode.org
00019  *
00020  *  See the file "LICENSE" for information on usage and
00021  *  redistribution of this file, and for a
00022  *     DISCLAIMER OF ALL WARRANTIES.
00023  *
00024  */
00025 
00026 #ifndef __GECODE_MINIMODEL_HH__
00027 #define __GECODE_MINIMODEL_HH__
00028 
00029 #include "gecode/kernel.hh"
00030 #include "gecode/int.hh"
00031 #include "gecode/int/linear.hh"
00032 
00033 #include "gecode/minimodel/exception.icc"
00034 
00035 #include <iostream>
00036 
00037 /*
00038  * Support for DLLs under Windows
00039  *
00040  */
00041 
00042 #if !defined(GECODE_STATIC_LIBS) && \
00043     (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00044 
00045 #ifdef GECODE_BUILD_MINIMODEL
00046 #define GECODE_MINIMODEL_EXPORT __declspec( dllexport )
00047 #else
00048 #define GECODE_MINIMODEL_EXPORT __declspec( dllimport )
00049 #endif
00050 
00051 #else
00052 
00053 #ifdef GCC_HASCLASSVISIBILITY
00054 
00055 #define GECODE_MINIMODEL_EXPORT __attribute__ ((visibility("default")))
00056 
00057 #else
00058 
00059 #define GECODE_MINIMODEL_EXPORT
00060 
00061 #endif
00062 #endif
00063 
00064 namespace Gecode {
00065 
00067   namespace MiniModel {
00068 
00070     class LinExpr {
00071     private:
00073       class Node {
00074       private:
00076         unsigned int use;
00078         Node *left, *right;
00080         int signLeft, signRight;
00082         int a;
00084         IntVar x;
00085       public:
00087         Node(int a, const IntVar& x);
00089         Node(Node* n0, int s0, Node* n1, int s1);
00090 
00092         void increment(void);
00094         GECODE_MINIMODEL_EXPORT bool decrement(void);
00095         
00097         GECODE_MINIMODEL_EXPORT int
00098         fill(Int::Linear::Term t[], int i, int s) const;
00099         
00101         static void* operator new(size_t size);
00103         static void  operator delete(void* p,size_t size);
00104       };
00105       Node* ax;       
00106     public:
00107       unsigned int n; 
00108       int c;          
00109       int sign;       
00110 
00111       LinExpr(void);
00113       LinExpr(const LinExpr& e);
00115       LinExpr(const IntVar& x, int a=1, int c=0);
00117       LinExpr(const LinExpr& e0, const LinExpr& e1, int s);
00119       LinExpr(const LinExpr& e, int c, int s);
00121       LinExpr(int a, const LinExpr& e);
00123       const LinExpr& operator=(const LinExpr& e);
00125       GECODE_MINIMODEL_EXPORT
00126       void post(Space* home, IntRelType irt, IntConLevel icl) const;
00128       GECODE_MINIMODEL_EXPORT
00129       void post(Space* home, IntRelType irt, const BoolVar& b) const;
00131       GECODE_MINIMODEL_EXPORT
00132       IntVar post(Space* home, IntConLevel icl) const;
00134       ~LinExpr(void);
00135     };
00136 
00138     class LinRel {
00139     private:
00141       LinExpr    e;
00143       IntRelType irt;
00145       static IntRelType neg(IntRelType irt);
00146     public:
00148       LinRel(void);
00150       LinRel(const LinExpr& l, IntRelType irt, const LinExpr& r);
00152       LinRel(const LinExpr& l, IntRelType irt, int r);
00154       LinRel(int l, IntRelType irt, const LinExpr& r);
00156       void post(Space* home, bool t, IntConLevel icl) const;
00158       void post(Space* home, const BoolVar& b) const;
00159     };
00160 
00161   }
00162 
00163 }
00164 
00182 
00184 Gecode::MiniModel::LinExpr
00185 operator+(int,
00186           const Gecode::MiniModel::LinExpr&);
00188 Gecode::MiniModel::LinExpr
00189 operator+(const Gecode::MiniModel::LinExpr&,
00190           int);
00192 Gecode::MiniModel::LinExpr
00193 operator+(const Gecode::MiniModel::LinExpr&,
00194           const Gecode::MiniModel::LinExpr&);
00195 
00197 Gecode::MiniModel::LinExpr
00198 operator-(int,
00199           const Gecode::MiniModel::LinExpr&);
00201 Gecode::MiniModel::LinExpr
00202 operator-(const Gecode::MiniModel::LinExpr&,
00203           int);
00205 Gecode::MiniModel::LinExpr
00206 operator-(const Gecode::MiniModel::LinExpr&,
00207           const Gecode::MiniModel::LinExpr&);
00208 
00210 Gecode::MiniModel::LinExpr
00211 operator-(const Gecode::MiniModel::LinExpr&);
00212 
00213 
00215 Gecode::MiniModel::LinExpr
00216 operator*(int, const Gecode::IntVar&);
00218 Gecode::MiniModel::LinExpr
00219 operator*(const Gecode::IntVar&, int);
00221 Gecode::MiniModel::LinExpr
00222 operator*(const Gecode::MiniModel::LinExpr&, int);
00224 Gecode::MiniModel::LinExpr
00225 operator*(int, const Gecode::MiniModel::LinExpr&);
00226 
00227 
00229 Gecode::MiniModel::LinRel
00230 operator==(int l,
00231            const Gecode::MiniModel::LinExpr& r);
00233 Gecode::MiniModel::LinRel
00234 operator==(const Gecode::MiniModel::LinExpr& l,
00235            int r);
00237 Gecode::MiniModel::LinRel
00238 operator==(const Gecode::MiniModel::LinExpr& l,
00239            const Gecode::MiniModel::LinExpr& r);
00240 
00242 Gecode::MiniModel::LinRel
00243 operator!=(int l,
00244            const Gecode::MiniModel::LinExpr& r);
00246 Gecode::MiniModel::LinRel
00247 operator!=(const Gecode::MiniModel::LinExpr& l,
00248            int r);
00250 Gecode::MiniModel::LinRel
00251 operator!=(const Gecode::MiniModel::LinExpr& l,
00252            const Gecode::MiniModel::LinExpr& r);
00253 
00255 Gecode::MiniModel::LinRel
00256 operator<(int l,
00257           const Gecode::MiniModel::LinExpr& r);
00259 Gecode::MiniModel::LinRel
00260 operator<(const Gecode::MiniModel::LinExpr& l,
00261           int r);
00263 Gecode::MiniModel::LinRel
00264 operator<(const Gecode::MiniModel::LinExpr& l,
00265           const Gecode::MiniModel::LinExpr& r);
00266 
00268 Gecode::MiniModel::LinRel
00269 operator<=(int l,
00270            const Gecode::MiniModel::LinExpr& r);
00272 Gecode::MiniModel::LinRel
00273 operator<=(const Gecode::MiniModel::LinExpr& l,
00274            int r);
00276 Gecode::MiniModel::LinRel
00277 operator<=(const Gecode::MiniModel::LinExpr& l,
00278            const Gecode::MiniModel::LinExpr& r);
00279 
00281 Gecode::MiniModel::LinRel
00282 operator>(int l,
00283           const Gecode::MiniModel::LinExpr& r);
00285 Gecode::MiniModel::LinRel
00286 operator>(const Gecode::MiniModel::LinExpr& l,
00287           int r);
00289 Gecode::MiniModel::LinRel
00290 operator>(const Gecode::MiniModel::LinExpr& l,
00291           const Gecode::MiniModel::LinExpr& r);
00292 
00294 Gecode::MiniModel::LinRel
00295 operator>=(int l,
00296            const Gecode::MiniModel::LinExpr& r);
00298 Gecode::MiniModel::LinRel
00299 operator>=(const Gecode::MiniModel::LinExpr& l,
00300            int r);
00302 Gecode::MiniModel::LinRel
00303 operator>=(const Gecode::MiniModel::LinExpr& l,
00304            const Gecode::MiniModel::LinExpr& r);
00305 
00307 
00308 namespace Gecode {
00309 
00310   namespace MiniModel {
00311 
00313     class BoolExpr {
00314     public:
00316       enum NodeType {
00317         BT_VAR, 
00318         BT_NOT, 
00319         BT_AND, 
00320         BT_OR,  
00321         BT_IMP, 
00322         BT_XOR, 
00323         BT_EQV, 
00324         BT_RLIN 
00325       };
00327       class Node {
00328       public:
00330         unsigned int use;
00332         unsigned int same;
00334         NodeType t;
00336         Node *l, *r;
00338         BoolVar x;
00340         LinRel rl;
00341 
00343         Node(void);
00345         GECODE_MINIMODEL_EXPORT bool decrement(void);
00347         GECODE_MINIMODEL_EXPORT int post(Space* home, NodeType t,
00348                                          BoolVarArgs& b, int i) const;
00350         GECODE_MINIMODEL_EXPORT void post(Space* home, BoolVar b) const;
00352         GECODE_MINIMODEL_EXPORT BoolVar post(Space* home) const;
00354         GECODE_MINIMODEL_EXPORT void post(Space* home, bool t) const;
00355         
00357         static void* operator new(size_t size);
00359         static void  operator delete(void* p,size_t size);
00360       };
00361     private:
00363       Node* n;
00364     public:
00366       BoolExpr(const BoolExpr& e);
00368       BoolExpr(const BoolExpr& l, NodeType t, const BoolExpr& r);
00370       BoolExpr(const BoolVar& x);
00372       BoolExpr(const BoolExpr& e, NodeType t);
00374       BoolExpr(const LinRel& rl);
00376       BoolVar post(Space* home) const;
00378       void post(Space* home, bool t) const;
00379 
00381       const BoolExpr& operator=(const BoolExpr& e);
00383       ~BoolExpr(void);
00384     };
00385 
00387     class BoolRel {
00388     private:
00390       BoolExpr e;
00392       bool t;
00393     public:
00395       BoolRel(const BoolExpr& e, bool t);
00397       void post(Space* home) const;
00398     };
00399   }
00400 
00401 }
00402 
00417 
00419 Gecode::MiniModel::BoolExpr
00420 operator!(const Gecode::MiniModel::BoolExpr&);
00421 
00423 Gecode::MiniModel::BoolExpr
00424 operator&&(const Gecode::MiniModel::BoolExpr&,
00425            const Gecode::MiniModel::BoolExpr&);
00426 
00428 Gecode::MiniModel::BoolExpr
00429 operator||(const Gecode::MiniModel::BoolExpr&,
00430            const Gecode::MiniModel::BoolExpr&);
00431 
00433 Gecode::MiniModel::BoolExpr
00434 operator^(const Gecode::MiniModel::BoolExpr&,
00435           const Gecode::MiniModel::BoolExpr&);
00436 
00438 Gecode::MiniModel::BoolExpr
00439 operator~(const Gecode::MiniModel::LinExpr&);
00440 
00441 namespace Gecode {
00442 
00444   MiniModel::BoolExpr
00445   eqv(const MiniModel::BoolExpr&,
00446       const MiniModel::BoolExpr&);
00448   MiniModel::BoolExpr
00449   imp(const MiniModel::BoolExpr&,
00450       const MiniModel::BoolExpr&);
00451 
00453   MiniModel::BoolRel
00454   tt(const MiniModel::BoolExpr&);
00455 
00457   MiniModel::BoolRel
00458   ff(const MiniModel::BoolExpr&);
00459 
00460 }
00461 
00463 
00464 namespace Gecode {
00465 
00472 
00473   IntVar post(Space* home, const MiniModel::LinExpr& e,
00474               IntConLevel icl=ICL_DEF);
00476   IntVar post(Space* home, const IntVar& x,
00477               IntConLevel icl=ICL_DEF);
00479   IntVar post(Space* home, int n,
00480               IntConLevel icl=ICL_DEF);
00481 
00483   void post(Space* home, const MiniModel::LinRel& r,
00484             IntConLevel icl=ICL_DEF);
00486   void post(Space* home, bool r,
00487             IntConLevel icl=ICL_DEF);
00488 
00490   BoolVar post(Space* home, const MiniModel::BoolExpr& e,
00491                IntConLevel icl=ICL_DEF);
00493   BoolVar post(Space* home, const BoolVar& b,
00494                IntConLevel icl=ICL_DEF);
00496   void post(Space* home, const MiniModel::BoolRel& r,
00497             IntConLevel icl=ICL_DEF);
00499 
00500 }
00501 
00502 #include "gecode/minimodel/lin-expr.icc"
00503 #include "gecode/minimodel/lin-rel.icc"
00504 #include "gecode/minimodel/bool-expr.icc"
00505 #include "gecode/minimodel/bool-rel.icc"
00506 
00507 namespace Gecode {
00508 
00515 
00516   GECODE_MINIMODEL_EXPORT IntVar
00517   abs(Space* home, IntVar x, IntConLevel icl=ICL_DEF);
00519   GECODE_MINIMODEL_EXPORT IntVar
00520   min(Space* home, IntVar x, IntVar y, IntConLevel icl=ICL_DEF);
00522   GECODE_MINIMODEL_EXPORT IntVar
00523   min(Space* home, const IntVarArgs& x, IntConLevel icl=ICL_DEF);
00525   GECODE_MINIMODEL_EXPORT IntVar
00526   max(Space* home, IntVar x, IntVar y, IntConLevel icl=ICL_DEF);
00528   GECODE_MINIMODEL_EXPORT IntVar
00529   max(Space* home, const IntVarArgs& x, IntConLevel icl=ICL_DEF);
00531   GECODE_MINIMODEL_EXPORT IntVar
00532   mult(Space* home, IntVar x, IntVar y, IntConLevel icl=ICL_DEF);
00534   GECODE_MINIMODEL_EXPORT IntVar
00535   sqr(Space* home, IntVar x, IntConLevel icl=ICL_DEF);
00537   GECODE_MINIMODEL_EXPORT IntVar
00538   plus(Space* home, IntVar x, IntVar y, IntConLevel icl=ICL_DEF);
00540   GECODE_MINIMODEL_EXPORT IntVar
00541   minus(Space* home, IntVar x, IntVar y, IntConLevel icl=ICL_DEF);
00543 
00544 }
00545 
00546 namespace Gecode {
00547 
00562   inline void
00563   atmost(Space* home, const IntVarArgs& x, int n, int m,
00564          IntConLevel icl=ICL_DEF) {
00565     count(home,x,n,IRT_LQ,m,icl);
00566   }
00571   inline void
00572   atmost(Space* home, const IntVarArgs& x, IntVar y, int m,
00573          IntConLevel icl=ICL_DEF) {
00574     count(home,x,y,IRT_LQ,m,icl);
00575   }
00580   inline void
00581   atmost(Space* home, const IntVarArgs& x, int n, IntVar z,
00582          IntConLevel icl=ICL_DEF) {
00583     count(home,x,n,IRT_LQ,z,icl);
00584   }
00589   inline void
00590   atmost(Space* home, const IntVarArgs& x, IntVar y, IntVar z,
00591          IntConLevel icl=ICL_DEF) {
00592     count(home,x,y,IRT_LQ,z,icl);
00593   }
00594 
00599   inline void
00600   atleast(Space* home, const IntVarArgs& x, int n, int m,
00601           IntConLevel icl=ICL_DEF) {
00602     count(home,x,n,IRT_GQ,m,icl);
00603   }
00608   inline void
00609   atleast(Space* home, const IntVarArgs& x, IntVar y, int m,
00610           IntConLevel icl=ICL_DEF) {
00611     count(home,x,y,IRT_GQ,m,icl);
00612   }
00617   inline void
00618   atleast(Space* home, const IntVarArgs& x, int n, IntVar z,
00619           IntConLevel icl=ICL_DEF) {
00620     count(home,x,n,IRT_GQ,z,icl);
00621   }
00626   inline void
00627   atleast(Space* home, const IntVarArgs& x, IntVar y, IntVar z,
00628           IntConLevel icl=ICL_DEF) {
00629     count(home,x,y,IRT_GQ,z,icl);
00630   }
00631 
00636   inline void
00637   exactly(Space* home, const IntVarArgs& x, int n, int m,
00638           IntConLevel icl=ICL_DEF) {
00639     count(home,x,n,IRT_EQ,m,icl);
00640   }
00645   inline void
00646   exactly(Space* home, const IntVarArgs& x, IntVar y, int m,
00647           IntConLevel icl=ICL_DEF) {
00648     count(home,x,y,IRT_EQ,m,icl);
00649   }
00654   inline void
00655   exactly(Space* home, const IntVarArgs& x, int n, IntVar z,
00656           IntConLevel icl=ICL_DEF) {
00657     count(home,x,n,IRT_EQ,z,icl);
00658   }
00663   inline void
00664   exactly(Space* home, const IntVarArgs& x, IntVar y, IntVar z,
00665           IntConLevel icl=ICL_DEF) {
00666     count(home,x,y,IRT_EQ,z,icl);
00667   }
00673   inline void
00674   lex(Space* home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
00675       IntConLevel icl=ICL_DEF) {
00676     rel(home,x,r,y,icl);
00677   }
00678 
00680 
00681 }
00682 
00683 namespace Gecode {
00684 
00721   GECODE_MINIMODEL_EXPORT void
00722   producer_consumer(Space *home,
00723                     const IntVarArgs& produce_date, const IntArgs& produce_amount,
00724                     const IntVarArgs& consume_date, const IntArgs& consume_amount,
00725                     int initial, IntConLevel icl=ICL_DEF);
00726 
00727 
00750   GECODE_MINIMODEL_EXPORT void
00751   cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00752              const IntVarArgs& height, int limit, bool at_most = true,
00753              IntConLevel cl=ICL_DEF);
00754 
00759   GECODE_MINIMODEL_EXPORT void
00760   cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
00761              const IntVarArgs& height, int limit, bool at_most = true,
00762              IntConLevel cl=ICL_DEF);
00763 
00768   GECODE_MINIMODEL_EXPORT void
00769   cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00770              const IntArgs& height, int limit, bool at_most = true,
00771              IntConLevel cl=ICL_DEF);
00772 
00777   GECODE_MINIMODEL_EXPORT void
00778   cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
00779              const IntArgs& height, int limit, bool at_most = true,
00780              IntConLevel cl=ICL_DEF);
00781 
00798   GECODE_MINIMODEL_EXPORT void
00799   serialized(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00800              IntConLevel cl=ICL_DEF);
00801 
00802 
00807   GECODE_MINIMODEL_EXPORT void
00808   serialized(Space *home, const IntVarArgs& start, const IntArgs& duration,
00809              IntConLevel cl=ICL_DEF);
00810 
00811 
00813 
00814 }
00815 
00824 namespace Gecode { namespace MiniModel {
00825 
00836   template <class A>
00837   class Matrix {
00838   public:
00840     typedef typename ArrayTraits<A>::value_type value_type;
00842     typedef typename ArrayTraits<A>::args_type  args_type;
00843 
00851     class Slice {
00852       args_type _r;     
00853       unsigned int _fc, 
00854         _tc,            
00855         _fr,            
00856         _tr;            
00857     public:
00858       Slice(Matrix<A>& a,
00859             unsigned int fc, unsigned int tc,
00860             unsigned int fr, unsigned int tr);
00861 
00862       operator args_type(void);
00863       operator Matrix<args_type>(void);
00864     };
00865 
00866   private:
00868     typedef typename ArrayTraits<A>::storage_type storage_type;
00869     storage_type _a; 
00870     unsigned int _w, 
00871       _h;            
00872 
00873   public:
00886     Matrix(A a, unsigned int w, unsigned int h);
00887 
00900     Matrix(A a, unsigned int n);
00901 
00903     unsigned int width(void) const;
00905     unsigned int height(void) const;
00907     args_type const get_array(void);
00908 
00914     value_type& operator()(unsigned int c, unsigned int r);
00915 
00925     Slice slice(unsigned int fc, unsigned int tc,
00926                 unsigned int fr, unsigned int tr);
00927 
00929     args_type row(int r);
00930 
00932     args_type col(int c);
00933   };
00934 }}
00935 
00936 #include "gecode/minimodel/matrix.icc"
00938 
00939 #endif
00940 
00941 // STATISTICS: minimodel-any
00942