00001 // File: $Id$ 00002 // Author: John Wu <John.Wu at acm.org> 00003 // Lawrence Berkeley National Laboratory 00004 // Copyright 1998-2012 the Regents of the University of California 00005 // 00006 // Primary contact: John Wu <John.Wu at acm.org> 00007 #ifndef IBIS_EXPR_H 00008 #define IBIS_EXPR_H 00009 00010 00011 00012 #include "util.h" 00013 #include "array_t.h" 00014 00015 namespace ibis { // additional names related to qExpr 00016 class qRange; 00017 class qContinuousRange; 00018 class qDiscreteRange; 00019 class qString; 00020 class qMultiString; 00021 class compRange; 00022 class deprecatedJoin; 00023 class qAnyAny; 00024 class qLike; 00025 class qIntHod; 00026 class qUIntHod; 00027 } 00028 00033 class FASTBIT_CXX_DLLSPEC ibis::qExpr { 00034 public: 00037 enum TYPE { 00038 LOGICAL_UNDEFINED, LOGICAL_NOT, LOGICAL_AND, LOGICAL_OR, LOGICAL_XOR, 00039 LOGICAL_MINUS, RANGE, DRANGE, STRING, MSTRING, COMPRANGE, MATHTERM, 00040 DEPRECATEDJOIN, TOPK, ANYANY, LIKE, INTHOD, UINTHOD 00041 }; 00043 enum COMPARE { 00044 OP_UNDEFINED, OP_LT, OP_GT, OP_LE, OP_GE, OP_EQ 00045 }; 00046 00048 qExpr() : type(LOGICAL_UNDEFINED), left(0), right(0) {} 00049 00051 explicit qExpr(TYPE op) : type(op), left(0), right(0) {} 00061 qExpr(TYPE op, qExpr* qe1, qExpr* qe2) : type(op), left(qe1), right(qe2) {} 00063 qExpr(const qExpr& qe) : type(qe.type), 00064 left(qe.left ? qe.left->dup() : 0), 00065 right(qe.right ? qe.right->dup() : 0) {} 00068 virtual ~qExpr() {delete right; delete left;} 00069 00073 void setLeft(qExpr *expr) {delete left; left=expr;} 00077 void setRight(qExpr *expr) {delete right; right=expr;} 00080 qExpr*& getLeft() {return left;} 00084 qExpr*& getRight() {return right;} 00085 00087 TYPE getType() const {return type;} 00089 const qExpr* getLeft() const {return left;} 00091 const qExpr* getRight() const {return right;} 00092 00094 void swap(qExpr& rhs) { 00095 {TYPE t = type; type = rhs.type; rhs.type = t;} 00096 {qExpr* p = left; left = rhs.left; rhs.left = p;} 00097 {qExpr* q = right; right = rhs.right; rhs.right = q;} 00098 } 00099 00101 qExpr& operator=(const qExpr& rhs) { 00102 qExpr tmp(rhs); // copy 00103 swap(tmp); 00104 return *this; 00105 } 00106 00108 virtual uint32_t nItems() const { 00109 return 1 + (left != 0 ? left->nItems() : 0) + 00110 (right != 0 ? right->nItems() : 0);} 00111 00113 virtual void print(std::ostream&) const; 00115 virtual void printFull(std::ostream& out) const; 00116 00118 struct weight { 00119 virtual double operator()(const qExpr* ex) const = 0; 00120 virtual ~weight() {}; 00121 }; 00122 double reorder(const weight&); 00123 00124 virtual qExpr* dup() const { 00125 qExpr* res = new qExpr(type); 00126 if (left) 00127 res->left = left->dup(); 00128 if (right) 00129 res->right = right->dup(); 00130 return res; 00131 } 00132 00135 virtual bool isConstant() const {return false;} 00137 bool isTerminal() const {return (left==0 && right==0);} 00139 bool directEval() const 00140 {return (type==RANGE || type==STRING || type==COMPRANGE || 00141 type==DRANGE || type==MSTRING || type==ANYANY || 00142 type==INTHOD || type==UINTHOD || 00143 (type==LOGICAL_NOT && left && left->directEval()));} 00144 00147 virtual bool isSimple() const { 00148 if (left) { 00149 if (right) return left->isSimple() && right->isSimple(); 00150 else return left->isSimple(); 00151 } 00152 else if (right) { 00153 return right->isSimple(); 00154 } 00155 else { // the derived classes essentially overrides this case. 00156 return true; 00157 } 00158 } 00159 00161 int separateSimple(ibis::qExpr *&simple, ibis::qExpr *&tail) const; 00162 void extractDeprecatedJoins(std::vector<const deprecatedJoin*>&) const; 00164 virtual void getTableNames(std::set<std::string>& plist) const; 00165 00167 qRange* findRange(const char* vname); 00168 00170 static void simplify(ibis::qExpr*&); 00171 00172 static std::string extractTableName(const char*); 00173 static void splitColumnName(const char*, std::string&, std::string&); 00174 00177 struct TTN { 00178 const qExpr* term; 00179 std::set<std::string> tnames; 00180 }; // TTN 00181 typedef std::vector<TTN> termTableList; 00182 void getConjunctiveTerms(termTableList&) const; 00183 00184 protected: 00185 TYPE type; // the type of node, logical operator, type of leaf 00186 qExpr* left; // the left child 00187 qExpr* right; // the right child 00188 00190 void adjust(); 00191 }; // ibis::qExpr 00192 00197 class FASTBIT_CXX_DLLSPEC ibis::qRange : public ibis::qExpr { 00198 public: 00200 virtual const char* colName() const = 0; 00203 virtual bool inRange(double val) const = 0; 00204 00206 virtual void restrictRange(double left, double right) = 0; 00208 virtual double leftBound() const = 0; 00210 virtual double rightBound() const = 0; 00212 virtual bool empty() const = 0; 00213 virtual void getTableNames(std::set<std::string>& plist) const; 00214 00215 virtual ~qRange() {}; // nothing to do 00216 00217 protected: 00218 // reduce the scope of the constructor 00219 qRange() : qExpr() {}; 00220 qRange(TYPE t) : qExpr(t) {}; 00221 00222 private: 00223 qRange(const qRange&) {}; // no copy constructor allowed, must use dup 00224 qRange& operator=(const qRange&); 00225 }; // ibis::qRange 00226 00242 class FASTBIT_CXX_DLLSPEC ibis::qContinuousRange : public ibis::qRange { 00243 public: 00245 qContinuousRange() 00246 : qRange(ibis::qExpr::RANGE), name(0), lower(0), upper(0), 00247 left_op(OP_UNDEFINED), right_op(OP_UNDEFINED) {}; 00249 qContinuousRange(const char* lstr, COMPARE lop, const char* prop, 00250 COMPARE rop, const char* rstr); 00252 qContinuousRange(const char* col, COMPARE op, uint32_t val) : 00253 qRange(ibis::qExpr::RANGE), name(ibis::util::strnewdup(col)), 00254 lower(DBL_MAX), upper(val), left_op(OP_UNDEFINED), right_op(op) {}; 00256 qContinuousRange(const qContinuousRange& rhs) : 00257 qRange(ibis::qExpr::RANGE), name(ibis::util::strnewdup(rhs.name)), 00258 lower(rhs.lower), upper(rhs.upper), left_op(rhs.left_op), 00259 right_op(rhs.right_op) {}; 00261 qContinuousRange(double lv, COMPARE lop, const char* prop, 00262 COMPARE rop, double rv) 00263 : qRange(ibis::qExpr::RANGE), name(ibis::util::strnewdup(prop)), 00264 lower(lv), upper(rv), left_op(lop), right_op(rop) {}; 00266 qContinuousRange(const char* prop, COMPARE op, double val) 00267 : qRange(ibis::qExpr::RANGE), name(ibis::util::strnewdup(prop)), 00268 lower(-DBL_MAX), upper(val), left_op(OP_UNDEFINED), right_op(op) { 00269 // prefer to use the operator < and <= rather than > and >= 00270 if (right_op == ibis::qExpr::OP_GT) { 00271 right_op = ibis::qExpr::OP_UNDEFINED; 00272 left_op = ibis::qExpr::OP_LT; 00273 lower = upper; 00274 upper = DBL_MAX; 00275 } 00276 else if (right_op == ibis::qExpr::OP_GE) { 00277 right_op = ibis::qExpr::OP_UNDEFINED; 00278 left_op = ibis::qExpr::OP_LE; 00279 lower = upper; 00280 upper = DBL_MAX; 00281 } 00282 }; 00283 00284 virtual ~qContinuousRange() {delete [] name;} 00285 00286 // provide read access to all private variables 00287 virtual const char *colName() const {return name;} 00288 COMPARE leftOperator() const {return left_op;} 00289 COMPARE rightOperator() const {return right_op;} 00290 virtual double leftBound() const {return lower;} 00291 virtual double rightBound() const {return upper;} 00292 // allow one to possibly change the left and right bounds, the left and 00293 // right operator 00294 double& leftBound() {return lower;} 00295 double& rightBound() {return upper;} 00296 COMPARE& leftOperator() {return left_op;} 00297 COMPARE& rightOperator() {return right_op;} 00298 00299 // Fold the boundaries to integers. 00300 void foldBoundaries(); 00301 // Fold the boundaries to unsigned integers. 00302 void foldUnsignedBoundaries(); 00303 00305 virtual qContinuousRange* dup() const {return new qContinuousRange(*this);} 00306 virtual bool inRange(double val) const; 00307 virtual void restrictRange(double left, double right); 00308 virtual bool empty() const; 00309 00310 virtual void print(std::ostream&) const; 00311 virtual void printFull(std::ostream& out) const; 00312 00313 bool overlap(double, double) const; 00314 inline bool operator<(const qContinuousRange& y) const; 00315 00316 private: 00317 char* name; 00318 double lower, upper; 00319 COMPARE left_op, right_op; 00320 00321 qContinuousRange& operator=(const qContinuousRange&); 00322 friend void ibis::qExpr::simplify(ibis::qExpr*&); 00323 }; // ibis::qContinuousRange 00324 00327 class FASTBIT_CXX_DLLSPEC ibis::qDiscreteRange : public ibis::qRange { 00328 public: 00330 qDiscreteRange() : qRange(DRANGE) {}; 00331 qDiscreteRange(const char *col, const char *nums); 00332 qDiscreteRange(const char *col, const std::vector<uint32_t>& val); 00333 qDiscreteRange(const char *col, const std::vector<double>& val); 00334 qDiscreteRange(const char *col, ibis::array_t<uint32_t>& val); 00335 qDiscreteRange(const char *col, ibis::array_t<double>& val); 00336 00338 qDiscreteRange(const qDiscreteRange& dr) 00339 : qRange(DRANGE), name(dr.name), values(dr.values) {} 00340 virtual ~qDiscreteRange() {}; // private variables automatically destructs 00341 00343 virtual const char* colName() const {return name.c_str();} 00345 const ibis::array_t<double>& getValues() const {return values;} 00347 ibis::array_t<double>& getValues() {return values;} 00348 00350 virtual qDiscreteRange* dup() const {return new qDiscreteRange(*this);} 00351 virtual bool inRange(double val) const; 00352 virtual void restrictRange(double left, double right); 00353 virtual bool empty() const {return values.empty();} 00354 virtual double leftBound() const { 00355 return (values.empty() ? DBL_MAX : values.front());} 00356 virtual double rightBound() const { 00357 return (values.empty() ? -DBL_MAX : values.back());} 00358 virtual uint32_t nItems() const {return values.size();} 00359 00360 ibis::qExpr* convert() const; 00361 00362 bool overlap(double, double) const; 00363 00364 virtual void print(std::ostream&) const; 00365 virtual void printFull(std::ostream& out) const {print(out);} 00366 00367 private: 00368 std::string name; 00369 ibis::array_t<double> values; 00370 00371 qDiscreteRange& operator=(const qDiscreteRange&); 00372 }; // ibis::qDiscreteRange 00373 00382 class FASTBIT_CXX_DLLSPEC ibis::qIntHod : public ibis::qRange { 00383 public: 00385 qIntHod() : qRange(INTHOD) {}; 00386 qIntHod(const char* col, int64_t v1); 00387 qIntHod(const char* col, int64_t v1, int64_t v2); 00388 qIntHod(const char* col, const char* nums); 00389 template <typename T> 00390 qIntHod(const char* col, const std::vector<T>& nums); 00391 template <typename T> 00392 qIntHod(const char* col, const ibis::array_t<T>& nums); 00393 00395 qIntHod(const qIntHod& ih) 00396 : qRange(INTHOD), name(ih.name), values(ih.values) {}; 00397 00399 virtual ~qIntHod() {}; 00400 00402 const char* colName() const {return name.c_str();} 00404 const ibis::array_t<int64_t>& getValues() const {return values;} 00406 ibis::array_t<int64_t>& getValues() {return values;} 00407 00408 virtual bool inRange(double val) const; 00409 virtual bool inRange(int64_t val) const; 00410 virtual void restrictRange(double, double); 00411 virtual double leftBound() const { 00412 return (values.empty() ? DBL_MAX : values.front());} 00413 virtual double rightBound() const { 00414 return (values.empty() ? -DBL_MAX : values.back());} 00415 virtual bool empty() const {return values.empty();} 00417 virtual qIntHod* dup() const {return new qIntHod(*this);} 00418 virtual uint32_t nItems() const {return values.size();} 00419 00420 virtual void print(std::ostream&) const; 00421 virtual void printFull(std::ostream&) const; 00422 00423 private: 00425 std::string name; 00428 ibis::array_t<int64_t> values; 00429 }; // ibis::qIntHod 00430 00439 class FASTBIT_CXX_DLLSPEC ibis::qUIntHod : public ibis::qRange { 00440 public: 00442 qUIntHod() : qRange(UINTHOD) {}; 00443 qUIntHod(const char* col, uint64_t v1); 00444 qUIntHod(const char* col, uint64_t v1, uint64_t v2); 00445 qUIntHod(const char* col, const char* nums); 00446 template <typename T> 00447 qUIntHod(const char* col, const std::vector<T>& nums); 00448 template <typename T> 00449 qUIntHod(const char* col, const ibis::array_t<T>& nums); 00450 00452 qUIntHod(const qUIntHod& ih) 00453 : qRange(UINTHOD), name(ih.name), values(ih.values) {}; 00454 00456 virtual ~qUIntHod() {}; 00457 00459 const char* colName() const {return name.c_str();} 00461 const ibis::array_t<uint64_t>& getValues() const {return values;} 00463 ibis::array_t<uint64_t>& getValues() {return values;} 00464 00465 virtual bool inRange(double val) const; 00466 virtual bool inRange(uint64_t val) const; 00467 virtual void restrictRange(double, double); 00468 virtual double leftBound() const { 00469 return (values.empty() ? DBL_MAX : values.front());} 00470 virtual double rightBound() const { 00471 return (values.empty() ? -DBL_MAX : values.back());} 00472 virtual bool empty() const {return values.empty();} 00474 virtual qUIntHod* dup() const {return new qUIntHod(*this);} 00475 virtual uint32_t nItems() const {return values.size();} 00476 00477 virtual void print(std::ostream&) const; 00478 virtual void printFull(std::ostream&) const; 00479 00480 private: 00482 std::string name; 00485 ibis::array_t<uint64_t> values; 00486 }; // ibis::qUIntHod 00487 00498 class FASTBIT_CXX_DLLSPEC ibis::qString : public ibis::qExpr { 00499 public: 00500 // construct the qString from two strings 00501 qString() : qExpr(STRING), lstr(0), rstr(0) {}; 00502 qString(const char* ls, const char* rs); 00503 virtual ~qString() {delete [] rstr; delete [] lstr;} 00504 00505 const char* leftString() const {return lstr;} 00506 const char* rightString() const {return rstr;} 00507 00508 virtual qString* dup() const {return new qString(*this);} 00509 virtual void print(std::ostream&) const; 00510 virtual void printFull(std::ostream& out) const {print(out);} 00511 virtual void getTableNames(std::set<std::string>& plist) const; 00512 00513 private: 00514 char* lstr; 00515 char* rstr; 00516 00517 qString(const qString& rhs) : qExpr(STRING), 00518 lstr(ibis::util::strnewdup(rhs.lstr)), 00519 rstr(ibis::util::strnewdup(rhs.rstr)) {} 00520 qString& operator=(const qString&); 00521 }; // ibis::qString 00522 00524 class FASTBIT_CXX_DLLSPEC ibis::qLike : public ibis::qExpr { 00525 public: 00527 qLike() : qExpr(LIKE), lstr(0), rpat(0) {}; 00528 qLike(const char* ls, const char* rs); 00530 virtual ~qLike() {delete [] rpat; delete [] lstr;} 00531 00533 const char* colName() const {return lstr;} 00535 const char* pattern() const {return rpat;} 00536 00537 virtual qLike* dup() const {return new qLike(*this);} 00538 virtual void print(std::ostream&) const; 00539 virtual void printFull(std::ostream& out) const {print(out);} 00540 virtual void getTableNames(std::set<std::string>& plist) const; 00541 00542 private: 00544 char* lstr; 00546 char* rpat; 00547 00549 qLike(const qLike& rhs) : qExpr(LIKE), 00550 lstr(ibis::util::strnewdup(rhs.lstr)), 00551 rpat(ibis::util::strnewdup(rhs.rpat)) {} 00552 qLike& operator=(const qLike&); 00553 }; // ibis::qLike 00554 00558 class FASTBIT_CXX_DLLSPEC ibis::qMultiString : public ibis::qExpr { 00559 public: 00560 qMultiString() : qExpr(MSTRING) {}; 00561 qMultiString(const char *col, const char *sval); 00562 virtual ~qMultiString() {}; // name and values automatically destroyed 00563 00565 virtual qMultiString* dup() const {return new qMultiString(*this);} 00566 virtual void print(std::ostream& out) const; 00567 virtual void printFull(std::ostream& out) const {print(out);} 00568 00570 const char* colName() const {return name.c_str();} 00572 const std::vector<std::string>& valueList() const {return values;} 00574 ibis::qExpr* convert() const; 00575 virtual void getTableNames(std::set<std::string>& plist) const; 00576 00577 private: 00578 std::string name; 00579 std::vector<std::string> values; 00580 }; // ibis::qMultiString 00581 00582 namespace ibis { 00584 namespace math { 00586 enum TERM_TYPE {UNDEF_TERM, VARIABLE, NUMBER, STRING, OPERATOR, 00587 STDFUNCTION1, STDFUNCTION2, 00588 CUSTOMFUNCTION1, CUSTOMFUNCTION2}; 00591 enum OPERADOR {UNKNOWN=0, BITOR, BITAND, PLUS, MINUS, MULTIPLY, 00592 DIVIDE, REMAINDER, NEGATE, POWER}; 00594 enum STDFUN1 {ACOS=0, ASIN, ATAN, CEIL, COS, COSH, EXP, FABS, FLOOR, 00595 FREXP, LOG10, LOG, MODF, ROUND, SIN, SINH, SQRT, TAN, 00596 TANH, IS_ZERO, IS_NONZERO}; 00597 enum STDFUN2 {ATAN2=0, FMOD, LDEXP, ROUND2, POW, IS_EQL, IS_GTE, 00598 IS_LTE}; 00599 00601 extern const char* operator_name[]; 00603 extern const char* stdfun1_name[]; 00605 extern const char* stdfun2_name[]; 00618 extern bool preserveInputExpressions; 00619 00625 class term : public ibis::qExpr { 00626 public: 00627 virtual ~term() {}; 00628 00629 virtual TERM_TYPE termType() const = 0; 00630 00632 virtual double eval() const = 0; 00636 virtual bool isTrue() const {return(eval() != 0);} 00638 virtual term* dup() const = 0; 00640 virtual void print(std::ostream& out) const = 0; 00642 virtual void printFull(std::ostream& out) const {print(out);} 00646 virtual term* reduce() {return this;}; 00647 00648 protected: 00649 term() : qExpr(MATHTERM) {}; // used by concrete derived classes 00650 }; // abstract term 00651 00656 class barrel { 00657 public: 00659 barrel() {}; 00661 barrel(const term* const t) {recordVariable(t);} 00663 virtual ~barrel() {}; 00664 00665 // access functions to the names and values 00666 uint32_t size() const {return varmap.size();} 00667 const char* name(uint32_t i) const {return namelist[i];} 00668 const double& value(uint32_t i) const {return varvalues[i];} 00669 double& value(uint32_t i) {return varvalues[i];} 00670 00672 void recordVariable(const term* const t); 00673 inline uint32_t recordVariable(const char* name); 00675 bool equivalent(const barrel& rhs) const; 00676 00677 protected: 00678 // the data structure to store the variable names in a mathematical 00679 // expression 00680 typedef std::map< const char*, uint32_t, ibis::lessi > termMap; 00681 00682 // functions used by the class variable for accessing values of the 00683 // variables 00684 friend class variable; 00685 double getValue(uint32_t i) const {return varvalues[i];} 00687 double getValue(const char* nm) const { 00688 termMap::const_iterator it = varmap.find(nm); 00689 if (it != varmap.end()) { 00690 uint32_t i = (*it).second; 00691 return varvalues[i]; 00692 } 00693 else { 00694 return DBL_MAX; 00695 } 00696 } 00697 00700 termMap varmap; 00701 std::vector< double > varvalues; 00702 std::vector< const char* > namelist; 00703 }; // class barrel 00704 00706 class variable : public term { 00707 public: 00708 // The constructor inserts the variable name to a list in expr and 00709 // record the position in private member variable (that is used 00710 // later to retrieve value from expr class). 00711 variable(const char* var) 00712 : name(ibis::util::strnewdup(var)), myBar(0), varind(0) {} 00713 variable(const variable& v) 00714 : name(ibis::util::strnewdup(v.name)), myBar(v.myBar), 00715 varind(v.varind) {} 00716 virtual ~variable() {delete [] name;} 00717 00718 virtual TERM_TYPE termType() const {return VARIABLE;} 00719 virtual variable* dup() const {return new variable(*this);} 00720 virtual double eval() const {return myBar->getValue(varind);} 00721 virtual void getTableNames(std::set<std::string>& plist) const; 00722 00723 virtual uint32_t nItems() const {return 1U;} 00724 virtual void print(std::ostream& out) const {out << name;} 00725 virtual void printFull(std::ostream& out) const {out << name;} 00726 const char* variableName() const {return name;} 00727 00728 void recordVariable(barrel& bar) const { 00729 if (name != 0 && *name != 0 && *name != '*') { 00730 varind = bar.recordVariable(name); 00731 myBar = &bar; 00732 } 00733 } 00734 00735 protected: 00736 char* name; // the variable name 00737 mutable barrel* myBar;// the barrel containing it 00738 mutable uint32_t varind;// the token to retrieve value from myBar 00739 00740 private: 00741 variable& operator=(const variable&); 00742 }; // the variable term 00743 00745 class number : public term { 00746 public: 00747 number(const char* num) : val(atof(num)) {}; 00748 number(double v) : val(v) {}; 00749 virtual ~number() {}; 00750 00751 virtual TERM_TYPE termType() const {return NUMBER;} 00752 virtual number* dup() const {return new number(val);} 00753 virtual double eval() const {return val;} 00754 00755 virtual uint32_t nItems() const {return 1U;} 00756 virtual void print(std::ostream& out) const {out << val;} 00757 virtual void printFull(std::ostream& out) const {out << val;} 00758 virtual bool isConstant() const {return true;} 00759 virtual bool isTrue() const {return(val != 0);} 00760 00762 void negate() {val = -val;} 00764 void invert() {val = 1.0/val;} 00765 00766 private: 00767 double val; 00768 friend class bediener; 00769 friend void ibis::qExpr::simplify(ibis::qExpr*&); 00770 }; // number 00771 00773 class literal : public term { 00774 public: 00775 literal(const char* s) : str(ibis::util::strnewdup(s)) {}; 00776 virtual ~literal() {delete [] str;} 00777 00778 virtual TERM_TYPE termType() const {return ibis::math::STRING;} 00779 virtual literal* dup() const {return new literal(str);} 00780 virtual double eval() const {return 0.0;} 00781 virtual bool isConstant() const {return true;} 00785 virtual bool isTrue() const { 00786 return(str != 0 && (*str == 't' || *str == 'T' || 00787 (*str == '1' && *str == 0)));} 00788 00789 virtual uint32_t nItems() const {return 1U;} 00790 virtual void print(std::ostream& out) const {out << str;} 00791 virtual void printFull(std::ostream& out) const {out << str;} 00792 operator const char* () const {return str;} 00793 00794 private: 00795 char* str; 00796 00797 literal(const literal&); 00798 literal& operator=(const literal&); 00799 }; // literal 00800 00802 class bediener : public term { 00803 public: 00804 bediener(ibis::math::OPERADOR op) : operador(op) {}; 00805 virtual ~bediener() {}; 00806 00807 virtual TERM_TYPE termType() const {return OPERATOR;} 00808 virtual bediener* dup() const { 00809 bediener *tmp = new bediener(operador); 00810 if (getRight() != 0) 00811 tmp->setRight(getRight()->dup()); 00812 if (getLeft() != 0) 00813 tmp->setLeft(getLeft()->dup()); 00814 return tmp; 00815 } 00816 virtual double eval() const; 00817 virtual void print(std::ostream& out) const; 00818 virtual void printFull(std::ostream& out) const {print(out);} 00819 virtual term* reduce(); 00820 OPERADOR getOperator() const {return operador;} 00821 00822 private: 00823 ibis::math::OPERADOR operador; // Spanish for operator 00824 00825 void reorder(); // reorder the tree of operators 00826 // place the operands into the list of terms if the operator 00827 // matches the specified one. 00828 void linearize(const ibis::math::OPERADOR op, 00829 std::vector<ibis::math::term*>& terms); 00830 // If the right operand is a constant, change operator from - to + 00831 // or from / to *. 00832 void convertConstants(); 00833 friend void ibis::qExpr::simplify(ibis::qExpr*&); 00834 }; // bediener 00835 00837 class stdFunction1 : public term { 00838 public: 00839 stdFunction1(const char* name); 00840 stdFunction1(const STDFUN1 ft) : ftype(ft) {} 00841 virtual ~stdFunction1() {} 00842 00843 virtual stdFunction1* dup() const { 00844 stdFunction1 *tmp = new stdFunction1(ftype); 00845 tmp->setLeft(getLeft()->dup()); 00846 return tmp; 00847 } 00848 virtual TERM_TYPE termType() const {return STDFUNCTION1;} 00849 virtual double eval() const; 00850 virtual void print(std::ostream& out) const; 00851 virtual void printFull(std::ostream& out) const {print(out);} 00852 virtual term* reduce(); 00853 00854 private: 00855 STDFUN1 ftype; 00856 }; // stdFunction1 00857 00859 class stdFunction2 : public term { 00860 public: 00861 stdFunction2(const char* name); 00862 stdFunction2(const STDFUN2 ft) : ftype(ft) {} 00863 virtual ~stdFunction2() {} 00864 00865 virtual stdFunction2* dup() const { 00866 stdFunction2 *tmp = new stdFunction2(ftype); 00867 tmp->setRight(getRight()->dup()); 00868 tmp->setLeft(getLeft()->dup()); 00869 return tmp; 00870 } 00871 virtual TERM_TYPE termType() const {return STDFUNCTION2;} 00872 virtual double eval() const; 00873 virtual void print(std::ostream& out) const; 00874 virtual void printFull(std::ostream& out) const {print(out);} 00875 virtual term* reduce(); 00876 00877 private: 00878 STDFUN2 ftype; 00879 }; // stdFunction2 00880 } // namespace ibis::math 00881 } // namespace ibis 00882 00885 class FASTBIT_CXX_DLLSPEC ibis::compRange : public ibis::qExpr { 00886 public: 00887 00889 compRange() : qExpr(ibis::qExpr::COMPRANGE), expr3(0), 00890 op12(ibis::qExpr::OP_UNDEFINED), 00891 op23(ibis::qExpr::OP_UNDEFINED) {;} 00894 compRange(ibis::math::term* me1, COMPARE lop, 00895 ibis::math::term* me2) 00896 : qExpr(ibis::qExpr::COMPRANGE, me1, me2), expr3(0), 00897 op12(lop), op23(ibis::qExpr::OP_UNDEFINED) {;} 00900 compRange(ibis::math::term* me1, ibis::qExpr::COMPARE lop, 00901 ibis::math::term* me2, ibis::qExpr::COMPARE rop, 00902 ibis::math::term* me3) 00903 : qExpr(ibis::qExpr::COMPRANGE, me1, me2), expr3(me3), 00904 op12(lop), op23(rop) {;} 00906 compRange(const compRange& rhs) : 00907 ibis::qExpr(rhs), expr3(rhs.expr3 ? rhs.expr3->dup() : 0), 00908 op12(rhs.op12), op23(rhs.op23) {}; 00910 virtual ~compRange() {delete expr3;} 00911 00912 // provide read access to the operators 00913 ibis::qExpr::COMPARE leftOperator() const {return op12;} 00914 ibis::qExpr::COMPARE rightOperator() const {return op23;} 00915 ibis::math::term* getTerm3() {return expr3;} 00916 const ibis::math::term* getTerm3() const {return expr3;} 00917 void setTerm3(ibis::math::term* t) {delete expr3; expr3 = t;} 00918 00920 virtual qExpr* dup() const {return new compRange(*this);} 00922 inline bool inRange() const; 00923 00924 virtual uint32_t nItems() const { 00925 return ibis::qExpr::nItems() + 00926 (expr3 != 0 ? expr3->nItems() : 0);} 00928 virtual void print(std::ostream&) const; 00929 virtual void printFull(std::ostream& out) const {print(out);} 00930 virtual void getTableNames(std::set<std::string>& plist) const; 00931 00932 virtual bool isConstant() const { 00933 return ((getLeft() != 0 ? getLeft()->isConstant() : true) && 00934 (getRight() != 0 ? getRight()->isConstant() : true) && 00935 (expr3 != 0 ? expr3->isConstant() : true));} 00936 virtual bool isSimple() const {return isSimpleRange();} 00938 inline bool isSimpleRange() const; 00939 00941 bool maybeStringCompare() const; 00942 00943 // convert a simple expression to qContinuousRange 00944 ibis::qContinuousRange* simpleRange() const; 00945 static compRange* makeConstantFalse(); 00946 static compRange* makeConstantTrue(); 00947 00948 private: 00949 ibis::math::term *expr3; // the right most expression 00950 ibis::qExpr::COMPARE op12; // between qExpr::left and qExpr::right 00951 ibis::qExpr::COMPARE op23; // between qExpr::right and expr3 00952 }; // ibis::compRange 00953 00958 class ibis::deprecatedJoin : public ibis::qExpr { 00959 public: 00960 deprecatedJoin(const char* n1, const char *n2) 00961 : ibis::qExpr(ibis::qExpr::DEPRECATEDJOIN), name1(n1), name2(n2), 00962 expr(0) {}; 00963 deprecatedJoin(const char* n1, const char *n2, ibis::math::term *x) : 00964 ibis::qExpr(ibis::qExpr::DEPRECATEDJOIN), name1(n1), name2(n2), 00965 expr(x) {}; 00966 virtual ~deprecatedJoin() {delete expr;}; 00967 00968 virtual void print(std::ostream& out) const; 00969 virtual void printFull(std::ostream& out) const {print(out);} 00970 virtual deprecatedJoin* dup() const 00971 {return new deprecatedJoin(name1.c_str(), name2.c_str(), expr->dup());}; 00972 00973 const char* getName1() const {return name1.c_str();} 00974 const char* getName2() const {return name2.c_str();} 00975 ibis::math::term* getRange() {return expr;} 00976 const ibis::math::term* getRange() const {return expr;} 00977 void setRange(ibis::math::term *t) {delete expr; expr = t;} 00978 00979 virtual uint32_t nItems() const { 00980 return ibis::qExpr::nItems() + 00981 (expr != 0 ? expr->nItems() : 0);} 00982 00983 private: 00984 std::string name1; 00985 std::string name2; 00986 ibis::math::term *expr; 00987 00988 deprecatedJoin(const deprecatedJoin&); 00989 deprecatedJoin& operator=(const deprecatedJoin&); 00990 }; // class ibis::deprecatedJoin 00991 01003 class ibis::qAnyAny : public ibis::qExpr { 01004 public: 01005 qAnyAny() : qExpr(ANYANY) {}; 01006 qAnyAny(const char *pre, const double dbl); 01007 qAnyAny(const char *pre, const char *val); 01008 ~qAnyAny() {}; // all data members can delete themselves. 01009 01010 const char* getPrefix() const {return prefix.c_str();} 01011 const ibis::array_t<double>& getValues() const {return values;} 01012 01015 virtual qExpr* dup() const {return new qAnyAny(*this);} 01016 01017 virtual void print(std::ostream& out) const; 01018 virtual void printFull(std::ostream& out) const {print(out);} 01019 virtual void getTableNames(std::set<std::string>& plist) const; 01020 01021 private: 01022 std::string prefix; 01023 ibis::array_t<double> values; 01024 }; // class ibis::qAnyAny 01025 01026 inline void ibis::qContinuousRange::foldBoundaries() { 01027 switch (left_op) { 01028 case ibis::qExpr::OP_LT: 01029 lower = floor(lower); 01030 break; 01031 case ibis::qExpr::OP_LE: 01032 lower = ceil(lower); 01033 break; 01034 case ibis::qExpr::OP_GT: 01035 lower = ceil(lower); 01036 break; 01037 case ibis::qExpr::OP_GE: 01038 lower = floor(lower); 01039 break; 01040 case ibis::qExpr::OP_EQ: 01041 if (lower != floor(lower)) 01042 left_op = ibis::qExpr::OP_UNDEFINED; 01043 break; 01044 default: 01045 break; 01046 } 01047 switch (right_op) { 01048 case ibis::qExpr::OP_LT: 01049 upper = ceil(upper); 01050 break; 01051 case ibis::qExpr::OP_LE: 01052 upper = floor(upper); 01053 break; 01054 case ibis::qExpr::OP_GT: 01055 upper = floor(upper); 01056 break; 01057 case ibis::qExpr::OP_GE: 01058 upper = ceil(upper); 01059 break; 01060 case ibis::qExpr::OP_EQ: 01061 if (upper != floor(upper)) 01062 right_op = ibis::qExpr::OP_UNDEFINED; 01063 break; 01064 default: 01065 break; 01066 } 01067 } //ibis::qContinuousRange::foldBoundaries 01068 01069 inline void ibis::qContinuousRange::foldUnsignedBoundaries() { 01070 switch (left_op) { 01071 case ibis::qExpr::OP_LT: 01072 if (lower >= 0.0) { 01073 lower = floor(lower); 01074 } 01075 else { 01076 left_op = ibis::qExpr::OP_LE; 01077 lower = 0.0; 01078 } 01079 break; 01080 case ibis::qExpr::OP_LE: 01081 if (lower >= 0.0) 01082 lower = ceil(lower); 01083 else 01084 lower = 0.0; 01085 break; 01086 case ibis::qExpr::OP_GT: 01087 lower = ceil(lower); 01088 break; 01089 case ibis::qExpr::OP_GE: 01090 lower = floor(lower); 01091 break; 01092 case ibis::qExpr::OP_EQ: 01093 if (lower != floor(lower) || lower < 0.0) 01094 left_op = ibis::qExpr::OP_UNDEFINED; 01095 break; 01096 default: 01097 break; 01098 } 01099 switch (right_op) { 01100 case ibis::qExpr::OP_LT: 01101 upper = ceil(upper); 01102 break; 01103 case ibis::qExpr::OP_LE: 01104 upper = floor(upper); 01105 break; 01106 case ibis::qExpr::OP_GT: 01107 if (upper > 0.0) { 01108 upper = floor(upper); 01109 } 01110 else { 01111 right_op = ibis::qExpr::OP_GE; 01112 upper = 0.0; 01113 } 01114 break; 01115 case ibis::qExpr::OP_GE: 01116 if (upper >= 0.0) 01117 upper = ceil(upper); 01118 else 01119 upper = 0.0; 01120 break; 01121 case ibis::qExpr::OP_EQ: 01122 if (upper != floor(upper) || upper < 0.0) 01123 right_op = ibis::qExpr::OP_UNDEFINED; 01124 break; 01125 default: 01126 break; 01127 } 01128 } //ibis::qContinuousRange::foldUnsignedBoundaries 01129 01133 inline bool 01134 ibis::qContinuousRange::operator<(const ibis::qContinuousRange& y) const { 01135 int cmp = strcmp(colName(), y.colName()); 01136 if (cmp < 0) 01137 return true; 01138 else if (cmp > 0) 01139 return false; 01140 else if (left_op < y.left_op) 01141 return true; 01142 else if (left_op > y.left_op) 01143 return false; 01144 else if (right_op < y.right_op) 01145 return true; 01146 else if (right_op > y.right_op) 01147 return false; 01148 else if (lower < y.lower) 01149 return true; 01150 else if (lower > y.lower) 01151 return false; 01152 else if (upper < y.upper) 01153 return true; 01154 else 01155 return false; 01156 } // ibis::qContinuousRange::operator< 01157 01158 inline bool ibis::compRange::isSimpleRange() const { 01159 bool res = false; 01160 if (expr3 == 0 && getLeft() != 0) 01161 res = ((static_cast<const ibis::math::term*>(getLeft())-> 01162 termType()==ibis::math::VARIABLE && 01163 static_cast<const ibis::math::term*>(getRight())-> 01164 termType()==ibis::math::NUMBER) || 01165 (static_cast<const ibis::math::term*>(getLeft())-> 01166 termType()==ibis::math::NUMBER && 01167 static_cast<const ibis::math::term*>(getRight())-> 01168 termType()==ibis::math::VARIABLE)); 01169 else if (expr3 != 0 && expr3->termType()==ibis::math::NUMBER) 01170 res = (getLeft() == 0 && 01171 static_cast<const ibis::math::term*>(getRight())->termType() 01172 == ibis::math::VARIABLE) || 01173 (static_cast<const ibis::math::term*>(getLeft())-> 01174 termType()==ibis::math::NUMBER && 01175 static_cast<const ibis::math::term*>(getRight())-> 01176 termType()==ibis::math::VARIABLE); 01177 return res; 01178 } // ibis::compRange::isSimpleRange 01179 01180 inline bool ibis::compRange::maybeStringCompare() const { 01181 return (expr3 == 0 && op12==OP_EQ && getLeft() != 0 && getRight() != 0 && 01182 (static_cast<const ibis::math::term*>(getLeft())->termType() 01183 ==ibis::math::VARIABLE || 01184 static_cast<const ibis::math::term*>(getLeft())->termType() 01185 ==ibis::math::STRING) && 01186 (static_cast<const ibis::math::term*>(getRight())->termType() 01187 ==ibis::math::VARIABLE || 01188 static_cast<const ibis::math::term*>(getRight())->termType() 01189 ==ibis::math::STRING)); 01190 } // ibis::compRange::maybeStringCompare 01191 01194 inline bool ibis::compRange::inRange() const { 01195 if (getRight() == 0) return false; 01196 01197 const double tm2 = 01198 static_cast<const ibis::math::term*>(getRight())->eval(); 01199 if (op12 == OP_UNDEFINED && op23 == OP_UNDEFINED) 01200 return (tm2 != 0.0); 01201 01202 bool res = true; 01203 if (getLeft() != 0 && op12 != OP_UNDEFINED) { 01204 const double tm1 = 01205 static_cast<const ibis::math::term*>(getLeft())->eval(); 01206 switch (op12) { 01207 case OP_LT: res = (tm1 < tm2); break; 01208 case OP_LE: res = (tm1 <= tm2); break; 01209 case OP_GT: res = (tm1 > tm2); break; 01210 case OP_GE: res = (tm1 >= tm2); break; 01211 case OP_EQ: res = (tm1 == tm2); break; 01212 default: break; 01213 } 01214 } 01215 if (expr3 != 0 && op23 != OP_UNDEFINED && res == true) { 01216 const double tm3 = expr3->eval(); 01217 switch (op23) { 01218 case OP_LT: res = (tm2 < tm3); break; 01219 case OP_LE: res = (tm2 <= tm3); break; 01220 case OP_GT: res = (tm2 > tm3); break; 01221 case OP_GE: res = (tm2 >= tm3); break; 01222 case OP_EQ: res = (tm2 == tm3); break; 01223 default: break; 01224 } 01225 } 01226 return res; 01227 } // ibis::compRange::inRange 01228 01233 inline bool ibis::qDiscreteRange::inRange(double val) const { 01234 if (values.empty()) return false; 01235 if (val < values[0] || val > values.back()) return false; 01236 01237 uint32_t i = 0, j = values.size(); 01238 if (j < 32) { // sequential search 01239 // -- because the heavy branch prediction cost, linear search is 01240 // more efficient for fairly large range. 01241 for (i = 0; i < j; ++ i) 01242 if (values[i] == val) return true; 01243 return false; 01244 } 01245 else { // binary search 01246 uint32_t m = (i + j) / 2; 01247 while (i < m) { 01248 if (values[m] == val) return true; 01249 if (values[m] < val) 01250 i = m; 01251 else 01252 j = m; 01253 m = (i + j) / 2; 01254 } 01255 return (values[m] == val); 01256 } 01257 } // ibis::qDiscreteRange::inRange 01258 01263 inline bool ibis::qIntHod::inRange(double val) const { 01264 if (values.empty()) return false; 01265 if (val < values[0] || val > values.back()) return false; 01266 01267 uint32_t i = 0, j = values.size(); 01268 if (j < 32) { // sequential search 01269 // -- because the heavy branch prediction cost, linear search is 01270 // more efficient for fairly large range. 01271 for (i = 0; i < j; ++ i) 01272 if (values[i] == val) return true; 01273 return false; 01274 } 01275 else { // binary search 01276 uint32_t m = (i + j) / 2; 01277 while (i < m) { 01278 if (values[m] == val) return true; 01279 if (values[m] < val) 01280 i = m; 01281 else 01282 j = m; 01283 m = (i + j) / 2; 01284 } 01285 return (values[m] == val); 01286 } 01287 } // ibis::qIntHod::inRange 01288 01293 inline bool ibis::qUIntHod::inRange(double val) const { 01294 if (values.empty()) return false; 01295 if (val < values[0] || val > values.back()) return false; 01296 01297 uint32_t i = 0, j = values.size(); 01298 if (j < 32) { // sequential search 01299 // -- because the heavy branch prediction cost, linear search is 01300 // more efficient for fairly large range. 01301 for (i = 0; i < j; ++ i) 01302 if (values[i] == val) return true; 01303 return false; 01304 } 01305 else { // binary search 01306 uint32_t m = (i + j) / 2; 01307 while (i < m) { 01308 if (values[m] == val) return true; 01309 if (values[m] < val) 01310 i = m; 01311 else 01312 j = m; 01313 m = (i + j) / 2; 01314 } 01315 return (values[m] == val); 01316 } 01317 } // ibis::qUIntHod::inRange 01318 01323 inline bool ibis::qIntHod::inRange(int64_t val) const { 01324 if (values.empty()) return false; 01325 if (val < values[0] || val > values.back()) return false; 01326 01327 uint32_t i = 0, j = values.size(); 01328 if (j < 32) { // sequential search 01329 // -- because the heavy branch prediction cost, linear search is 01330 // more efficient for fairly large range. 01331 for (i = 0; i < j; ++ i) 01332 if (values[i] == val) return true; 01333 return false; 01334 } 01335 else { // binary search 01336 uint32_t m = (i + j) / 2; 01337 while (i < m) { 01338 if (values[m] == val) return true; 01339 if (values[m] < val) 01340 i = m; 01341 else 01342 j = m; 01343 m = (i + j) / 2; 01344 } 01345 return (values[m] == val); 01346 } 01347 } // ibis::qIntHod::inRange 01348 01353 inline bool ibis::qUIntHod::inRange(uint64_t val) const { 01354 if (values.empty()) return false; 01355 if (val < values[0] || val > values.back()) return false; 01356 01357 uint32_t i = 0, j = values.size(); 01358 if (j < 32) { // sequential search 01359 // -- because the heavy branch prediction cost, linear search is 01360 // more efficient for fairly large range. 01361 for (i = 0; i < j; ++ i) 01362 if (values[i] == val) return true; 01363 return false; 01364 } 01365 else { // binary search 01366 uint32_t m = (i + j) / 2; 01367 while (i < m) { 01368 if (values[m] == val) return true; 01369 if (values[m] < val) 01370 i = m; 01371 else 01372 j = m; 01373 m = (i + j) / 2; 01374 } 01375 return (values[m] == val); 01376 } 01377 } // ibis::qUIntHod::inRange 01378 01382 inline uint32_t ibis::math::barrel::recordVariable(const char* name) { 01383 uint32_t ind = varmap.size(); 01384 termMap::const_iterator it = varmap.find(name); 01385 if (it == varmap.end()) { 01386 varmap[name] = ind; 01387 namelist.push_back(name); 01388 varvalues.push_back(0.0); 01389 } 01390 else { 01391 ind = (*it).second; 01392 } 01393 return ind; 01394 } // ibis::math::barrel::recordVariable 01395 01396 namespace std { 01397 inline ostream& operator<<(ostream&, const ibis::qExpr&); 01398 inline ostream& operator<<(ostream&, const ibis::qExpr::COMPARE&); 01399 } 01400 01404 inline std::ostream& std::operator<<(std::ostream& out, const ibis::qExpr& pn) { 01405 if (ibis::gVerbose > 5) 01406 pn.printFull(out); 01407 else 01408 pn.print(out); 01409 return out; 01410 } // std::operator<< 01411 01413 inline std::ostream& std::operator<<(std::ostream& out, 01414 const ibis::qExpr::COMPARE& op) { 01415 switch (op) { 01416 default: 01417 case ibis::qExpr::OP_UNDEFINED: 01418 out << "??"; break; 01419 case ibis::qExpr::OP_LT: 01420 out << "<"; break; 01421 case ibis::qExpr::OP_LE: 01422 out << "<="; break; 01423 case ibis::qExpr::OP_GT: 01424 out << ">"; break; 01425 case ibis::qExpr::OP_GE: 01426 out << ">="; break; 01427 case ibis::qExpr::OP_EQ: 01428 out << "=="; break; 01429 } 01430 return out; 01431 } // std::operator<< 01432 #endif // IBIS_EXPR_H
![]() |