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