Generated on Mon Nov 30 23:53:33 2009 for Gecode by doxygen 1.6.1

lin-expr.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-10-12 17:36:53 +0200 (Mon, 12 Oct 2009) $ by $Author: schulte $
00011  *     $Revision: 9878 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode {
00039 
00040   /*
00041    * Operations for nodes
00042    *
00043    */
00044   template<class Var>
00045   forceinline
00046   LinExpr<Var>::Node::Node(void) : use(1) {
00047   }
00048 
00049   template<class Var>
00050   forceinline void*
00051   LinExpr<Var>::Node::operator new(size_t size) {
00052     return heap.ralloc(size);
00053   }
00054 
00055   template<class Var>
00056   forceinline void
00057   LinExpr<Var>::Node::operator delete(void* p, size_t) {
00058     heap.rfree(p);
00059   }
00060 
00061   template<class Var>
00062   bool
00063   LinExpr<Var>::Node::decrement(void) {
00064     if (--use == 0) {
00065       if ((l != NULL) && l->decrement())
00066         delete l;
00067       if ((r != NULL) && r->decrement())
00068         delete r;
00069       return true;
00070     }
00071     return false;
00072   }
00073 
00074   template<class Var>
00075   int
00076   LinExpr<Var>::Node::fill(Int::Linear::Term<View> t[],
00077                            int i, int m, int c_i, int& c_o) const {
00078     switch (this->t) {
00079     case NT_VAR:
00080       c_o = c_i;
00081       if (a != 0) {
00082         t[i].a=m*a; t[i].x=x;
00083         return i+1;
00084       } else {
00085         return i;
00086       }
00087     case NT_ADD:
00088       if (l == NULL) {
00089         return r->fill(t,i,m,c_i+m*c,c_o);
00090       } else {
00091         int c_m = 0;
00092         i = l->fill(t,i,m,c_i,c_m);
00093         return r->fill(t,i,m,c_m,c_o);
00094       }
00095     case NT_SUB:
00096       if (l == NULL) {
00097         return r->fill(t,i,-m,c_i+m*c,c_o);
00098       } else {
00099         int c_m = 0;
00100         i = l->fill(t,i,m,c_i,c_m);
00101         return r->fill(t,i,-m,c_m,c_o);
00102       }
00103     case NT_MUL:
00104       return l->fill(t,i,a*m,c_i,c_o);
00105     default:
00106       GECODE_NEVER;
00107     }
00108     GECODE_NEVER;
00109     return 0;
00110   }
00111 
00112 
00113   /*
00114    * Operations for expressions
00115    *
00116    */
00117 
00118   template<class Var>
00119   inline
00120   LinExpr<Var>::LinExpr(void) :
00121     n(new Node) {
00122     n->n = 0;
00123     n->t = NT_VAR;
00124     n->l = n->r = NULL;
00125     n->a = 0;
00126   }
00127 
00128   template<class Var>
00129   inline
00130   LinExpr<Var>::LinExpr(const Var& x, int a) :
00131     n(new Node) {
00132     n->n = 1;
00133     n->t = NT_VAR;
00134     n->l = n->r = NULL;
00135     n->a = a;
00136     n->x = x;
00137   }
00138 
00139   template<class Var>
00140   inline
00141   LinExpr<Var>::LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1) :
00142     n(new Node) {
00143     n->n = e0.n->n+e1.n->n;
00144     n->t = t;
00145     n->l = e0.n; n->l->use++;
00146     n->r = e1.n; n->r->use++;
00147   }
00148 
00149   template<class Var>
00150   inline
00151   LinExpr<Var>::LinExpr(const LinExpr& e, NodeType t, int c) :
00152     n(new Node) {
00153     n->n = e.n->n;
00154     n->t = t;
00155     n->l = NULL;
00156     n->r = e.n; n->r->use++;
00157     n->c = c;
00158   }
00159 
00160   template<class Var>
00161   inline
00162   LinExpr<Var>::LinExpr(int a, const LinExpr& e) :
00163     n(new Node) {
00164     n->n = e.n->n;
00165     n->t = NT_MUL;
00166     n->l = e.n; n->l->use++;
00167     n->r = NULL;
00168     n->a = a;
00169   }
00170 
00171   template<class Var>
00172   inline
00173   LinExpr<Var>::LinExpr(const LinExpr<Var>& e)
00174     : n(e.n) {
00175     n->use++;
00176   }
00177 
00178   template<class Var>
00179   inline const LinExpr<Var>&
00180   LinExpr<Var>::operator =(const LinExpr<Var>& e) {
00181     if (this != &e) {
00182       if (n->decrement())
00183         delete n;
00184       n = e.n; n->use++;
00185     }
00186     return *this;
00187   }
00188 
00189   template<class Var>
00190   forceinline
00191   LinExpr<Var>::~LinExpr(void) {
00192     if (n->decrement())
00193       delete n;
00194   }
00195 
00196   template<class Var>
00197   inline void
00198   LinExpr<Var>::post(Home home, IntRelType irt, IntConLevel icl) const {
00199     Region r(home);
00200     Int::Linear::Term<typename VarViewTraits<Var>::View>* ts =
00201       r.alloc<Int::Linear::Term<typename VarViewTraits<Var>::View> >(n->n);
00202     int c_o = 0;
00203     int i = n->fill(ts,0,1,0,c_o);
00204     Int::Linear::post(home, ts, i, irt, -c_o, icl);
00205   }
00206 
00207   template<class Var>
00208   inline void
00209   LinExpr<Var>::post(Home home, IntRelType irt, const BoolVar& b,
00210                      IntConLevel icl) const {
00211     Region r(home);
00212     Int::Linear::Term<typename VarViewTraits<Var>::View>* ts =
00213       r.alloc<Int::Linear::Term<typename VarViewTraits<Var>::View> >(n->n);
00214     int c_o = 0;
00215     int i = n->fill(ts,0,1,0,c_o);
00216     Int::Linear::post(home, ts, i, irt, -c_o, b, icl);
00217   }
00218 
00219   template<>
00220   inline IntVar
00221   LinExpr<IntVar>::post(Home home, IntConLevel icl) const {
00222     Region r(home);
00223     Int::Linear::Term<Int::IntView>* ts =
00224       r.alloc<Int::Linear::Term<Int::IntView> >(n->n+1);
00225     int c_o = 0;
00226     int i = n->fill(ts,0,1,0,c_o);
00227     int min, max;
00228     Int::Linear::estimate(&ts[0],i,c_o,min,max);
00229     IntVar x(home, min, max);
00230     ts[i].x = x; ts[i].a = -1;
00231     Int::Linear::post(home, ts, i+1, IRT_EQ, -c_o, icl);
00232     return x;
00233   }
00234 
00235   template<>
00236   inline IntVar
00237   LinExpr<BoolVar>::post(Home home, IntConLevel icl) const {
00238     Region r(home);
00239     Int::Linear::Term<Int::BoolView>* ts =
00240       r.alloc<Int::Linear::Term<Int::BoolView> >(n->n);
00241     int c_o = 0;
00242     int i = n->fill(ts,0,1,0,c_o);
00243     int min, max;
00244     Int::Linear::estimate(&ts[0],i,c_o,min,max);
00245     IntVar x(home, min, max);
00246     Int::Linear::post(home, ts, i, IRT_EQ, x, -c_o, icl);
00247     return x;
00248   }
00249 
00250   inline LinExpr<IntVar>
00251   operator +(int c, const IntVar& x) {
00252     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,c);
00253   }
00254   inline LinExpr<IntVar>
00255   operator +(int c, const LinExpr<IntVar>& e) {
00256     return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,c);
00257   }
00258   inline LinExpr<IntVar>
00259   operator +(const IntVar& x, int c) {
00260     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,c);
00261   }
00262   inline LinExpr<IntVar>
00263   operator +(const LinExpr<IntVar>& e, int c) {
00264     return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,c);
00265   }
00266   inline LinExpr<IntVar>
00267   operator +(const IntVar& x, const IntVar& y) {
00268     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,y);
00269   }
00270   inline LinExpr<IntVar>
00271   operator +(const IntVar& x, const LinExpr<IntVar>& e) {
00272     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,e);
00273   }
00274   inline LinExpr<IntVar>
00275   operator +(const LinExpr<IntVar>& e, const IntVar& x) {
00276     return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,x);
00277   }
00278   inline LinExpr<IntVar>
00279   operator +(const LinExpr<IntVar>& e1, const LinExpr<IntVar>& e2) {
00280     return LinExpr<IntVar>(e1,LinExpr<IntVar>::NT_ADD,e2);
00281   }
00282 
00283   inline LinExpr<IntVar>
00284   operator -(int c, const IntVar& x) {
00285     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,c);
00286   }
00287   inline LinExpr<IntVar>
00288   operator -(int c, const LinExpr<IntVar>& e) {
00289     return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_SUB,c);
00290   }
00291   inline LinExpr<IntVar>
00292   operator -(const IntVar& x, int c) {
00293     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_ADD,-c);
00294   }
00295   inline LinExpr<IntVar>
00296   operator -(const LinExpr<IntVar>& e, int c) {
00297     return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_ADD,-c);
00298   }
00299   inline LinExpr<IntVar>
00300   operator -(const IntVar& x, const IntVar& y) {
00301     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,y);
00302   }
00303   inline LinExpr<IntVar>
00304   operator -(const IntVar& x, const LinExpr<IntVar>& e) {
00305     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,e);
00306   }
00307   inline LinExpr<IntVar>
00308   operator -(const LinExpr<IntVar>& e, const IntVar& x) {
00309     return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_SUB,x);
00310   }
00311   inline LinExpr<IntVar>
00312   operator -(const LinExpr<IntVar>& e1, const LinExpr<IntVar>& e2) {
00313     return LinExpr<IntVar>(e1,LinExpr<IntVar>::NT_SUB,e2);
00314   }
00315   inline LinExpr<IntVar>
00316   operator -(const IntVar& x) {
00317     return LinExpr<IntVar>(x,LinExpr<IntVar>::NT_SUB,0);
00318   }
00319   inline LinExpr<IntVar>
00320   operator -(const LinExpr<IntVar>& e) {
00321     return LinExpr<IntVar>(e,LinExpr<IntVar>::NT_SUB,0);
00322   }
00323 
00324   inline LinExpr<IntVar>
00325   operator *(int a, const IntVar& x) {
00326     return LinExpr<IntVar>(x,a);
00327   }
00328   inline LinExpr<IntVar>
00329   operator *(const IntVar& x, int a) {
00330     return LinExpr<IntVar>(x,a);
00331   }
00332   inline LinExpr<IntVar>
00333   operator *(const LinExpr<IntVar>& e, int a) {
00334     return LinExpr<IntVar>(a,e);
00335   }
00336   inline LinExpr<IntVar>
00337   operator *(int a, const LinExpr<IntVar>& e) {
00338     return LinExpr<IntVar>(a,e);
00339   }
00340 
00341 
00342   inline LinExpr<BoolVar>
00343   operator +(int c, const BoolVar& x) {
00344     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,c);
00345   }
00346   inline LinExpr<BoolVar>
00347   operator +(int c, const LinExpr<BoolVar>& e) {
00348     return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,c);
00349   }
00350   inline LinExpr<BoolVar>
00351   operator +(const BoolVar& x, int c) {
00352     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,c);
00353   }
00354   inline LinExpr<BoolVar>
00355   operator +(const LinExpr<BoolVar>& e, int c) {
00356     return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,c);
00357   }
00358   inline LinExpr<BoolVar>
00359   operator +(const BoolVar& x, const BoolVar& y) {
00360     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,y);
00361   }
00362   inline LinExpr<BoolVar>
00363   operator +(const BoolVar& x, const LinExpr<BoolVar>& e) {
00364     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,e);
00365   }
00366   inline LinExpr<BoolVar>
00367   operator +(const LinExpr<BoolVar>& e, const BoolVar& x) {
00368     return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,x);
00369   }
00370   inline LinExpr<BoolVar>
00371   operator +(const LinExpr<BoolVar>& e1, const LinExpr<BoolVar>& e2) {
00372     return LinExpr<BoolVar>(e1,LinExpr<BoolVar>::NT_ADD,e2);
00373   }
00374 
00375   inline LinExpr<BoolVar>
00376   operator -(int c, const BoolVar& x) {
00377     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,c);
00378   }
00379   inline LinExpr<BoolVar>
00380   operator -(int c, const LinExpr<BoolVar>& e) {
00381     return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_SUB,c);
00382   }
00383   inline LinExpr<BoolVar>
00384   operator -(const BoolVar& x, int c) {
00385     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_ADD,-c);
00386   }
00387   inline LinExpr<BoolVar>
00388   operator -(const LinExpr<BoolVar>& e, int c) {
00389     return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_ADD,-c);
00390   }
00391   inline LinExpr<BoolVar>
00392   operator -(const BoolVar& x, const BoolVar& y) {
00393     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,y);
00394   }
00395   inline LinExpr<BoolVar>
00396   operator -(const BoolVar& x, const LinExpr<BoolVar>& e) {
00397     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,e);
00398   }
00399   inline LinExpr<BoolVar>
00400   operator -(const LinExpr<BoolVar>& e, const BoolVar& x) {
00401     return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_SUB,x);
00402   }
00403   inline LinExpr<BoolVar>
00404   operator -(const LinExpr<BoolVar>& e1, const LinExpr<BoolVar>& e2) {
00405     return LinExpr<BoolVar>(e1,LinExpr<BoolVar>::NT_SUB,e2);
00406   }
00407   inline LinExpr<BoolVar>
00408   operator -(const BoolVar& x) {
00409     return LinExpr<BoolVar>(x,LinExpr<BoolVar>::NT_SUB,0);
00410   }
00411   inline LinExpr<BoolVar>
00412   operator -(const LinExpr<BoolVar>& e) {
00413     return LinExpr<BoolVar>(e,LinExpr<BoolVar>::NT_SUB,0);
00414   }
00415 
00416   inline LinExpr<BoolVar>
00417   operator *(int a, const BoolVar& x) {
00418     return LinExpr<BoolVar>(x,a);
00419   }
00420   inline LinExpr<BoolVar>
00421   operator *(const BoolVar& x, int a) {
00422     return LinExpr<BoolVar>(x,a);
00423   }
00424   inline LinExpr<BoolVar>
00425   operator *(const LinExpr<BoolVar>& e, int a) {
00426     return LinExpr<BoolVar>(a,e);
00427   }
00428   inline LinExpr<BoolVar>
00429   operator *(int a, const LinExpr<BoolVar>& e) {
00430     return LinExpr<BoolVar>(a,e);
00431   }
00432 
00433 
00434   forceinline IntVar
00435   post(Home, const IntVar& x, IntConLevel) {
00436     return x;
00437   }
00438 
00439   inline IntVar
00440   post(Home home, int n, IntConLevel) {
00441     IntVar x(home, n, n);
00442     return x;
00443   }
00444 
00445   template<class Var>
00446   inline IntVar
00447   post(Home home, const LinExpr<Var>& e, IntConLevel icl) {
00448     if (!home.failed())
00449       return e.post(home,icl);
00450     IntVar x(home,Int::Limits::min,Int::Limits::max);
00451     return x;
00452   }
00453 
00454 }
00455 
00456 // STATISTICS: minimodel-any