minimodel.hh
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Christian Schulte <schulte@gecode.org> 00005 * Guido Tack <tack@gecode.org> 00006 * Mikael Lagerkvist <lagerkvist@gecode.org> 00007 * 00008 * Copyright: 00009 * Christian Schulte, 2004 00010 * Guido Tack, 2004 00011 * Mikael Lagerkvist, 2005 00012 * 00013 * Last modified: 00014 * $Date: 2011-01-21 16:01:14 +0100 (Fri, 21 Jan 2011) $ by $Author: schulte $ 00015 * $Revision: 11553 $ 00016 * 00017 * This file is part of Gecode, the generic constraint 00018 * development environment: 00019 * http://www.gecode.org 00020 * 00021 * Permission is hereby granted, free of charge, to any person obtaining 00022 * a copy of this software and associated documentation files (the 00023 * "Software"), to deal in the Software without restriction, including 00024 * without limitation the rights to use, copy, modify, merge, publish, 00025 * distribute, sublicense, and/or sell copies of the Software, and to 00026 * permit persons to whom the Software is furnished to do so, subject to 00027 * the following conditions: 00028 * 00029 * The above copyright notice and this permission notice shall be 00030 * included in all copies or substantial portions of the Software. 00031 * 00032 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00033 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00034 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00035 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00036 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00037 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00038 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 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 * Support for DLLs under Windows 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 // Configure auto-linking 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 // IFDEF: GECODE_HAS_INT_VARS 01810 // STATISTICS: minimodel-any 01811