00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042 #ifndef __GECODE_MINIMODEL_HH__
00043 #define __GECODE_MINIMODEL_HH__
00044
00045 #include <gecode/kernel.hh>
00046 #include <gecode/int.hh>
00047 #ifdef GECODE_HAS_SET_VARS
00048 #include <gecode/set.hh>
00049 #endif
00050 #include <gecode/int/linear.hh>
00051
00052 #include <gecode/minimodel/exception.hpp>
00053
00054 #include <iostream>
00055
00056
00057
00058
00059
00060
00061 #if !defined(GECODE_STATIC_LIBS) && \
00062 (defined(__CYGWIN__) || defined(__MINGW32__) || defined(_MSC_VER))
00063
00064 #ifdef GECODE_BUILD_MINIMODEL
00065 #define GECODE_MINIMODEL_EXPORT __declspec( dllexport )
00066 #else
00067 #define GECODE_MINIMODEL_EXPORT __declspec( dllimport )
00068 #endif
00069
00070 #else
00071
00072 #ifdef GECODE_GCC_HAS_CLASS_VISIBILITY
00073
00074 #define GECODE_MINIMODEL_EXPORT __attribute__ ((visibility("default")))
00075
00076 #else
00077
00078 #define GECODE_MINIMODEL_EXPORT
00079
00080 #endif
00081 #endif
00082
00083
00084 #ifndef GECODE_BUILD_MINIMODEL
00085 #define GECODE_LIBRARY_NAME "MiniModel"
00086 #include <gecode/support/auto-link.hpp>
00087 #endif
00088
00089 namespace Gecode {
00090
00092 namespace MiniModel {}
00093
00094 class LinRel;
00095 #ifdef GECODE_HAS_SET_VARS
00096 class SetExpr;
00097 #endif
00098
00100 class NonLinExpr {
00101 public:
00103 virtual IntVar post(Home home, IntVar* ret, IntConLevel icl) const = 0;
00105 virtual void post(Home home, IntRelType irt, int c,
00106 IntConLevel icl) const = 0;
00108 virtual void post(Home home, IntRelType irt, int c,
00109 BoolVar b, IntConLevel icl) const = 0;
00111 virtual ~NonLinExpr(void) {}
00113 static IntVar result(Home home, IntVar* x) {
00114 if (x==NULL)
00115 return IntVar(home,Int::Limits::min,Int::Limits::max);
00116 return *x;
00117 }
00119 static IntVar result(Home home, IntVar* x, IntVar y) {
00120 if (x!=NULL)
00121 rel(home,*x,IRT_EQ,y);
00122 return y;
00123 }
00125 void* operator new(size_t size) { return heap.ralloc(size); }
00127 void operator delete(void* p, size_t) { heap.rfree(p); }
00128 };
00129
00131 class LinExpr {
00132 friend class LinRel;
00133 #ifdef GECODE_HAS_SET_VARS
00134 friend class SetExpr;
00135 #endif
00136 public:
00138 enum NodeType {
00139 NT_CONST,
00140 NT_VAR_INT,
00141 NT_VAR_BOOL,
00142 NT_NONLIN,
00143 NT_SUM_INT,
00144 NT_SUM_BOOL,
00145 NT_ADD,
00146 NT_SUB,
00147 NT_MUL
00148 };
00149 private:
00151 class Node {
00152 public:
00154 unsigned int use;
00156 int n_int;
00158 int n_bool;
00160 NodeType t;
00162 Node *l, *r;
00164 union {
00166 Int::Linear::Term<Int::IntView>* ti;
00168 Int::Linear::Term<Int::BoolView>* tb;
00170 NonLinExpr* ne;
00171 } sum;
00173 int a, c;
00175 IntVar x_int;
00177 BoolVar x_bool;
00179 Node(void);
00181 GECODE_MINIMODEL_EXPORT
00182 void fill(Home home, IntConLevel icl,
00183 Int::Linear::Term<Int::IntView>*& ti,
00184 Int::Linear::Term<Int::BoolView>*& tb,
00185 double m, double& d) const;
00187 int fill(Home home, IntConLevel icl,
00188 Int::Linear::Term<Int::IntView>* ti,
00189 Int::Linear::Term<Int::BoolView>* tb) const;
00191 bool decrement(void);
00193 ~Node(void);
00195 static void* operator new(size_t size);
00197 static void operator delete(void* p,size_t size);
00198 };
00199 Node* n;
00200 public:
00202 GECODE_MINIMODEL_EXPORT
00203 LinExpr(void);
00205 GECODE_MINIMODEL_EXPORT
00206 LinExpr(double c);
00208 GECODE_MINIMODEL_EXPORT
00209 LinExpr(const IntVar& x, int a=1);
00211 GECODE_MINIMODEL_EXPORT
00212 LinExpr(const BoolVar& x, int a=1);
00214 GECODE_MINIMODEL_EXPORT
00215 explicit LinExpr(const IntVarArgs& x);
00217 GECODE_MINIMODEL_EXPORT
00218 LinExpr(const IntArgs& a, const IntVarArgs& x);
00220 GECODE_MINIMODEL_EXPORT
00221 explicit LinExpr(const BoolVarArgs& x);
00223 GECODE_MINIMODEL_EXPORT
00224 LinExpr(const IntArgs& a, const BoolVarArgs& x);
00226 LinExpr(const LinExpr& e);
00228 GECODE_MINIMODEL_EXPORT
00229 LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1);
00231 GECODE_MINIMODEL_EXPORT
00232 LinExpr(const LinExpr& e0, NodeType t, int c);
00234 GECODE_MINIMODEL_EXPORT
00235 LinExpr(int a, const LinExpr& e);
00237 GECODE_MINIMODEL_EXPORT
00238 explicit LinExpr(NonLinExpr* e);
00240 GECODE_MINIMODEL_EXPORT
00241 const LinExpr& operator =(const LinExpr& e);
00243 void post(Home home, IntRelType irt, IntConLevel icl) const;
00245 void post(Home home, IntRelType irt, const BoolVar& b,
00246 IntConLevel icl) const;
00248 IntVar post(Home home, IntConLevel icl) const;
00250 NonLinExpr* nle(void) const;
00252 GECODE_MINIMODEL_EXPORT
00253 ~LinExpr(void);
00254 };
00255
00256 class BoolExpr;
00257
00259 class LinRel {
00260 friend class BoolExpr;
00261 private:
00263 LinExpr e;
00265 IntRelType irt;
00267 static IntRelType neg(IntRelType irt);
00269 LinRel(void);
00270 public:
00272 LinRel(const LinExpr& l, IntRelType irt, const LinExpr& r);
00274 LinRel(const LinExpr& l, IntRelType irt, int r);
00276 LinRel(int l, IntRelType irt, const LinExpr& r);
00278 void post(Home home, bool t, IntConLevel icl) const;
00280 void post(Home home, const BoolVar& b, bool t, IntConLevel icl) const;
00281 };
00282
00301
00302 GECODE_MINIMODEL_EXPORT LinExpr
00303 operator +(int, const IntVar&);
00305 GECODE_MINIMODEL_EXPORT LinExpr
00306 operator +(int, const BoolVar&);
00308 GECODE_MINIMODEL_EXPORT LinExpr
00309 operator +(int, const LinExpr&);
00311 GECODE_MINIMODEL_EXPORT LinExpr
00312 operator +(const IntVar&, int);
00314 GECODE_MINIMODEL_EXPORT LinExpr
00315 operator +(const BoolVar&, int);
00317 GECODE_MINIMODEL_EXPORT LinExpr
00318 operator +(const LinExpr&, int);
00320 GECODE_MINIMODEL_EXPORT LinExpr
00321 operator +(const IntVar&, const IntVar&);
00323 GECODE_MINIMODEL_EXPORT LinExpr
00324 operator +(const IntVar&, const BoolVar&);
00326 GECODE_MINIMODEL_EXPORT LinExpr
00327 operator +(const BoolVar&, const IntVar&);
00329 GECODE_MINIMODEL_EXPORT LinExpr
00330 operator +(const BoolVar&, const BoolVar&);
00332 GECODE_MINIMODEL_EXPORT LinExpr
00333 operator +(const IntVar&, const LinExpr&);
00335 GECODE_MINIMODEL_EXPORT LinExpr
00336 operator +(const BoolVar&, const LinExpr&);
00338 GECODE_MINIMODEL_EXPORT LinExpr
00339 operator +(const LinExpr&, const IntVar&);
00341 GECODE_MINIMODEL_EXPORT LinExpr
00342 operator +(const LinExpr&, const BoolVar&);
00344 GECODE_MINIMODEL_EXPORT LinExpr
00345 operator +(const LinExpr&, const LinExpr&);
00346
00348 GECODE_MINIMODEL_EXPORT LinExpr
00349 operator -(int, const IntVar&);
00351 GECODE_MINIMODEL_EXPORT LinExpr
00352 operator -(int, const BoolVar&);
00354 GECODE_MINIMODEL_EXPORT LinExpr
00355 operator -(int, const LinExpr&);
00357 GECODE_MINIMODEL_EXPORT LinExpr
00358 operator -(const IntVar&, int);
00360 GECODE_MINIMODEL_EXPORT LinExpr
00361 operator -(const BoolVar&, int);
00363 GECODE_MINIMODEL_EXPORT LinExpr
00364 operator -(const LinExpr&, int);
00366 GECODE_MINIMODEL_EXPORT LinExpr
00367 operator -(const IntVar&, const IntVar&);
00369 GECODE_MINIMODEL_EXPORT LinExpr
00370 operator -(const IntVar&, const BoolVar&);
00372 GECODE_MINIMODEL_EXPORT LinExpr
00373 operator -(const BoolVar&, const IntVar&);
00375 GECODE_MINIMODEL_EXPORT LinExpr
00376 operator -(const BoolVar&, const BoolVar&);
00378 GECODE_MINIMODEL_EXPORT LinExpr
00379 operator -(const IntVar&, const LinExpr&);
00381 GECODE_MINIMODEL_EXPORT LinExpr
00382 operator -(const BoolVar&, const LinExpr&);
00384 GECODE_MINIMODEL_EXPORT LinExpr
00385 operator -(const LinExpr&, const IntVar&);
00387 GECODE_MINIMODEL_EXPORT LinExpr
00388 operator -(const LinExpr&, const BoolVar&);
00390 GECODE_MINIMODEL_EXPORT LinExpr
00391 operator -(const LinExpr&, const LinExpr&);
00392
00394 GECODE_MINIMODEL_EXPORT LinExpr
00395 operator -(const IntVar&);
00397 GECODE_MINIMODEL_EXPORT LinExpr
00398 operator -(const BoolVar&);
00400 GECODE_MINIMODEL_EXPORT LinExpr
00401 operator -(const LinExpr&);
00402
00404 GECODE_MINIMODEL_EXPORT LinExpr
00405 operator *(int, const IntVar&);
00407 GECODE_MINIMODEL_EXPORT LinExpr
00408 operator *(int, const BoolVar&);
00410 GECODE_MINIMODEL_EXPORT LinExpr
00411 operator *(const IntVar&, int);
00413 GECODE_MINIMODEL_EXPORT LinExpr
00414 operator *(const BoolVar&, int);
00416 GECODE_MINIMODEL_EXPORT LinExpr
00417 operator *(const LinExpr&, int);
00419 GECODE_MINIMODEL_EXPORT LinExpr
00420 operator *(int, const LinExpr&);
00421
00423 GECODE_MINIMODEL_EXPORT LinExpr
00424 sum(const IntVarArgs& x);
00426 GECODE_MINIMODEL_EXPORT LinExpr
00427 sum(const IntArgs& a, const IntVarArgs& x);
00429 GECODE_MINIMODEL_EXPORT LinExpr
00430 sum(const BoolVarArgs& x);
00432 GECODE_MINIMODEL_EXPORT LinExpr
00433 sum(const IntArgs& a, const BoolVarArgs& x);
00434
00436 GECODE_MINIMODEL_EXPORT LinRel
00437 operator ==(int l, const IntVar& r);
00439 GECODE_MINIMODEL_EXPORT LinRel
00440 operator ==(int l, const BoolVar& r);
00442 GECODE_MINIMODEL_EXPORT LinRel
00443 operator ==(int l, const LinExpr& r);
00445 GECODE_MINIMODEL_EXPORT LinRel
00446 operator ==(const IntVar& l, int r);
00448 GECODE_MINIMODEL_EXPORT LinRel
00449 operator ==(const BoolVar& l, int r);
00451 GECODE_MINIMODEL_EXPORT LinRel
00452 operator ==(const LinExpr& l, int r);
00454 GECODE_MINIMODEL_EXPORT LinRel
00455 operator ==(const IntVar& l, const IntVar& r);
00457 GECODE_MINIMODEL_EXPORT LinRel
00458 operator ==(const IntVar& l, const BoolVar& r);
00460 GECODE_MINIMODEL_EXPORT LinRel
00461 operator ==(const BoolVar& l, const IntVar& r);
00463 GECODE_MINIMODEL_EXPORT LinRel
00464 operator ==(const BoolVar& l, const BoolVar& r);
00466 GECODE_MINIMODEL_EXPORT LinRel
00467 operator ==(const IntVar& l, const LinExpr& r);
00469 GECODE_MINIMODEL_EXPORT LinRel
00470 operator ==(const BoolVar& l, const LinExpr& r);
00472 GECODE_MINIMODEL_EXPORT LinRel
00473 operator ==(const LinExpr& l, const IntVar& r);
00475 GECODE_MINIMODEL_EXPORT LinRel
00476 operator ==(const LinExpr& l, const BoolVar& r);
00478 GECODE_MINIMODEL_EXPORT LinRel
00479 operator ==(const LinExpr& l, const LinExpr& r);
00480
00482 GECODE_MINIMODEL_EXPORT LinRel
00483 operator !=(int l, const IntVar& r);
00485 GECODE_MINIMODEL_EXPORT LinRel
00486 operator !=(int l, const BoolVar& r);
00488 GECODE_MINIMODEL_EXPORT LinRel
00489 operator !=(int l, const LinExpr& r);
00491 GECODE_MINIMODEL_EXPORT LinRel
00492 operator !=(const IntVar& l, int r);
00494 GECODE_MINIMODEL_EXPORT LinRel
00495 operator !=(const BoolVar& l, int r);
00497 GECODE_MINIMODEL_EXPORT LinRel
00498 operator !=(const LinExpr& l, int r);
00500 GECODE_MINIMODEL_EXPORT LinRel
00501 operator !=(const IntVar& l, const IntVar& r);
00503 GECODE_MINIMODEL_EXPORT LinRel
00504 operator !=(const IntVar& l, const BoolVar& r);
00506 GECODE_MINIMODEL_EXPORT LinRel
00507 operator !=(const BoolVar& l, const IntVar& r);
00509 GECODE_MINIMODEL_EXPORT LinRel
00510 operator !=(const BoolVar& l, const BoolVar& r);
00512 GECODE_MINIMODEL_EXPORT LinRel
00513 operator !=(const IntVar& l, const LinExpr& r);
00515 GECODE_MINIMODEL_EXPORT LinRel
00516 operator !=(const BoolVar& l, const LinExpr& r);
00518 GECODE_MINIMODEL_EXPORT LinRel
00519 operator !=(const LinExpr& l, const IntVar& r);
00521 GECODE_MINIMODEL_EXPORT LinRel
00522 operator !=(const LinExpr& l, const BoolVar& r);
00524 GECODE_MINIMODEL_EXPORT LinRel
00525 operator !=(const LinExpr& l, const LinExpr& r);
00526
00528 GECODE_MINIMODEL_EXPORT LinRel
00529 operator <(int l, const IntVar& r);
00531 GECODE_MINIMODEL_EXPORT LinRel
00532 operator <(int l, const BoolVar& r);
00534 GECODE_MINIMODEL_EXPORT LinRel
00535 operator <(int l, const LinExpr& r);
00537 GECODE_MINIMODEL_EXPORT LinRel
00538 operator <(const IntVar& l, int r);
00540 GECODE_MINIMODEL_EXPORT LinRel
00541 operator <(const BoolVar& l, int r);
00543 GECODE_MINIMODEL_EXPORT LinRel
00544 operator <(const LinExpr& l, int r);
00546 GECODE_MINIMODEL_EXPORT LinRel
00547 operator <(const IntVar& l, const IntVar& r);
00549 GECODE_MINIMODEL_EXPORT LinRel
00550 operator <(const IntVar& l, const BoolVar& r);
00552 GECODE_MINIMODEL_EXPORT LinRel
00553 operator <(const BoolVar& l, const IntVar& r);
00555 GECODE_MINIMODEL_EXPORT LinRel
00556 operator <(const BoolVar& l, const BoolVar& r);
00558 GECODE_MINIMODEL_EXPORT LinRel
00559 operator <(const IntVar& l, const LinExpr& r);
00561 GECODE_MINIMODEL_EXPORT LinRel
00562 operator <(const BoolVar& l, const LinExpr& r);
00564 GECODE_MINIMODEL_EXPORT LinRel
00565 operator <(const LinExpr& l, const IntVar& r);
00567 GECODE_MINIMODEL_EXPORT LinRel
00568 operator <(const LinExpr& l, const BoolVar& r);
00570 GECODE_MINIMODEL_EXPORT LinRel
00571 operator <(const LinExpr& l, const LinExpr& r);
00572
00574 GECODE_MINIMODEL_EXPORT LinRel
00575 operator <=(int l, const IntVar& r);
00577 GECODE_MINIMODEL_EXPORT LinRel
00578 operator <=(int l, const BoolVar& r);
00580 GECODE_MINIMODEL_EXPORT LinRel
00581 operator <=(int l, const LinExpr& r);
00583 GECODE_MINIMODEL_EXPORT LinRel
00584 operator <=(const IntVar& l, int r);
00586 GECODE_MINIMODEL_EXPORT LinRel
00587 operator <=(const BoolVar& l, int r);
00589 GECODE_MINIMODEL_EXPORT LinRel
00590 operator <=(const LinExpr& l, int r);
00592 GECODE_MINIMODEL_EXPORT LinRel
00593 operator <=(const IntVar& l, const IntVar& r);
00595 GECODE_MINIMODEL_EXPORT LinRel
00596 operator <=(const IntVar& l, const BoolVar& r);
00598 GECODE_MINIMODEL_EXPORT LinRel
00599 operator <=(const BoolVar& l, const IntVar& r);
00601 GECODE_MINIMODEL_EXPORT LinRel
00602 operator <=(const BoolVar& l, const BoolVar& r);
00604 GECODE_MINIMODEL_EXPORT LinRel
00605 operator <=(const IntVar& l, const LinExpr& r);
00607 GECODE_MINIMODEL_EXPORT LinRel
00608 operator <=(const BoolVar& l, const LinExpr& r);
00610 GECODE_MINIMODEL_EXPORT LinRel
00611 operator <=(const LinExpr& l, const IntVar& r);
00613 GECODE_MINIMODEL_EXPORT LinRel
00614 operator <=(const LinExpr& l, const BoolVar& r);
00616 GECODE_MINIMODEL_EXPORT LinRel
00617 operator <=(const LinExpr& l, const LinExpr& r);
00618
00620 GECODE_MINIMODEL_EXPORT LinRel
00621 operator >(int l, const IntVar& r);
00623 GECODE_MINIMODEL_EXPORT LinRel
00624 operator >(int l, const BoolVar& r);
00626 GECODE_MINIMODEL_EXPORT LinRel
00627 operator >(int l, const LinExpr& r);
00629 GECODE_MINIMODEL_EXPORT LinRel
00630 operator >(const IntVar& l, int r);
00632 GECODE_MINIMODEL_EXPORT LinRel
00633 operator >(const BoolVar& l, int r);
00635 GECODE_MINIMODEL_EXPORT LinRel
00636 operator >(const LinExpr& l, int r);
00638 GECODE_MINIMODEL_EXPORT LinRel
00639 operator >(const IntVar& l, const IntVar& r);
00641 GECODE_MINIMODEL_EXPORT LinRel
00642 operator >(const IntVar& l, const BoolVar& r);
00644 GECODE_MINIMODEL_EXPORT LinRel
00645 operator >(const BoolVar& l, const IntVar& r);
00647 GECODE_MINIMODEL_EXPORT LinRel
00648 operator >(const BoolVar& l, const BoolVar& r);
00650 GECODE_MINIMODEL_EXPORT LinRel
00651 operator >(const IntVar& l, const LinExpr& r);
00653 GECODE_MINIMODEL_EXPORT LinRel
00654 operator >(const BoolVar& l, const LinExpr& r);
00656 GECODE_MINIMODEL_EXPORT LinRel
00657 operator >(const LinExpr& l, const IntVar& r);
00659 GECODE_MINIMODEL_EXPORT LinRel
00660 operator >(const LinExpr& l, const BoolVar& r);
00662 GECODE_MINIMODEL_EXPORT LinRel
00663 operator >(const LinExpr& l, const LinExpr& r);
00664
00666 GECODE_MINIMODEL_EXPORT LinRel
00667 operator >=(int l, const IntVar& r);
00669 GECODE_MINIMODEL_EXPORT LinRel
00670 operator >=(int l, const BoolVar& r);
00672 GECODE_MINIMODEL_EXPORT LinRel
00673 operator >=(int l, const LinExpr& r);
00675 GECODE_MINIMODEL_EXPORT LinRel
00676 operator >=(const IntVar& l, int r);
00678 GECODE_MINIMODEL_EXPORT LinRel
00679 operator >=(const BoolVar& l, int r);
00681 GECODE_MINIMODEL_EXPORT LinRel
00682 operator >=(const LinExpr& l, int r);
00684 GECODE_MINIMODEL_EXPORT LinRel
00685 operator >=(const IntVar& l, const IntVar& r);
00687 GECODE_MINIMODEL_EXPORT LinRel
00688 operator >=(const IntVar& l, const BoolVar& r);
00690 GECODE_MINIMODEL_EXPORT LinRel
00691 operator >=(const BoolVar& l, const IntVar& r);
00693 GECODE_MINIMODEL_EXPORT LinRel
00694 operator >=(const BoolVar& l, const BoolVar& r);
00696 GECODE_MINIMODEL_EXPORT LinRel
00697 operator >=(const IntVar& l, const LinExpr& r);
00699 GECODE_MINIMODEL_EXPORT LinRel
00700 operator >=(const BoolVar& l, const LinExpr& r);
00702 GECODE_MINIMODEL_EXPORT LinRel
00703 operator >=(const LinExpr& l, const IntVar& r);
00705 GECODE_MINIMODEL_EXPORT LinRel
00706 operator >=(const LinExpr& l, const BoolVar& r);
00708 GECODE_MINIMODEL_EXPORT LinRel
00709 operator >=(const LinExpr& l, const LinExpr& r);
00711
00712 #ifdef GECODE_HAS_SET_VARS
00713
00714 class SetExpr {
00715 public:
00717 enum NodeType {
00718 NT_VAR,
00719 NT_CONST,
00720 NT_LEXP,
00721 NT_CMPL,
00722 NT_INTER,
00723 NT_UNION,
00724 NT_DUNION
00725 };
00727 static bool same(NodeType t0, NodeType t1);
00729 class Node {
00730 public:
00732 unsigned int use;
00734 int same;
00736 NodeType t;
00738 Node *l, *r;
00740 SetVar x;
00742 IntSet s;
00744 LinExpr e;
00745
00747 Node(void);
00749 GECODE_MINIMODEL_EXPORT
00750 bool decrement(void);
00752 static void* operator new(size_t size);
00754 static void operator delete(void* p, size_t size);
00755 };
00757 class NNF {
00758 public:
00760 NodeType t;
00762 int p;
00764 int n;
00766 union {
00768 struct {
00770 NNF* l;
00772 NNF* r;
00773 } b;
00775 struct {
00777 Node* x;
00778 } a;
00779 } u;
00781 bool neg;
00783 GECODE_MINIMODEL_EXPORT
00784 static NNF* nnf(Region& r, Node* n, bool neg);
00786 GECODE_MINIMODEL_EXPORT
00787 void post(Home home, NodeType t, SetVarArgs& b, int& i) const;
00789 GECODE_MINIMODEL_EXPORT
00790 void post(Home home, SetRelType srt, SetVar s) const;
00792 GECODE_MINIMODEL_EXPORT
00793 void post(Home home, SetRelType srt, SetVar s, BoolVar b) const;
00795 GECODE_MINIMODEL_EXPORT
00796 void post(Home home, SetRelType srt, const NNF* n) const;
00798 GECODE_MINIMODEL_EXPORT
00799 void post(Home home, BoolVar b, bool t, SetRelType srt,
00800 const NNF* n) const;
00802 static void* operator new(size_t s, Region& r);
00804 static void operator delete(void*);
00806 static void operator delete(void*, Region&);
00807 };
00808 private:
00810 Node* n;
00811 public:
00813 GECODE_MINIMODEL_EXPORT
00814 SetExpr(void);
00816 SetExpr(const SetExpr& e);
00818 GECODE_MINIMODEL_EXPORT
00819 SetExpr(const SetExpr& l, NodeType t, const SetExpr& r);
00821 GECODE_MINIMODEL_EXPORT
00822 SetExpr(const SetVar& x);
00824 GECODE_MINIMODEL_EXPORT
00825 explicit SetExpr(const LinExpr& x);
00827 GECODE_MINIMODEL_EXPORT
00828 SetExpr(const IntSet& s);
00830 GECODE_MINIMODEL_EXPORT
00831 SetExpr(const SetExpr& e, NodeType t);
00833 SetVar post(Home home) const;
00835 void post(Home home, SetRelType srt, const SetExpr& e) const;
00837 void post(Home home, BoolVar b, bool t,
00838 SetRelType srt, const SetExpr& e) const;
00840 GECODE_MINIMODEL_EXPORT
00841 const SetExpr& operator =(const SetExpr& e);
00843 GECODE_MINIMODEL_EXPORT
00844 ~SetExpr(void);
00845 };
00846
00848 class SetCmpRel {
00849 public:
00851 SetExpr l;
00853 SetExpr r;
00855 SetRelType srt;
00857 SetCmpRel(const SetExpr& l, SetRelType srt, const SetExpr& r);
00858 };
00859
00861 class SetRel {
00862 private:
00864 SetExpr _e0;
00866 SetRelType _srt;
00868 SetExpr _e1;
00869 public:
00871 SetRel(void);
00873 SetRel(const SetExpr& e0, SetRelType srt, const SetExpr& e1);
00875 SetRel(const SetCmpRel& r);
00877 void post(Home home, bool t) const;
00879 void post(Home home, BoolVar b, bool t) const;
00880 };
00881
00892
00893 GECODE_MINIMODEL_EXPORT SetExpr
00894 singleton(const LinExpr&);
00896 GECODE_MINIMODEL_EXPORT SetExpr
00897 operator -(const SetExpr&);
00899 GECODE_MINIMODEL_EXPORT SetExpr
00900 operator &(const SetExpr&, const SetExpr&);
00902 GECODE_MINIMODEL_EXPORT SetExpr
00903 operator |(const SetExpr&, const SetExpr&);
00905 GECODE_MINIMODEL_EXPORT SetExpr
00906 operator +(const SetExpr&, const SetExpr&);
00908 GECODE_MINIMODEL_EXPORT SetExpr
00909 operator -(const SetExpr&, const SetExpr&);
00910
00912 GECODE_MINIMODEL_EXPORT SetExpr
00913 inter(const SetVarArgs&);
00915 GECODE_MINIMODEL_EXPORT SetExpr
00916 setunion(const SetVarArgs&);
00918 GECODE_MINIMODEL_EXPORT SetExpr
00919 setdunion(const SetVarArgs&);
00920
00922 GECODE_MINIMODEL_EXPORT LinExpr
00923 cardinality(const SetExpr&);
00925 GECODE_MINIMODEL_EXPORT LinExpr
00926 min(const SetExpr&);
00928 GECODE_MINIMODEL_EXPORT LinExpr
00929 max(const SetExpr&);
00930
00932 GECODE_MINIMODEL_EXPORT SetRel
00933 operator ==(const SetExpr&, const SetExpr&);
00935 GECODE_MINIMODEL_EXPORT SetRel
00936 operator !=(const SetExpr&, const SetExpr&);
00938 GECODE_MINIMODEL_EXPORT SetCmpRel
00939 operator <=(const SetExpr&, const SetExpr&);
00941 GECODE_MINIMODEL_EXPORT BoolExpr
00942 operator <=(const SetCmpRel&, const SetExpr&);
00944 GECODE_MINIMODEL_EXPORT SetCmpRel
00945 operator >=(const SetExpr&, const SetExpr&);
00947 GECODE_MINIMODEL_EXPORT BoolExpr
00948 operator >=(const SetCmpRel&, const SetExpr&);
00950 GECODE_MINIMODEL_EXPORT SetRel
00951 operator ||(const SetExpr&, const SetExpr&);
00953 #endif
00954
00956 class BoolExpr {
00957 public:
00959 enum NodeType {
00960 NT_VAR,
00961 NT_NOT,
00962 NT_AND,
00963 NT_OR,
00964 NT_EQV,
00965 NT_RLIN,
00966 NT_RSET,
00967 NT_MISC
00968 };
00969 class MiscExpr {
00970 public:
00974 virtual void post(Space& home, BoolVar b, bool neg,
00975 IntConLevel icl) = 0;
00977 virtual GECODE_MINIMODEL_EXPORT ~MiscExpr(void);
00979 static void* operator new(size_t size);
00981 static void operator delete(void* p, size_t size);
00982 };
00984 class Node {
00985 public:
00987 unsigned int use;
00989 int same;
00991 NodeType t;
00993 Node *l, *r;
00995 BoolVar x;
00997 LinRel rl;
00998 #ifdef GECODE_HAS_SET_VARS
00999
01000 SetRel rs;
01001 #endif
01002
01003 MiscExpr* m;
01004
01006 Node(void);
01008 ~Node(void);
01010 GECODE_MINIMODEL_EXPORT
01011 bool decrement(void);
01013 static void* operator new(size_t size);
01015 static void operator delete(void* p, size_t size);
01016 };
01018 class NNF {
01019 public:
01021 NodeType t;
01023 int p;
01025 int n;
01027 union {
01029 struct {
01031 NNF* l;
01033 NNF* r;
01034 } b;
01036 struct {
01038 bool neg;
01040 Node* x;
01041 } a;
01042 } u;
01044 GECODE_MINIMODEL_EXPORT
01045 static NNF* nnf(Region& r, Node* n, bool neg);
01047 GECODE_MINIMODEL_EXPORT
01048 void post(Home home, NodeType t,
01049 BoolVarArgs& bp, BoolVarArgs& bn,
01050 int& ip, int& in,
01051 IntConLevel icl) const;
01053 GECODE_MINIMODEL_EXPORT
01054 BoolVar expr(Home home, IntConLevel icl) const;
01056 GECODE_MINIMODEL_EXPORT
01057 void rel(Home home, IntConLevel icl) const;
01059 static void* operator new(size_t s, Region& r);
01061 static void operator delete(void*);
01063 static void operator delete(void*, Region&);
01064 };
01065 private:
01067 Node* n;
01068 public:
01070 BoolExpr(void);
01072 BoolExpr(const BoolExpr& e);
01074 GECODE_MINIMODEL_EXPORT
01075 BoolExpr(const BoolExpr& l, NodeType t, const BoolExpr& r);
01077 GECODE_MINIMODEL_EXPORT
01078 BoolExpr(const BoolVar& x);
01080 GECODE_MINIMODEL_EXPORT
01081 BoolExpr(const BoolExpr& e, NodeType t);
01083 GECODE_MINIMODEL_EXPORT
01084 BoolExpr(const LinRel& rl);
01085 #ifdef GECODE_HAS_SET_VARS
01086
01087 GECODE_MINIMODEL_EXPORT
01088 BoolExpr(const SetRel& rs);
01090 GECODE_MINIMODEL_EXPORT
01091 BoolExpr(const SetCmpRel& rs);
01092 #endif
01093
01094 GECODE_MINIMODEL_EXPORT
01095 explicit BoolExpr(MiscExpr* m);
01097 BoolVar expr(Home home, IntConLevel icl) const;
01099 void rel(Home home, IntConLevel icl) const;
01101 GECODE_MINIMODEL_EXPORT
01102 const BoolExpr& operator =(const BoolExpr& e);
01104 GECODE_MINIMODEL_EXPORT
01105 ~BoolExpr(void);
01106 };
01107
01118
01119 GECODE_MINIMODEL_EXPORT BoolExpr
01120 operator !(const BoolExpr&);
01122 GECODE_MINIMODEL_EXPORT BoolExpr
01123 operator &&(const BoolExpr&, const BoolExpr&);
01125 GECODE_MINIMODEL_EXPORT BoolExpr
01126 operator ||(const BoolExpr&, const BoolExpr&);
01128 GECODE_MINIMODEL_EXPORT BoolExpr
01129 operator ^(const BoolExpr&, const BoolExpr&);
01130
01132 GECODE_MINIMODEL_EXPORT BoolExpr
01133 operator !=(const BoolExpr&, const BoolExpr&);
01135 GECODE_MINIMODEL_EXPORT BoolExpr
01136 operator ==(const BoolExpr&, const BoolExpr&);
01138 GECODE_MINIMODEL_EXPORT BoolExpr
01139 operator >>(const BoolExpr&, const BoolExpr&);
01141 GECODE_MINIMODEL_EXPORT BoolExpr
01142 operator <<(const BoolExpr&, const BoolExpr&);
01143
01145
01152
01153 GECODE_MINIMODEL_EXPORT IntVar
01154 expr(Home home, const LinExpr& e, IntConLevel icl=ICL_DEF);
01155 #ifdef GECODE_HAS_SET_VARS
01156
01157 GECODE_MINIMODEL_EXPORT SetVar
01158 expr(Home home, const SetExpr& e);
01159 #endif
01160
01161 GECODE_MINIMODEL_EXPORT BoolVar
01162 expr(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF);
01164 GECODE_MINIMODEL_EXPORT void
01165 rel(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF);
01167
01168 }
01169
01170 #include <gecode/minimodel/lin-expr.hpp>
01171 #include <gecode/minimodel/lin-rel.hpp>
01172 #include <gecode/minimodel/bool-expr.hpp>
01173 #include <gecode/minimodel/set-expr.hpp>
01174 #include <gecode/minimodel/set-rel.hpp>
01175
01176 namespace Gecode {
01177
01178 namespace MiniModel {
01179 class ExpInfo;
01180 }
01181
01187 class GECODE_MINIMODEL_EXPORT REG {
01188 friend class MiniModel::ExpInfo;
01189 private:
01191 class Exp;
01193 Exp* e;
01195 REG(Exp* e);
01196 public:
01198 REG(void);
01200 REG(int s);
01207 REG(const IntArgs& x);
01208
01210 REG(const REG& r);
01212 const REG& operator =(const REG& r);
01213
01215 REG operator +(const REG& r);
01217 REG& operator +=(const REG& r);
01219 REG operator |(const REG& r);
01221 REG& operator |=(const REG& r);
01223 REG operator *(void);
01225 REG operator +(void);
01227 REG operator ()(unsigned int n, unsigned int m);
01229 REG operator ()(unsigned int n);
01231 template<class Char, class Traits>
01232 std::basic_ostream<Char,Traits>&
01233 print(std::basic_ostream<Char,Traits>& os) const;
01235 operator DFA(void);
01237 ~REG(void);
01238 };
01239
01243 template<class Char, class Traits>
01244 std::basic_ostream<Char,Traits>&
01245 operator <<(std::basic_ostream<Char,Traits>& os, const REG& r);
01246
01247
01254
01255 GECODE_MINIMODEL_EXPORT LinExpr
01256 abs(const LinExpr& e);
01258 GECODE_MINIMODEL_EXPORT LinExpr
01259 min(const LinExpr& x, const LinExpr& y);
01261 GECODE_MINIMODEL_EXPORT LinExpr
01262 min(const IntVarArgs& x);
01264 GECODE_MINIMODEL_EXPORT LinExpr
01265 max(const LinExpr& x, const LinExpr& y);
01267 GECODE_MINIMODEL_EXPORT LinExpr
01268 max(const IntVarArgs& x);
01270 GECODE_MINIMODEL_EXPORT LinExpr
01271 operator *(const LinExpr& x, const LinExpr& y);
01273 GECODE_MINIMODEL_EXPORT LinExpr
01274 operator /(const LinExpr& x, const LinExpr& y);
01276 GECODE_MINIMODEL_EXPORT LinExpr
01277 operator %(const LinExpr& x, const LinExpr& y);
01279 GECODE_MINIMODEL_EXPORT LinExpr
01280 sqr(const LinExpr& x);
01282 GECODE_MINIMODEL_EXPORT LinExpr
01283 sqrt(const LinExpr& x);
01285 GECODE_MINIMODEL_EXPORT LinExpr
01286 element(const IntVarArgs& x, const LinExpr& y);
01288 GECODE_MINIMODEL_EXPORT BoolExpr
01289 element(const BoolVarArgs& x, const LinExpr& y);
01291 GECODE_MINIMODEL_EXPORT LinExpr
01292 element(const IntArgs& x, const LinExpr& y);
01294
01301
01302 inline BoolVar
01303 channel(Home home, IntVar x,
01304 IntConLevel icl=ICL_DEF) {
01305 (void) icl;
01306 BoolVar b(home,0,1); channel(home,b,x);
01307 return b;
01308 }
01310 inline IntVar
01311 channel(Home home, BoolVar b,
01312 IntConLevel icl=ICL_DEF) {
01313 (void) icl;
01314 IntVar x(home,0,1); channel(home,b,x);
01315 return x;
01316 }
01318
01319 }
01320
01321 namespace Gecode {
01322
01337 inline void
01338 atmost(Home home, const IntVarArgs& x, int n, int m,
01339 IntConLevel icl=ICL_DEF) {
01340 count(home,x,n,IRT_LQ,m,icl);
01341 }
01346 inline void
01347 atmost(Home home, const IntVarArgs& x, IntVar y, int m,
01348 IntConLevel icl=ICL_DEF) {
01349 count(home,x,y,IRT_LQ,m,icl);
01350 }
01358 inline void
01359 atmost(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01360 IntConLevel icl=ICL_DEF) {
01361 count(home,x,y,IRT_LQ,m,icl);
01362 }
01367 inline void
01368 atmost(Home home, const IntVarArgs& x, int n, IntVar z,
01369 IntConLevel icl=ICL_DEF) {
01370 count(home,x,n,IRT_LQ,z,icl);
01371 }
01376 inline void
01377 atmost(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01378 IntConLevel icl=ICL_DEF) {
01379 count(home,x,y,IRT_LQ,z,icl);
01380 }
01388 inline void
01389 atmost(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01390 IntConLevel icl=ICL_DEF) {
01391 count(home,x,y,IRT_LQ,z,icl);
01392 }
01393
01398 inline void
01399 atleast(Home home, const IntVarArgs& x, int n, int m,
01400 IntConLevel icl=ICL_DEF) {
01401 count(home,x,n,IRT_GQ,m,icl);
01402 }
01407 inline void
01408 atleast(Home home, const IntVarArgs& x, IntVar y, int m,
01409 IntConLevel icl=ICL_DEF) {
01410 count(home,x,y,IRT_GQ,m,icl);
01411 }
01419 inline void
01420 atleast(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01421 IntConLevel icl=ICL_DEF) {
01422 count(home,x,y,IRT_GQ,m,icl);
01423 }
01428 inline void
01429 atleast(Home home, const IntVarArgs& x, int n, IntVar z,
01430 IntConLevel icl=ICL_DEF) {
01431 count(home,x,n,IRT_GQ,z,icl);
01432 }
01437 inline void
01438 atleast(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01439 IntConLevel icl=ICL_DEF) {
01440 count(home,x,y,IRT_GQ,z,icl);
01441 }
01449 inline void
01450 atleast(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01451 IntConLevel icl=ICL_DEF) {
01452 count(home,x,y,IRT_GQ,z,icl);
01453 }
01454
01459 inline void
01460 exactly(Home home, const IntVarArgs& x, int n, int m,
01461 IntConLevel icl=ICL_DEF) {
01462 count(home,x,n,IRT_EQ,m,icl);
01463 }
01468 inline void
01469 exactly(Home home, const IntVarArgs& x, IntVar y, int m,
01470 IntConLevel icl=ICL_DEF) {
01471 count(home,x,y,IRT_EQ,m,icl);
01472 }
01480 inline void
01481 exactly(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01482 IntConLevel icl=ICL_DEF) {
01483 count(home,x,y,IRT_EQ,m,icl);
01484 }
01489 inline void
01490 exactly(Home home, const IntVarArgs& x, int n, IntVar z,
01491 IntConLevel icl=ICL_DEF) {
01492 count(home,x,n,IRT_EQ,z,icl);
01493 }
01498 inline void
01499 exactly(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01500 IntConLevel icl=ICL_DEF) {
01501 count(home,x,y,IRT_EQ,z,icl);
01502 }
01510 inline void
01511 exactly(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01512 IntConLevel icl=ICL_DEF) {
01513 count(home,x,y,IRT_EQ,z,icl);
01514 }
01520 inline void
01521 lex(Home home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
01522 IntConLevel icl=ICL_DEF) {
01523 rel(home,x,r,y,icl);
01524 }
01530 inline void
01531 lex(Home home, const BoolVarArgs& x, IntRelType r, const BoolVarArgs& y,
01532 IntConLevel icl=ICL_DEF) {
01533 rel(home,x,r,y,icl);
01534 }
01535
01537
01538 }
01539
01540 namespace Gecode {
01541
01542 template<class> class Matrix;
01543
01551 template<class A>
01552 class Slice {
01553 public:
01555 typedef typename ArrayTraits<A>::ArgsType ArgsType;
01556 private:
01557 ArgsType _r;
01558 unsigned int _fc,
01559 _tc,
01560 _fr,
01561 _tr;
01562 public:
01564 Slice(const Matrix<A>& a, int fc, int tc, int fr, int tr);
01568 Slice& reverse(void);
01570 operator ArgsType(void);
01572 operator Matrix<ArgsType>(void);
01573
01575 operator const ArgsType(void) const;
01577 operator const Matrix<ArgsType>(void) const;
01578 };
01579
01581 template<class A>
01582 typename Slice<A>::ArgsType
01583 operator+(const Slice<A>& x, const Slice<A>& y);
01584
01586 template<class A>
01587 typename Slice<A>::ArgsType
01588 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ArgsType& y);
01589
01591 template<class A>
01592 typename Slice<A>::ArgsType
01593 operator+(const typename ArrayTraits<A>::ArgsType& x, const Slice<A>& y);
01594
01596 template<class A>
01597 typename Slice<A>::ArgsType
01598 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ValueType& y);
01599
01601 template<class A>
01602 typename Slice<A>::ArgsType
01603 operator+(const typename ArrayTraits<A>::ValueType& x, const Slice<A>& y);
01604
01615 template<class A>
01616 class Matrix {
01617 public:
01619 typedef typename ArrayTraits<A>::ValueType ValueType;
01621 typedef typename ArrayTraits<A>::ArgsType ArgsType;
01622
01623 private:
01625 typedef typename ArrayTraits<A>::StorageType StorageType;
01626 StorageType _a;
01627 int _w;
01628 int _h;
01629
01630 public:
01643 Matrix(A a, int w, int h);
01644
01657 Matrix(A a, int n);
01658
01660 int width(void) const;
01662 int height(void) const;
01664 ArgsType const get_array(void) const;
01665
01671 ValueType& operator ()(int c, int r);
01672
01678 const ValueType& operator ()(int c, int r) const;
01679
01689 Slice<A> slice(int fc, int tc, int fr, int tr) const;
01690
01692 Slice<A> row(int r) const;
01693
01695 Slice<A> col(int c) const;
01696 };
01697
01701 template<class Char, class Traits, class A>
01702 std::basic_ostream<Char,Traits>&
01703 operator <<(std::basic_ostream<Char,Traits>& os, const Matrix<A>& m);
01704
01708 template<class Char, class Traits, class A>
01709 std::basic_ostream<Char,Traits>&
01710 operator <<(std::basic_ostream<Char,Traits>& os, const Slice<A>& s);
01711
01718 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y,
01719 IntVar z, IntConLevel icl=ICL_DEF);
01726 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y,
01727 BoolVar z, IntConLevel icl=ICL_DEF);
01734 void element(Home home, const Matrix<IntVarArgs>& m, IntVar x, IntVar y,
01735 IntVar z, IntConLevel icl=ICL_DEF);
01742 void element(Home home, const Matrix<BoolVarArgs>& m, IntVar x, IntVar y,
01743 BoolVar z, IntConLevel icl=ICL_DEF);
01744 #ifdef GECODE_HAS_SET_VARS
01745
01751 void element(Home home, const Matrix<IntSetArgs>& m, IntVar x, IntVar y,
01752 SetVar z);
01759 void element(Home home, const Matrix<SetVarArgs>& m, IntVar x, IntVar y,
01760 SetVar z);
01761 #endif
01762
01763 }
01764
01765 #include <gecode/minimodel/matrix.hpp>
01766
01767 namespace Gecode {
01768
01778 namespace MiniModel {
01779
01781 template<IntRelType irt>
01782 class OptimizeSpace : public Space {
01783 public:
01785 OptimizeSpace(void);
01787 OptimizeSpace(bool share, OptimizeSpace& s);
01789 virtual void constrain(const Space& best);
01791 virtual IntVar cost(void) const = 0;
01792 };
01793
01794 }
01795
01797 typedef MiniModel::OptimizeSpace<IRT_LE> MinimizeSpace;
01798
01800 typedef MiniModel::OptimizeSpace<IRT_GR> MaximizeSpace;
01802
01803 }
01804
01805 #include <gecode/minimodel/optimize.hpp>
01806
01807 #endif
01808
01809
01810
01811