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

int-arith.cpp

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  *
00006  *  Copyright:
00007  *     Christian Schulte, 2006
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 namespace Gecode { namespace MiniModel {
00037 
00039   class GECODE_MINIMODEL_EXPORT ArithNonLinIntExpr : public NonLinIntExpr {
00040   public:
00042     enum ArithNonLinIntExprType {
00043       ANLE_ABS,   
00044       ANLE_MIN,   
00045       ANLE_MAX,   
00046       ANLE_MULT,  
00047       ANLE_DIV,   
00048       ANLE_MOD,   
00049       ANLE_SQR,   
00050       ANLE_SQRT,  
00051       ANLE_POW,   
00052       ANLE_NROOT, 
00053       ANLE_ELMNT, 
00054       ANLE_ITE    
00055     } t;
00057     LinIntExpr* a;
00059     int n;
00061     int aInt;
00063     BoolExpr b;
00065     ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0)
00066       : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0) {}
00068     ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0, int a0)
00069       : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0), aInt(a0) {}
00071     ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0, const BoolExpr& b0)
00072       : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0), b(b0) {}
00074     ~ArithNonLinIntExpr(void) {
00075       heap.free<LinIntExpr>(a,n);
00076     }
00078     virtual IntVar post(Home home, IntVar* ret,
00079                         const IntPropLevels& ipls) const {
00080       IntVar y;
00081       switch (t) {
00082       case ANLE_ABS:
00083         {
00084           IntVar x = a[0].post(home, ipls);
00085           if (x.min() >= 0)
00086             y = result(home,ret,x);
00087           else {
00088             y = result(home,ret);
00089             abs(home, x, y, ipls.abs());
00090           }
00091         }
00092         break;
00093       case ANLE_MIN:
00094         if (n==1) {
00095           y = result(home,ret, a[0].post(home, ipls));
00096         } else if (n==2) {
00097           IntVar x0 = a[0].post(home, ipls);
00098           IntVar x1 = a[1].post(home, ipls);
00099           if (x0.max() <= x1.min())
00100             y = result(home,ret,x0);
00101           else if (x1.max() <= x0.min())
00102             y = result(home,ret,x1);
00103           else {
00104             y = result(home,ret);
00105             min(home, x0, x1, y, ipls.min2());
00106           }
00107         } else {
00108           IntVarArgs x(n);
00109           for (int i=n; i--;)
00110             x[i] = a[i].post(home, ipls);
00111           y = result(home,ret);
00112           min(home, x, y, ipls.min());
00113         }
00114         break;
00115       case ANLE_MAX:
00116         if (n==1) {
00117           y = result(home,ret,a[0].post(home, ipls));
00118         } else if (n==2) {
00119           IntVar x0 = a[0].post(home, ipls);
00120           IntVar x1 = a[1].post(home, ipls);
00121           if (x0.max() <= x1.min())
00122             y = result(home,ret,x1);
00123           else if (x1.max() <= x0.min())
00124             y = result(home,ret,x0);
00125           else {
00126             y = result(home,ret);
00127             max(home, x0, x1, y, ipls.max2());
00128           }
00129         } else {
00130           IntVarArgs x(n);
00131           for (int i=n; i--;)
00132             x[i] = a[i].post(home, ipls);
00133           y = result(home,ret);
00134           max(home, x, y, ipls.max());
00135         }
00136         break;
00137       case ANLE_MULT:
00138         {
00139           assert(n == 2);
00140           IntVar x0 = a[0].post(home, ipls);
00141           IntVar x1 = a[1].post(home, ipls);
00142           if (x0.assigned() && (x0.val() == 0))
00143             y = result(home,ret,x0);
00144           else if (x0.assigned() && (x0.val() == 1))
00145             y = result(home,ret,x1);
00146           else if (x1.assigned() && (x1.val() == 0))
00147             y = result(home,ret,x1);
00148           else if (x1.assigned() && (x1.val() == 1))
00149             y = result(home,ret,x0);
00150           else {
00151             y = result(home,ret);
00152             mult(home, x0, x1, y, ipls.mult());
00153           }
00154         }
00155         break;
00156       case ANLE_DIV:
00157         {
00158           assert(n == 2);
00159           IntVar x0 = a[0].post(home, ipls);
00160           IntVar x1 = a[1].post(home, ipls);
00161           rel(home, x1, IRT_NQ, 0);
00162           if (x1.assigned() && (x1.val() == 1))
00163             y = result(home,ret,x0);
00164           else if (x0.assigned() && (x0.val() == 0))
00165             y = result(home,ret,x0);
00166           else {
00167             y = result(home,ret);
00168             div(home, x0, x1, y, ipls.div());
00169           }
00170         }
00171         break;
00172       case ANLE_MOD:
00173         {
00174           assert(n == 2);
00175           IntVar x0 = a[0].post(home, ipls);
00176           IntVar x1 = a[1].post(home, ipls);
00177           y = result(home,ret);
00178           mod(home, x0, x1, y, ipls.mod());
00179         }
00180         break;
00181       case ANLE_SQR:
00182         {
00183           assert(n == 1);
00184           IntVar x = a[0].post(home, ipls);
00185           if (x.assigned() && ((x.val() == 0) || (x.val() == 1)))
00186             y = result(home,ret,x);
00187           else {
00188             y = result(home,ret);
00189             sqr(home, x, y, ipls.sqr());
00190           }
00191         }
00192         break;
00193       case ANLE_SQRT:
00194         {
00195           assert(n == 1);
00196           IntVar x = a[0].post(home, ipls);
00197           if (x.assigned() && ((x.val() == 0) || (x.val() == 1)))
00198             y = result(home,ret,x);
00199           else {
00200             y = result(home,ret);
00201             sqrt(home, x, y, ipls.sqrt());
00202           }
00203         }
00204         break;
00205       case ANLE_POW:
00206         {
00207           assert(n == 1);
00208           IntVar x = a[0].post(home, ipls);
00209           if (x.assigned() && (aInt > 0) &&
00210               ((x.val() == 0) || (x.val() == 1)))
00211             y = result(home,ret,x);
00212           else {
00213             y = result(home,ret);
00214             pow(home, x, aInt, y, ipls.pow());
00215           }
00216         }
00217         break;
00218       case ANLE_NROOT:
00219         {
00220           assert(n == 1);
00221           IntVar x = a[0].post(home, ipls);
00222           if (x.assigned() && (aInt > 0) &&
00223               ((x.val() == 0) || (x.val() == 1)))
00224             y = result(home,ret,x);
00225           else {
00226             y = result(home,ret);
00227             nroot(home, x, aInt, y, ipls.nroot());
00228           }
00229         }
00230         break;
00231       case ANLE_ELMNT:
00232         {
00233           IntVar z = a[n-1].post(home, ipls);
00234           if (z.assigned() && z.val() >= 0 && z.val() < n-1) {
00235             y = result(home,ret,a[z.val()].post(home, ipls));
00236           } else {
00237             IntVarArgs x(n-1);
00238             bool assigned = true;
00239             for (int i=n-1; i--;) {
00240               x[i] = a[i].post(home, ipls);
00241               if (!x[i].assigned())
00242                 assigned = false;
00243             }
00244             y = result(home,ret);
00245             if (assigned) {
00246               IntArgs xa(n-1);
00247               for (int i=n-1; i--;)
00248                 xa[i] = x[i].val();
00249               element(home, xa, z, y, ipls.element());
00250             } else {
00251               element(home, x, z, y, ipls.element());
00252             }
00253           }
00254         }
00255         break;
00256       case ANLE_ITE:
00257         {
00258           assert(n == 2);
00259           BoolVar c = b.expr(home, ipls);
00260           IntVar x0 = a[0].post(home, ipls);
00261           IntVar x1 = a[1].post(home, ipls);
00262           y = result(home,ret);
00263           ite(home, c, x0, x1, y, ipls.ite());
00264         }
00265         break;
00266       default:
00267         GECODE_NEVER;
00268       }
00269       return y;
00270     }
00271     virtual void post(Home home, IntRelType irt, int c,
00272                       const IntPropLevels& ipls) const {
00273       if ((t == ANLE_MIN && (irt == IRT_GQ || irt == IRT_GR)) ||
00274           (t == ANLE_MAX && (irt == IRT_LQ || irt == IRT_LE)) ) {
00275         IntVarArgs x(n);
00276         for (int i=n; i--;)
00277           x[i] = a[i].post(home, ipls);
00278         rel(home, x, irt, c);
00279       } else {
00280         rel(home, post(home,nullptr,ipls), irt, c);
00281       }
00282     }
00283     virtual void post(Home home, IntRelType irt, int c, BoolVar b,
00284                       const IntPropLevels& ipls) const {
00285       rel(home, post(home,nullptr,ipls), irt, c, b);
00286     }
00287   };
00289   bool hasType(const LinIntExpr& e, ArithNonLinIntExpr::ArithNonLinIntExprType t) {
00290     return e.nle() &&
00291       dynamic_cast<ArithNonLinIntExpr*>(e.nle()) != nullptr &&
00292       dynamic_cast<ArithNonLinIntExpr*>(e.nle())->t == t;
00293   }
00294 
00295 }}
00296 
00297 namespace Gecode {
00298 
00299   LinIntExpr
00300   abs(const LinIntExpr& e) {
00301     using namespace MiniModel;
00302     if (hasType(e, ArithNonLinIntExpr::ANLE_ABS))
00303       return e;
00304     ArithNonLinIntExpr* ae =
00305       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ABS,1);
00306     ae->a[0] = e;
00307     return LinIntExpr(ae);
00308   }
00309 
00310   LinIntExpr
00311   min(const LinIntExpr& e0, const LinIntExpr& e1) {
00312     using namespace MiniModel;
00313     int n = 0;
00314     if (hasType(e0, ArithNonLinIntExpr::ANLE_MIN))
00315       n += static_cast<ArithNonLinIntExpr*>(e0.nle())->n;
00316     else
00317       n += 1;
00318     if (hasType(e1, ArithNonLinIntExpr::ANLE_MIN))
00319       n += static_cast<ArithNonLinIntExpr*>(e1.nle())->n;
00320     else
00321       n += 1;
00322     ArithNonLinIntExpr* ae =
00323       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MIN,n);
00324     int i=0;
00325     if (hasType(e0, ArithNonLinIntExpr::ANLE_MIN)) {
00326       ArithNonLinIntExpr* e0e = static_cast<ArithNonLinIntExpr*>(e0.nle());
00327       for (; i<e0e->n; i++)
00328         ae->a[i] = e0e->a[i];
00329     } else {
00330       ae->a[i++] = e0;
00331     }
00332     if (hasType(e1, ArithNonLinIntExpr::ANLE_MIN)) {
00333       ArithNonLinIntExpr* e1e = static_cast<ArithNonLinIntExpr*>(e1.nle());
00334       int curN = i;
00335       for (; i<curN+e1e->n; i++)
00336         ae->a[i] = e1e->a[i-curN];
00337     } else {
00338       ae->a[i++] = e1;
00339     }
00340     return LinIntExpr(ae);
00341   }
00342 
00343   LinIntExpr
00344   max(const LinIntExpr& e0, const LinIntExpr& e1) {
00345     using namespace MiniModel;
00346     int n = 0;
00347     if (hasType(e0, ArithNonLinIntExpr::ANLE_MAX))
00348       n += static_cast<ArithNonLinIntExpr*>(e0.nle())->n;
00349     else
00350       n += 1;
00351     if (hasType(e1, ArithNonLinIntExpr::ANLE_MAX))
00352       n += static_cast<ArithNonLinIntExpr*>(e1.nle())->n;
00353     else
00354       n += 1;
00355     ArithNonLinIntExpr* ae =
00356       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MAX,n);
00357     int i=0;
00358     if (hasType(e0, ArithNonLinIntExpr::ANLE_MAX)) {
00359       ArithNonLinIntExpr* e0e = static_cast<ArithNonLinIntExpr*>(e0.nle());
00360       for (; i<e0e->n; i++)
00361         ae->a[i] = e0e->a[i];
00362     } else {
00363       ae->a[i++] = e0;
00364     }
00365     if (hasType(e1, ArithNonLinIntExpr::ANLE_MAX)) {
00366       ArithNonLinIntExpr* e1e = static_cast<ArithNonLinIntExpr*>(e1.nle());
00367       int curN = i;
00368       for (; i<curN+e1e->n; i++)
00369         ae->a[i] = e1e->a[i-curN];
00370     } else {
00371       ae->a[i++] = e1;
00372     }
00373     return LinIntExpr(ae);
00374   }
00375 
00376   LinIntExpr
00377   min(const IntVarArgs& x) {
00378     using namespace MiniModel;
00379     ArithNonLinIntExpr* ae =
00380       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MIN,x.size());
00381     for (int i=x.size(); i--;)
00382       ae->a[i] = x[i];
00383     return LinIntExpr(ae);
00384   }
00385 
00386   LinIntExpr
00387   max(const IntVarArgs& x) {
00388     using namespace MiniModel;
00389     ArithNonLinIntExpr* ae =
00390       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MAX,x.size());
00391     for (int i=x.size(); i--;)
00392       ae->a[i] = x[i];
00393     return LinIntExpr(ae);
00394   }
00395 
00396   LinIntExpr
00397   operator *(const LinIntExpr& e0, const LinIntExpr& e1) {
00398     using namespace MiniModel;
00399     ArithNonLinIntExpr* ae =
00400       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MULT,2);
00401     ae->a[0] = e0;
00402     ae->a[1] = e1;
00403     return LinIntExpr(ae);
00404   }
00405 
00406   LinIntExpr
00407   sqr(const LinIntExpr& e) {
00408     using namespace MiniModel;
00409     ArithNonLinIntExpr* ae =
00410       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_SQR,1);
00411     ae->a[0] = e;
00412     return LinIntExpr(ae);
00413   }
00414 
00415   LinIntExpr
00416   sqrt(const LinIntExpr& e) {
00417     using namespace MiniModel;
00418     ArithNonLinIntExpr* ae =
00419       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_SQRT,1);
00420     ae->a[0] = e;
00421     return LinIntExpr(ae);
00422   }
00423 
00424   LinIntExpr
00425   pow(const LinIntExpr& e, int n) {
00426     using namespace MiniModel;
00427     ArithNonLinIntExpr* ae =
00428       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_POW,1,n);
00429     ae->a[0] = e;
00430     return LinIntExpr(ae);
00431   }
00432 
00433   LinIntExpr
00434   nroot(const LinIntExpr& e, int n) {
00435     using namespace MiniModel;
00436     ArithNonLinIntExpr* ae =
00437       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_NROOT,1,n);
00438     ae->a[0] = e;
00439     return LinIntExpr(ae);
00440   }
00441 
00442   LinIntExpr
00443   operator /(const LinIntExpr& e0, const LinIntExpr& e1) {
00444     using namespace MiniModel;
00445     ArithNonLinIntExpr* ae =
00446       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_DIV,2);
00447     ae->a[0] = e0;
00448     ae->a[1] = e1;
00449     return LinIntExpr(ae);
00450   }
00451 
00452   LinIntExpr
00453   operator %(const LinIntExpr& e0, const LinIntExpr& e1) {
00454     using namespace MiniModel;
00455     ArithNonLinIntExpr* ae =
00456       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MOD,2);
00457     ae->a[0] = e0;
00458     ae->a[1] = e1;
00459     return LinIntExpr(ae);
00460   }
00461 
00462   LinIntExpr
00463   element(const IntVarArgs& x, const LinIntExpr& e) {
00464     using namespace MiniModel;
00465     ArithNonLinIntExpr* ae =
00466       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ELMNT,x.size()+1);
00467     for (int i=x.size(); i--;)
00468       ae->a[i] = x[i];
00469     ae->a[x.size()] = e;
00470     return LinIntExpr(ae);
00471   }
00472 
00473   LinIntExpr
00474   element(const IntArgs& x, const LinIntExpr& e) {
00475     using namespace MiniModel;
00476     ArithNonLinIntExpr* ae =
00477       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ELMNT,x.size()+1);
00478     for (int i=x.size(); i--;)
00479       ae->a[i] = x[i];
00480     ae->a[x.size()] = e;
00481     return LinIntExpr(ae);
00482   }
00483 
00484   LinIntExpr
00485   ite(const BoolExpr& b, const LinIntExpr& e0, const LinIntExpr& e1) {
00486     using namespace MiniModel;
00487     ArithNonLinIntExpr* ae =
00488       new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ITE,2,b);
00489     ae->a[0] = e0;
00490     ae->a[1] = e1;
00491     return LinIntExpr(ae);
00492   }
00493 
00494 }
00495 
00496 // STATISTICS: minimodel-any