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: 2010-07-16 10:51:05 +0200 (Fri, 16 Jul 2010) $ by $Author: tack $ 00015 * $Revision: 11208 $ 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 } 00124 }; 00125 00127 class LinExpr { 00128 friend class LinRel; 00129 #ifdef GECODE_HAS_SET_VARS 00130 friend class SetExpr; 00131 #endif 00132 public: 00134 enum NodeType { 00135 NT_CONST, 00136 NT_VAR_INT, 00137 NT_VAR_BOOL, 00138 NT_NONLIN, 00139 NT_SUM_INT, 00140 NT_SUM_BOOL, 00141 NT_ADD, 00142 NT_SUB, 00143 NT_MUL 00144 }; 00145 private: 00147 class Node { 00148 public: 00150 unsigned int use; 00152 int n_int; 00154 int n_bool; 00156 NodeType t; 00158 Node *l, *r; 00160 union { 00162 Int::Linear::Term<Int::IntView>* ti; 00164 Int::Linear::Term<Int::BoolView>* tb; 00166 NonLinExpr* ne; 00167 } sum; 00169 int a, c; 00171 IntVar x_int; 00173 BoolVar x_bool; 00175 Node(void); 00177 GECODE_MINIMODEL_EXPORT 00178 void fill(Home home, IntConLevel icl, 00179 Int::Linear::Term<Int::IntView>*& ti, 00180 Int::Linear::Term<Int::BoolView>*& tb, 00181 double m, double& d) const; 00183 int fill(Home home, IntConLevel icl, 00184 Int::Linear::Term<Int::IntView>* ti, 00185 Int::Linear::Term<Int::BoolView>* tb) const; 00187 bool decrement(void); 00189 ~Node(void); 00191 static void* operator new(size_t size); 00193 static void operator delete(void* p,size_t size); 00194 }; 00195 Node* n; 00196 public: 00198 LinExpr(void); 00200 LinExpr(double c); 00202 LinExpr(const IntVar& x, int a=1); 00204 LinExpr(const BoolVar& x, int a=1); 00206 explicit LinExpr(const IntVarArgs& x); 00208 LinExpr(const IntArgs& a, const IntVarArgs& x); 00210 explicit LinExpr(const BoolVarArgs& x); 00212 LinExpr(const IntArgs& a, const BoolVarArgs& x); 00214 LinExpr(const LinExpr& e); 00216 LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1); 00218 LinExpr(const LinExpr& e0, NodeType t, int c); 00220 LinExpr(int a, const LinExpr& e); 00222 LinExpr(NonLinExpr* e); 00224 GECODE_MINIMODEL_EXPORT 00225 const LinExpr& operator =(const LinExpr& e); 00227 void post(Home home, IntRelType irt, IntConLevel icl) const; 00229 void post(Home home, IntRelType irt, const BoolVar& b, 00230 IntConLevel icl) const; 00232 IntVar post(Home home, IntConLevel icl) const; 00234 NonLinExpr* nle(void) const; 00236 GECODE_MINIMODEL_EXPORT 00237 ~LinExpr(void); 00238 }; 00239 00240 class BoolExpr; 00241 00243 class LinRel { 00244 friend class BoolExpr; 00245 private: 00247 LinExpr e; 00249 IntRelType irt; 00251 static IntRelType neg(IntRelType irt); 00253 LinRel(void); 00254 public: 00256 LinRel(const LinExpr& l, IntRelType irt, const LinExpr& r); 00258 LinRel(const LinExpr& l, IntRelType irt, int r); 00260 LinRel(int l, IntRelType irt, const LinExpr& r); 00262 void post(Home home, bool t, IntConLevel icl) const; 00264 void post(Home home, const BoolVar& b, bool t, IntConLevel icl) const; 00265 }; 00266 00285 00286 GECODE_MINIMODEL_EXPORT LinExpr 00287 operator +(int, const IntVar&); 00289 GECODE_MINIMODEL_EXPORT LinExpr 00290 operator +(int, const BoolVar&); 00292 GECODE_MINIMODEL_EXPORT LinExpr 00293 operator +(int, const LinExpr&); 00295 GECODE_MINIMODEL_EXPORT LinExpr 00296 operator +(const IntVar&, int); 00298 GECODE_MINIMODEL_EXPORT LinExpr 00299 operator +(const BoolVar&, int); 00301 GECODE_MINIMODEL_EXPORT LinExpr 00302 operator +(const LinExpr&, int); 00304 GECODE_MINIMODEL_EXPORT LinExpr 00305 operator +(const IntVar&, const IntVar&); 00307 GECODE_MINIMODEL_EXPORT LinExpr 00308 operator +(const IntVar&, const BoolVar&); 00310 GECODE_MINIMODEL_EXPORT LinExpr 00311 operator +(const BoolVar&, const IntVar&); 00313 GECODE_MINIMODEL_EXPORT LinExpr 00314 operator +(const BoolVar&, const BoolVar&); 00316 GECODE_MINIMODEL_EXPORT LinExpr 00317 operator +(const IntVar&, const LinExpr&); 00319 GECODE_MINIMODEL_EXPORT LinExpr 00320 operator +(const BoolVar&, const LinExpr&); 00322 GECODE_MINIMODEL_EXPORT LinExpr 00323 operator +(const LinExpr&, const IntVar&); 00325 GECODE_MINIMODEL_EXPORT LinExpr 00326 operator +(const LinExpr&, const BoolVar&); 00328 GECODE_MINIMODEL_EXPORT LinExpr 00329 operator +(const LinExpr&, const LinExpr&); 00330 00332 GECODE_MINIMODEL_EXPORT LinExpr 00333 operator -(int, const IntVar&); 00335 GECODE_MINIMODEL_EXPORT LinExpr 00336 operator -(int, const BoolVar&); 00338 GECODE_MINIMODEL_EXPORT LinExpr 00339 operator -(int, const LinExpr&); 00341 GECODE_MINIMODEL_EXPORT LinExpr 00342 operator -(const IntVar&, int); 00344 GECODE_MINIMODEL_EXPORT LinExpr 00345 operator -(const BoolVar&, int); 00347 GECODE_MINIMODEL_EXPORT LinExpr 00348 operator -(const LinExpr&, int); 00350 GECODE_MINIMODEL_EXPORT LinExpr 00351 operator -(const IntVar&, const IntVar&); 00353 GECODE_MINIMODEL_EXPORT LinExpr 00354 operator -(const IntVar&, const BoolVar&); 00356 GECODE_MINIMODEL_EXPORT LinExpr 00357 operator -(const BoolVar&, const IntVar&); 00359 GECODE_MINIMODEL_EXPORT LinExpr 00360 operator -(const BoolVar&, const BoolVar&); 00362 GECODE_MINIMODEL_EXPORT LinExpr 00363 operator -(const IntVar&, const LinExpr&); 00365 GECODE_MINIMODEL_EXPORT LinExpr 00366 operator -(const BoolVar&, const LinExpr&); 00368 GECODE_MINIMODEL_EXPORT LinExpr 00369 operator -(const LinExpr&, const IntVar&); 00371 GECODE_MINIMODEL_EXPORT LinExpr 00372 operator -(const LinExpr&, const BoolVar&); 00374 GECODE_MINIMODEL_EXPORT LinExpr 00375 operator -(const LinExpr&, const LinExpr&); 00376 00378 GECODE_MINIMODEL_EXPORT LinExpr 00379 operator -(const IntVar&); 00381 GECODE_MINIMODEL_EXPORT LinExpr 00382 operator -(const BoolVar&); 00384 GECODE_MINIMODEL_EXPORT LinExpr 00385 operator -(const LinExpr&); 00386 00388 GECODE_MINIMODEL_EXPORT LinExpr 00389 operator *(int, const IntVar&); 00391 GECODE_MINIMODEL_EXPORT LinExpr 00392 operator *(int, const BoolVar&); 00394 GECODE_MINIMODEL_EXPORT LinExpr 00395 operator *(const IntVar&, int); 00397 GECODE_MINIMODEL_EXPORT LinExpr 00398 operator *(const BoolVar&, int); 00400 GECODE_MINIMODEL_EXPORT LinExpr 00401 operator *(const LinExpr&, int); 00403 GECODE_MINIMODEL_EXPORT LinExpr 00404 operator *(int, const LinExpr&); 00405 00407 GECODE_MINIMODEL_EXPORT LinExpr 00408 sum(const IntVarArgs& x); 00410 GECODE_MINIMODEL_EXPORT LinExpr 00411 sum(const IntArgs& a, const IntVarArgs& x); 00413 GECODE_MINIMODEL_EXPORT LinExpr 00414 sum(const BoolVarArgs& x); 00416 GECODE_MINIMODEL_EXPORT LinExpr 00417 sum(const IntArgs& a, const BoolVarArgs& x); 00418 00420 GECODE_MINIMODEL_EXPORT LinRel 00421 operator ==(int l, const IntVar& r); 00423 GECODE_MINIMODEL_EXPORT LinRel 00424 operator ==(int l, const BoolVar& r); 00426 GECODE_MINIMODEL_EXPORT LinRel 00427 operator ==(int l, const LinExpr& r); 00429 GECODE_MINIMODEL_EXPORT LinRel 00430 operator ==(const IntVar& l, int r); 00432 GECODE_MINIMODEL_EXPORT LinRel 00433 operator ==(const BoolVar& l, int r); 00435 GECODE_MINIMODEL_EXPORT LinRel 00436 operator ==(const LinExpr& l, int r); 00438 GECODE_MINIMODEL_EXPORT LinRel 00439 operator ==(const IntVar& l, const IntVar& r); 00441 GECODE_MINIMODEL_EXPORT LinRel 00442 operator ==(const IntVar& l, const BoolVar& r); 00444 GECODE_MINIMODEL_EXPORT LinRel 00445 operator ==(const BoolVar& l, const IntVar& r); 00447 GECODE_MINIMODEL_EXPORT LinRel 00448 operator ==(const BoolVar& l, const BoolVar& r); 00450 GECODE_MINIMODEL_EXPORT LinRel 00451 operator ==(const IntVar& l, const LinExpr& r); 00453 GECODE_MINIMODEL_EXPORT LinRel 00454 operator ==(const BoolVar& l, const LinExpr& r); 00456 GECODE_MINIMODEL_EXPORT LinRel 00457 operator ==(const LinExpr& l, const IntVar& r); 00459 GECODE_MINIMODEL_EXPORT LinRel 00460 operator ==(const LinExpr& l, const BoolVar& r); 00462 GECODE_MINIMODEL_EXPORT LinRel 00463 operator ==(const LinExpr& l, const LinExpr& r); 00464 00466 GECODE_MINIMODEL_EXPORT LinRel 00467 operator !=(int l, const IntVar& r); 00469 GECODE_MINIMODEL_EXPORT LinRel 00470 operator !=(int l, const BoolVar& r); 00472 GECODE_MINIMODEL_EXPORT LinRel 00473 operator !=(int l, const LinExpr& r); 00475 GECODE_MINIMODEL_EXPORT LinRel 00476 operator !=(const IntVar& l, int r); 00478 GECODE_MINIMODEL_EXPORT LinRel 00479 operator !=(const BoolVar& l, int r); 00481 GECODE_MINIMODEL_EXPORT LinRel 00482 operator !=(const LinExpr& l, int r); 00484 GECODE_MINIMODEL_EXPORT LinRel 00485 operator !=(const IntVar& l, const IntVar& r); 00487 GECODE_MINIMODEL_EXPORT LinRel 00488 operator !=(const IntVar& l, const BoolVar& r); 00490 GECODE_MINIMODEL_EXPORT LinRel 00491 operator !=(const BoolVar& l, const IntVar& r); 00493 GECODE_MINIMODEL_EXPORT LinRel 00494 operator !=(const BoolVar& l, const BoolVar& r); 00496 GECODE_MINIMODEL_EXPORT LinRel 00497 operator !=(const IntVar& l, const LinExpr& r); 00499 GECODE_MINIMODEL_EXPORT LinRel 00500 operator !=(const BoolVar& l, const LinExpr& r); 00502 GECODE_MINIMODEL_EXPORT LinRel 00503 operator !=(const LinExpr& l, const IntVar& r); 00505 GECODE_MINIMODEL_EXPORT LinRel 00506 operator !=(const LinExpr& l, const BoolVar& r); 00508 GECODE_MINIMODEL_EXPORT LinRel 00509 operator !=(const LinExpr& l, const LinExpr& r); 00510 00512 GECODE_MINIMODEL_EXPORT LinRel 00513 operator <(int l, const IntVar& r); 00515 GECODE_MINIMODEL_EXPORT LinRel 00516 operator <(int l, const BoolVar& r); 00518 GECODE_MINIMODEL_EXPORT LinRel 00519 operator <(int l, const LinExpr& r); 00521 GECODE_MINIMODEL_EXPORT LinRel 00522 operator <(const IntVar& l, int r); 00524 GECODE_MINIMODEL_EXPORT LinRel 00525 operator <(const BoolVar& l, int r); 00527 GECODE_MINIMODEL_EXPORT LinRel 00528 operator <(const LinExpr& l, int r); 00530 GECODE_MINIMODEL_EXPORT LinRel 00531 operator <(const IntVar& l, const IntVar& r); 00533 GECODE_MINIMODEL_EXPORT LinRel 00534 operator <(const IntVar& l, const BoolVar& r); 00536 GECODE_MINIMODEL_EXPORT LinRel 00537 operator <(const BoolVar& l, const IntVar& r); 00539 GECODE_MINIMODEL_EXPORT LinRel 00540 operator <(const BoolVar& l, const BoolVar& r); 00542 GECODE_MINIMODEL_EXPORT LinRel 00543 operator <(const IntVar& l, const LinExpr& r); 00545 GECODE_MINIMODEL_EXPORT LinRel 00546 operator <(const BoolVar& l, const LinExpr& r); 00548 GECODE_MINIMODEL_EXPORT LinRel 00549 operator <(const LinExpr& l, const IntVar& r); 00551 GECODE_MINIMODEL_EXPORT LinRel 00552 operator <(const LinExpr& l, const BoolVar& r); 00554 GECODE_MINIMODEL_EXPORT LinRel 00555 operator <(const LinExpr& l, const LinExpr& r); 00556 00558 GECODE_MINIMODEL_EXPORT LinRel 00559 operator <=(int l, const IntVar& r); 00561 GECODE_MINIMODEL_EXPORT LinRel 00562 operator <=(int l, const BoolVar& r); 00564 GECODE_MINIMODEL_EXPORT LinRel 00565 operator <=(int l, const LinExpr& r); 00567 GECODE_MINIMODEL_EXPORT LinRel 00568 operator <=(const IntVar& l, int r); 00570 GECODE_MINIMODEL_EXPORT LinRel 00571 operator <=(const BoolVar& l, int r); 00573 GECODE_MINIMODEL_EXPORT LinRel 00574 operator <=(const LinExpr& l, int r); 00576 GECODE_MINIMODEL_EXPORT LinRel 00577 operator <=(const IntVar& l, const IntVar& r); 00579 GECODE_MINIMODEL_EXPORT LinRel 00580 operator <=(const IntVar& l, const BoolVar& r); 00582 GECODE_MINIMODEL_EXPORT LinRel 00583 operator <=(const BoolVar& l, const IntVar& r); 00585 GECODE_MINIMODEL_EXPORT LinRel 00586 operator <=(const BoolVar& l, const BoolVar& r); 00588 GECODE_MINIMODEL_EXPORT LinRel 00589 operator <=(const IntVar& l, const LinExpr& r); 00591 GECODE_MINIMODEL_EXPORT LinRel 00592 operator <=(const BoolVar& l, const LinExpr& r); 00594 GECODE_MINIMODEL_EXPORT LinRel 00595 operator <=(const LinExpr& l, const IntVar& r); 00597 GECODE_MINIMODEL_EXPORT LinRel 00598 operator <=(const LinExpr& l, const BoolVar& r); 00600 GECODE_MINIMODEL_EXPORT LinRel 00601 operator <=(const LinExpr& l, const LinExpr& r); 00602 00604 GECODE_MINIMODEL_EXPORT LinRel 00605 operator >(int l, const IntVar& r); 00607 GECODE_MINIMODEL_EXPORT LinRel 00608 operator >(int l, const BoolVar& r); 00610 GECODE_MINIMODEL_EXPORT LinRel 00611 operator >(int l, const LinExpr& r); 00613 GECODE_MINIMODEL_EXPORT LinRel 00614 operator >(const IntVar& l, int r); 00616 GECODE_MINIMODEL_EXPORT LinRel 00617 operator >(const BoolVar& l, int r); 00619 GECODE_MINIMODEL_EXPORT LinRel 00620 operator >(const LinExpr& l, int r); 00622 GECODE_MINIMODEL_EXPORT LinRel 00623 operator >(const IntVar& l, const IntVar& r); 00625 GECODE_MINIMODEL_EXPORT LinRel 00626 operator >(const IntVar& l, const BoolVar& r); 00628 GECODE_MINIMODEL_EXPORT LinRel 00629 operator >(const BoolVar& l, const IntVar& r); 00631 GECODE_MINIMODEL_EXPORT LinRel 00632 operator >(const BoolVar& l, const BoolVar& r); 00634 GECODE_MINIMODEL_EXPORT LinRel 00635 operator >(const IntVar& l, const LinExpr& r); 00637 GECODE_MINIMODEL_EXPORT LinRel 00638 operator >(const BoolVar& l, const LinExpr& r); 00640 GECODE_MINIMODEL_EXPORT LinRel 00641 operator >(const LinExpr& l, const IntVar& r); 00643 GECODE_MINIMODEL_EXPORT LinRel 00644 operator >(const LinExpr& l, const BoolVar& r); 00646 GECODE_MINIMODEL_EXPORT LinRel 00647 operator >(const LinExpr& l, const LinExpr& r); 00648 00650 GECODE_MINIMODEL_EXPORT LinRel 00651 operator >=(int l, const IntVar& r); 00653 GECODE_MINIMODEL_EXPORT LinRel 00654 operator >=(int l, const BoolVar& r); 00656 GECODE_MINIMODEL_EXPORT LinRel 00657 operator >=(int l, const LinExpr& r); 00659 GECODE_MINIMODEL_EXPORT LinRel 00660 operator >=(const IntVar& l, int r); 00662 GECODE_MINIMODEL_EXPORT LinRel 00663 operator >=(const BoolVar& l, int r); 00665 GECODE_MINIMODEL_EXPORT LinRel 00666 operator >=(const LinExpr& l, int r); 00668 GECODE_MINIMODEL_EXPORT LinRel 00669 operator >=(const IntVar& l, const IntVar& r); 00671 GECODE_MINIMODEL_EXPORT LinRel 00672 operator >=(const IntVar& l, const BoolVar& r); 00674 GECODE_MINIMODEL_EXPORT LinRel 00675 operator >=(const BoolVar& l, const IntVar& r); 00677 GECODE_MINIMODEL_EXPORT LinRel 00678 operator >=(const BoolVar& l, const BoolVar& r); 00680 GECODE_MINIMODEL_EXPORT LinRel 00681 operator >=(const IntVar& l, const LinExpr& r); 00683 GECODE_MINIMODEL_EXPORT LinRel 00684 operator >=(const BoolVar& l, const LinExpr& r); 00686 GECODE_MINIMODEL_EXPORT LinRel 00687 operator >=(const LinExpr& l, const IntVar& r); 00689 GECODE_MINIMODEL_EXPORT LinRel 00690 operator >=(const LinExpr& l, const BoolVar& r); 00692 GECODE_MINIMODEL_EXPORT LinRel 00693 operator >=(const LinExpr& l, const LinExpr& r); 00695 00696 #ifdef GECODE_HAS_SET_VARS 00697 00698 class SetExpr { 00699 public: 00701 enum NodeType { 00702 NT_VAR, 00703 NT_CONST, 00704 NT_LEXP, 00705 NT_CMPL, 00706 NT_INTER, 00707 NT_UNION, 00708 NT_DUNION 00709 }; 00711 static bool same(NodeType t0, NodeType t1); 00713 class Node { 00714 public: 00716 unsigned int use; 00718 int same; 00720 NodeType t; 00722 Node *l, *r; 00724 SetVar x; 00726 IntSet s; 00728 LinExpr e; 00729 00731 Node(void); 00733 GECODE_MINIMODEL_EXPORT 00734 bool decrement(void); 00736 static void* operator new(size_t size); 00738 static void operator delete(void* p, size_t size); 00739 }; 00741 class NNF { 00742 public: 00744 NodeType t; 00746 int p; 00748 int n; 00750 union { 00752 struct { 00754 NNF* l; 00756 NNF* r; 00757 } b; 00759 struct { 00761 Node* x; 00762 } a; 00763 } u; 00765 bool neg; 00767 GECODE_MINIMODEL_EXPORT 00768 static NNF* nnf(Region& r, Node* n, bool neg); 00770 GECODE_MINIMODEL_EXPORT 00771 void post(Home home, NodeType t, SetVarArgs& b, int& i) const; 00773 GECODE_MINIMODEL_EXPORT 00774 void post(Home home, SetRelType srt, SetVar s) const; 00776 GECODE_MINIMODEL_EXPORT 00777 void post(Home home, SetRelType srt, SetVar s, BoolVar b) const; 00779 GECODE_MINIMODEL_EXPORT 00780 void post(Home home, SetRelType srt, const NNF* n) const; 00782 GECODE_MINIMODEL_EXPORT 00783 void post(Home home, BoolVar b, bool t, SetRelType srt, 00784 const NNF* n) const; 00786 static void* operator new(size_t s, Region& r); 00788 static void operator delete(void*); 00790 static void operator delete(void*, Region&); 00791 }; 00792 private: 00794 Node* n; 00795 public: 00797 SetExpr(void); 00799 SetExpr(const SetExpr& e); 00801 SetExpr(const SetExpr& l, NodeType t, const SetExpr& r); 00803 SetExpr(const SetVar& x); 00805 explicit SetExpr(const LinExpr& x); 00807 SetExpr(const IntSet& s); 00809 SetExpr(const SetExpr& e, NodeType t); 00811 SetVar post(Home home) const; 00813 void post(Home home, SetRelType srt, const SetExpr& e) const; 00815 void post(Home home, BoolVar b, bool t, 00816 SetRelType srt, const SetExpr& e) const; 00818 GECODE_MINIMODEL_EXPORT 00819 const SetExpr& operator =(const SetExpr& e); 00821 GECODE_MINIMODEL_EXPORT 00822 ~SetExpr(void); 00823 }; 00824 00826 class SetCmpRel { 00827 public: 00829 SetExpr l; 00831 SetExpr r; 00833 SetRelType srt; 00835 SetCmpRel(const SetExpr& l, SetRelType srt, const SetExpr& r); 00836 }; 00837 00839 class SetRel { 00840 private: 00842 SetExpr _e0; 00844 SetRelType _srt; 00846 SetExpr _e1; 00847 public: 00849 SetRel(void); 00851 SetRel(const SetExpr& e0, SetRelType srt, const SetExpr& e1); 00853 SetRel(const SetCmpRel& r); 00855 void post(Home home, bool t) const; 00857 void post(Home home, BoolVar b, bool t) const; 00858 }; 00859 00870 00871 GECODE_MINIMODEL_EXPORT SetExpr 00872 singleton(const LinExpr&); 00874 GECODE_MINIMODEL_EXPORT SetExpr 00875 operator -(const SetExpr&); 00877 GECODE_MINIMODEL_EXPORT SetExpr 00878 operator &(const SetExpr&, const SetExpr&); 00880 GECODE_MINIMODEL_EXPORT SetExpr 00881 operator |(const SetExpr&, const SetExpr&); 00883 GECODE_MINIMODEL_EXPORT SetExpr 00884 operator +(const SetExpr&, const SetExpr&); 00886 GECODE_MINIMODEL_EXPORT SetExpr 00887 operator -(const SetExpr&, const SetExpr&); 00888 00890 GECODE_MINIMODEL_EXPORT SetExpr 00891 inter(const SetVarArgs&); 00893 GECODE_MINIMODEL_EXPORT SetExpr 00894 setunion(const SetVarArgs&); 00896 GECODE_MINIMODEL_EXPORT SetExpr 00897 setdunion(const SetVarArgs&); 00898 00900 GECODE_MINIMODEL_EXPORT LinExpr 00901 cardinality(const SetExpr&); 00903 GECODE_MINIMODEL_EXPORT LinExpr 00904 min(const SetExpr&); 00906 GECODE_MINIMODEL_EXPORT LinExpr 00907 max(const SetExpr&); 00908 00910 GECODE_MINIMODEL_EXPORT SetRel 00911 operator ==(const SetExpr&, const SetExpr&); 00913 GECODE_MINIMODEL_EXPORT SetRel 00914 operator !=(const SetExpr&, const SetExpr&); 00916 GECODE_MINIMODEL_EXPORT SetCmpRel 00917 operator <=(const SetExpr&, const SetExpr&); 00919 GECODE_MINIMODEL_EXPORT BoolExpr 00920 operator <=(const SetCmpRel&, const SetExpr&); 00922 GECODE_MINIMODEL_EXPORT SetCmpRel 00923 operator >=(const SetExpr&, const SetExpr&); 00925 GECODE_MINIMODEL_EXPORT BoolExpr 00926 operator >=(const SetCmpRel&, const SetExpr&); 00928 GECODE_MINIMODEL_EXPORT SetRel 00929 operator ||(const SetExpr&, const SetExpr&); 00931 #endif 00932 00934 class BoolExpr { 00935 public: 00937 enum NodeType { 00938 NT_VAR, 00939 NT_NOT, 00940 NT_AND, 00941 NT_OR, 00942 NT_EQV, 00943 NT_RLIN, 00944 NT_RSET 00945 }; 00947 class Node { 00948 public: 00950 unsigned int use; 00952 int same; 00954 NodeType t; 00956 Node *l, *r; 00958 BoolVar x; 00960 LinRel rl; 00961 #ifdef GECODE_HAS_SET_VARS 00962 00963 SetRel rs; 00964 #endif 00965 00967 Node(void); 00969 GECODE_MINIMODEL_EXPORT 00970 bool decrement(void); 00972 static void* operator new(size_t size); 00974 static void operator delete(void* p, size_t size); 00975 }; 00977 class NNF { 00978 public: 00980 NodeType t; 00982 int p; 00984 int n; 00986 union { 00988 struct { 00990 NNF* l; 00992 NNF* r; 00993 } b; 00995 struct { 00997 bool neg; 00999 Node* x; 01000 } a; 01001 } u; 01003 GECODE_MINIMODEL_EXPORT 01004 static NNF* nnf(Region& r, Node* n, bool neg); 01006 GECODE_MINIMODEL_EXPORT 01007 void post(Home home, NodeType t, 01008 BoolVarArgs& bp, BoolVarArgs& bn, 01009 int& ip, int& in, 01010 IntConLevel icl) const; 01012 GECODE_MINIMODEL_EXPORT 01013 BoolVar expr(Home home, IntConLevel icl) const; 01015 GECODE_MINIMODEL_EXPORT 01016 void rel(Home home, IntConLevel icl) const; 01018 static void* operator new(size_t s, Region& r); 01020 static void operator delete(void*); 01022 static void operator delete(void*, Region&); 01023 }; 01024 private: 01026 Node* n; 01027 public: 01029 BoolExpr(const BoolExpr& e); 01031 BoolExpr(const BoolExpr& l, NodeType t, const BoolExpr& r); 01033 BoolExpr(const BoolVar& x); 01035 BoolExpr(const BoolExpr& e, NodeType t); 01037 BoolExpr(const LinRel& rl); 01038 #ifdef GECODE_HAS_SET_VARS 01039 01040 BoolExpr(const SetRel& rs); 01042 BoolExpr(const SetCmpRel& rs); 01043 #endif 01044 01045 BoolVar expr(Home home, IntConLevel icl) const; 01047 void rel(Home home, IntConLevel icl) const; 01049 GECODE_MINIMODEL_EXPORT 01050 const BoolExpr& operator =(const BoolExpr& e); 01052 GECODE_MINIMODEL_EXPORT 01053 ~BoolExpr(void); 01054 }; 01055 01070 01071 GECODE_MINIMODEL_EXPORT BoolExpr 01072 operator !(const BoolExpr&); 01074 GECODE_MINIMODEL_EXPORT BoolExpr 01075 operator &&(const BoolExpr&, const BoolExpr&); 01077 GECODE_MINIMODEL_EXPORT BoolExpr 01078 operator ||(const BoolExpr&, const BoolExpr&); 01080 GECODE_MINIMODEL_EXPORT BoolExpr 01081 operator ^(const BoolExpr&, const BoolExpr&); 01082 01084 GECODE_MINIMODEL_EXPORT BoolExpr 01085 operator !=(const BoolExpr&, const BoolExpr&); 01087 GECODE_MINIMODEL_EXPORT BoolExpr 01088 operator ==(const BoolExpr&, const BoolExpr&); 01090 GECODE_MINIMODEL_EXPORT BoolExpr 01091 operator >>(const BoolExpr&, const BoolExpr&); 01093 GECODE_MINIMODEL_EXPORT BoolExpr 01094 operator <<(const BoolExpr&, const BoolExpr&); 01095 01097 01104 01105 GECODE_MINIMODEL_EXPORT IntVar 01106 expr(Home home, const LinExpr& e, IntConLevel icl=ICL_DEF); 01107 #ifdef GECODE_HAS_SET_VARS 01108 01109 GECODE_MINIMODEL_EXPORT SetVar 01110 expr(Home home, const SetExpr& e); 01111 #endif 01112 01113 GECODE_MINIMODEL_EXPORT BoolVar 01114 expr(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF); 01116 GECODE_MINIMODEL_EXPORT void 01117 rel(Home home, const BoolExpr& e, IntConLevel icl=ICL_DEF); 01119 01120 } 01121 01122 #include <gecode/minimodel/lin-expr.hpp> 01123 #include <gecode/minimodel/lin-rel.hpp> 01124 #include <gecode/minimodel/bool-expr.hpp> 01125 #include <gecode/minimodel/set-expr.hpp> 01126 #include <gecode/minimodel/set-rel.hpp> 01127 01128 namespace Gecode { 01129 01130 namespace MiniModel { 01131 class ExpInfo; 01132 } 01133 01139 class GECODE_MINIMODEL_EXPORT REG { 01140 friend class MiniModel::ExpInfo; 01141 private: 01143 class Exp; 01145 Exp* e; 01147 REG(Exp* e); 01148 public: 01150 REG(void); 01152 REG(int s); 01159 REG(const IntArgs& x); 01160 01162 REG(const REG& r); 01164 const REG& operator =(const REG& r); 01165 01167 REG operator +(const REG& r); 01169 REG& operator +=(const REG& r); 01171 REG operator |(const REG& r); 01173 REG& operator |=(const REG& r); 01175 REG operator *(void); 01177 REG operator +(void); 01179 REG operator ()(unsigned int n, unsigned int m); 01181 REG operator ()(unsigned int n); 01183 template<class Char, class Traits> 01184 std::basic_ostream<Char,Traits>& 01185 print(std::basic_ostream<Char,Traits>& os) const; 01187 operator DFA(void); 01189 ~REG(void); 01190 }; 01191 01195 template<class Char, class Traits> 01196 std::basic_ostream<Char,Traits>& 01197 operator <<(std::basic_ostream<Char,Traits>& os, const REG& r); 01198 01199 01206 01207 GECODE_MINIMODEL_EXPORT LinExpr 01208 abs(const LinExpr& e); 01210 GECODE_MINIMODEL_EXPORT LinExpr 01211 min(const LinExpr& x, const LinExpr& y); 01213 GECODE_MINIMODEL_EXPORT LinExpr 01214 min(const IntVarArgs& x); 01216 GECODE_MINIMODEL_EXPORT LinExpr 01217 max(const LinExpr& x, const LinExpr& y); 01219 GECODE_MINIMODEL_EXPORT LinExpr 01220 max(const IntVarArgs& x); 01222 GECODE_MINIMODEL_EXPORT LinExpr 01223 operator *(const LinExpr& x, const LinExpr& y); 01225 GECODE_MINIMODEL_EXPORT LinExpr 01226 operator /(const LinExpr& x, const LinExpr& y); 01228 GECODE_MINIMODEL_EXPORT LinExpr 01229 operator %(const LinExpr& x, const LinExpr& y); 01231 GECODE_MINIMODEL_EXPORT LinExpr 01232 sqr(const LinExpr& x); 01234 GECODE_MINIMODEL_EXPORT LinExpr 01235 sqrt(const LinExpr& x); 01237 GECODE_MINIMODEL_EXPORT LinExpr 01238 element(const IntVarArgs& x, const LinExpr& y); 01240 GECODE_MINIMODEL_EXPORT LinExpr 01241 element(const IntArgs& x, const LinExpr& y); 01243 01250 01251 inline BoolVar 01252 channel(Home home, IntVar x, 01253 IntConLevel icl=ICL_DEF) { 01254 (void) icl; 01255 BoolVar b(home,0,1); channel(home,b,x); 01256 return b; 01257 } 01259 inline IntVar 01260 channel(Home home, BoolVar b, 01261 IntConLevel icl=ICL_DEF) { 01262 (void) icl; 01263 IntVar x(home,0,1); channel(home,b,x); 01264 return x; 01265 } 01267 01268 } 01269 01270 namespace Gecode { 01271 01286 inline void 01287 atmost(Home home, const IntVarArgs& x, int n, int m, 01288 IntConLevel icl=ICL_DEF) { 01289 count(home,x,n,IRT_LQ,m,icl); 01290 } 01295 inline void 01296 atmost(Home home, const IntVarArgs& x, IntVar y, int m, 01297 IntConLevel icl=ICL_DEF) { 01298 count(home,x,y,IRT_LQ,m,icl); 01299 } 01307 inline void 01308 atmost(Home home, const IntVarArgs& x, const IntArgs& y, int m, 01309 IntConLevel icl=ICL_DEF) { 01310 count(home,x,y,IRT_LQ,m,icl); 01311 } 01316 inline void 01317 atmost(Home home, const IntVarArgs& x, int n, IntVar z, 01318 IntConLevel icl=ICL_DEF) { 01319 count(home,x,n,IRT_LQ,z,icl); 01320 } 01325 inline void 01326 atmost(Home home, const IntVarArgs& x, IntVar y, IntVar z, 01327 IntConLevel icl=ICL_DEF) { 01328 count(home,x,y,IRT_LQ,z,icl); 01329 } 01337 inline void 01338 atmost(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z, 01339 IntConLevel icl=ICL_DEF) { 01340 count(home,x,y,IRT_LQ,z,icl); 01341 } 01342 01347 inline void 01348 atleast(Home home, const IntVarArgs& x, int n, int m, 01349 IntConLevel icl=ICL_DEF) { 01350 count(home,x,n,IRT_GQ,m,icl); 01351 } 01356 inline void 01357 atleast(Home home, const IntVarArgs& x, IntVar y, int m, 01358 IntConLevel icl=ICL_DEF) { 01359 count(home,x,y,IRT_GQ,m,icl); 01360 } 01368 inline void 01369 atleast(Home home, const IntVarArgs& x, const IntArgs& y, int m, 01370 IntConLevel icl=ICL_DEF) { 01371 count(home,x,y,IRT_GQ,m,icl); 01372 } 01377 inline void 01378 atleast(Home home, const IntVarArgs& x, int n, IntVar z, 01379 IntConLevel icl=ICL_DEF) { 01380 count(home,x,n,IRT_GQ,z,icl); 01381 } 01386 inline void 01387 atleast(Home home, const IntVarArgs& x, IntVar y, IntVar z, 01388 IntConLevel icl=ICL_DEF) { 01389 count(home,x,y,IRT_GQ,z,icl); 01390 } 01398 inline void 01399 atleast(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z, 01400 IntConLevel icl=ICL_DEF) { 01401 count(home,x,y,IRT_GQ,z,icl); 01402 } 01403 01408 inline void 01409 exactly(Home home, const IntVarArgs& x, int n, int m, 01410 IntConLevel icl=ICL_DEF) { 01411 count(home,x,n,IRT_EQ,m,icl); 01412 } 01417 inline void 01418 exactly(Home home, const IntVarArgs& x, IntVar y, int m, 01419 IntConLevel icl=ICL_DEF) { 01420 count(home,x,y,IRT_EQ,m,icl); 01421 } 01429 inline void 01430 exactly(Home home, const IntVarArgs& x, const IntArgs& y, int m, 01431 IntConLevel icl=ICL_DEF) { 01432 count(home,x,y,IRT_EQ,m,icl); 01433 } 01438 inline void 01439 exactly(Home home, const IntVarArgs& x, int n, IntVar z, 01440 IntConLevel icl=ICL_DEF) { 01441 count(home,x,n,IRT_EQ,z,icl); 01442 } 01447 inline void 01448 exactly(Home home, const IntVarArgs& x, IntVar y, IntVar z, 01449 IntConLevel icl=ICL_DEF) { 01450 count(home,x,y,IRT_EQ,z,icl); 01451 } 01459 inline void 01460 exactly(Home home, const IntVarArgs& x, const IntArgs& y, IntVar z, 01461 IntConLevel icl=ICL_DEF) { 01462 count(home,x,y,IRT_EQ,z,icl); 01463 } 01469 inline void 01470 lex(Home home, const IntVarArgs& x, IntRelType r, const IntVarArgs& y, 01471 IntConLevel icl=ICL_DEF) { 01472 rel(home,x,r,y,icl); 01473 } 01479 inline void 01480 lex(Home home, const BoolVarArgs& x, IntRelType r, const BoolVarArgs& y, 01481 IntConLevel icl=ICL_DEF) { 01482 rel(home,x,r,y,icl); 01483 } 01484 01486 01487 } 01488 01489 namespace Gecode { 01490 01491 template<class> class Matrix; 01492 01500 template<class A> 01501 class Slice { 01502 public: 01504 typedef typename ArrayTraits<A>::ArgsType ArgsType; 01505 private: 01506 ArgsType _r; 01507 unsigned int _fc, 01508 _tc, 01509 _fr, 01510 _tr; 01511 public: 01513 Slice(const Matrix<A>& a, int fc, int tc, int fr, int tr); 01517 Slice& reverse(void); 01519 operator ArgsType(void); 01521 operator Matrix<ArgsType>(void); 01522 01524 operator const ArgsType(void) const; 01526 operator const Matrix<ArgsType>(void) const; 01527 }; 01528 01530 template<class A> 01531 typename Slice<A>::ArgsType 01532 operator+(const Slice<A>& x, const Slice<A>& y); 01533 01535 template<class A> 01536 typename Slice<A>::ArgsType 01537 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ArgsType& y); 01538 01540 template<class A> 01541 typename Slice<A>::ArgsType 01542 operator+(const typename ArrayTraits<A>::ArgsType& x, const Slice<A>& y); 01543 01545 template<class A> 01546 typename Slice<A>::ArgsType 01547 operator+(const Slice<A>& x, const typename ArrayTraits<A>::ValueType& y); 01548 01550 template<class A> 01551 typename Slice<A>::ArgsType 01552 operator+(const typename ArrayTraits<A>::ValueType& x, const Slice<A>& y); 01553 01564 template<class A> 01565 class Matrix { 01566 public: 01568 typedef typename ArrayTraits<A>::ValueType ValueType; 01570 typedef typename ArrayTraits<A>::ArgsType ArgsType; 01571 01572 private: 01574 typedef typename ArrayTraits<A>::StorageType StorageType; 01575 StorageType _a; 01576 int _w; 01577 int _h; 01578 01579 public: 01592 Matrix(A a, int w, int h); 01593 01606 Matrix(A a, int n); 01607 01609 int width(void) const; 01611 int height(void) const; 01613 ArgsType const get_array(void) const; 01614 01620 ValueType& operator ()(int c, int r); 01621 01627 const ValueType& operator ()(int c, int r) const; 01628 01638 Slice<A> slice(int fc, int tc, int fr, int tr) const; 01639 01641 Slice<A> row(int r) const; 01642 01644 Slice<A> col(int c) const; 01645 }; 01646 01650 template<class Char, class Traits, class A> 01651 std::basic_ostream<Char,Traits>& 01652 operator <<(std::basic_ostream<Char,Traits>& os, const Matrix<A>& m); 01653 01657 template<class Char, class Traits, class A> 01658 std::basic_ostream<Char,Traits>& 01659 operator <<(std::basic_ostream<Char,Traits>& os, const Slice<A>& s); 01660 01667 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y, 01668 IntVar z, IntConLevel icl=ICL_DEF); 01675 void element(Home home, const Matrix<IntArgs>& m, IntVar x, IntVar y, 01676 BoolVar z, IntConLevel icl=ICL_DEF); 01683 void element(Home home, const Matrix<IntVarArgs>& m, IntVar x, IntVar y, 01684 IntVar z, IntConLevel icl=ICL_DEF); 01691 void element(Home home, const Matrix<BoolVarArgs>& m, IntVar x, IntVar y, 01692 BoolVar z, IntConLevel icl=ICL_DEF); 01693 #ifdef GECODE_HAS_SET_VARS 01694 01700 void element(Home home, const Matrix<IntSetArgs>& m, IntVar x, IntVar y, 01701 SetVar z); 01708 void element(Home home, const Matrix<SetVarArgs>& m, IntVar x, IntVar y, 01709 SetVar z); 01710 #endif 01711 01712 } 01713 01714 #include <gecode/minimodel/matrix.hpp> 01715 01716 namespace Gecode { 01717 01727 namespace MiniModel { 01728 01730 template<IntRelType irt> 01731 class OptimizeSpace : public Space { 01732 public: 01734 OptimizeSpace(void); 01736 OptimizeSpace(bool share, OptimizeSpace& s); 01738 virtual void constrain(const Space& best); 01740 virtual IntVar cost(void) const = 0; 01741 }; 01742 01743 } 01744 01746 typedef MiniModel::OptimizeSpace<IRT_LE> MinimizeSpace; 01747 01749 typedef MiniModel::OptimizeSpace<IRT_GR> MaximizeSpace; 01751 01752 } 01753 01754 #include <gecode/minimodel/optimize.hpp> 01755 01756 #endif 01757 01758 // IFDEF: GECODE_HAS_INT_VARS 01759 // STATISTICS: minimodel-any 01760