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