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 GECODE_MINIMODEL_EXPORT
01072 BoolExpr(void);
01074 BoolExpr(const BoolExpr& e);
01076 GECODE_MINIMODEL_EXPORT
01077 BoolExpr(const BoolExpr& l, NodeType t, const BoolExpr& r);
01079 GECODE_MINIMODEL_EXPORT
01080 BoolExpr(const BoolVar& x);
01082 GECODE_MINIMODEL_EXPORT
01083 BoolExpr(const BoolExpr& e, NodeType t);
01085 GECODE_MINIMODEL_EXPORT
01086 BoolExpr(const LinRel& rl);
01087 #ifdef GECODE_HAS_SET_VARS
01088
01089 GECODE_MINIMODEL_EXPORT
01090 BoolExpr(const SetRel& rs);
01092 GECODE_MINIMODEL_EXPORT
01093 BoolExpr(const SetCmpRel& rs);
01094 #endif
01095
01096 GECODE_MINIMODEL_EXPORT
01097 explicit BoolExpr(MiscExpr* m);
01099 BoolVar expr(Home home, IntConLevel icl) const;
01101 void rel(Home home, IntConLevel icl) const;
01103 GECODE_MINIMODEL_EXPORT
01104 const BoolExpr& operator =(const BoolExpr& e);
01106 GECODE_MINIMODEL_EXPORT
01107 ~BoolExpr(void);
01108 };
01109
01120
01121 GECODE_MINIMODEL_EXPORT BoolExpr
01122 operator !(const BoolExpr&);
01124 GECODE_MINIMODEL_EXPORT BoolExpr
01125 operator &&(const BoolExpr&, const BoolExpr&);
01127 GECODE_MINIMODEL_EXPORT BoolExpr
01128 operator ||(const BoolExpr&, const BoolExpr&);
01130 GECODE_MINIMODEL_EXPORT BoolExpr
01131 operator ^(const BoolExpr&, const BoolExpr&);
01132
01134 GECODE_MINIMODEL_EXPORT BoolExpr
01135 operator !=(const BoolExpr&, const BoolExpr&);
01137 GECODE_MINIMODEL_EXPORT BoolExpr
01138 operator ==(const BoolExpr&, const BoolExpr&);
01140 GECODE_MINIMODEL_EXPORT BoolExpr
01141 operator >>(const BoolExpr&, const BoolExpr&);
01143 GECODE_MINIMODEL_EXPORT BoolExpr
01144 operator <<(const BoolExpr&, const BoolExpr&);
01145
01147
01154
01155 GECODE_MINIMODEL_EXPORT IntVar
01156 expr(Home home, const LinExpr& e, IntConLevel icl=ICL_DEF);
01157 #ifdef GECODE_HAS_SET_VARS
01158
01159 GECODE_MINIMODEL_EXPORT SetVar
01160 expr(Home home, const SetExpr& e);
01161 #endif
01162
01163 GECODE_MINIMODEL_EXPORT BoolVar
01164 expr(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF);
01166 GECODE_MINIMODEL_EXPORT void
01167 rel(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF);
01169
01170 }
01171
01172 #include <gecode/minimodel/lin-expr.hpp>
01173 #include <gecode/minimodel/lin-rel.hpp>
01174 #include <gecode/minimodel/bool-expr.hpp>
01175 #include <gecode/minimodel/set-expr.hpp>
01176 #include <gecode/minimodel/set-rel.hpp>
01177
01178 namespace Gecode {
01179
01180 namespace MiniModel {
01181 class ExpInfo;
01182 }
01183
01189 class GECODE_MINIMODEL_EXPORT REG {
01190 friend class MiniModel::ExpInfo;
01191 private:
01193 class Exp;
01195 Exp* e;
01197 REG(Exp* e);
01198 public:
01200 REG(void);
01202 REG(int s);
01209 REG(const IntArgs& x);
01210
01212 REG(const REG& r);
01214 const REG& operator =(const REG& r);
01215
01217 REG operator +(const REG& r);
01219 REG& operator +=(const REG& r);
01221 REG operator |(const REG& r);
01223 REG& operator |=(const REG& r);
01225 REG operator *(void);
01227 REG operator +(void);
01229 REG operator ()(unsigned int n, unsigned int m);
01231 REG operator ()(unsigned int n);
01233 template<class Char, class Traits>
01234 std::basic_ostream<Char,Traits>&
01235 print(std::basic_ostream<Char,Traits>& os) const;
01237 operator DFA(void);
01239 ~REG(void);
01240 };
01241
01245 template<class Char, class Traits>
01246 std::basic_ostream<Char,Traits>&
01247 operator <<(std::basic_ostream<Char,Traits>& os, const REG& r);
01248
01249
01256
01257 GECODE_MINIMODEL_EXPORT LinExpr
01258 abs(const LinExpr& e);
01260 GECODE_MINIMODEL_EXPORT LinExpr
01261 min(const LinExpr& x, const LinExpr& y);
01263 GECODE_MINIMODEL_EXPORT LinExpr
01264 min(const IntVarArgs& x);
01266 GECODE_MINIMODEL_EXPORT LinExpr
01267 max(const LinExpr& x, const LinExpr& y);
01269 GECODE_MINIMODEL_EXPORT LinExpr
01270 max(const IntVarArgs& x);
01272 GECODE_MINIMODEL_EXPORT LinExpr
01273 operator *(const LinExpr& x, const LinExpr& y);
01275 GECODE_MINIMODEL_EXPORT LinExpr
01276 operator /(const LinExpr& x, const LinExpr& y);
01278 GECODE_MINIMODEL_EXPORT LinExpr
01279 operator %(const LinExpr& x, const LinExpr& y);
01281 GECODE_MINIMODEL_EXPORT LinExpr
01282 sqr(const LinExpr& x);
01284 GECODE_MINIMODEL_EXPORT LinExpr
01285 sqrt(const LinExpr& x);
01287 GECODE_MINIMODEL_EXPORT LinExpr
01288 element(const IntVarArgs& x, const LinExpr& y);
01290 GECODE_MINIMODEL_EXPORT BoolExpr
01291 element(const BoolVarArgs& x, const LinExpr& y);
01293 GECODE_MINIMODEL_EXPORT LinExpr
01294 element(const IntArgs& x, const LinExpr& y);
01296
01303
01304 inline BoolVar
01305 channel(Home home, IntVar x,
01306 IntConLevel icl=ICL_DEF) {
01307 (void) icl;
01308 BoolVar b(home,0,1); channel(home,b,x);
01309 return b;
01310 }
01312 inline IntVar
01313 channel(Home home, BoolVar b,
01314 IntConLevel icl=ICL_DEF) {
01315 (void) icl;
01316 IntVar x(home,0,1); channel(home,b,x);
01317 return x;
01318 }
01319 #ifdef GECODE_HAS_SET_VARS
01320
01321 inline SetVar
01322 channel(Home home, const IntVarArgs& x, IntConLevel icl=ICL_DEF) {
01323 (void) icl;
01324 SetVar s(home,IntSet::empty,Set::Limits::min,Set::Limits::max);
01325 rel(home,SOT_UNION,x,s);
01326 nvalues(home,x,IRT_EQ,expr(home,cardinality(s)));
01327 return s;
01328 }
01329 #endif
01330
01331
01332 }
01333
01334 namespace Gecode {
01335
01350 inline void
01351 atmost(Home home, const IntVarArgs& x, int n, int m,
01352 IntConLevel icl=ICL_DEF) {
01353 count(home,x,n,IRT_LQ,m,icl);
01354 }
01359 inline void
01360 atmost(Home home, const IntVarArgs& x, IntVar y, int m,
01361 IntConLevel icl=ICL_DEF) {
01362 count(home,x,y,IRT_LQ,m,icl);
01363 }
01371 inline void
01372 atmost(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01373 IntConLevel icl=ICL_DEF) {
01374 count(home,x,y,IRT_LQ,m,icl);
01375 }
01380 inline void
01381 atmost(Home home, const IntVarArgs& x, int n, IntVar z,
01382 IntConLevel icl=ICL_DEF) {
01383 count(home,x,n,IRT_LQ,z,icl);
01384 }
01389 inline void
01390 atmost(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01391 IntConLevel icl=ICL_DEF) {
01392 count(home,x,y,IRT_LQ,z,icl);
01393 }
01401 inline void
01402 atmost(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01403 IntConLevel icl=ICL_DEF) {
01404 count(home,x,y,IRT_LQ,z,icl);
01405 }
01406
01411 inline void
01412 atleast(Home home, const IntVarArgs& x, int n, int m,
01413 IntConLevel icl=ICL_DEF) {
01414 count(home,x,n,IRT_GQ,m,icl);
01415 }
01420 inline void
01421 atleast(Home home, const IntVarArgs& x, IntVar y, int m,
01422 IntConLevel icl=ICL_DEF) {
01423 count(home,x,y,IRT_GQ,m,icl);
01424 }
01432 inline void
01433 atleast(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01434 IntConLevel icl=ICL_DEF) {
01435 count(home,x,y,IRT_GQ,m,icl);
01436 }
01441 inline void
01442 atleast(Home home, const IntVarArgs& x, int n, IntVar z,
01443 IntConLevel icl=ICL_DEF) {
01444 count(home,x,n,IRT_GQ,z,icl);
01445 }
01450 inline void
01451 atleast(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01452 IntConLevel icl=ICL_DEF) {
01453 count(home,x,y,IRT_GQ,z,icl);
01454 }
01462 inline void
01463 atleast(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01464 IntConLevel icl=ICL_DEF) {
01465 count(home,x,y,IRT_GQ,z,icl);
01466 }
01467
01472 inline void
01473 exactly(Home home, const IntVarArgs& x, int n, int m,
01474 IntConLevel icl=ICL_DEF) {
01475 count(home,x,n,IRT_EQ,m,icl);
01476 }
01481 inline void
01482 exactly(Home home, const IntVarArgs& x, IntVar y, int m,
01483 IntConLevel icl=ICL_DEF) {
01484 count(home,x,y,IRT_EQ,m,icl);
01485 }
01493 inline void
01494 exactly(Home home, const IntVarArgs& x, const IntArgs& y, int m,
01495 IntConLevel icl=ICL_DEF) {
01496 count(home,x,y,IRT_EQ,m,icl);
01497 }
01502 inline void
01503 exactly(Home home, const IntVarArgs& x, int n, IntVar z,
01504 IntConLevel icl=ICL_DEF) {
01505 count(home,x,n,IRT_EQ,z,icl);
01506 }
01511 inline void
01512 exactly(Home home, const IntVarArgs& x, IntVar y, IntVar z,
01513 IntConLevel icl=ICL_DEF) {
01514 count(home,x,y,IRT_EQ,z,icl);
01515 }
01523 inline void
01524 exactly(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z,
01525 IntConLevel icl=ICL_DEF) {
01526 count(home,x,y,IRT_EQ,z,icl);
01527 }
01530 inline void
01531 lex(Home home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y,
01532 IntConLevel icl=ICL_DEF) {
01533 rel(home,x,r,y,icl);
01534 }
01537 inline void
01538 lex(Home home, const BoolVarArgs& x, IntRelType r, const BoolVarArgs& y,
01539 IntConLevel icl=ICL_DEF) {
01540 rel(home,x,r,y,icl);
01541 }
01544 inline void
01545 values(Home home, const IntVarArgs& x, IntSet y,
01546 IntConLevel icl=ICL_DEF) {
01547 dom(home,x,y,icl);
01548 nvalues(home,x,IRT_EQ,y.size(),icl);
01549 }
01550
01552
01553 #ifdef GECODE_HAS_SET_VARS
01554
01569 inline void
01570 channel(Home home, const IntVarArgs& x, SetVar y) {
01571 rel(home,SOT_UNION,x,y);
01572 nvalues(home,x,IRT_EQ,expr(home,cardinality(y)));
01573 }
01574
01577 inline void
01578 range(Home home, const IntVarArgs& x, SetVar y, SetVar z) {
01579 element(home,SOT_UNION,x,y,z);
01580 }
01581
01587 inline void
01588 roots(Home home, const IntVarArgs& x, SetVar y, SetVar z) {
01589 SetVarArgs xiv(home,z.lubMax()+1,IntSet::empty,0,x.size()-1);
01590 channel(home,x,xiv);
01591 element(home,SOT_UNION,xiv,z,y);
01592 }
01593
01595 #endif
01596
01597 }
01598
01599 namespace Gecode {
01600
01601 template<class> class Matrix;
01602
01610 template<class A>
01611 class Slice {
01612 public:
01614 typedef typename ArrayTraits<A>::ArgsType ArgsType;
01615 private:
01616 ArgsType _r;
01617 unsigned int _fc,
01618 _tc,
01619 _fr,
01620 _tr;
01621 public:
01623 Slice(const Matrix<A>& a, int fc, int tc, int fr, int tr);
01627 Slice& reverse(void);
01629 operator ArgsType(void);
01631 operator Matrix<ArgsType>(void);
01632
01634 operator const ArgsType(void) const;
01636 operator const Matrix<ArgsType>(void) const;
01637 };
01638
01640 template<class A>
01641 typename Slice<A>::ArgsType
01642 operator+(const Slice<A>& x, const Slice<A>& y);
01643
01645 template<class A>
01646 typename Slice<A>::ArgsType
01647 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ArgsType& y);
01648
01650 template<class A>
01651 typename Slice<A>::ArgsType
01652 operator+(const typename ArrayTraits<A>::ArgsType& x, const Slice<A>& y);
01653
01655 template<class A>
01656 typename Slice<A>::ArgsType
01657 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ValueType& y);
01658
01660 template<class A>
01661 typename Slice<A>::ArgsType
01662 operator+(const typename ArrayTraits<A>::ValueType& x, const Slice<A>& y);
01663
01674 template<class A>
01675 class Matrix {
01676 public:
01678 typedef typename ArrayTraits<A>::ValueType ValueType;
01680 typedef typename ArrayTraits<A>::ArgsType ArgsType;
01681
01682 private:
01684 typedef typename ArrayTraits<A>::StorageType StorageType;
01685 StorageType _a;
01686 int _w;
01687 int _h;
01688
01689 public:
01702 Matrix(A a, int w, int h);
01703
01716 Matrix(A a, int n);
01717
01719 int width(void) const;
01721 int height(void) const;
01723 ArgsType const get_array(void) const;
01724
01730 ValueType& operator ()(int c, int r);
01731
01737 const ValueType& operator ()(int c, int r) const;
01738
01748 Slice<A> slice(int fc, int tc, int fr, int tr) const;
01749
01751 Slice<A> row(int r) const;
01752
01754 Slice<A> col(int c) const;
01755 };
01756
01760 template<class Char, class Traits, class A>
01761 std::basic_ostream<Char,Traits>&
01762 operator <<(std::basic_ostream<Char,Traits>& os, const Matrix<A>& m);
01763
01767 template<class Char, class Traits, class A>
01768 std::basic_ostream<Char,Traits>&
01769 operator <<(std::basic_ostream<Char,Traits>& os, const Slice<A>& s);
01770
01777 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y,
01778 IntVar z, IntConLevel icl=ICL_DEF);
01785 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y,
01786 BoolVar z, IntConLevel icl=ICL_DEF);
01793 void element(Home home, const Matrix<IntVarArgs>& m, IntVar x, IntVar y,
01794 IntVar z, IntConLevel icl=ICL_DEF);
01801 void element(Home home, const Matrix<BoolVarArgs>& m, IntVar x, IntVar y,
01802 BoolVar z, IntConLevel icl=ICL_DEF);
01803 #ifdef GECODE_HAS_SET_VARS
01804
01810 void element(Home home, const Matrix<IntSetArgs>& m, IntVar x, IntVar y,
01811 SetVar z);
01818 void element(Home home, const Matrix<SetVarArgs>& m, IntVar x, IntVar y,
01819 SetVar z);
01820 #endif
01821
01822 }
01823
01824 #include <gecode/minimodel/matrix.hpp>
01825
01826 namespace Gecode {
01827
01837 namespace MiniModel {
01838
01840 template<IntRelType irt>
01841 class OptimizeSpace : public Space {
01842 public:
01844 OptimizeSpace(void);
01846 OptimizeSpace(bool share, OptimizeSpace& s);
01848 virtual void constrain(const Space& best);
01850 virtual IntVar cost(void) const = 0;
01851 };
01852
01853 }
01854
01856 typedef MiniModel::OptimizeSpace<IRT_LE> MinimizeSpace;
01857
01859 typedef MiniModel::OptimizeSpace<IRT_GR> MaximizeSpace;
01861
01862 }
01863
01864 #include <gecode/minimodel/optimize.hpp>
01865
01866 #endif
01867
01868
01869
01870
