lin-expr.cpp

00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2010
00008  *
00009  *  Last modified:
00010  *     $Date: 2011-04-12 12:54:34 +0200 (Tue, 12 Apr 2011) $ by $Author: tack $
00011  *     $Revision: 11941 $
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 #include <gecode/minimodel.hh>
00039 
00040 namespace Gecode {
00041 
00042   bool
00043   LinExpr::Node::decrement(void) {
00044     if (--use == 0) {
00045       if ((l != NULL) && l->decrement())
00046         delete l;
00047       if ((r != NULL) && r->decrement())
00048         delete r;
00049       return true;
00050     }
00051     return false;
00052   }
00053 
00054   /*
00055    * Operations for expressions
00056    *
00057    */
00058   LinExpr::LinExpr(void) :
00059     n(new Node) {
00060     n->n_int = n->n_bool = 0;
00061     n->t = NT_VAR_INT;
00062     n->l = n->r = NULL;
00063     n->a = 0;
00064   }
00065 
00066   LinExpr::LinExpr(int c) :
00067     n(new Node) {
00068     n->n_int = n->n_bool = 0;
00069     n->t = NT_CONST;
00070     n->l = n->r = NULL;
00071     n->a = 0;
00072     Int::Limits::check(c,"MiniModel::LinExpr");
00073     n->c = c;
00074   }
00075 
00076   LinExpr::LinExpr(const IntVar& x, int a) :
00077     n(new Node) {
00078     n->n_int = 1;
00079     n->n_bool = 0;
00080     n->t = NT_VAR_INT;
00081     n->l = n->r = NULL;
00082     n->a = a;
00083     n->x_int = x;
00084   }
00085 
00086   LinExpr::LinExpr(const BoolVar& x, int a) :
00087     n(new Node) {
00088     n->n_int = 0;
00089     n->n_bool = 1;
00090     n->t = NT_VAR_BOOL;
00091     n->l = n->r = NULL;
00092     n->a = a;
00093     n->x_bool = x;
00094   }
00095 
00096   LinExpr::LinExpr(const IntVarArgs& x) :
00097     n(new Node) {
00098     n->n_int = x.size();
00099     n->n_bool = 0;
00100     n->t = NT_SUM_INT;
00101     n->l = n->r = NULL;
00102     if (x.size() > 0) {
00103       n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
00104       for (int i=x.size(); i--; ) {
00105         n->sum.ti[i].x = x[i];
00106         n->sum.ti[i].a = 1;
00107       }
00108     }
00109   }
00110 
00111   LinExpr::LinExpr(const IntArgs& a, const IntVarArgs& x) :
00112     n(new Node) {
00113     if (a.size() != x.size())
00114       throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
00115     n->n_int = x.size();
00116     n->n_bool = 0;
00117     n->t = NT_SUM_INT;
00118     n->l = n->r = NULL;
00119     if (x.size() > 0) {
00120       n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size());
00121       for (int i=x.size(); i--; ) {
00122         n->sum.ti[i].x = x[i];
00123         n->sum.ti[i].a = a[i];
00124       }
00125     }
00126   }
00127 
00128   LinExpr::LinExpr(const BoolVarArgs& x) :
00129     n(new Node) {
00130     n->n_int = 0;
00131     n->n_bool = x.size();
00132     n->t = NT_SUM_BOOL;
00133     n->l = n->r = NULL;
00134     if (x.size() > 0) {
00135       n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
00136       for (int i=x.size(); i--; ) {
00137         n->sum.tb[i].x = x[i];
00138         n->sum.tb[i].a = 1;
00139       }
00140     }
00141   }
00142 
00143   LinExpr::LinExpr(const IntArgs& a, const BoolVarArgs& x) :
00144     n(new Node) {
00145     if (a.size() != x.size())
00146       throw Int::ArgumentSizeMismatch("MiniModel::LinExpr");
00147     n->n_int = 0;
00148     n->n_bool = x.size();
00149     n->t = NT_SUM_BOOL;
00150     n->l = n->r = NULL;
00151     if (x.size() > 0) {
00152       n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size());
00153       for (int i=x.size(); i--; ) {
00154         n->sum.tb[i].x = x[i];
00155         n->sum.tb[i].a = a[i];
00156       }
00157     }
00158   }
00159 
00160   LinExpr::LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1) :
00161     n(new Node) {
00162     n->n_int = e0.n->n_int + e1.n->n_int;
00163     n->n_bool = e0.n->n_bool + e1.n->n_bool;
00164     n->t = t;
00165     n->l = e0.n; n->l->use++;
00166     n->r = e1.n; n->r->use++;
00167   }
00168 
00169   LinExpr::LinExpr(const LinExpr& e, NodeType t, int c) :
00170     n(new Node) {
00171     n->n_int = e.n->n_int;
00172     n->n_bool = e.n->n_bool;
00173     n->t = t;
00174     n->l = NULL;
00175     n->r = e.n; n->r->use++;
00176     n->c = c;
00177   }
00178 
00179   LinExpr::LinExpr(int a, const LinExpr& e) :
00180     n(new Node) {
00181     n->n_int = e.n->n_int;
00182     n->n_bool = e.n->n_bool;
00183     n->t = NT_MUL;
00184     n->l = e.n; n->l->use++;
00185     n->r = NULL;
00186     n->a = a;
00187   }
00188 
00189   LinExpr::LinExpr(NonLinExpr* e) :
00190     n(new Node) {
00191     n->n_int = 1;
00192     n->n_bool = 0;
00193     n->t = NT_NONLIN;
00194     n->l = n->r = NULL;
00195     n->a = 0;
00196     n->sum.ne = e;
00197   }
00198 
00199   const LinExpr&
00200   LinExpr::operator =(const LinExpr& e) {
00201     if (this != &e) {
00202       if (n->decrement())
00203         delete n;
00204       n = e.n; n->use++;
00205     }
00206     return *this;
00207   }
00208 
00209   LinExpr::~LinExpr(void) {
00210     if (n->decrement())
00211       delete n;
00212   }
00213 
00214 
00215   void
00216   LinExpr::Node::fill(Home home, IntConLevel icl,
00217                       Int::Linear::Term<Int::IntView>*& ti, 
00218                       Int::Linear::Term<Int::BoolView>*& tb,
00219                       double m, double& d) const {
00220     switch (this->t) {
00221     case NT_CONST:
00222       Int::Limits::check(m*c,"MiniModel::LinExpr");
00223       d += m*c;
00224       break;
00225     case NT_VAR_INT:
00226       Int::Limits::check(m*a,"MiniModel::LinExpr");
00227       ti->a=static_cast<int>(m*a); ti->x=x_int; ti++;
00228       break;
00229     case NT_NONLIN:
00230       ti->a=static_cast<int>(m); ti->x=sum.ne->post(home, NULL, icl); ti++;
00231       break;
00232     case NT_VAR_BOOL:
00233       Int::Limits::check(m*a,"MiniModel::LinExpr");
00234       tb->a=static_cast<int>(m*a); tb->x=x_bool; tb++;
00235       break;
00236     case NT_SUM_INT:
00237       for (int i=n_int; i--; ) {
00238         Int::Limits::check(m*sum.ti[i].a,"MiniModel::LinExpr");
00239         ti[i].x = sum.ti[i].x; ti[i].a = static_cast<int>(m*sum.ti[i].a);
00240       }
00241       ti += n_int;
00242       break;
00243     case NT_SUM_BOOL:
00244       for (int i=n_bool; i--; ) {
00245         Int::Limits::check(m*sum.tb[i].a,"MiniModel::LinExpr");
00246         tb[i].x = sum.tb[i].x; tb[i].a = static_cast<int>(m*sum.tb[i].a);
00247       }
00248       tb += n_bool;
00249       break;
00250     case NT_ADD:
00251       if (l == NULL) {
00252         Int::Limits::check(m*c,"MiniModel::LinExpr");
00253         d += m*c;
00254       } else {
00255         l->fill(home,icl,ti,tb,m,d);
00256       }
00257       r->fill(home,icl,ti,tb,m,d);
00258       break;
00259     case NT_SUB:
00260       if (l == NULL) {
00261         Int::Limits::check(m*c,"MiniModel::LinExpr");
00262         d += m*c;
00263       } else {
00264         l->fill(home,icl,ti,tb,m,d);
00265       }
00266       r->fill(home,icl,ti,tb,-m,d);
00267       break;
00268     case NT_MUL:
00269       Int::Limits::check(m*a,"MiniModel::LinExpr");
00270       l->fill(home,icl,ti,tb,m*a,d);
00271       break;
00272     default:
00273       GECODE_NEVER;
00274     }
00275   }
00276 
00277 
00278   /*
00279    * Operators
00280    *
00281    */
00282   LinExpr
00283   operator +(int c, const IntVar& x) {
00284     if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
00285       return LinExpr(static_cast<double>(c)+x.val());
00286     else
00287       return LinExpr(x,LinExpr::NT_ADD,c);
00288   }
00289   LinExpr
00290   operator +(int c, const BoolVar& x) {
00291     if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
00292       return LinExpr(static_cast<double>(c)+x.val());
00293     else
00294       return LinExpr(x,LinExpr::NT_ADD,c);
00295   }
00296   LinExpr
00297   operator +(int c, const LinExpr& e) {
00298     return LinExpr(e,LinExpr::NT_ADD,c);
00299   }
00300   LinExpr
00301   operator +(const IntVar& x, int c) {
00302     if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
00303       return LinExpr(static_cast<double>(c)+x.val());
00304     else
00305       return LinExpr(x,LinExpr::NT_ADD,c);
00306   }
00307   LinExpr
00308   operator +(const BoolVar& x, int c) {
00309     if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val()))
00310       return LinExpr(static_cast<double>(c)+x.val());
00311     else
00312       return LinExpr(x,LinExpr::NT_ADD,c);
00313   }
00314   LinExpr
00315   operator +(const LinExpr& e, int c) {
00316     return LinExpr(e,LinExpr::NT_ADD,c);
00317   }
00318   LinExpr
00319   operator +(const IntVar& x, const IntVar& y) {
00320     if (x.assigned())
00321       return x.val() + y;
00322     else if (y.assigned())
00323       return x + y.val();
00324     else
00325       return LinExpr(x,LinExpr::NT_ADD,y);
00326   }
00327   LinExpr
00328   operator +(const IntVar& x, const BoolVar& y) {
00329     if (x.assigned())
00330       return x.val() + y;
00331     else if (y.assigned())
00332       return x + y.val();
00333     else
00334       return LinExpr(x,LinExpr::NT_ADD,y);
00335   }
00336   LinExpr
00337   operator +(const BoolVar& x, const IntVar& y) {
00338     if (x.assigned())
00339       return x.val() + y;
00340     else if (y.assigned())
00341       return x + y.val();
00342     else
00343       return LinExpr(x,LinExpr::NT_ADD,y);
00344   }
00345   LinExpr
00346   operator +(const BoolVar& x, const BoolVar& y) {
00347     if (x.assigned())
00348       return x.val() + y;
00349     else if (y.assigned())
00350       return x + y.val();
00351     else
00352       return LinExpr(x,LinExpr::NT_ADD,y);
00353   }
00354   LinExpr
00355   operator +(const IntVar& x, const LinExpr& e) {
00356     if (x.assigned())
00357       return x.val() + e;
00358     else
00359       return LinExpr(x,LinExpr::NT_ADD,e);
00360   }
00361   LinExpr
00362   operator +(const BoolVar& x, const LinExpr& e) {
00363     if (x.assigned())
00364       return x.val() + e;
00365     else
00366       return LinExpr(x,LinExpr::NT_ADD,e);
00367   }
00368   LinExpr
00369   operator +(const LinExpr& e, const IntVar& x) {
00370     if (x.assigned())
00371       return e + x.val();
00372     else
00373       return LinExpr(e,LinExpr::NT_ADD,x);
00374   }
00375   LinExpr
00376   operator +(const LinExpr& e, const BoolVar& x) {
00377     if (x.assigned())
00378       return e + x.val();
00379     else
00380       return LinExpr(e,LinExpr::NT_ADD,x);
00381   }
00382   LinExpr
00383   operator +(const LinExpr& e1, const LinExpr& e2) {
00384     return LinExpr(e1,LinExpr::NT_ADD,e2);
00385   }
00386 
00387   LinExpr
00388   operator -(int c, const IntVar& x) {
00389     if (x.assigned() && Int::Limits::valid(static_cast<double>(c)-x.val()))
00390       return LinExpr(static_cast<double>(c)-x.val());
00391     else
00392       return LinExpr(x,LinExpr::NT_SUB,c);
00393   }
00394   LinExpr
00395   operator -(int c, const BoolVar& x) {
00396     if (x.assigned() && Int::Limits::valid(static_cast<double>(c)-x.val()))
00397       return LinExpr(static_cast<double>(c)-x.val());
00398     else
00399       return LinExpr(x,LinExpr::NT_SUB,c);
00400   }
00401   LinExpr
00402   operator -(int c, const LinExpr& e) {
00403     return LinExpr(e,LinExpr::NT_SUB,c);
00404   }
00405   LinExpr
00406   operator -(const IntVar& x, int c) {
00407     if (x.assigned() && Int::Limits::valid(x.val()-static_cast<double>(c)))
00408       return LinExpr(x.val()-static_cast<double>(c));
00409     else
00410       return LinExpr(x,LinExpr::NT_ADD,-c);
00411   }
00412   LinExpr
00413   operator -(const BoolVar& x, int c) {
00414     if (x.assigned() && Int::Limits::valid(x.val()-static_cast<double>(c)))
00415       return LinExpr(x.val()-static_cast<double>(c));
00416     else
00417       return LinExpr(x,LinExpr::NT_ADD,-c);
00418   }
00419   LinExpr
00420   operator -(const LinExpr& e, int c) {
00421     return LinExpr(e,LinExpr::NT_ADD,-c);
00422   }
00423   LinExpr
00424   operator -(const IntVar& x, const IntVar& y) {
00425     if (x.assigned())
00426       return x.val() - y;
00427     else if (y.assigned())
00428       return x - y.val();
00429     else
00430       return LinExpr(x,LinExpr::NT_SUB,y);
00431   }
00432   LinExpr
00433   operator -(const IntVar& x, const BoolVar& y) {
00434     if (x.assigned())
00435       return x.val() - y;
00436     else if (y.assigned())
00437       return x - y.val();
00438     else
00439       return LinExpr(x,LinExpr::NT_SUB,y);
00440   }
00441   LinExpr
00442   operator -(const BoolVar& x, const IntVar& y) {
00443     if (x.assigned())
00444       return x.val() - y;
00445     else if (y.assigned())
00446       return x - y.val();
00447     else
00448       return LinExpr(x,LinExpr::NT_SUB,y);
00449   }
00450   LinExpr
00451   operator -(const BoolVar& x, const BoolVar& y) {
00452     if (x.assigned())
00453       return x.val() - y;
00454     else if (y.assigned())
00455       return x - y.val();
00456     else
00457       return LinExpr(x,LinExpr::NT_SUB,y);
00458   }
00459   LinExpr
00460   operator -(const IntVar& x, const LinExpr& e) {
00461     if (x.assigned())
00462       return x.val() - e;
00463     else
00464       return LinExpr(x,LinExpr::NT_SUB,e);
00465   }
00466   LinExpr
00467   operator -(const BoolVar& x, const LinExpr& e) {
00468     if (x.assigned())
00469       return x.val() - e;
00470     else
00471       return LinExpr(x,LinExpr::NT_SUB,e);
00472   }
00473   LinExpr
00474   operator -(const LinExpr& e, const IntVar& x) {
00475     if (x.assigned())
00476       return e - x.val();
00477     else
00478       return LinExpr(e,LinExpr::NT_SUB,x);
00479   }
00480   LinExpr
00481   operator -(const LinExpr& e, const BoolVar& x) {
00482     if (x.assigned())
00483       return e - x.val();
00484     else
00485       return LinExpr(e,LinExpr::NT_SUB,x);
00486   }
00487   LinExpr
00488   operator -(const LinExpr& e1, const LinExpr& e2) {
00489     return LinExpr(e1,LinExpr::NT_SUB,e2);
00490   }
00491 
00492   LinExpr
00493   operator -(const IntVar& x) {
00494     if (x.assigned())
00495       return LinExpr(-x.val());
00496     else
00497       return LinExpr(x,LinExpr::NT_SUB,0);
00498   }
00499   LinExpr
00500   operator -(const BoolVar& x) {
00501     if (x.assigned())
00502       return LinExpr(-x.val());
00503     else
00504       return LinExpr(x,LinExpr::NT_SUB,0);
00505   }
00506   LinExpr
00507   operator -(const LinExpr& e) {
00508     return LinExpr(e,LinExpr::NT_SUB,0);
00509   }
00510 
00511   LinExpr
00512   operator *(int a, const IntVar& x) {
00513     if (a == 0)
00514       return LinExpr(0.0);
00515     else if (x.assigned() && 
00516              Int::Limits::valid(static_cast<double>(a)*x.val()))
00517       return LinExpr(static_cast<double>(a)*x.val());
00518     else
00519       return LinExpr(x,a);
00520   }
00521   LinExpr
00522   operator *(int a, const BoolVar& x) {
00523     if (a == 0)
00524       return LinExpr(0.0);
00525     else if (x.assigned() && 
00526              Int::Limits::valid(static_cast<double>(a)*x.val()))
00527       return LinExpr(static_cast<double>(a)*x.val());
00528     else
00529       return LinExpr(x,a);
00530   }
00531   LinExpr
00532   operator *(const IntVar& x, int a) {
00533     if (a == 0)
00534       return LinExpr(0.0);
00535     else if (x.assigned() && 
00536              Int::Limits::valid(static_cast<double>(a)*x.val()))
00537       return LinExpr(static_cast<double>(a)*x.val());
00538     else
00539       return LinExpr(x,a);
00540   }
00541   LinExpr
00542   operator *(const BoolVar& x, int a) {
00543     if (a == 0)
00544       return LinExpr(0.0);
00545     else if (x.assigned() && 
00546              Int::Limits::valid(static_cast<double>(a)*x.val()))
00547       return LinExpr(static_cast<double>(a)*x.val());
00548     else
00549       return LinExpr(x,a);
00550   }
00551   LinExpr
00552   operator *(const LinExpr& e, int a) {
00553     if (a == 0)
00554       return LinExpr(0.0);
00555     else
00556       return LinExpr(a,e);
00557   }
00558   LinExpr
00559   operator *(int a, const LinExpr& e) {
00560     if (a == 0)
00561       return LinExpr(0.0);
00562     else
00563       return LinExpr(a,e);
00564   }
00565 
00566   LinExpr
00567   sum(const IntVarArgs& x) {
00568     return LinExpr(x);
00569   }
00570   LinExpr
00571   sum(const IntArgs& a, const IntVarArgs& x) {
00572     return LinExpr(a,x);
00573   }
00574   LinExpr
00575   sum(const BoolVarArgs& x) {
00576     return LinExpr(x);
00577   }
00578   LinExpr
00579   sum(const IntArgs& a, const BoolVarArgs& x) {
00580     return LinExpr(a,x);
00581   }
00582 
00583 
00584   IntVar
00585   expr(Home home, const LinExpr& e, IntConLevel icl) {
00586     if (!home.failed())
00587       return e.post(home,icl);
00588     IntVar x(home,Int::Limits::min,Int::Limits::max);
00589     return x;
00590   }
00591 
00592 }
00593 
00594 // STATISTICS: minimodel-any