arithmetic.cpp
Go to the documentation of this file.
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: 2010-07-15 22:33:36 +0200 (Thu, 15 Jul 2010) $ by $Author: tack $ 00011 * $Revision: 11206 $ 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 { 00041 00042 namespace MiniModel { 00044 class GECODE_MINIMODEL_EXPORT ArithNonLinExpr : public NonLinExpr { 00045 public: 00047 enum ArithNonLinExprType { 00048 ANLE_ABS, 00049 ANLE_MIN, 00050 ANLE_MAX, 00051 ANLE_MULT, 00052 ANLE_DIV, 00053 ANLE_MOD, 00054 ANLE_SQR, 00055 ANLE_SQRT, 00056 ANLE_ELMNT 00057 } t; 00059 LinExpr* a; 00061 int n; 00063 ArithNonLinExpr(ArithNonLinExprType t0, int n0) 00064 : t(t0), a(heap.alloc<LinExpr>(n0)), n(n0) {} 00066 ~ArithNonLinExpr(void) { heap.free<LinExpr>(a,n); } 00068 virtual IntVar post(Home home, IntVar* ret, IntConLevel icl) const { 00069 IntVar y; 00070 switch (t) { 00071 case ANLE_ABS: 00072 { 00073 IntVar x = a[0].post(home, icl); 00074 if (x.min() >= 0) 00075 y = result(home,ret,x); 00076 else { 00077 y = result(home,ret); 00078 abs(home, x, y, icl); 00079 } 00080 } 00081 break; 00082 case ANLE_MIN: 00083 if (n==1) { 00084 y = result(home,ret, a[0].post(home, icl)); 00085 } else if (n==2) { 00086 IntVar x0 = a[0].post(home, icl); 00087 IntVar x1 = a[1].post(home, icl); 00088 if (x0.max() <= x1.min()) 00089 y = result(home,ret,x0); 00090 else if (x1.max() <= x0.min()) 00091 y = result(home,ret,x1); 00092 else { 00093 y = result(home,ret); 00094 min(home, x0, x1, y, icl); 00095 } 00096 } else { 00097 IntVarArgs x(n); 00098 for (int i=n; i--;) 00099 x[i] = a[i].post(home, icl); 00100 y = result(home,ret); 00101 min(home, x, y, icl); 00102 } 00103 break; 00104 case ANLE_MAX: 00105 if (n==1) { 00106 y = result(home,ret,a[0].post(home, icl)); 00107 } else if (n==2) { 00108 IntVar x0 = a[0].post(home, icl); 00109 IntVar x1 = a[1].post(home, icl); 00110 if (x0.max() <= x1.min()) 00111 y = result(home,ret,x1); 00112 else if (x1.max() <= x0.min()) 00113 y = result(home,ret,x0); 00114 else { 00115 y = result(home,ret); 00116 max(home, x0, x1, y, icl); 00117 } 00118 } else { 00119 IntVarArgs x(n); 00120 for (int i=n; i--;) 00121 x[i] = a[i].post(home, icl); 00122 y = result(home,ret); 00123 max(home, x, y, icl); 00124 } 00125 break; 00126 case ANLE_MULT: 00127 { 00128 assert(n == 2); 00129 IntVar x0 = a[0].post(home, icl); 00130 IntVar x1 = a[1].post(home, icl); 00131 if (x0.assigned() && (x0.val() == 0)) 00132 y = result(home,ret,x0); 00133 else if (x0.assigned() && (x0.val() == 1)) 00134 y = result(home,ret,x1); 00135 else if (x1.assigned() && (x1.val() == 0)) 00136 y = result(home,ret,x1); 00137 else if (x1.assigned() && (x1.val() == 1)) 00138 y = result(home,ret,x0); 00139 else { 00140 y = result(home,ret); 00141 mult(home, x0, x1, y, icl); 00142 } 00143 } 00144 break; 00145 case ANLE_DIV: 00146 { 00147 assert(n == 2); 00148 IntVar x0 = a[0].post(home, icl); 00149 IntVar x1 = a[1].post(home, icl); 00150 rel(home, x1, IRT_NQ, 0); 00151 if (x1.assigned() && (x1.val() == 1)) 00152 y = result(home,ret,x0); 00153 else if (x0.assigned() && (x0.val() == 0)) 00154 y = result(home,ret,x0); 00155 else { 00156 y = result(home,ret); 00157 div(home, x0, x1, y, icl); 00158 } 00159 } 00160 break; 00161 case ANLE_MOD: 00162 { 00163 assert(n == 2); 00164 IntVar x0 = a[0].post(home, icl); 00165 IntVar x1 = a[1].post(home, icl); 00166 y = result(home,ret); 00167 mod(home, x0, x1, y, icl); 00168 } 00169 break; 00170 case ANLE_SQR: 00171 { 00172 assert(n == 1); 00173 IntVar x = a[0].post(home, icl); 00174 if (x.assigned() && ((x.val() == 0) || (x.val() == 1))) 00175 y = x; 00176 else { 00177 y = result(home,ret); 00178 sqr(home, x, y, icl); 00179 } 00180 } 00181 break; 00182 case ANLE_SQRT: 00183 { 00184 assert(n == 1); 00185 IntVar x = a[0].post(home, icl); 00186 if (x.assigned() && ((x.val() == 0) || (x.val() == 1))) 00187 y = result(home,ret,x); 00188 else { 00189 y = result(home,ret); 00190 sqrt(home, x, y, icl); 00191 } 00192 } 00193 break; 00194 case ANLE_ELMNT: 00195 { 00196 IntVar z = a[n-1].post(home, icl); 00197 if (z.assigned() && z.val() >= 0 && z.val() < n-1) { 00198 y = result(home,ret,a[z.val()].post(home, icl)); 00199 } else { 00200 IntVarArgs x(n-1); 00201 bool assigned = true; 00202 for (int i=n-1; i--;) { 00203 x[i] = a[i].post(home, icl); 00204 if (!x[i].assigned()) 00205 assigned = false; 00206 } 00207 y = result(home,ret); 00208 if (assigned) { 00209 IntArgs xa(n-1); 00210 for (int i=n-1; i--;) 00211 xa[i] = x[i].val(); 00212 element(home, xa, z, y, icl); 00213 } else { 00214 element(home, x, z, y, icl); 00215 } 00216 } 00217 } 00218 break; 00219 default: 00220 GECODE_NEVER; 00221 } 00222 return y; 00223 } 00224 virtual void post(Home home, IntRelType irt, int c, 00225 IntConLevel icl) const { 00226 if ( (t == ANLE_MIN && (irt == IRT_GQ || irt == IRT_GR)) || 00227 (t == ANLE_MAX && (irt == IRT_LQ || irt == IRT_LE)) ) { 00228 IntVarArgs x(n); 00229 for (int i=n; i--;) 00230 x[i] = a[i].post(home, icl); 00231 rel(home, x, irt, c); 00232 } else { 00233 rel(home, post(home,NULL,icl), irt, c); 00234 } 00235 } 00236 virtual void post(Home home, IntRelType irt, int c, 00237 BoolVar b, IntConLevel icl) const { 00238 rel(home, post(home,NULL,icl), irt, c, b); 00239 } 00240 }; 00242 bool hasType(const LinExpr& e, ArithNonLinExpr::ArithNonLinExprType t) { 00243 return e.nle() && 00244 dynamic_cast<ArithNonLinExpr*>(e.nle()) != NULL && 00245 dynamic_cast<ArithNonLinExpr*>(e.nle())->t == t; 00246 } 00247 } 00248 00249 using namespace MiniModel; 00250 00251 LinExpr 00252 abs(const LinExpr& e) { 00253 if (hasType(e, ArithNonLinExpr::ANLE_ABS)) 00254 return e; 00255 ArithNonLinExpr* ae = 00256 new ArithNonLinExpr(ArithNonLinExpr::ANLE_ABS,1); 00257 ae->a[0] = e; 00258 return LinExpr(ae); 00259 } 00260 00261 LinExpr 00262 min(const LinExpr& e0, const LinExpr& e1) { 00263 int n = 0; 00264 if (hasType(e0, ArithNonLinExpr::ANLE_MIN)) 00265 n += static_cast<ArithNonLinExpr*>(e0.nle())->n; 00266 else 00267 n += 1; 00268 if (hasType(e1, ArithNonLinExpr::ANLE_MIN)) 00269 n += static_cast<ArithNonLinExpr*>(e1.nle())->n; 00270 else 00271 n += 1; 00272 ArithNonLinExpr* ae = 00273 new ArithNonLinExpr(ArithNonLinExpr::ANLE_MIN,n); 00274 int i=0; 00275 if (hasType(e0, ArithNonLinExpr::ANLE_MIN)) { 00276 ArithNonLinExpr* e0e = static_cast<ArithNonLinExpr*>(e0.nle()); 00277 for (; i<e0e->n; i++) 00278 ae->a[i] = e0e->a[i]; 00279 } else { 00280 ae->a[i++] = e0; 00281 } 00282 if (hasType(e1, ArithNonLinExpr::ANLE_MIN)) { 00283 ArithNonLinExpr* e1e = static_cast<ArithNonLinExpr*>(e1.nle()); 00284 int curN = i; 00285 for (; i<curN+e1e->n; i++) 00286 ae->a[i] = e1e->a[i-curN]; 00287 } else { 00288 ae->a[i++] = e1; 00289 } 00290 return LinExpr(ae); 00291 } 00292 00293 LinExpr 00294 max(const LinExpr& e0, const LinExpr& e1) { 00295 int n = 0; 00296 if (hasType(e0, ArithNonLinExpr::ANLE_MAX)) 00297 n += static_cast<ArithNonLinExpr*>(e0.nle())->n; 00298 else 00299 n += 1; 00300 if (hasType(e1, ArithNonLinExpr::ANLE_MAX)) 00301 n += static_cast<ArithNonLinExpr*>(e1.nle())->n; 00302 else 00303 n += 1; 00304 ArithNonLinExpr* ae = 00305 new ArithNonLinExpr(ArithNonLinExpr::ANLE_MAX,n); 00306 int i=0; 00307 if (hasType(e0, ArithNonLinExpr::ANLE_MAX)) { 00308 ArithNonLinExpr* e0e = static_cast<ArithNonLinExpr*>(e0.nle()); 00309 for (; i<e0e->n; i++) 00310 ae->a[i] = e0e->a[i]; 00311 } else { 00312 ae->a[i++] = e0; 00313 } 00314 if (hasType(e1, ArithNonLinExpr::ANLE_MAX)) { 00315 ArithNonLinExpr* e1e = static_cast<ArithNonLinExpr*>(e1.nle()); 00316 int curN = i; 00317 for (; i<curN+e1e->n; i++) 00318 ae->a[i] = e1e->a[i-curN]; 00319 } else { 00320 ae->a[i++] = e1; 00321 } 00322 return LinExpr(ae); 00323 } 00324 00325 LinExpr 00326 min(const IntVarArgs& x) { 00327 ArithNonLinExpr* ae = 00328 new ArithNonLinExpr(ArithNonLinExpr::ANLE_MIN,x.size()); 00329 for (int i=x.size(); i--;) 00330 ae->a[i] = x[i]; 00331 return LinExpr(ae); 00332 } 00333 00334 LinExpr 00335 max(const IntVarArgs& x) { 00336 ArithNonLinExpr* ae = 00337 new ArithNonLinExpr(ArithNonLinExpr::ANLE_MAX,x.size()); 00338 for (int i=x.size(); i--;) 00339 ae->a[i] = x[i]; 00340 return LinExpr(ae); 00341 } 00342 00343 LinExpr 00344 operator *(const LinExpr& e0, const LinExpr& e1) { 00345 ArithNonLinExpr* ae = 00346 new ArithNonLinExpr(ArithNonLinExpr::ANLE_MULT,2); 00347 ae->a[0] = e0; 00348 ae->a[1] = e1; 00349 return LinExpr(ae); 00350 } 00351 00352 LinExpr 00353 sqr(const LinExpr& e) { 00354 ArithNonLinExpr* ae = 00355 new ArithNonLinExpr(ArithNonLinExpr::ANLE_SQR,1); 00356 ae->a[0] = e; 00357 return LinExpr(ae); 00358 } 00359 00360 LinExpr 00361 sqrt(const LinExpr& e) { 00362 ArithNonLinExpr* ae = 00363 new ArithNonLinExpr(ArithNonLinExpr::ANLE_SQRT,1); 00364 ae->a[0] = e; 00365 return LinExpr(ae); 00366 } 00367 00368 LinExpr 00369 operator /(const LinExpr& e0, const LinExpr& e1) { 00370 ArithNonLinExpr* ae = 00371 new ArithNonLinExpr(ArithNonLinExpr::ANLE_DIV,2); 00372 ae->a[0] = e0; 00373 ae->a[1] = e1; 00374 return LinExpr(ae); 00375 } 00376 00377 LinExpr 00378 operator %(const LinExpr& e0, const LinExpr& e1) { 00379 ArithNonLinExpr* ae = 00380 new ArithNonLinExpr(ArithNonLinExpr::ANLE_MOD,2); 00381 ae->a[0] = e0; 00382 ae->a[1] = e1; 00383 return LinExpr(ae); 00384 } 00385 00386 LinExpr 00387 element(const IntVarArgs& x, const LinExpr& e) { 00388 ArithNonLinExpr* ae = 00389 new ArithNonLinExpr(ArithNonLinExpr::ANLE_ELMNT,x.size()+1); 00390 for (int i=x.size(); i--;) 00391 ae->a[i] = x[i]; 00392 ae->a[x.size()] = e; 00393 return LinExpr(ae); 00394 } 00395 00396 LinExpr 00397 element(const IntArgs& x, const LinExpr& e) { 00398 ArithNonLinExpr* ae = 00399 new ArithNonLinExpr(ArithNonLinExpr::ANLE_ELMNT,x.size()+1); 00400 for (int i=x.size(); i--;) 00401 ae->a[i] = x[i]; 00402 ae->a[x.size()] = e; 00403 return LinExpr(ae); 00404 } 00405 00406 } 00407 00408 // STATISTICS: minimodel-any