lin-expr.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, 2010 00008 * 00009 * Last modified: 00010 * $Date: 2011-01-21 16:01:14 +0100 (Fri, 21 Jan 2011) $ by $Author: schulte $ 00011 * $Revision: 11553 $ 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 bool 00043 LinExpr::Node::decrement(void) { 00044 if (--use == 0) { 00045 if ((l != NULL) && l->decrement()) 00046 delete l; 00047 if ((r != NULL) && r->decrement()) 00048 delete r; 00049 return true; 00050 } 00051 return false; 00052 } 00053 00054 /* 00055 * Operations for expressions 00056 * 00057 */ 00058 LinExpr::LinExpr(void) : 00059 n(new Node) { 00060 n->n_int = n->n_bool = 0; 00061 n->t = NT_VAR_INT; 00062 n->l = n->r = NULL; 00063 n->a = 0; 00064 } 00065 00066 LinExpr::LinExpr(double c) : 00067 n(new Node) { 00068 n->n_int = n->n_bool = 0; 00069 n->t = NT_CONST; 00070 n->l = n->r = NULL; 00071 n->a = 0; 00072 Int::Limits::check(c,"MiniModel::LinExpr"); 00073 n->c = static_cast<int>(c); 00074 } 00075 00076 LinExpr::LinExpr(const IntVar& x, int a) : 00077 n(new Node) { 00078 n->n_int = 1; 00079 n->n_bool = 0; 00080 n->t = NT_VAR_INT; 00081 n->l = n->r = NULL; 00082 n->a = a; 00083 n->x_int = x; 00084 } 00085 00086 LinExpr::LinExpr(const BoolVar& x, int a) : 00087 n(new Node) { 00088 n->n_int = 0; 00089 n->n_bool = 1; 00090 n->t = NT_VAR_BOOL; 00091 n->l = n->r = NULL; 00092 n->a = a; 00093 n->x_bool = x; 00094 } 00095 00096 LinExpr::LinExpr(const IntVarArgs& x) : 00097 n(new Node) { 00098 n->n_int = x.size(); 00099 n->n_bool = 0; 00100 n->t = NT_SUM_INT; 00101 n->l = n->r = NULL; 00102 if (x.size() > 0) { 00103 n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size()); 00104 for (int i=x.size(); i--; ) { 00105 n->sum.ti[i].x = x[i]; 00106 n->sum.ti[i].a = 1; 00107 } 00108 } 00109 } 00110 00111 LinExpr::LinExpr(const IntArgs& a, const IntVarArgs& x) : 00112 n(new Node) { 00113 if (a.size() != x.size()) 00114 throw Int::ArgumentSizeMismatch("MiniModel::LinExpr"); 00115 n->n_int = x.size(); 00116 n->n_bool = 0; 00117 n->t = NT_SUM_INT; 00118 n->l = n->r = NULL; 00119 if (x.size() > 0) { 00120 n->sum.ti = heap.alloc<Int::Linear::Term<Int::IntView> >(x.size()); 00121 for (int i=x.size(); i--; ) { 00122 n->sum.ti[i].x = x[i]; 00123 n->sum.ti[i].a = a[i]; 00124 } 00125 } 00126 } 00127 00128 LinExpr::LinExpr(const BoolVarArgs& x) : 00129 n(new Node) { 00130 n->n_int = 0; 00131 n->n_bool = x.size(); 00132 n->t = NT_SUM_BOOL; 00133 n->l = n->r = NULL; 00134 if (x.size() > 0) { 00135 n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size()); 00136 for (int i=x.size(); i--; ) { 00137 n->sum.tb[i].x = x[i]; 00138 n->sum.tb[i].a = 1; 00139 } 00140 } 00141 } 00142 00143 LinExpr::LinExpr(const IntArgs& a, const BoolVarArgs& x) : 00144 n(new Node) { 00145 if (a.size() != x.size()) 00146 throw Int::ArgumentSizeMismatch("MiniModel::LinExpr"); 00147 n->n_int = 0; 00148 n->n_bool = x.size(); 00149 n->t = NT_SUM_BOOL; 00150 n->l = n->r = NULL; 00151 if (x.size() > 0) { 00152 n->sum.tb = heap.alloc<Int::Linear::Term<Int::BoolView> >(x.size()); 00153 for (int i=x.size(); i--; ) { 00154 n->sum.tb[i].x = x[i]; 00155 n->sum.tb[i].a = a[i]; 00156 } 00157 } 00158 } 00159 00160 LinExpr::LinExpr(const LinExpr& e0, NodeType t, const LinExpr& e1) : 00161 n(new Node) { 00162 n->n_int = e0.n->n_int + e1.n->n_int; 00163 n->n_bool = e0.n->n_bool + e1.n->n_bool; 00164 n->t = t; 00165 n->l = e0.n; n->l->use++; 00166 n->r = e1.n; n->r->use++; 00167 } 00168 00169 LinExpr::LinExpr(const LinExpr& e, NodeType t, int c) : 00170 n(new Node) { 00171 n->n_int = e.n->n_int; 00172 n->n_bool = e.n->n_bool; 00173 n->t = t; 00174 n->l = NULL; 00175 n->r = e.n; n->r->use++; 00176 n->c = c; 00177 } 00178 00179 LinExpr::LinExpr(int a, const LinExpr& e) : 00180 n(new Node) { 00181 n->n_int = e.n->n_int; 00182 n->n_bool = e.n->n_bool; 00183 n->t = NT_MUL; 00184 n->l = e.n; n->l->use++; 00185 n->r = NULL; 00186 n->a = a; 00187 } 00188 00189 LinExpr::LinExpr(NonLinExpr* e) : 00190 n(new Node) { 00191 n->n_int = 1; 00192 n->n_bool = 0; 00193 n->t = NT_NONLIN; 00194 n->l = n->r = NULL; 00195 n->a = 0; 00196 n->sum.ne = e; 00197 } 00198 00199 const LinExpr& 00200 LinExpr::operator =(const LinExpr& e) { 00201 if (this != &e) { 00202 if (n->decrement()) 00203 delete n; 00204 n = e.n; n->use++; 00205 } 00206 return *this; 00207 } 00208 00209 LinExpr::~LinExpr(void) { 00210 if (n->decrement()) 00211 delete n; 00212 } 00213 00214 00215 void 00216 LinExpr::Node::fill(Home home, IntConLevel icl, 00217 Int::Linear::Term<Int::IntView>*& ti, 00218 Int::Linear::Term<Int::BoolView>*& tb, 00219 double m, double& d) const { 00220 switch (this->t) { 00221 case NT_CONST: 00222 Int::Limits::check(m*c,"MiniModel::LinExpr"); 00223 d += m*c; 00224 break; 00225 case NT_VAR_INT: 00226 Int::Limits::check(m*a,"MiniModel::LinExpr"); 00227 ti->a=static_cast<int>(m*a); ti->x=x_int; ti++; 00228 break; 00229 case NT_NONLIN: 00230 ti->a=static_cast<int>(m); ti->x=sum.ne->post(home, NULL, icl); ti++; 00231 break; 00232 case NT_VAR_BOOL: 00233 Int::Limits::check(m*a,"MiniModel::LinExpr"); 00234 tb->a=static_cast<int>(m*a); tb->x=x_bool; tb++; 00235 break; 00236 case NT_SUM_INT: 00237 for (int i=n_int; i--; ) { 00238 Int::Limits::check(m*sum.ti[i].a,"MiniModel::LinExpr"); 00239 ti[i].x = sum.ti[i].x; ti[i].a = static_cast<int>(m*sum.ti[i].a); 00240 } 00241 ti += n_int; 00242 break; 00243 case NT_SUM_BOOL: 00244 for (int i=n_bool; i--; ) { 00245 Int::Limits::check(m*sum.tb[i].a,"MiniModel::LinExpr"); 00246 tb[i].x = sum.tb[i].x; tb[i].a = static_cast<int>(m*sum.tb[i].a); 00247 } 00248 tb += n_bool; 00249 break; 00250 case NT_ADD: 00251 if (l == NULL) { 00252 Int::Limits::check(m*c,"MiniModel::LinExpr"); 00253 d += m*c; 00254 } else { 00255 l->fill(home,icl,ti,tb,m,d); 00256 } 00257 r->fill(home,icl,ti,tb,m,d); 00258 break; 00259 case NT_SUB: 00260 if (l == NULL) { 00261 Int::Limits::check(m*c,"MiniModel::LinExpr"); 00262 d += m*c; 00263 } else { 00264 l->fill(home,icl,ti,tb,m,d); 00265 } 00266 r->fill(home,icl,ti,tb,-m,d); 00267 break; 00268 case NT_MUL: 00269 Int::Limits::check(m*a,"MiniModel::LinExpr"); 00270 l->fill(home,icl,ti,tb,m*a,d); 00271 break; 00272 default: 00273 GECODE_NEVER; 00274 } 00275 } 00276 00277 00278 /* 00279 * Operators 00280 * 00281 */ 00282 LinExpr 00283 operator +(int c, const IntVar& x) { 00284 if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val())) 00285 return LinExpr(static_cast<double>(c)+x.val()); 00286 else 00287 return LinExpr(x,LinExpr::NT_ADD,c); 00288 } 00289 LinExpr 00290 operator +(int c, const BoolVar& x) { 00291 if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val())) 00292 return LinExpr(static_cast<double>(c)+x.val()); 00293 else 00294 return LinExpr(x,LinExpr::NT_ADD,c); 00295 } 00296 LinExpr 00297 operator +(int c, const LinExpr& e) { 00298 return LinExpr(e,LinExpr::NT_ADD,c); 00299 } 00300 LinExpr 00301 operator +(const IntVar& x, int c) { 00302 if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val())) 00303 return LinExpr(static_cast<double>(c)+x.val()); 00304 else 00305 return LinExpr(x,LinExpr::NT_ADD,c); 00306 } 00307 LinExpr 00308 operator +(const BoolVar& x, int c) { 00309 if (x.assigned() && Int::Limits::valid(static_cast<double>(c)+x.val())) 00310 return LinExpr(static_cast<double>(c)+x.val()); 00311 else 00312 return LinExpr(x,LinExpr::NT_ADD,c); 00313 } 00314 LinExpr 00315 operator +(const LinExpr& e, int c) { 00316 return LinExpr(e,LinExpr::NT_ADD,c); 00317 } 00318 LinExpr 00319 operator +(const IntVar& x, const IntVar& y) { 00320 if (x.assigned()) 00321 return x.val() + y; 00322 else if (y.assigned()) 00323 return x + y.val(); 00324 else 00325 return LinExpr(x,LinExpr::NT_ADD,y); 00326 } 00327 LinExpr 00328 operator +(const IntVar& x, const BoolVar& y) { 00329 if (x.assigned()) 00330 return x.val() + y; 00331 else if (y.assigned()) 00332 return x + y.val(); 00333 else 00334 return LinExpr(x,LinExpr::NT_ADD,y); 00335 } 00336 LinExpr 00337 operator +(const BoolVar& x, const IntVar& y) { 00338 if (x.assigned()) 00339 return x.val() + y; 00340 else if (y.assigned()) 00341 return x + y.val(); 00342 else 00343 return LinExpr(x,LinExpr::NT_ADD,y); 00344 } 00345 LinExpr 00346 operator +(const BoolVar& x, const BoolVar& y) { 00347 if (x.assigned()) 00348 return x.val() + y; 00349 else if (y.assigned()) 00350 return x + y.val(); 00351 else 00352 return LinExpr(x,LinExpr::NT_ADD,y); 00353 } 00354 LinExpr 00355 operator +(const IntVar& x, const LinExpr& e) { 00356 if (x.assigned()) 00357 return x.val() + e; 00358 else 00359 return LinExpr(x,LinExpr::NT_ADD,e); 00360 } 00361 LinExpr 00362 operator +(const BoolVar& x, const LinExpr& e) { 00363 if (x.assigned()) 00364 return x.val() + e; 00365 else 00366 return LinExpr(x,LinExpr::NT_ADD,e); 00367 } 00368 LinExpr 00369 operator +(const LinExpr& e, const IntVar& x) { 00370 if (x.assigned()) 00371 return e + x.val(); 00372 else 00373 return LinExpr(e,LinExpr::NT_ADD,x); 00374 } 00375 LinExpr 00376 operator +(const LinExpr& e, const BoolVar& x) { 00377 if (x.assigned()) 00378 return e + x.val(); 00379 else 00380 return LinExpr(e,LinExpr::NT_ADD,x); 00381 } 00382 LinExpr 00383 operator +(const LinExpr& e1, const LinExpr& e2) { 00384 return LinExpr(e1,LinExpr::NT_ADD,e2); 00385 } 00386 00387 LinExpr 00388 operator -(int c, const IntVar& x) { 00389 if (x.assigned() && Int::Limits::valid(static_cast<double>(c)-x.val())) 00390 return LinExpr(static_cast<double>(c)-x.val()); 00391 else 00392 return LinExpr(x,LinExpr::NT_SUB,c); 00393 } 00394 LinExpr 00395 operator -(int c, const BoolVar& x) { 00396 if (x.assigned() && Int::Limits::valid(static_cast<double>(c)-x.val())) 00397 return LinExpr(static_cast<double>(c)-x.val()); 00398 else 00399 return LinExpr(x,LinExpr::NT_SUB,c); 00400 } 00401 LinExpr 00402 operator -(int c, const LinExpr& e) { 00403 return LinExpr(e,LinExpr::NT_SUB,c); 00404 } 00405 LinExpr 00406 operator -(const IntVar& x, int c) { 00407 if (x.assigned() && Int::Limits::valid(x.val()-static_cast<double>(c))) 00408 return LinExpr(x.val()-static_cast<double>(c)); 00409 else 00410 return LinExpr(x,LinExpr::NT_ADD,-c); 00411 } 00412 LinExpr 00413 operator -(const BoolVar& x, int c) { 00414 if (x.assigned() && Int::Limits::valid(x.val()-static_cast<double>(c))) 00415 return LinExpr(x.val()-static_cast<double>(c)); 00416 else 00417 return LinExpr(x,LinExpr::NT_ADD,-c); 00418 } 00419 LinExpr 00420 operator -(const LinExpr& e, int c) { 00421 return LinExpr(e,LinExpr::NT_ADD,-c); 00422 } 00423 LinExpr 00424 operator -(const IntVar& x, const IntVar& y) { 00425 if (x.assigned()) 00426 return x.val() - y; 00427 else if (y.assigned()) 00428 return x - y.val(); 00429 else 00430 return LinExpr(x,LinExpr::NT_SUB,y); 00431 } 00432 LinExpr 00433 operator -(const IntVar& x, const BoolVar& y) { 00434 if (x.assigned()) 00435 return x.val() - y; 00436 else if (y.assigned()) 00437 return x - y.val(); 00438 else 00439 return LinExpr(x,LinExpr::NT_SUB,y); 00440 } 00441 LinExpr 00442 operator -(const BoolVar& x, const IntVar& y) { 00443 if (x.assigned()) 00444 return x.val() - y; 00445 else if (y.assigned()) 00446 return x - y.val(); 00447 else 00448 return LinExpr(x,LinExpr::NT_SUB,y); 00449 } 00450 LinExpr 00451 operator -(const BoolVar& x, const BoolVar& y) { 00452 if (x.assigned()) 00453 return x.val() - y; 00454 else if (y.assigned()) 00455 return x - y.val(); 00456 else 00457 return LinExpr(x,LinExpr::NT_SUB,y); 00458 } 00459 LinExpr 00460 operator -(const IntVar& x, const LinExpr& e) { 00461 if (x.assigned()) 00462 return x.val() - e; 00463 else 00464 return LinExpr(x,LinExpr::NT_SUB,e); 00465 } 00466 LinExpr 00467 operator -(const BoolVar& x, const LinExpr& e) { 00468 if (x.assigned()) 00469 return x.val() - e; 00470 else 00471 return LinExpr(x,LinExpr::NT_SUB,e); 00472 } 00473 LinExpr 00474 operator -(const LinExpr& e, const IntVar& x) { 00475 if (x.assigned()) 00476 return e - x.val(); 00477 else 00478 return LinExpr(e,LinExpr::NT_SUB,x); 00479 } 00480 LinExpr 00481 operator -(const LinExpr& e, const BoolVar& x) { 00482 if (x.assigned()) 00483 return e - x.val(); 00484 else 00485 return LinExpr(e,LinExpr::NT_SUB,x); 00486 } 00487 LinExpr 00488 operator -(const LinExpr& e1, const LinExpr& e2) { 00489 return LinExpr(e1,LinExpr::NT_SUB,e2); 00490 } 00491 00492 LinExpr 00493 operator -(const IntVar& x) { 00494 if (x.assigned()) 00495 return LinExpr(-x.val()); 00496 else 00497 return LinExpr(x,LinExpr::NT_SUB,0); 00498 } 00499 LinExpr 00500 operator -(const BoolVar& x) { 00501 if (x.assigned()) 00502 return LinExpr(-x.val()); 00503 else 00504 return LinExpr(x,LinExpr::NT_SUB,0); 00505 } 00506 LinExpr 00507 operator -(const LinExpr& e) { 00508 return LinExpr(e,LinExpr::NT_SUB,0); 00509 } 00510 00511 LinExpr 00512 operator *(int a, const IntVar& x) { 00513 if (a == 0) 00514 return LinExpr(0.0); 00515 else if (x.assigned() && 00516 Int::Limits::valid(static_cast<double>(a)*x.val())) 00517 return LinExpr(static_cast<double>(a)*x.val()); 00518 else 00519 return LinExpr(x,a); 00520 } 00521 LinExpr 00522 operator *(int a, const BoolVar& x) { 00523 if (a == 0) 00524 return LinExpr(0.0); 00525 else if (x.assigned() && 00526 Int::Limits::valid(static_cast<double>(a)*x.val())) 00527 return LinExpr(static_cast<double>(a)*x.val()); 00528 else 00529 return LinExpr(x,a); 00530 } 00531 LinExpr 00532 operator *(const IntVar& x, int a) { 00533 if (a == 0) 00534 return LinExpr(0.0); 00535 else if (x.assigned() && 00536 Int::Limits::valid(static_cast<double>(a)*x.val())) 00537 return LinExpr(static_cast<double>(a)*x.val()); 00538 else 00539 return LinExpr(x,a); 00540 } 00541 LinExpr 00542 operator *(const BoolVar& x, int a) { 00543 if (a == 0) 00544 return LinExpr(0.0); 00545 else if (x.assigned() && 00546 Int::Limits::valid(static_cast<double>(a)*x.val())) 00547 return LinExpr(static_cast<double>(a)*x.val()); 00548 else 00549 return LinExpr(x,a); 00550 } 00551 LinExpr 00552 operator *(const LinExpr& e, int a) { 00553 if (a == 0) 00554 return LinExpr(0.0); 00555 else 00556 return LinExpr(a,e); 00557 } 00558 LinExpr 00559 operator *(int a, const LinExpr& e) { 00560 if (a == 0) 00561 return LinExpr(0.0); 00562 else 00563 return LinExpr(a,e); 00564 } 00565 00566 LinExpr 00567 sum(const IntVarArgs& x) { 00568 return LinExpr(x); 00569 } 00570 LinExpr 00571 sum(const IntArgs& a, const IntVarArgs& x) { 00572 return LinExpr(a,x); 00573 } 00574 LinExpr 00575 sum(const BoolVarArgs& x) { 00576 return LinExpr(x); 00577 } 00578 LinExpr 00579 sum(const IntArgs& a, const BoolVarArgs& x) { 00580 return LinExpr(a,x); 00581 } 00582 00583 00584 IntVar 00585 expr(Home home, const LinExpr& e, IntConLevel icl) { 00586 if (!home.failed()) 00587 return e.post(home,icl); 00588 IntVar x(home,Int::Limits::min,Int::Limits::max); 00589 return x; 00590 } 00591 00592 } 00593 00594 // STATISTICS: minimodel-any