Generated on Thu Apr 11 13:59:17 2019 for Gecode by doxygen 1.6.3

float-expr.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Vincent Barichard <Vincent.Barichard@univ-angers.fr>
00005  *
00006  *  Copyright:
00007  *     Vincent Barichard, 2012
00008  *
00009  *  This file is part of Gecode, the generic constraint
00010  *  development environment:
00011  *     http://www.gecode.org
00012  *
00013  *  Permission is hereby granted, free of charge, to any person obtaining
00014  *  a copy of this software and associated documentation files (the
00015  *  "Software"), to deal in the Software without restriction, including
00016  *  without limitation the rights to use, copy, modify, merge, publish,
00017  *  distribute, sublicense, and/or sell copies of the Software, and to
00018  *  permit persons to whom the Software is furnished to do so, subject to
00019  *  the following conditions:
00020  *
00021  *  The above copyright notice and this permission notice shall be
00022  *  included in all copies or substantial portions of the Software.
00023  *
00024  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00025  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00026  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00027  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00028  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00029  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00030  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00031  *
00032  */
00033 
00034 #include <gecode/minimodel.hh>
00035 
00036 #ifdef GECODE_HAS_FLOAT_VARS
00037 
00038 #include <gecode/float/linear.hh>
00039 
00040 namespace Gecode {
00041 
00043   class LinFloatExpr::Node {
00044   public:
00046     unsigned int use;
00048     int n_float;
00050     NodeType t;
00052     Node *l, *r;
00054     union {
00056       Float::Linear::Term* tf;
00058       NonLinFloatExpr* ne;
00059     } sum;
00061     FloatVal a, c;
00063     FloatVar x_float;
00065     Node(void);
00067     GECODE_MINIMODEL_EXPORT
00068     void fill(Home home, Float::Linear::Term*& tf,
00069               FloatVal m, FloatVal& d) const;
00071     FloatVal fill(Home home, Float::Linear::Term* tf) const;
00073     bool decrement(void);
00075     ~Node(void);
00077     static void* operator new(size_t size);
00079     static void  operator delete(void* p,size_t size);
00080 
00081   };
00082 
00083   /*
00084    * Operations for nodes
00085    *
00086    */
00087   forceinline
00088   LinFloatExpr::Node::Node(void) : use(1) {
00089   }
00090 
00091   forceinline
00092   LinFloatExpr::Node::~Node(void) {
00093     switch (t) {
00094     case NT_SUM:
00095       if (n_float > 0)
00096         heap.free<Float::Linear::Term>(sum.tf,n_float);
00097       break;
00098     case NT_NONLIN:
00099       delete sum.ne;
00100       break;
00101     default: ;
00102     }
00103   }
00104 
00105   forceinline void*
00106   LinFloatExpr::Node::operator new(size_t size) {
00107     return heap.ralloc(size);
00108   }
00109 
00110   forceinline void
00111   LinFloatExpr::Node::operator delete(void* p, size_t) {
00112     heap.rfree(p);
00113   }
00114 
00115   bool
00116   LinFloatExpr::Node::decrement(void) {
00117     if (--use == 0) {
00118       if ((l != nullptr) && l->decrement())
00119         delete l;
00120       if ((r != nullptr) && r->decrement())
00121         delete r;
00122       return true;
00123     }
00124     return false;
00125   }
00126 
00127   /*
00128    * Operations for float expressions
00129    *
00130    */
00131 
00132   LinFloatExpr::LinFloatExpr(const LinFloatExpr& e)
00133     : n(e.n) {
00134     n->use++;
00135   }
00136 
00137   NonLinFloatExpr*
00138   LinFloatExpr::nlfe(void) const {
00139     return n->t == NT_NONLIN ? n->sum.ne : nullptr;
00140   }
00141 
00142   FloatVal
00143   LinFloatExpr::Node::fill(Home home,
00144                            Float::Linear::Term* tf) const {
00145     FloatVal d=0;
00146     fill(home,tf,1.0,d);
00147     Float::Limits::check(d,"MiniModel::LinFloatExpr");
00148     return d;
00149   }
00150 
00151   void
00152   LinFloatExpr::post(Home home, FloatRelType frt) const {
00153     if (home.failed()) return;
00154     Region r;
00155     if (n->t==NT_ADD && n->l == nullptr && n->r->t==NT_NONLIN) {
00156       n->r->sum.ne->post(home,frt,-n->c);
00157     } else if (n->t==NT_SUB && n->r->t==NT_NONLIN && n->l==nullptr) {
00158       switch (frt) {
00159       case FRT_LQ: frt=FRT_GQ; break;
00160       case FRT_LE: frt=FRT_GR; break;
00161       case FRT_GQ: frt=FRT_LQ; break;
00162       case FRT_GR: frt=FRT_LE; break;
00163       default: break;
00164       }
00165       n->r->sum.ne->post(home,frt,n->c);
00166     } else if (frt==FRT_EQ &&
00167                n->t==NT_SUB && n->r->t==NT_NONLIN &&
00168                n->l != nullptr && n->l->t==NT_VAR
00169                && n->l->a==1) {
00170       (void) n->r->sum.ne->post(home,&n->l->x_float);
00171     } else if (frt==FRT_EQ &&
00172                n->t==NT_SUB && n->r->t==NT_VAR &&
00173                n->l != nullptr && n->l->t==NT_NONLIN
00174                && n->r->a==1) {
00175       (void) n->l->sum.ne->post(home,&n->r->x_float);
00176     } else {
00177       Float::Linear::Term* fts =
00178         r.alloc<Float::Linear::Term>(n->n_float);
00179       FloatVal c = n->fill(home,fts);
00180       Float::Linear::post(home, fts, n->n_float, frt, -c);
00181     }
00182   }
00183 
00184   void
00185   LinFloatExpr::post(Home home, FloatRelType frt, const BoolVar& b) const {
00186     if (home.failed()) return;
00187     Region r;
00188     if (n->t==NT_ADD && n->l==nullptr && n->r->t==NT_NONLIN) {
00189       n->r->sum.ne->post(home,frt,-n->c,b);
00190     } else if (n->t==NT_SUB && n->l==nullptr && n->r->t==NT_NONLIN) {
00191       switch (frt) {
00192       case FRT_LQ: frt=FRT_GQ; break;
00193       case FRT_LE: frt=FRT_GR; break;
00194       case FRT_GQ: frt=FRT_LQ; break;
00195       case FRT_GR: frt=FRT_LE; break;
00196       default: break;
00197       }
00198       n->r->sum.ne->post(home,frt,n->c,b);
00199     } else {
00200       Float::Linear::Term* fts =
00201         r.alloc<Float::Linear::Term>(n->n_float);
00202       FloatVal c = n->fill(home,fts);
00203       Float::Linear::post(home, fts, n->n_float, frt, -c, b);
00204     }
00205 
00206   }
00207 
00208   FloatVar
00209   LinFloatExpr::post(Home home) const {
00210     if (home.failed()) return FloatVar(home,0,0);
00211     Region r;
00212     Float::Linear::Term* fts =
00213       r.alloc<Float::Linear::Term>(n->n_float+1);
00214     FloatVal c = n->fill(home,fts);
00215     if ((n->n_float == 1) && (c == 0) && (fts[0].a == 1))
00216       return fts[0].x;
00217     FloatNum min, max;
00218     Float::Linear::estimate(&fts[0],n->n_float,c,min,max);
00219     FloatVar x(home, min, max);
00220     fts[n->n_float].x = x; fts[n->n_float].a = -1;
00221     Float::Linear::post(home, fts, n->n_float+1, FRT_EQ, -c);
00222     return x;
00223 
00224   }
00225 
00226   LinFloatExpr::LinFloatExpr(void) :
00227     n(new Node) {
00228     n->n_float = 0;
00229     n->t = NT_VAR;
00230     n->l = n->r = nullptr;
00231     n->a = 0;
00232   }
00233 
00234   LinFloatExpr::LinFloatExpr(const FloatVal& c) :
00235     n(new Node) {
00236     n->n_float = 0;
00237     n->t = NT_CONST;
00238     n->l = n->r = nullptr;
00239     n->a = 0;
00240     Float::Limits::check(c,"MiniModel::LinFloatExpr");
00241     n->c = c;
00242   }
00243 
00244   LinFloatExpr::LinFloatExpr(const FloatVar& x) :
00245     n(new Node) {
00246     n->n_float = 1;
00247     n->t = NT_VAR;
00248     n->l = n->r = nullptr;
00249     n->a = 1.0;
00250     n->x_float = x;
00251   }
00252 
00253   LinFloatExpr::LinFloatExpr(const FloatVar& x, FloatVal a) :
00254     n(new Node) {
00255     n->n_float = 1;
00256     n->t = NT_VAR;
00257     n->l = n->r = nullptr;
00258     n->a = a;
00259     n->x_float = x;
00260   }
00261 
00262   LinFloatExpr::LinFloatExpr(const FloatVarArgs& x) :
00263     n(new Node) {
00264     n->n_float = x.size();
00265     n->t = NT_SUM;
00266     n->l = n->r = nullptr;
00267     if (x.size() > 0) {
00268       n->sum.tf = heap.alloc<Float::Linear::Term>(x.size());
00269       for (int i=x.size(); i--; ) {
00270         n->sum.tf[i].x = x[i];
00271         n->sum.tf[i].a = 1.0;
00272       }
00273     }
00274   }
00275 
00276   LinFloatExpr::LinFloatExpr(const FloatValArgs& a, const FloatVarArgs& x) :
00277     n(new Node) {
00278     if (a.size() != x.size())
00279       throw Float::ArgumentSizeMismatch("MiniModel::LinFloatExpr");
00280     n->n_float = x.size();
00281     n->t = NT_SUM;
00282     n->l = n->r = nullptr;
00283     if (x.size() > 0) {
00284       n->sum.tf = heap.alloc<Float::Linear::Term>(x.size());
00285       for (int i=x.size(); i--; ) {
00286         n->sum.tf[i].x = x[i];
00287         n->sum.tf[i].a = a[i];
00288       }
00289     }
00290   }
00291 
00292   LinFloatExpr::LinFloatExpr(const LinFloatExpr& e0, NodeType t, const LinFloatExpr& e1) :
00293     n(new Node) {
00294     n->n_float = e0.n->n_float + e1.n->n_float;
00295     n->t = t;
00296     n->l = e0.n; n->l->use++;
00297     n->r = e1.n; n->r->use++;
00298   }
00299 
00300   LinFloatExpr::LinFloatExpr(const LinFloatExpr& e, NodeType t, const FloatVal& c) :
00301     n(new Node) {
00302     n->n_float = e.n->n_float;
00303     n->t = t;
00304     n->l = nullptr;
00305     n->r = e.n; n->r->use++;
00306     n->c = c;
00307   }
00308 
00309   LinFloatExpr::LinFloatExpr(FloatVal a, const LinFloatExpr& e) :
00310     n(new Node) {
00311     n->n_float = e.n->n_float;
00312     n->t = NT_MUL;
00313     n->l = e.n; n->l->use++;
00314     n->r = nullptr;
00315     n->a = a;
00316   }
00317 
00318   LinFloatExpr::LinFloatExpr(NonLinFloatExpr* e) :
00319     n(new Node) {
00320     n->n_float = 1;
00321     n->t = NT_NONLIN;
00322     n->l = n->r = nullptr;
00323     n->a = 0;
00324     n->sum.ne = e;
00325   }
00326 
00327   const LinFloatExpr&
00328   LinFloatExpr::operator =(const LinFloatExpr& e) {
00329     if (this != &e) {
00330       if (n->decrement())
00331         delete n;
00332       n = e.n; n->use++;
00333     }
00334     return *this;
00335   }
00336 
00337   LinFloatExpr::~LinFloatExpr(void) {
00338     if (n->decrement())
00339       delete n;
00340   }
00341 
00342 
00343   void
00344   LinFloatExpr::Node::fill(Home home,
00345                            Float::Linear::Term*& tf,
00346                            FloatVal m, FloatVal& d) const {
00347     switch (this->t) {
00348     case NT_CONST:
00349       Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
00350       d += m*c;
00351       break;
00352     case NT_VAR:
00353       Float::Limits::check(m*a,"MiniModel::LinFloatExpr");
00354       tf->a=m*a; tf->x=x_float; tf++;
00355       break;
00356     case NT_NONLIN:
00357       tf->a=m; tf->x=sum.ne->post(home, nullptr); tf++;
00358       break;
00359     case NT_SUM:
00360       for (int i=n_float; i--; ) {
00361         Float::Limits::check(m*sum.tf[i].a,"MiniModel::LinFloatExpr");
00362         tf[i].x = sum.tf[i].x; tf[i].a = m*sum.tf[i].a;
00363       }
00364       tf += n_float;
00365       break;
00366     case NT_ADD:
00367       if (l == nullptr) {
00368         Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
00369         d += m*c;
00370       } else {
00371         l->fill(home,tf,m,d);
00372       }
00373       r->fill(home,tf,m,d);
00374       break;
00375     case NT_SUB:
00376       if (l == nullptr) {
00377         Float::Limits::check(m*c,"MiniModel::LinFloatExpr");
00378         d += m*c;
00379       } else {
00380         l->fill(home,tf,m,d);
00381       }
00382       r->fill(home,tf,-m,d);
00383       break;
00384     case NT_MUL:
00385       Float::Limits::check(m*a,"MiniModel::LinFloatExpr");
00386       l->fill(home,tf,m*a,d);
00387       break;
00388     default:
00389       GECODE_NEVER;
00390     }
00391   }
00392 
00393 
00394   /*
00395    * Operators
00396    *
00397    */
00398   LinFloatExpr
00399   operator +(const FloatVal& c, const FloatVar& x) {
00400     if (x.assigned() && Float::Limits::valid(c+x.val()))
00401       return LinFloatExpr(c+x.val());
00402     else
00403       return LinFloatExpr(x,LinFloatExpr::NT_ADD,c);
00404   }
00405   LinFloatExpr
00406   operator +(const FloatVal& c, const LinFloatExpr& e) {
00407     return LinFloatExpr(e,LinFloatExpr::NT_ADD,c);
00408   }
00409   LinFloatExpr
00410   operator +(const FloatVar& x, const FloatVal& c) {
00411     if (x.assigned() && Float::Limits::valid(c+x.val()))
00412       return LinFloatExpr(c+x.val());
00413     else
00414       return LinFloatExpr(x,LinFloatExpr::NT_ADD,c);
00415   }
00416   LinFloatExpr
00417   operator +(const LinFloatExpr& e, const FloatVal& c) {
00418     return LinFloatExpr(e,LinFloatExpr::NT_ADD,c);
00419   }
00420   LinFloatExpr
00421   operator +(const FloatVar& x, const FloatVar& y) {
00422     if (x.assigned())
00423       return x.val() + y;
00424     else if (y.assigned())
00425       return x + y.val();
00426     else
00427       return LinFloatExpr(x,LinFloatExpr::NT_ADD,(const LinFloatExpr&)y);
00428   }
00429   LinFloatExpr
00430   operator +(const FloatVar& x, const LinFloatExpr& e) {
00431     if (x.assigned())
00432       return x.val() + e;
00433     else
00434       return LinFloatExpr(x,LinFloatExpr::NT_ADD,e);
00435   }
00436   LinFloatExpr
00437   operator +(const LinFloatExpr& e, const FloatVar& x) {
00438     if (x.assigned())
00439       return e + x.val();
00440     else
00441       return LinFloatExpr(e,LinFloatExpr::NT_ADD,(const LinFloatExpr&)x);
00442   }
00443   LinFloatExpr
00444   operator +(const LinFloatExpr& e1, const LinFloatExpr& e2) {
00445     return LinFloatExpr(e1,LinFloatExpr::NT_ADD,e2);
00446   }
00447 
00448   LinFloatExpr
00449   operator -(const FloatVal& c, const FloatVar& x) {
00450     if (x.assigned() && Float::Limits::valid(c-x.val()))
00451       return LinFloatExpr(c-x.val());
00452     else
00453       return LinFloatExpr(x,LinFloatExpr::NT_SUB,c);
00454   }
00455   LinFloatExpr
00456   operator -(const FloatVal& c, const LinFloatExpr& e) {
00457     return LinFloatExpr(e,LinFloatExpr::NT_SUB,c);
00458   }
00459   LinFloatExpr
00460   operator -(const FloatVar& x, const FloatVal& c) {
00461     if (x.assigned() && Float::Limits::valid(x.val()-c))
00462       return LinFloatExpr(x.val()-c);
00463     else
00464       return LinFloatExpr(x,LinFloatExpr::NT_ADD,-c);
00465   }
00466   LinFloatExpr
00467   operator -(const LinFloatExpr& e, const FloatVal& c) {
00468     return LinFloatExpr(e,LinFloatExpr::NT_ADD,-c);
00469   }
00470   LinFloatExpr
00471   operator -(const FloatVar& x, const FloatVar& y) {
00472     if (x.assigned())
00473       return x.val() - y;
00474     else if (y.assigned())
00475       return x - y.val();
00476     else
00477       return LinFloatExpr(x,LinFloatExpr::NT_SUB,(const LinFloatExpr&)y);
00478   }
00479   LinFloatExpr
00480   operator -(const FloatVar& x, const LinFloatExpr& e) {
00481     if (x.assigned())
00482       return x.val() - e;
00483     else
00484       return LinFloatExpr(x,LinFloatExpr::NT_SUB,e);
00485   }
00486   LinFloatExpr
00487   operator -(const LinFloatExpr& e, const FloatVar& x) {
00488     if (x.assigned())
00489       return e - x.val();
00490     else
00491       return LinFloatExpr(e,LinFloatExpr::NT_SUB,(const LinFloatExpr&)x);
00492   }
00493   LinFloatExpr
00494   operator -(const LinFloatExpr& e1, const LinFloatExpr& e2) {
00495     return LinFloatExpr(e1,LinFloatExpr::NT_SUB,e2);
00496   }
00497 
00498   LinFloatExpr
00499   operator -(const FloatVar& x) {
00500     if (x.assigned())
00501       return LinFloatExpr(-x.val());
00502     else
00503       return LinFloatExpr(x,LinFloatExpr::NT_SUB,0);
00504   }
00505   LinFloatExpr
00506   operator -(const LinFloatExpr& e) {
00507     return LinFloatExpr(e,LinFloatExpr::NT_SUB,0);
00508   }
00509 
00510   LinFloatExpr
00511   operator *(const FloatVal& a, const FloatVar& x) {
00512     if (a == 0)
00513       return LinFloatExpr(0.0);
00514     else if (x.assigned() &&
00515              Float::Limits::valid(a*x.val()))
00516       return LinFloatExpr(a*x.val());
00517     else
00518       return LinFloatExpr(x,a);
00519   }
00520   LinFloatExpr
00521   operator *(const FloatVar& x, const FloatVal& a) {
00522     if (a == 0)
00523       return LinFloatExpr(0.0);
00524     else if (x.assigned() &&
00525              Float::Limits::valid(a*x.val()))
00526       return LinFloatExpr(a*x.val());
00527     else
00528       return LinFloatExpr(x,a);
00529   }
00530   LinFloatExpr
00531   operator *(const LinFloatExpr& e, const FloatVal& a) {
00532     if (a == 0)
00533       return LinFloatExpr(0.0);
00534     else
00535       return LinFloatExpr(a,e);
00536   }
00537   LinFloatExpr
00538   operator *(const FloatVal& a, const LinFloatExpr& e) {
00539     if (a == 0)
00540       return LinFloatExpr(0.0);
00541     else
00542       return LinFloatExpr(a,e);
00543   }
00544 
00545   LinFloatExpr
00546   sum(const FloatVarArgs& x) {
00547     return LinFloatExpr(x);
00548   }
00549 
00550   LinFloatExpr
00551   sum(const FloatValArgs& a, const FloatVarArgs& x) {
00552     return LinFloatExpr(a,x);
00553   }
00554 
00555   FloatVar
00556   expr(Home home, const LinFloatExpr& e) {
00557     PostInfo pi(home);
00558     if (!home.failed())
00559       return e.post(home);
00560     FloatVar x(home,Float::Limits::min,Float::Limits::max);
00561     return x;
00562   }
00563 
00564 }
00565 
00566 #endif
00567 
00568 // STATISTICS: minimodel-any