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