00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
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