Something went wrong. Try again.
This repository has no description
Something went wrong. Try again.
15 kB · 496 lines
C++
at develop
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- *//* * Main authors: * Christian Schulte <schulte@gecode.org> * * Copyright: * Christian Schulte, 2006 * * This file is part of Gecode, the generic constraint * development environment: * http://www.gecode.org * * Permission is hereby granted, free of charge, to any person obtaining * a copy of this software and associated documentation files (the * "Software"), to deal in the Software without restriction, including * without limitation the rights to use, copy, modify, merge, publish, * distribute, sublicense, and/or sell copies of the Software, and to * permit persons to whom the Software is furnished to do so, subject to * the following conditions: * * The above copyright notice and this permission notice shall be * included in all copies or substantial portions of the Software. * * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. * */
#include <gecode/minimodel.hh>
namespace Gecode { namespace MiniModel {
/// Non-linear arithmetic expressions over integer variables class GECODE_MINIMODEL_EXPORT ArithNonLinIntExpr : public NonLinIntExpr { public: /// The expression type enum ArithNonLinIntExprType { ANLE_ABS, ///< Absolute value expression ANLE_MIN, ///< Minimum expression ANLE_MAX, ///< Maximum expression ANLE_MULT, ///< Multiplication expression ANLE_DIV, ///< Division expression ANLE_MOD, ///< Modulo expression ANLE_SQR, ///< Square expression ANLE_SQRT, ///< Square root expression ANLE_POW, ///< Pow expression ANLE_NROOT, ///< Nroot expression ANLE_ELMNT, ///< Element expression ANLE_ITE ///< If-then-else expression } t; /// Expressions LinIntExpr* a; /// Size of variable array int n; /// Integer argument (used in nroot for example) int aInt; /// Boolean expression argument (used in ite for example) BoolExpr b; /// Constructor ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0) : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0) {} /// Constructor ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0, int a0) : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0), aInt(a0) {} /// Constructor ArithNonLinIntExpr(ArithNonLinIntExprType t0, int n0, const BoolExpr& b0) : t(t0), a(heap.alloc<LinIntExpr>(n0)), n(n0), b(b0) {} /// Destructor ~ArithNonLinIntExpr(void) { heap.free<LinIntExpr>(a,n); } /// Post expression virtual IntVar post(Home home, IntVar* ret, const IntPropLevels& ipls) const { IntVar y; switch (t) { case ANLE_ABS: { IntVar x = a[0].post(home, ipls); if (x.min() >= 0) y = result(home,ret,x); else { y = result(home,ret); abs(home, x, y, ipls.abs()); } } break; case ANLE_MIN: if (n==1) { y = result(home,ret, a[0].post(home, ipls)); } else if (n==2) { IntVar x0 = a[0].post(home, ipls); IntVar x1 = a[1].post(home, ipls); if (x0.max() <= x1.min()) y = result(home,ret,x0); else if (x1.max() <= x0.min()) y = result(home,ret,x1); else { y = result(home,ret); min(home, x0, x1, y, ipls.min2()); } } else { IntVarArgs x(n); for (int i=n; i--;) x[i] = a[i].post(home, ipls); y = result(home,ret); min(home, x, y, ipls.min()); } break; case ANLE_MAX: if (n==1) { y = result(home,ret,a[0].post(home, ipls)); } else if (n==2) { IntVar x0 = a[0].post(home, ipls); IntVar x1 = a[1].post(home, ipls); if (x0.max() <= x1.min()) y = result(home,ret,x1); else if (x1.max() <= x0.min()) y = result(home,ret,x0); else { y = result(home,ret); max(home, x0, x1, y, ipls.max2()); } } else { IntVarArgs x(n); for (int i=n; i--;) x[i] = a[i].post(home, ipls); y = result(home,ret); max(home, x, y, ipls.max()); } break; case ANLE_MULT: { assert(n == 2); IntVar x0 = a[0].post(home, ipls); IntVar x1 = a[1].post(home, ipls); if (x0.assigned() && (x0.val() == 0)) y = result(home,ret,x0); else if (x0.assigned() && (x0.val() == 1)) y = result(home,ret,x1); else if (x1.assigned() && (x1.val() == 0)) y = result(home,ret,x1); else if (x1.assigned() && (x1.val() == 1)) y = result(home,ret,x0); else { y = result(home,ret); mult(home, x0, x1, y, ipls.mult()); } } break; case ANLE_DIV: { assert(n == 2); IntVar x0 = a[0].post(home, ipls); IntVar x1 = a[1].post(home, ipls); rel(home, x1, IRT_NQ, 0); if (x1.assigned() && (x1.val() == 1)) y = result(home,ret,x0); else if (x0.assigned() && (x0.val() == 0)) y = result(home,ret,x0); else { y = result(home,ret); div(home, x0, x1, y, ipls.div()); } } break; case ANLE_MOD: { assert(n == 2); IntVar x0 = a[0].post(home, ipls); IntVar x1 = a[1].post(home, ipls); y = result(home,ret); mod(home, x0, x1, y, ipls.mod()); } break; case ANLE_SQR: { assert(n == 1); IntVar x = a[0].post(home, ipls); if (x.assigned() && ((x.val() == 0) || (x.val() == 1))) y = result(home,ret,x); else { y = result(home,ret); sqr(home, x, y, ipls.sqr()); } } break; case ANLE_SQRT: { assert(n == 1); IntVar x = a[0].post(home, ipls); if (x.assigned() && ((x.val() == 0) || (x.val() == 1))) y = result(home,ret,x); else { y = result(home,ret); sqrt(home, x, y, ipls.sqrt()); } } break; case ANLE_POW: { assert(n == 1); IntVar x = a[0].post(home, ipls); if (x.assigned() && (aInt > 0) && ((x.val() == 0) || (x.val() == 1))) y = result(home,ret,x); else { y = result(home,ret); pow(home, x, aInt, y, ipls.pow()); } } break; case ANLE_NROOT: { assert(n == 1); IntVar x = a[0].post(home, ipls); if (x.assigned() && (aInt > 0) && ((x.val() == 0) || (x.val() == 1))) y = result(home,ret,x); else { y = result(home,ret); nroot(home, x, aInt, y, ipls.nroot()); } } break; case ANLE_ELMNT: { IntVar z = a[n-1].post(home, ipls); if (z.assigned() && z.val() >= 0 && z.val() < n-1) { y = result(home,ret,a[z.val()].post(home, ipls)); } else { IntVarArgs x(n-1); bool assigned = true; for (int i=n-1; i--;) { x[i] = a[i].post(home, ipls); if (!x[i].assigned()) assigned = false; } y = result(home,ret); if (assigned) { IntArgs xa(n-1); for (int i=n-1; i--;) xa[i] = x[i].val(); element(home, xa, z, y, ipls.element()); } else { element(home, x, z, y, ipls.element()); } } } break; case ANLE_ITE: { assert(n == 2); BoolVar c = b.expr(home, ipls); IntVar x0 = a[0].post(home, ipls); IntVar x1 = a[1].post(home, ipls); y = result(home,ret); ite(home, c, x0, x1, y, ipls.ite()); } break; default: GECODE_NEVER; } return y; } virtual void post(Home home, IntRelType irt, int c, const IntPropLevels& ipls) const { if ((t == ANLE_MIN && (irt == IRT_GQ || irt == IRT_GR)) || (t == ANLE_MAX && (irt == IRT_LQ || irt == IRT_LE)) ) { IntVarArgs x(n); for (int i=n; i--;) x[i] = a[i].post(home, ipls); rel(home, x, irt, c); } else { rel(home, post(home,nullptr,ipls), irt, c); } } virtual void post(Home home, IntRelType irt, int c, BoolVar b, const IntPropLevels& ipls) const { rel(home, post(home,nullptr,ipls), irt, c, b); } }; /// Check if \a e is of type \a t bool hasType(const LinIntExpr& e, ArithNonLinIntExpr::ArithNonLinIntExprType t) { return e.nle() && dynamic_cast<ArithNonLinIntExpr*>(e.nle()) != nullptr && dynamic_cast<ArithNonLinIntExpr*>(e.nle())->t == t; }
}}
namespace Gecode {
LinIntExpr abs(const LinIntExpr& e) { using namespace MiniModel; if (hasType(e, ArithNonLinIntExpr::ANLE_ABS)) return e; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ABS,1); ae->a[0] = e; return LinIntExpr(ae); }
LinIntExpr min(const LinIntExpr& e0, const LinIntExpr& e1) { using namespace MiniModel; int n = 0; if (hasType(e0, ArithNonLinIntExpr::ANLE_MIN)) n += static_cast<ArithNonLinIntExpr*>(e0.nle())->n; else n += 1; if (hasType(e1, ArithNonLinIntExpr::ANLE_MIN)) n += static_cast<ArithNonLinIntExpr*>(e1.nle())->n; else n += 1; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MIN,n); int i=0; if (hasType(e0, ArithNonLinIntExpr::ANLE_MIN)) { ArithNonLinIntExpr* e0e = static_cast<ArithNonLinIntExpr*>(e0.nle()); for (; i<e0e->n; i++) ae->a[i] = e0e->a[i]; } else { ae->a[i++] = e0; } if (hasType(e1, ArithNonLinIntExpr::ANLE_MIN)) { ArithNonLinIntExpr* e1e = static_cast<ArithNonLinIntExpr*>(e1.nle()); int curN = i; for (; i<curN+e1e->n; i++) ae->a[i] = e1e->a[i-curN]; } else { ae->a[i++] = e1; } return LinIntExpr(ae); }
LinIntExpr max(const LinIntExpr& e0, const LinIntExpr& e1) { using namespace MiniModel; int n = 0; if (hasType(e0, ArithNonLinIntExpr::ANLE_MAX)) n += static_cast<ArithNonLinIntExpr*>(e0.nle())->n; else n += 1; if (hasType(e1, ArithNonLinIntExpr::ANLE_MAX)) n += static_cast<ArithNonLinIntExpr*>(e1.nle())->n; else n += 1; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MAX,n); int i=0; if (hasType(e0, ArithNonLinIntExpr::ANLE_MAX)) { ArithNonLinIntExpr* e0e = static_cast<ArithNonLinIntExpr*>(e0.nle()); for (; i<e0e->n; i++) ae->a[i] = e0e->a[i]; } else { ae->a[i++] = e0; } if (hasType(e1, ArithNonLinIntExpr::ANLE_MAX)) { ArithNonLinIntExpr* e1e = static_cast<ArithNonLinIntExpr*>(e1.nle()); int curN = i; for (; i<curN+e1e->n; i++) ae->a[i] = e1e->a[i-curN]; } else { ae->a[i++] = e1; } return LinIntExpr(ae); }
LinIntExpr min(const IntVarArgs& x) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MIN,x.size()); for (int i=x.size(); i--;) ae->a[i] = x[i]; return LinIntExpr(ae); }
LinIntExpr max(const IntVarArgs& x) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MAX,x.size()); for (int i=x.size(); i--;) ae->a[i] = x[i]; return LinIntExpr(ae); }
LinIntExpr operator *(const LinIntExpr& e0, const LinIntExpr& e1) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MULT,2); ae->a[0] = e0; ae->a[1] = e1; return LinIntExpr(ae); }
LinIntExpr sqr(const LinIntExpr& e) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_SQR,1); ae->a[0] = e; return LinIntExpr(ae); }
LinIntExpr sqrt(const LinIntExpr& e) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_SQRT,1); ae->a[0] = e; return LinIntExpr(ae); }
LinIntExpr pow(const LinIntExpr& e, int n) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_POW,1,n); ae->a[0] = e; return LinIntExpr(ae); }
LinIntExpr nroot(const LinIntExpr& e, int n) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_NROOT,1,n); ae->a[0] = e; return LinIntExpr(ae); }
LinIntExpr operator /(const LinIntExpr& e0, const LinIntExpr& e1) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_DIV,2); ae->a[0] = e0; ae->a[1] = e1; return LinIntExpr(ae); }
LinIntExpr operator %(const LinIntExpr& e0, const LinIntExpr& e1) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_MOD,2); ae->a[0] = e0; ae->a[1] = e1; return LinIntExpr(ae); }
LinIntExpr element(const IntVarArgs& x, const LinIntExpr& e) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ELMNT,x.size()+1); for (int i=x.size(); i--;) ae->a[i] = x[i]; ae->a[x.size()] = e; return LinIntExpr(ae); }
LinIntExpr element(const IntArgs& x, const LinIntExpr& e) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ELMNT,x.size()+1); for (int i=x.size(); i--;) ae->a[i] = x[i]; ae->a[x.size()] = e; return LinIntExpr(ae); }
LinIntExpr ite(const BoolExpr& b, const LinIntExpr& e0, const LinIntExpr& e1) { using namespace MiniModel; ArithNonLinIntExpr* ae = new ArithNonLinIntExpr(ArithNonLinIntExpr::ANLE_ITE,2,b); ae->a[0] = e0; ae->a[1] = e1; return LinIntExpr(ae); }
}
// STATISTICS: minimodel-any