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
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, IntConLevel icl) const {
00083 IntVar y;
00084 switch (t) {
00085 case ANLE_ABS:
00086 {
00087 IntVar x = a[0].post(home, icl);
00088 if (x.min() >= 0)
00089 y = result(home,ret,x);
00090 else {
00091 y = result(home,ret);
00092 abs(home, x, y, icl);
00093 }
00094 }
00095 break;
00096 case ANLE_MIN:
00097 if (n==1) {
00098 y = result(home,ret, a[0].post(home, icl));
00099 } else if (n==2) {
00100 IntVar x0 = a[0].post(home, icl);
00101 IntVar x1 = a[1].post(home, icl);
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, icl);
00109 }
00110 } else {
00111 IntVarArgs x(n);
00112 for (int i=n; i--;)
00113 x[i] = a[i].post(home, icl);
00114 y = result(home,ret);
00115 min(home, x, y, icl);
00116 }
00117 break;
00118 case ANLE_MAX:
00119 if (n==1) {
00120 y = result(home,ret,a[0].post(home, icl));
00121 } else if (n==2) {
00122 IntVar x0 = a[0].post(home, icl);
00123 IntVar x1 = a[1].post(home, icl);
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, icl);
00131 }
00132 } else {
00133 IntVarArgs x(n);
00134 for (int i=n; i--;)
00135 x[i] = a[i].post(home, icl);
00136 y = result(home,ret);
00137 max(home, x, y, icl);
00138 }
00139 break;
00140 case ANLE_MULT:
00141 {
00142 assert(n == 2);
00143 IntVar x0 = a[0].post(home, icl);
00144 IntVar x1 = a[1].post(home, icl);
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, icl);
00156 }
00157 }
00158 break;
00159 case ANLE_DIV:
00160 {
00161 assert(n == 2);
00162 IntVar x0 = a[0].post(home, icl);
00163 IntVar x1 = a[1].post(home, icl);
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, icl);
00172 }
00173 }
00174 break;
00175 case ANLE_MOD:
00176 {
00177 assert(n == 2);
00178 IntVar x0 = a[0].post(home, icl);
00179 IntVar x1 = a[1].post(home, icl);
00180 y = result(home,ret);
00181 mod(home, x0, x1, y, icl);
00182 }
00183 break;
00184 case ANLE_SQR:
00185 {
00186 assert(n == 1);
00187 IntVar x = a[0].post(home, icl);
00188 if (x.assigned() && ((x.val() == 0) || (x.val() == 1)))
00189 y = x;
00190 else {
00191 y = result(home,ret);
00192 sqr(home, x, y, icl);
00193 }
00194 }
00195 break;
00196 case ANLE_SQRT:
00197 {
00198 assert(n == 1);
00199 IntVar x = a[0].post(home, icl);
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, icl);
00205 }
00206 }
00207 break;
00208 case ANLE_POW:
00209 {
00210 assert(n == 1);
00211 IntVar x = a[0].post(home, icl);
00212 if (x.assigned() && (aInt > 0) &&
00213 ((x.val() == 0) || (x.val() == 1)))
00214 y = x;
00215 else {
00216 y = result(home,ret);
00217 pow(home, x, aInt, y, icl);
00218 }
00219 }
00220 break;
00221 case ANLE_NROOT:
00222 {
00223 assert(n == 1);
00224 IntVar x = a[0].post(home, icl);
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, icl);
00231 }
00232 }
00233 break;
00234 case ANLE_ELMNT:
00235 {
00236 IntVar z = a[n-1].post(home, icl);
00237 if (z.assigned() && z.val() >= 0 && z.val() < n-1) {
00238 y = result(home,ret,a[z.val()].post(home, icl));
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, icl);
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, icl);
00253 } else {
00254 element(home, x, z, y, icl);
00255 }
00256 }
00257 }
00258 break;
00259 case ANLE_ITE:
00260 {
00261 assert(n == 2);
00262 BoolVar c = b.expr(home, icl);
00263 IntVar x0 = a[0].post(home, icl);
00264 IntVar x1 = a[1].post(home, icl);
00265 y = result(home,ret);
00266 ite(home, c, x0, x1, y, icl);
00267 }
00268 break;
00269 default:
00270 GECODE_NEVER;
00271 }
00272 return y;
00273 }
00274 virtual void post(Home home, IntRelType irt, int c,
00275 IntConLevel icl) 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, icl);
00281 rel(home, x, irt, c);
00282 } else {
00283 rel(home, post(home,NULL,icl), irt, c);
00284 }
00285 }
00286 virtual void post(Home home, IntRelType irt, int c,
00287 BoolVar b, IntConLevel icl) const {
00288 rel(home, post(home,NULL,icl), 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