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