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(int 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 };
00970 class MiscExpr {
00971 public:
00975 virtual void post(Space& home, BoolVar b, bool neg,
00976 IntConLevel icl) = 0;
00978 virtual GECODE_MINIMODEL_EXPORT ~MiscExpr(void);
00980 static void* operator new(size_t size);
00982 static void operator delete(void* p, size_t size);
00983 };
00985 class Node {
00986 public:
00988 unsigned int use;
00990 int same;
00992 NodeType t;
00994 Node *l, *r;
00996 BoolVar x;
00998 LinRel rl;
00999 #ifdef GECODE_HAS_SET_VARS
01000
01001 SetRel rs;
01002 #endif
01003
01004 MiscExpr* m;
01005
01007 Node(void);
01009 ~Node(void);
01011 GECODE_MINIMODEL_EXPORT
01012 bool decrement(void);
01014 static void* operator new(size_t size);
01016 static void operator delete(void* p, size_t size);
01017 };
01019 class NNF {
01020 public:
01022 NodeType t;
01024 int p;
01026 int n;
01028 union {
01030 struct {
01032 NNF* l;
01034 NNF* r;
01035 } b;
01037 struct {
01039 bool neg;
01041 Node* x;
01042 } a;
01043 } u;
01045 GECODE_MINIMODEL_EXPORT
01046 static NNF* nnf(Region& r, Node* n, bool neg);
01048 GECODE_MINIMODEL_EXPORT
01049 void post(Home home, NodeType t,
01050 BoolVarArgs& bp, BoolVarArgs& bn,
01051 int& ip, int& in,
01052 IntConLevel icl) const;
01054 GECODE_MINIMODEL_EXPORT
01055 BoolVar expr(Home home, IntConLevel icl) const;
01057 GECODE_MINIMODEL_EXPORT
01058 void rel(Home home, IntConLevel icl) const;
01060 static void* operator new(size_t s, Region& r);
01062 static void operator delete(void*);
01064 static void operator delete(void*, Region&);
01065 };
01066 private:
01068 Node* n;
01069 public:
01071 BoolExpr(void);
01073 BoolExpr(const BoolExpr& e);
01075 GECODE_MINIMODEL_EXPORT
01076 BoolExpr(const BoolExpr& l, NodeType t, const BoolExpr& r);
01078 GECODE_MINIMODEL_EXPORT
01079 BoolExpr(const BoolVar& x);
01081 GECODE_MINIMODEL_EXPORT
01082 BoolExpr(const BoolExpr& e, NodeType t);
01084 GECODE_MINIMODEL_EXPORT
01085 BoolExpr(const LinRel& rl);
01086 #ifdef GECODE_HAS_SET_VARS
01087
01088 GECODE_MINIMODEL_EXPORT
01089 BoolExpr(const SetRel& rs);
01091 GECODE_MINIMODEL_EXPORT
01092 BoolExpr(const SetCmpRel& rs);
01093 #endif
01094
01095 GECODE_MINIMODEL_EXPORT
01096 explicit BoolExpr(MiscExpr* m);
01098 BoolVar expr(Home home, IntConLevel icl) const;
01100 void rel(Home home, IntConLevel icl) const;
01102 GECODE_MINIMODEL_EXPORT
01103 const BoolExpr& operator =(const BoolExpr& e);
01105 GECODE_MINIMODEL_EXPORT
01106 ~BoolExpr(void);
01107 };
01108
01119
01120 GECODE_MINIMODEL_EXPORT BoolExpr
01121 operator !(const BoolExpr&);
01123 GECODE_MINIMODEL_EXPORT BoolExpr
01124 operator &&(const BoolExpr&, const BoolExpr&);
01126 GECODE_MINIMODEL_EXPORT BoolExpr
01127 operator ||(const BoolExpr&, const BoolExpr&);
01129 GECODE_MINIMODEL_EXPORT BoolExpr
01130 operator ^(const BoolExpr&, const BoolExpr&);
01131
01133 GECODE_MINIMODEL_EXPORT BoolExpr
01134 operator !=(const BoolExpr&, const BoolExpr&);
01136 GECODE_MINIMODEL_EXPORT BoolExpr
01137 operator ==(const BoolExpr&, const BoolExpr&);
01139 GECODE_MINIMODEL_EXPORT BoolExpr
01140 operator >>(const BoolExpr&, const BoolExpr&);
01142 GECODE_MINIMODEL_EXPORT BoolExpr
01143 operator <<(const BoolExpr&, const BoolExpr&);
01144
01146
01153
01154 GECODE_MINIMODEL_EXPORT IntVar
01155 expr(Home home, const LinExpr& e, IntConLevel icl=ICL_DEF);
01156 #ifdef GECODE_HAS_SET_VARS
01157
01158 GECODE_MINIMODEL_EXPORT SetVar
01159 expr(Home home, const SetExpr& e);
01160 #endif
01161
01162 GECODE_MINIMODEL_EXPORT BoolVar
01163 expr(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF);
01165 GECODE_MINIMODEL_EXPORT void
01166 rel(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF);
01168
01169 }
01170
01171 #include <gecode/minimodel/lin-expr.hpp>
01172 #include <gecode/minimodel/lin-rel.hpp>
01173 #include <gecode/minimodel/bool-expr.hpp>
01174 #include <gecode/minimodel/set-expr.hpp>
01175 #include <gecode/minimodel/set-rel.hpp>
01176
01177 namespace Gecode {
01178
01179 namespace MiniModel {
01180 class ExpInfo;
01181 }
01182
01188 class GECODE_MINIMODEL_EXPORT REG {
01189 friend class MiniModel::ExpInfo;
01190 private:
01192 class Exp;
01194 Exp* e;
01196 REG(Exp* e);
01197 public:
01199 REG(void);
01201 REG(int s);
01208 REG(const IntArgs& x);
01209
01211 REG(const REG& r);
01213 const REG& operator =(const REG& r);
01214
01216 REG operator +(const REG& r);
01218 REG& operator +=(const REG& r);
01220 REG operator |(const REG& r);
01222 REG& operator |=(const REG& r);
01224 REG operator *(void);
01226 REG operator +(void);
01228 REG operator ()(unsigned int n, unsigned int m);
01230 REG operator ()(unsigned int n);
01232 template<class Char, class Traits>
01233 std::basic_ostream<Char,Traits>&
01234 print(std::basic_ostream<Char,Traits>& os) const;
01236 operator DFA(void);
01238 ~REG(void);
01239 };
01240
01244 template<class Char, class Traits>
01245 std::basic_ostream<Char,Traits>&
01246 operator <<(std::basic_ostream<Char,Traits>& os, const REG& r);
01247
01248
01255
01256 GECODE_MINIMODEL_EXPORT LinExpr
01257 abs(const LinExpr& e);
01259 GECODE_MINIMODEL_EXPORT LinExpr
01260 min(const LinExpr& x, const LinExpr& y);
01262 GECODE_MINIMODEL_EXPORT LinExpr
01263 min(const IntVarArgs& x);
01265 GECODE_MINIMODEL_EXPORT LinExpr
01266 max(const LinExpr& x, const LinExpr& y);
01268 GECODE_MINIMODEL_EXPORT LinExpr
01269 max(const IntVarArgs& x);
01271 GECODE_MINIMODEL_EXPORT LinExpr
01272 operator *(const LinExpr& x, const LinExpr& y);
01274 GECODE_MINIMODEL_EXPORT LinExpr
01275 operator /(const LinExpr& x, const LinExpr& y);
01277 GECODE_MINIMODEL_EXPORT LinExpr
01278 operator %(const LinExpr& x, const LinExpr& y);
01280 GECODE_MINIMODEL_EXPORT LinExpr
01281 sqr(const LinExpr& x);
01283 GECODE_MINIMODEL_EXPORT LinExpr
01284 sqrt(const LinExpr& x);
01286 GECODE_MINIMODEL_EXPORT LinExpr
01287 element(const IntVarArgs& x, const LinExpr& y);
01289 GECODE_MINIMODEL_EXPORT BoolExpr
01290 element(const BoolVarArgs& x, const LinExpr& y);
01292 GECODE_MINIMODEL_EXPORT LinExpr
01293 element(const IntArgs& x, const LinExpr& y);
01295
01302
01303 inline BoolVar
01304 channel(Home home, IntVar x,
01305 IntConLevel icl=ICL_DEF) {
01306 (void) icl;
01307 BoolVar b(home,0,1); channel(home,b,x);
01308 return b;
01309 }
01311 inline IntVar
01312 channel(Home home, BoolVar b,
01313 IntConLevel icl=ICL_DEF) {
01314 (void) icl;
01315 IntVar x(home,0,1); channel(home,b,x);
01316 return x;
01317 }
01318 #ifdef GECODE_HAS_SET_VARS
01319
01320 inline SetVar
01321 channel(Home home, const IntVarArgs& x, IntConLevel icl=ICL_DEF) {
01322 (void) icl;
01323 SetVar s(home,IntSet::empty,Set::Limits::min,Set::Limits::max);
01324 rel(home,SOT_UNION,x,s);
01325 nvalues(home,x,IRT_EQ,expr(home,cardinality(s)));
01326 return s;
01327 }
01328 #endif
01329
01330
01331 }
01332
01333 namespace Gecode {
01334
01349 inline void
01350 atmost(Home home, const IntVarArgs& x, int n, int m,
01351 IntConLevel icl=ICL_DEF) {
01352 count(home,x,n,IRT_LQ,m,icl);
01353 }
01358 inline void
01359 atmost(Home home, const IntVarArgs& x, IntVar y, int m,
01360 IntConLevel icl=ICL_DEF) {
01361 count(home,x,y,IRT_LQ,m,icl);
01362 }
01370 inline void
01371 atmost(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01372 IntConLevel icl=ICL_DEF) {
01373 count(home,x,y,IRT_LQ,m,icl);
01374 }
01379 inline void
01380 atmost(Home home, const IntVarArgs& x, int n, IntVar z,
01381 IntConLevel icl=ICL_DEF) {
01382 count(home,x,n,IRT_LQ,z,icl);
01383 }
01388 inline void
01389 atmost(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01390 IntConLevel icl=ICL_DEF) {
01391 count(home,x,y,IRT_LQ,z,icl);
01392 }
01400 inline void
01401 atmost(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01402 IntConLevel icl=ICL_DEF) {
01403 count(home,x,y,IRT_LQ,z,icl);
01404 }
01405
01410 inline void
01411 atleast(Home home, const IntVarArgs& x, int n, int m,
01412 IntConLevel icl=ICL_DEF) {
01413 count(home,x,n,IRT_GQ,m,icl);
01414 }
01419 inline void
01420 atleast(Home home, const IntVarArgs& x, IntVar y, int m,
01421 IntConLevel icl=ICL_DEF) {
01422 count(home,x,y,IRT_GQ,m,icl);
01423 }
01431 inline void
01432 atleast(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01433 IntConLevel icl=ICL_DEF) {
01434 count(home,x,y,IRT_GQ,m,icl);
01435 }
01440 inline void
01441 atleast(Home home, const IntVarArgs& x, int n, IntVar z,
01442 IntConLevel icl=ICL_DEF) {
01443 count(home,x,n,IRT_GQ,z,icl);
01444 }
01449 inline void
01450 atleast(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01451 IntConLevel icl=ICL_DEF) {
01452 count(home,x,y,IRT_GQ,z,icl);
01453 }
01461 inline void
01462 atleast(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01463 IntConLevel icl=ICL_DEF) {
01464 count(home,x,y,IRT_GQ,z,icl);
01465 }
01466
01471 inline void
01472 exactly(Home home, const IntVarArgs& x, int n, int m,
01473 IntConLevel icl=ICL_DEF) {
01474 count(home,x,n,IRT_EQ,m,icl);
01475 }
01480 inline void
01481 exactly(Home home, const IntVarArgs& x, IntVar y, int m,
01482 IntConLevel icl=ICL_DEF) {
01483 count(home,x,y,IRT_EQ,m,icl);
01484 }
01492 inline void
01493 exactly(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01494 IntConLevel icl=ICL_DEF) {
01495 count(home,x,y,IRT_EQ,m,icl);
01496 }
01501 inline void
01502 exactly(Home home, const IntVarArgs& x, int n, IntVar z,
01503 IntConLevel icl=ICL_DEF) {
01504 count(home,x,n,IRT_EQ,z,icl);
01505 }
01510 inline void
01511 exactly(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01512 IntConLevel icl=ICL_DEF) {
01513 count(home,x,y,IRT_EQ,z,icl);
01514 }
01522 inline void
01523 exactly(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01524 IntConLevel icl=ICL_DEF) {
01525 count(home,x,y,IRT_EQ,z,icl);
01526 }
01529 inline void
01530 lex(Home home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
01531 IntConLevel icl=ICL_DEF) {
01532 rel(home,x,r,y,icl);
01533 }
01536 inline void
01537 lex(Home home, const BoolVarArgs& x, IntRelType r, const BoolVarArgs& y,
01538 IntConLevel icl=ICL_DEF) {
01539 rel(home,x,r,y,icl);
01540 }
01543 inline void
01544 values(Home home, const IntVarArgs& x, IntSet y,
01545 IntConLevel icl=ICL_DEF) {
01546 dom(home,x,y,icl);
01547 nvalues(home,x,IRT_EQ,y.size(),icl);
01548 }
01549
01551
01552 #ifdef GECODE_HAS_SET_VARS
01553
01568 inline void
01569 channel(Home home, const IntVarArgs& x, SetVar y) {
01570 rel(home,SOT_UNION,x,y);
01571 nvalues(home,x,IRT_EQ,expr(home,cardinality(y)));
01572 }
01573
01576 inline void
01577 range(Home home, const IntVarArgs& x, SetVar y, SetVar z) {
01578 element(home,SOT_UNION,x,y,z);
01579 }
01580
01586 inline void
01587 roots(Home home, const IntVarArgs& x, SetVar y, SetVar z) {
01588 SetVarArgs xiv(home,z.lubMax()+1,IntSet::empty,0,x.size()-1);
01589 channel(home,x,xiv);
01590 element(home,SOT_UNION,xiv,z,y);
01591 }
01592
01594 #endif
01595
01596 }
01597
01598 namespace Gecode {
01599
01600 template<class> class Matrix;
01601
01609 template<class A>
01610 class Slice {
01611 public:
01613 typedef typename ArrayTraits<A>::ArgsType ArgsType;
01614 private:
01615 ArgsType _r;
01616 unsigned int _fc,
01617 _tc,
01618 _fr,
01619 _tr;
01620 public:
01622 Slice(const Matrix<A>& a, int fc, int tc, int fr, int tr);
01626 Slice& reverse(void);
01628 operator ArgsType(void);
01630 operator Matrix<ArgsType>(void);
01631
01633 operator const ArgsType(void) const;
01635 operator const Matrix<ArgsType>(void) const;
01636 };
01637
01639 template<class A>
01640 typename Slice<A>::ArgsType
01641 operator+(const Slice<A>& x, const Slice<A>& y);
01642
01644 template<class A>
01645 typename Slice<A>::ArgsType
01646 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ArgsType& y);
01647
01649 template<class A>
01650 typename Slice<A>::ArgsType
01651 operator+(const typename ArrayTraits<A>::ArgsType& x, const Slice<A>& y);
01652
01654 template<class A>
01655 typename Slice<A>::ArgsType
01656 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ValueType& y);
01657
01659 template<class A>
01660 typename Slice<A>::ArgsType
01661 operator+(const typename ArrayTraits<A>::ValueType& x, const Slice<A>& y);
01662
01673 template<class A>
01674 class Matrix {
01675 public:
01677 typedef typename ArrayTraits<A>::ValueType ValueType;
01679 typedef typename ArrayTraits<A>::ArgsType ArgsType;
01680
01681 private:
01683 typedef typename ArrayTraits<A>::StorageType StorageType;
01684 StorageType _a;
01685 int _w;
01686 int _h;
01687
01688 public:
01701 Matrix(A a, int w, int h);
01702
01715 Matrix(A a, int n);
01716
01718 int width(void) const;
01720 int height(void) const;
01722 ArgsType const get_array(void) const;
01723
01729 ValueType& operator ()(int c, int r);
01730
01736 const ValueType& operator ()(int c, int r) const;
01737
01747 Slice<A> slice(int fc, int tc, int fr, int tr) const;
01748
01750 Slice<A> row(int r) const;
01751
01753 Slice<A> col(int c) const;
01754 };
01755
01759 template<class Char, class Traits, class A>
01760 std::basic_ostream<Char,Traits>&
01761 operator <<(std::basic_ostream<Char,Traits>& os, const Matrix<A>& m);
01762
01766 template<class Char, class Traits, class A>
01767 std::basic_ostream<Char,Traits>&
01768 operator <<(std::basic_ostream<Char,Traits>& os, const Slice<A>& s);
01769
01776 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y,
01777 IntVar z, IntConLevel icl=ICL_DEF);
01784 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y,
01785 BoolVar z, IntConLevel icl=ICL_DEF);
01792 void element(Home home, const Matrix<IntVarArgs>& m, IntVar x, IntVar y,
01793 IntVar z, IntConLevel icl=ICL_DEF);
01800 void element(Home home, const Matrix<BoolVarArgs>& m, IntVar x, IntVar y,
01801 BoolVar z, IntConLevel icl=ICL_DEF);
01802 #ifdef GECODE_HAS_SET_VARS
01803
01809 void element(Home home, const Matrix<IntSetArgs>& m, IntVar x, IntVar y,
01810 SetVar z);
01817 void element(Home home, const Matrix<SetVarArgs>& m, IntVar x, IntVar y,
01818 SetVar z);
01819 #endif
01820
01821 }
01822
01823 #include <gecode/minimodel/matrix.hpp>
01824
01825 namespace Gecode {
01826
01836 namespace MiniModel {
01837
01839 template<IntRelType irt>
01840 class OptimizeSpace : public Space {
01841 public:
01843 OptimizeSpace(void);
01845 OptimizeSpace(bool share, OptimizeSpace& s);
01847 virtual void constrain(const Space& best);
01849 virtual IntVar cost(void) const = 0;
01850 };
01851
01852 }
01853
01855 typedef MiniModel::OptimizeSpace<IRT_LE> MinimizeSpace;
01856
01858 typedef MiniModel::OptimizeSpace<IRT_GR> MaximizeSpace;
01860
01861 }
01862
01863 #include <gecode/minimodel/optimize.hpp>
01864
01865 #endif
01866
01867
01868
01869