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
00028 #ifndef _EXPRESSION_H_
00029 #define _EXPRESSION_H_
00030
00031 #include <coconut_config.h>
00032 #include <stdarg.h>
00033 #include <stdio.h>
00034 #include <interval.h>
00035 #include <dag.h>
00036 #include <visitor.h>
00037 #include <semantics.h>
00038 #include <evaluator.h>
00039 #include <basic_alltype.h>
00040 #include <g_algo.h>
00041 #include <fstream>
00042 #include <cerrno>
00043 #include <string>
00044 #include <utility>
00045 #if !defined(COCONUT_WINDOWS) && !defined(COCONUT_FREEBSD)
00046 #include <values.h>
00047 #endif
00048 #include <linalg.h>
00049 #include <api_debug.h>
00050
00051 using namespace vgtl;
00052
00053 namespace coco {
00054
00055
00056
00057
00058
00059
00060
00061
00076 #define EXPRINFO_GHOST 0 // number is overlayed params.b
00077
00081 #define EXPRINFO_CONSTANT -1 // contained in params.d or .nd
00082
00084 #define EXPRINFO_VARIABLE -2 // index contained in params.nn
00085
00086
00087
00088
00096 #define EXPRINFO_SUM -3 // params.nd contains additive const
00097
00101 #define EXPRINFO_MEAN -4 // no params
00102
00105 #define EXPRINFO_PROD -5 // params.nd contains multiplic. const
00106
00109 #define EXPRINFO_MAX -6 // params.nd contains min value
00110
00113 #define EXPRINFO_MIN -7 // params.nd contains max value
00114
00118 #define EXPRINFO_MONOME -8 // params.n contains the exponents
00119
00122 #define EXPRINFO_SCPROD -9 // no params
00123
00127 #define EXPRINFO_NORM -10 // params.nd contains the norm-type
00128
00129
00133 #define EXPRINFO_INVERT -11 // params.nd/x
00134
00137 #define EXPRINFO_SQUARE -12 // (x+q)^2, q in params.nd
00138
00141 #define EXPRINFO_SQROOT -13 // sqrt(x+c) c in params.nd
00142
00145 #define EXPRINFO_ABS -14 // abs(x+c) c in params.nd
00146
00149 #define EXPRINFO_INTPOWER -15 // x^n (n const. in params.nn)
00150
00153 #define EXPRINFO_EXP -16 // exp(x+p) p in params.nd
00154
00157 #define EXPRINFO_LOG -17 // log(x+p) p in params.nd
00158
00161 #define EXPRINFO_SIN -18 // sin(x + th) th in params.nd
00162
00165 #define EXPRINFO_COS -19 // cos(x + th) th in params.nd
00166
00170 #define EXPRINFO_GAUSS -20 // exp(-(x-m)^2/s^2) m, s in params.d
00171
00175 #define EXPRINFO_POLY -21 // a_0+a_1 x+...+a_n x^n, a in params.d
00176
00177
00181 #define EXPRINFO_POW -22 // (x+p)^y, p in params.nd
00182
00185 #define EXPRINFO_DIV -23 // a*x/y, a in params.nd
00186
00190 #define EXPRINFO_ATAN2 -24 // atan(x,y) no params
00191
00192
00197 #define EXPRINFO_LIN -25 // number of row in lin in params.nn
00198
00203 #define EXPRINFO_QUAD -26 // (A|b) cont. in params.m x^T A x+b^T x
00204
00205
00206
00209 #define EXPRINFO_RE -27 // no params
00210
00212 #define EXPRINFO_IM -28 // no params
00213
00215 #define EXPRINFO_ARG -29 // no params
00216
00217
00220 #define EXPRINFO_CPLXCONJ -30 // no params
00221
00222
00226 #define EXPRINFO_LOOKUP -31 // table in params.m
00227
00230 #define EXPRINFO_PWLIN -32 // table in params.m
00231
00234 #define EXPRINFO_SPLINE -33 // table in params.m
00235
00238 #define EXPRINFO_PWCONSTLC -34 // table in params.m
00239
00242 #define EXPRINFO_PWCONSTRC -35 // table in params.m
00243
00244
00250 #define EXPRINFO_IN -36 // box in params.i
00251
00261 #define EXPRINFO_IF -37 // truth-interval in params.ni
00262
00265 #define EXPRINFO_AND -38 // truth-intervals in params.i
00266
00269 #define EXPRINFO_OR -39 // truth-intervals in params.i
00270
00273 #define EXPRINFO_NOT -40 // truth-interval in params.ni
00274
00279 #define EXPRINFO_IMPLIES -41 // truth-intervals in params.i
00280
00283 #define EXPRINFO_COUNT -42 // truth-intervals in params.i
00284
00288 #define EXPRINFO_ALLDIFF -43 // max of abs(x_i-x_j) in params.nd
00289
00294 #define EXPRINFO_HISTOGRAM -44 // pairs of intervals in params.i
00295
00300 #define EXPRINFO_LEVEL -45 // boxes in params.mi (multi-in)
00301
00302
00308 #define EXPRINFO_NEIGHBOR -46 // list of pairs in double long params.n
00309
00312 #define EXPRINFO_NOGOOD -47 // vector x_0 in params.n
00313
00314
00318 #define EXPRINFO_EXPECTATION -48 // no params
00319
00322 #define EXPRINFO_INTEGRAL -49 // integration area in params.i
00323
00324
00325
00326
00327
00330 #define EXPRINFO_DET -50 // [0]=0(sparse),1(dense), [1]=dim
00331
00333 #define EXPRINFO_COND -51 // [0]=0(sparse),1(dense), [1],[2]=dim
00334
00336 #define EXPRINFO_PSD -52 // [0]=0(sparse),1(dense), [1]=dim
00337
00339 #define EXPRINFO_MPROD -53 // [0]=0(sparse),1(dense), [1],[2]=dim
00340
00342 #define EXPRINFO_FEM -54 // [0]=0(sparse),1(dense), [1],[2]=dim
00343
00344
00347 #define EXPRINFO_CMPROD -55 // params.m contains A
00348
00351 #define EXPRINFO_CGFEM -56 // params.m contains A
00352
00353
00356 #define EXPRINFO_UNDEFINED -57
00357
00359 #define EXPRINFO_NUMOFPREDEF -(EXPRINFO_UNDEFINED)
00360
00361
00362 #define EXPR_LASTARG NULL
00363
00364
00365
00366
00369 typedef enum {
00370 ex_bound=1,
00371 ex_linear=1<<1,
00372 ex_quadratic=1<<2,
00373 ex_polynomial=1<<3,
00374 ex_other=1<<4,
00375
00376
00377
00378
00379 ex_kj=1<<7,
00380 ex_org=1<<8,
00381
00382
00383 ex_redundant=1<<9,
00384 ex_notredundant=1<<10,
00385
00386
00387
00388 ex_active_lo=1<<11,
00389 ex_inactive_lo=1<<12,
00390 ex_active_hi=1<<13,
00391 ex_inactive_hi=1<<14,
00392 ex_active=ex_active_lo|ex_active_hi,
00393 ex_inactive=ex_inactive_lo|ex_inactive_hi,
00394
00395
00396 ex_integer=1<<15,
00397
00398
00399
00400 ex_exists = 1<<16,
00401 ex_forall = 1<<17,
00402 ex_free = 1<<18,
00403 ex_stochastic = 1<<19,
00404
00405
00406 ex_convex=1<<20,
00407 ex_concave=1<<21,
00408
00409
00410 ex_inequality=1<<28,
00411 ex_equality=1<<29,
00412 ex_leftbound=1<<30,
00413 ex_rightbound=1<<31,
00414
00415
00416 ex_atmlin=ex_bound|ex_linear,
00417 ex_atmquad=ex_atmlin|ex_quadratic,
00418 ex_atmpoly=ex_atmquad|ex_polynomial,
00419 ex_nonlin=ex_quadratic|ex_polynomial|ex_other,
00420 ex_nonbnd=ex_linear|ex_nonlin,
00421 ex_any=ex_atmlin|ex_nonlin,
00422 ex_bothbound=ex_leftbound|ex_rightbound
00423 } e_expression_type;
00424
00426 typedef interval rhs_t;
00427
00429 typedef std::vector<void*> evaluator_v;
00430
00431 #include <basic_alltype.h>
00432
00434
00439 class expression_node
00440 {
00441 public:
00442 unsigned int node_num;
00443
00444 int operator_type;
00445
00446
00447
00448
00449
00450
00451
00452
00453 unsigned int n_parents,
00454 n_children;
00455
00456
00457 std::vector<double> coeffs;
00458
00459 basic_alltype params;
00460
00461 rhs_t f_bounds;
00462
00463 unsigned short is_var;
00464 std::vector<unsigned int> var_idx;
00465
00466 semantics sem;
00467
00468
00469
00470 variable_indicator v_i;
00471
00472 evaluator_v* ev;
00473
00474
00475
00476 private:
00478 void init()
00479 {
00480 is_var = 0;
00481 f_bounds.set(-COCO_INF, COCO_INF);
00482 }
00483
00484 public:
00486 expression_node() : node_num(), operator_type(0), n_parents(0),
00487 n_children(0), coeffs(), params(), var_idx(),
00488 sem(), v_i(), ev(NULL)
00489 { init(); }
00490
00493 expression_node(int et, int nn) : node_num(nn), operator_type(et),
00494 n_parents(0), n_children(0), coeffs(),
00495 params(), var_idx(), sem(), v_i(),
00496 ev(NULL)
00497 { init(); }
00498
00500 expression_node(const expression_node& __x) : node_num(__x.node_num),
00501 operator_type(__x.operator_type), n_parents(__x.n_parents),
00502 n_children(__x.n_children), coeffs(__x.coeffs), params(__x.params),
00503 f_bounds(__x.f_bounds), is_var(__x.is_var), var_idx(__x.var_idx),
00504 sem(__x.sem), v_i(__x.v_i), ev(__x.ev)
00505 { }
00506
00508 virtual ~expression_node()
00509 {
00510 if(node_num == 0)
00511 return;
00512 if(ev) delete(ev);
00513 }
00514
00516 expression_node& operator=(const expression_node& __x)
00517 {
00518 operator_type = __x.operator_type;
00519 node_num = __x.node_num;
00520 v_i = __x.v_i;
00521 coeffs = __x.coeffs;
00522 params = __x.params;
00523 ev = __x.ev;
00524 sem = __x.sem;
00525 var_idx = __x.var_idx;
00526 is_var = __x.is_var;
00527 f_bounds = __x.f_bounds;
00528 return *this;
00529 }
00530
00533 class parents_compare;
00536 class children_compare;
00539 class parents_compare_eq;
00541 bool operator<(const expression_node& __x) const;
00542
00543
00544
00547 void merge(const expression_node& __s)
00548 {
00549 f_bounds.intersectwith(__s.f_bounds);
00550 if(operator_type != EXPRINFO_VARIABLE)
00551 {
00552 is_var += __s.is_var;
00553 var_idx.insert(var_idx.end(), __s.var_idx.begin(), __s.var_idx.end());
00554 }
00555 n_parents += __s.n_parents;
00556 sem.merge(__s.sem);
00557 }
00558
00560 void set_bounds(rhs_t __i)
00561 {
00562 f_bounds = __i;
00563 }
00564
00567 void set_bounds(double __d = 0.)
00568 {
00569 f_bounds = rhs_t(__d);
00570 }
00571
00573 void set_bounds(int __i)
00574 {
00575 set_bounds(__i+0.);
00576 }
00577
00580 void set_bounds(double lo, double up)
00581 {
00582 f_bounds = rhs_t(lo, up);
00583 }
00584
00587 void add_is_var(unsigned int idx)
00588 {
00589 is_var++;
00590 var_idx.push_back(idx);
00591 }
00592
00595 void rm_is_var(unsigned int idx)
00596 {
00597 for(std::vector<unsigned int>::iterator b = var_idx.begin();
00598 b != var_idx.end(); b++)
00599 if(*b == idx)
00600 {
00601 var_idx.erase(b);
00602 is_var--;
00603 }
00604 }
00605
00609 bool is(unsigned int __tp) const;
00610
00611
00612
00613 friend std::ostream& operator<< (std::ostream& o, const expression_node& __x);
00614
00615
00617 const variable_indicator& var_indicator() const { return v_i; }
00618
00620
00622 virtual double f_evaluate(int argnum, int idx, const std::vector<double> &x,
00623 const variable_indicator& v_i, double fold, double fupd,
00624 std::vector<double> *cache_data) const
00625 { return 0; }
00626 virtual interval i_evaluate(int argnum, int idx, const std::vector<interval> &x,
00627 const variable_indicator& v_i, interval fold, interval fupd,
00628 std::vector<interval> *cache_data) const
00629 { return interval(); }
00630 virtual interval cp_evaluate(int argnum, int idx,
00631 const std::vector<interval> &node_range,
00632 const variable_indicator& v_i, interval fold, interval fupd,
00633 std::vector<interval> *cache_data) const
00634 { return interval(); }
00636
00637 #if DEBUG_EXPRESSIONS
00638 public:
00640 unsigned int test() const { return node_num; }
00641 #endif
00642 };
00643
00644 }
00645
00646
00647 #include <expression.hpp>
00648
00649 #endif // _EXPRESSION_H_