00001 // File: $Id$ 00002 // Author: John Wu <John.Wu at acm.org> 00003 // Lawrence Berkeley National Laboratory 00004 // Copyright 1998-2011 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 // Duplicate this query expression. Return the pointer to the new object. 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 00304 // duplicate *this 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; 00313 inline bool operator<(const qContinuousRange& y) const; 00314 00315 private: 00316 char* name; 00317 double lower, upper; 00318 COMPARE left_op, right_op; 00319 00320 qContinuousRange& operator=(const qContinuousRange&); 00321 friend void ibis::qExpr::simplify(ibis::qExpr*&); 00322 }; // ibis::qContinuousRange 00323 00326 class FASTBIT_CXX_DLLSPEC ibis::qDiscreteRange : public ibis::qRange { 00327 public: 00329 qDiscreteRange() : qRange(DRANGE) {}; 00330 qDiscreteRange(const char *col, const char *nums); 00331 qDiscreteRange(const char *col, const std::vector<uint32_t>& val); 00332 qDiscreteRange(const char *col, const std::vector<double>& val); 00333 qDiscreteRange(const char *col, ibis::array_t<uint32_t>& val); 00334 qDiscreteRange(const char *col, ibis::array_t<double>& val); 00335 00337 qDiscreteRange(const qDiscreteRange& dr) 00338 : qRange(DRANGE), name(dr.name), values(dr.values) {} 00339 virtual ~qDiscreteRange() {}; // private variables automatically destructs 00340 00342 virtual const char* colName() const {return name.c_str();} 00344 const ibis::array_t<double>& getValues() const {return values;} 00346 ibis::array_t<double>& getValues() {return values;} 00347 00349 virtual qDiscreteRange* dup() const {return new qDiscreteRange(*this);} 00350 virtual bool inRange(double val) const; 00351 virtual void restrictRange(double left, double right); 00352 virtual bool empty() const {return values.empty();} 00353 virtual double leftBound() const { 00354 return (values.empty() ? DBL_MAX : values.front());} 00355 virtual double rightBound() const { 00356 return (values.empty() ? -DBL_MAX : values.back());} 00357 virtual uint32_t nItems() const {return values.size();} 00358 00360 ibis::qExpr* convert() const; 00361 00362 virtual void print(std::ostream&) const; 00363 virtual void printFull(std::ostream& out) const {print(out);} 00364 00365 private: 00366 std::string name; 00367 ibis::array_t<double> values; 00368 00369 qDiscreteRange& operator=(const qDiscreteRange&); 00370 }; // ibis::qDiscreteRange 00371 00380 class FASTBIT_CXX_DLLSPEC ibis::qIntHod : public ibis::qRange { 00381 public: 00383 qIntHod() : qRange(INTHOD) {}; 00384 qIntHod(const char* col, int64_t v1); 00385 qIntHod(const char* col, int64_t v1, int64_t v2); 00386 qIntHod(const char* col, const char* nums); 00387 template <typename T> 00388 qIntHod(const char* col, const std::vector<T>& nums); 00389 template <typename T> 00390 qIntHod(const char* col, const ibis::array_t<T>& nums); 00391 00393 qIntHod(const qIntHod& ih) 00394 : qRange(INTHOD), name(ih.name), values(ih.values) {}; 00395 00397 virtual ~qIntHod() {}; 00398 00400 const char* colName() const {return name.c_str();} 00402 const ibis::array_t<int64_t>& getValues() const {return values;} 00404 ibis::array_t<int64_t>& getValues() {return values;} 00405 00406 virtual bool inRange(double val) const; 00407 virtual bool inRange(int64_t val) const; 00408 virtual void restrictRange(double, double); 00409 virtual double leftBound() const { 00410 return (values.empty() ? DBL_MAX : values.front());} 00411 virtual double rightBound() const { 00412 return (values.empty() ? -DBL_MAX : values.back());} 00413 virtual bool empty() const {return values.empty();} 00415 virtual qIntHod* dup() const {return new qIntHod(*this);} 00416 virtual uint32_t nItems() const {return values.size();} 00417 00418 virtual void print(std::ostream&) const; 00419 virtual void printFull(std::ostream&) const; 00420 00421 private: 00423 std::string name; 00426 ibis::array_t<int64_t> values; 00427 }; // ibis::qIntHod 00428 00437 class FASTBIT_CXX_DLLSPEC ibis::qUIntHod : public ibis::qRange { 00438 public: 00440 qUIntHod() : qRange(UINTHOD) {}; 00441 qUIntHod(const char* col, uint64_t v1); 00442 qUIntHod(const char* col, uint64_t v1, uint64_t v2); 00443 qUIntHod(const char* col, const char* nums); 00444 template <typename T> 00445 qUIntHod(const char* col, const std::vector<T>& nums); 00446 template <typename T> 00447 qUIntHod(const char* col, const ibis::array_t<T>& nums); 00448 00450 qUIntHod(const qUIntHod& ih) 00451 : qRange(UINTHOD), name(ih.name), values(ih.values) {}; 00452 00454 virtual ~qUIntHod() {}; 00455 00457 const char* colName() const {return name.c_str();} 00459 const ibis::array_t<uint64_t>& getValues() const {return values;} 00461 ibis::array_t<uint64_t>& getValues() {return values;} 00462 00463 virtual bool inRange(double val) const; 00464 virtual bool inRange(uint64_t val) const; 00465 virtual void restrictRange(double, double); 00466 virtual double leftBound() const { 00467 return (values.empty() ? DBL_MAX : values.front());} 00468 virtual double rightBound() const { 00469 return (values.empty() ? -DBL_MAX : values.back());} 00470 virtual bool empty() const {return values.empty();} 00472 virtual qUIntHod* dup() const {return new qUIntHod(*this);} 00473 virtual uint32_t nItems() const {return values.size();} 00474 00475 virtual void print(std::ostream&) const; 00476 virtual void printFull(std::ostream&) const; 00477 00478 private: 00480 std::string name; 00483 ibis::array_t<uint64_t> values; 00484 }; // ibis::qUIntHod 00485 00496 class FASTBIT_CXX_DLLSPEC ibis::qString : public ibis::qExpr { 00497 public: 00498 // construct the qString from two strings 00499 qString() : qExpr(STRING), lstr(0), rstr(0) {}; 00500 qString(const char* ls, const char* rs); 00501 virtual ~qString() {delete [] rstr; delete [] lstr;} 00502 00503 const char* leftString() const {return lstr;} 00504 const char* rightString() const {return rstr;} 00505 00506 virtual qString* dup() const {return new qString(*this);} 00507 virtual void print(std::ostream&) const; 00508 virtual void printFull(std::ostream& out) const {print(out);} 00509 virtual void getTableNames(std::set<std::string>& plist) const; 00510 00511 private: 00512 char* lstr; 00513 char* rstr; 00514 00515 qString(const qString& rhs) : qExpr(STRING), 00516 lstr(ibis::util::strnewdup(rhs.lstr)), 00517 rstr(ibis::util::strnewdup(rhs.rstr)) {} 00518 qString& operator=(const qString&); 00519 }; // ibis::qString 00520 00522 class FASTBIT_CXX_DLLSPEC ibis::qLike : public ibis::qExpr { 00523 public: 00525 qLike() : qExpr(LIKE), lstr(0), rpat(0) {}; 00526 qLike(const char* ls, const char* rs); 00528 virtual ~qLike() {delete [] rpat; delete [] lstr;} 00529 00531 const char* colName() const {return lstr;} 00533 const char* pattern() const {return rpat;} 00534 00535 virtual qLike* dup() const {return new qLike(*this);} 00536 virtual void print(std::ostream&) const; 00537 virtual void printFull(std::ostream& out) const {print(out);} 00538 virtual void getTableNames(std::set<std::string>& plist) const; 00539 00540 private: 00542 char* lstr; 00544 char* rpat; 00545 00547 qLike(const qLike& rhs) : qExpr(LIKE), 00548 lstr(ibis::util::strnewdup(rhs.lstr)), 00549 rpat(ibis::util::strnewdup(rhs.rpat)) {} 00550 qLike& operator=(const qLike&); 00551 }; // ibis::qLike 00552 00556 class FASTBIT_CXX_DLLSPEC ibis::qMultiString : public ibis::qExpr { 00557 public: 00558 qMultiString() : qExpr(MSTRING) {}; 00559 qMultiString(const char *col, const char *sval); 00560 virtual ~qMultiString() {}; // name and values automatically destroyed 00561 00563 virtual qMultiString* dup() const {return new qMultiString(*this);} 00564 virtual void print(std::ostream& out) const; 00565 virtual void printFull(std::ostream& out) const {print(out);} 00566 00568 const char* colName() const {return name.c_str();} 00570 const std::vector<std::string>& valueList() const {return values;} 00572 ibis::qExpr* convert() const; 00573 virtual void getTableNames(std::set<std::string>& plist) const; 00574 00575 private: 00576 std::string name; 00577 std::vector<std::string> values; 00578 }; // ibis::qMultiString 00579 00580 namespace ibis { 00582 namespace math { 00584 enum TERM_TYPE {UNDEF_TERM, VARIABLE, NUMBER, STRING, OPERATOR, 00585 STDFUNCTION1, STDFUNCTION2, 00586 CUSTOMFUNCTION1, CUSTOMFUNCTION2}; 00589 enum OPERADOR {UNKNOWN=0, BITOR, BITAND, PLUS, MINUS, MULTIPLY, 00590 DIVIDE, REMAINDER, NEGATE, POWER}; 00592 enum STDFUN1 {ACOS=0, ASIN, ATAN, CEIL, COS, COSH, EXP, FABS, FLOOR, 00593 FREXP, LOG10, LOG, MODF, ROUND, SIN, SINH, SQRT, TAN, 00594 TANH}; 00595 enum STDFUN2 {ATAN2=0, FMOD, LDEXP, ROUND2, POW}; 00596 00598 extern const char* operator_name[]; 00600 extern const char* stdfun1_name[]; 00602 extern const char* stdfun2_name[]; 00615 extern bool preserveInputExpressions; 00616 00622 class term : public ibis::qExpr { 00623 public: 00624 virtual ~term() {}; 00625 00626 virtual TERM_TYPE termType() const = 0; 00627 00629 virtual double eval() const = 0; 00633 virtual bool isTrue() const {return(eval() != 0);} 00635 virtual term* dup() const = 0; 00637 virtual void print(std::ostream& out) const = 0; 00639 virtual void printFull(std::ostream& out) const {print(out);} 00643 virtual term* reduce() {return this;}; 00644 00645 protected: 00646 term() : qExpr(MATHTERM) {}; // used by concrete derived classes 00647 }; // abstract term 00648 00653 class barrel { 00654 public: 00656 barrel() {}; 00658 barrel(const term* const t) {recordVariable(t);} 00660 virtual ~barrel() {}; 00661 00662 // access functions to the names and values 00663 uint32_t size() const {return varmap.size();} 00664 const char* name(uint32_t i) const {return namelist[i];} 00665 const double& value(uint32_t i) const {return varvalues[i];} 00666 double& value(uint32_t i) {return varvalues[i];} 00667 00669 void recordVariable(const term* const t); 00670 inline uint32_t recordVariable(const char* name); 00672 bool equivalent(const barrel& rhs) const; 00673 00674 protected: 00675 // the data structure to store the variable names in a mathematical 00676 // expression 00677 typedef std::map< const char*, uint32_t, ibis::lessi > termMap; 00678 00679 // functions used by the class variable for accessing values of the 00680 // variables 00681 friend class variable; 00682 double getValue(uint32_t i) const {return varvalues[i];} 00684 double getValue(const char* nm) const { 00685 termMap::const_iterator it = varmap.find(nm); 00686 if (it != varmap.end()) { 00687 uint32_t i = (*it).second; 00688 return varvalues[i]; 00689 } 00690 else { 00691 return DBL_MAX; 00692 } 00693 } 00694 00697 termMap varmap; 00698 std::vector< double > varvalues; 00699 std::vector< const char* > namelist; 00700 }; // class barrel 00701 00703 class variable : public term { 00704 public: 00705 // The constructor inserts the variable name to a list in expr and 00706 // record the position in private member variable (that is used 00707 // later to retrieve value from expr class). 00708 variable(const char* var) 00709 : name(ibis::util::strnewdup(var)), myBar(0), varind(0) {} 00710 variable(const variable& v) 00711 : name(ibis::util::strnewdup(v.name)), myBar(v.myBar), 00712 varind(v.varind) {} 00713 virtual ~variable() {delete [] name;} 00714 00715 virtual TERM_TYPE termType() const {return VARIABLE;} 00716 virtual variable* dup() const {return new variable(*this);} 00717 virtual double eval() const {return myBar->getValue(varind);} 00718 virtual void getTableNames(std::set<std::string>& plist) const; 00719 00720 virtual uint32_t nItems() const {return 1U;} 00721 virtual void print(std::ostream& out) const {out << name;} 00722 virtual void printFull(std::ostream& out) const {out << name;} 00723 const char* variableName() const {return name;} 00724 00725 void recordVariable(barrel& bar) const { 00726 if (name != 0 && *name != 0 && *name != '*') { 00727 varind = bar.recordVariable(name); 00728 myBar = &bar; 00729 } 00730 } 00731 00732 protected: 00733 char* name; // the variable name 00734 mutable barrel* myBar;// the barrel containing it 00735 mutable uint32_t varind;// the token to retrieve value from myBar 00736 00737 private: 00738 variable& operator=(const variable&); 00739 }; // the variable term 00740 00742 class number : public term { 00743 public: 00744 number(const char* num) : val(atof(num)) {}; 00745 number(double v) : val(v) {}; 00746 virtual ~number() {}; 00747 00748 virtual TERM_TYPE termType() const {return NUMBER;} 00749 virtual number* dup() const {return new number(val);} 00750 virtual double eval() const {return val;} 00751 00752 virtual uint32_t nItems() const {return 1U;} 00753 virtual void print(std::ostream& out) const {out << val;} 00754 virtual void printFull(std::ostream& out) const {out << val;} 00755 virtual bool isConstant() const {return true;} 00756 virtual bool isTrue() const {return(val != 0);} 00757 00759 void negate() {val = -val;} 00761 void invert() {val = 1.0/val;} 00762 00763 private: 00764 double val; 00765 friend class bediener; 00766 friend void ibis::qExpr::simplify(ibis::qExpr*&); 00767 }; // number 00768 00770 class literal : public term { 00771 public: 00772 literal(const char* s) : str(ibis::util::strnewdup(s)) {}; 00773 virtual ~literal() {delete [] str;} 00774 00775 virtual TERM_TYPE termType() const {return ibis::math::STRING;} 00776 virtual literal* dup() const {return new literal(str);} 00777 virtual double eval() const {return 0.0;} 00778 virtual bool isConstant() const {return true;} 00782 virtual bool isTrue() const { 00783 return(str != 0 && (*str == 't' || *str == 'T' || 00784 (*str == '1' && *str == 0)));} 00785 00786 virtual uint32_t nItems() const {return 1U;} 00787 virtual void print(std::ostream& out) const {out << str;} 00788 virtual void printFull(std::ostream& out) const {out << str;} 00789 operator const char* () const {return str;} 00790 00791 private: 00792 char* str; 00793 00794 literal(const literal&); 00795 literal& operator=(const literal&); 00796 }; // literal 00797 00799 class bediener : public term { 00800 public: 00801 bediener(ibis::math::OPERADOR op) : operador(op) {}; 00802 virtual ~bediener() {}; 00803 00804 virtual TERM_TYPE termType() const {return OPERATOR;} 00805 virtual bediener* dup() const { 00806 bediener *tmp = new bediener(operador); 00807 if (getRight() != 0) 00808 tmp->setRight(getRight()->dup()); 00809 if (getLeft() != 0) 00810 tmp->setLeft(getLeft()->dup()); 00811 return tmp; 00812 } 00813 virtual double eval() const; 00814 virtual void print(std::ostream& out) const; 00815 virtual void printFull(std::ostream& out) const {print(out);} 00816 virtual term* reduce(); 00817 OPERADOR getOperator() const {return operador;} 00818 00819 private: 00820 ibis::math::OPERADOR operador; // Spanish for operator 00821 00822 void reorder(); // reorder the tree of operators 00823 // place the operands into the list of terms if the operator 00824 // matches the specified one. 00825 void linearize(const ibis::math::OPERADOR op, 00826 std::vector<ibis::math::term*>& terms); 00827 // If the right operand is a constant, change operator from - to + 00828 // or from / to *. 00829 void convertConstants(); 00830 friend void ibis::qExpr::simplify(ibis::qExpr*&); 00831 }; // bediener 00832 00834 class stdFunction1 : public term { 00835 public: 00836 stdFunction1(const char* name); 00837 stdFunction1(const STDFUN1 ft) : ftype(ft) {} 00838 virtual ~stdFunction1() {} 00839 00840 virtual stdFunction1* dup() const { 00841 stdFunction1 *tmp = new stdFunction1(ftype); 00842 tmp->setLeft(getLeft()->dup()); 00843 return tmp; 00844 } 00845 virtual TERM_TYPE termType() const {return STDFUNCTION1;} 00846 virtual double eval() const; 00847 virtual void print(std::ostream& out) const; 00848 virtual void printFull(std::ostream& out) const {print(out);} 00849 virtual term* reduce(); 00850 00851 private: 00852 STDFUN1 ftype; 00853 }; // stdFunction1 00854 00856 class stdFunction2 : public term { 00857 public: 00858 stdFunction2(const char* name); 00859 stdFunction2(const STDFUN2 ft) : ftype(ft) {} 00860 virtual ~stdFunction2() {} 00861 00862 virtual stdFunction2* dup() const { 00863 stdFunction2 *tmp = new stdFunction2(ftype); 00864 tmp->setRight(getRight()->dup()); 00865 tmp->setLeft(getLeft()->dup()); 00866 return tmp; 00867 } 00868 virtual TERM_TYPE termType() const {return STDFUNCTION2;} 00869 virtual double eval() const; 00870 virtual void print(std::ostream& out) const; 00871 virtual void printFull(std::ostream& out) const {print(out);} 00872 virtual term* reduce(); 00873 00874 private: 00875 STDFUN2 ftype; 00876 }; // stdFunction2 00877 } // namespace ibis::math 00878 } // namespace ibis 00879 00882 class FASTBIT_CXX_DLLSPEC ibis::compRange : public ibis::qExpr { 00883 public: 00884 00886 compRange() : qExpr(ibis::qExpr::COMPRANGE), expr3(0), 00887 op12(ibis::qExpr::OP_UNDEFINED), 00888 op23(ibis::qExpr::OP_UNDEFINED) {;} 00891 compRange(ibis::math::term* me1, COMPARE lop, 00892 ibis::math::term* me2) 00893 : qExpr(ibis::qExpr::COMPRANGE, me1, me2), expr3(0), 00894 op12(lop), op23(ibis::qExpr::OP_UNDEFINED) {;} 00897 compRange(ibis::math::term* me1, ibis::qExpr::COMPARE lop, 00898 ibis::math::term* me2, ibis::qExpr::COMPARE rop, 00899 ibis::math::term* me3) 00900 : qExpr(ibis::qExpr::COMPRANGE, me1, me2), expr3(me3), 00901 op12(lop), op23(rop) {;} 00903 compRange(const compRange& rhs) : 00904 ibis::qExpr(rhs), expr3(rhs.expr3 ? rhs.expr3->dup() : 0), 00905 op12(rhs.op12), op23(rhs.op23) {}; 00907 virtual ~compRange() {delete expr3;} 00908 00909 // provide read access to the operators 00910 ibis::qExpr::COMPARE leftOperator() const {return op12;} 00911 ibis::qExpr::COMPARE rightOperator() const {return op23;} 00912 ibis::math::term* getTerm3() {return expr3;} 00913 const ibis::math::term* getTerm3() const {return expr3;} 00914 void setTerm3(ibis::math::term* t) {delete expr3; expr3 = t;} 00915 00917 virtual qExpr* dup() const {return new compRange(*this);} 00919 inline bool inRange() const; 00920 00921 virtual uint32_t nItems() const { 00922 return ibis::qExpr::nItems() + 00923 (expr3 != 0 ? expr3->nItems() : 0);} 00925 virtual void print(std::ostream&) const; 00926 virtual void printFull(std::ostream& out) const {print(out);} 00927 virtual void getTableNames(std::set<std::string>& plist) const; 00928 00929 virtual bool isConstant() const { 00930 return ((getLeft() != 0 ? getLeft()->isConstant() : true) && 00931 (getRight() != 0 ? getRight()->isConstant() : true) && 00932 (expr3 != 0 ? expr3->isConstant() : true));} 00933 virtual bool isSimple() const {return isSimpleRange();} 00935 inline bool isSimpleRange() const; 00936 00938 bool maybeStringCompare() const; 00939 00940 // convert a simple expression to qContinuousRange 00941 ibis::qContinuousRange* simpleRange() const; 00942 static compRange* makeConstantFalse(); 00943 00944 private: 00945 ibis::math::term *expr3; // the right most expression 00946 ibis::qExpr::COMPARE op12; // between qExpr::left and qExpr::right 00947 ibis::qExpr::COMPARE op23; // between qExpr::right and expr3 00948 }; // ibis::compRange 00949 00954 class ibis::deprecatedJoin : public ibis::qExpr { 00955 public: 00956 deprecatedJoin(const char* n1, const char *n2) 00957 : ibis::qExpr(ibis::qExpr::DEPRECATEDJOIN), name1(n1), name2(n2), 00958 expr(0) {}; 00959 deprecatedJoin(const char* n1, const char *n2, ibis::math::term *x) : 00960 ibis::qExpr(ibis::qExpr::DEPRECATEDJOIN), name1(n1), name2(n2), 00961 expr(x) {}; 00962 virtual ~deprecatedJoin() {delete expr;}; 00963 00964 virtual void print(std::ostream& out) const; 00965 virtual void printFull(std::ostream& out) const {print(out);} 00966 virtual deprecatedJoin* dup() const 00967 {return new deprecatedJoin(name1.c_str(), name2.c_str(), expr->dup());}; 00968 00969 const char* getName1() const {return name1.c_str();} 00970 const char* getName2() const {return name2.c_str();} 00971 ibis::math::term* getRange() {return expr;} 00972 const ibis::math::term* getRange() const {return expr;} 00973 void setRange(ibis::math::term *t) {delete expr; expr = t;} 00974 00975 virtual uint32_t nItems() const { 00976 return ibis::qExpr::nItems() + 00977 (expr != 0 ? expr->nItems() : 0);} 00978 00979 private: 00980 std::string name1; 00981 std::string name2; 00982 ibis::math::term *expr; 00983 00984 deprecatedJoin(const deprecatedJoin&); 00985 deprecatedJoin& operator=(const deprecatedJoin&); 00986 }; // class ibis::deprecatedJoin 00987 00999 class ibis::qAnyAny : public ibis::qExpr { 01000 public: 01001 qAnyAny() : qExpr(ANYANY) {}; 01002 qAnyAny(const char *pre, const double dbl); 01003 qAnyAny(const char *pre, const char *val); 01004 ~qAnyAny() {}; // all data members can delete themselves. 01005 01006 const char* getPrefix() const {return prefix.c_str();} 01007 const ibis::array_t<double>& getValues() const {return values;} 01008 01009 // Use the compiler generated copy constructor to perform duplication. 01010 virtual qExpr* dup() const {return new qAnyAny(*this);} 01011 01012 virtual void print(std::ostream& out) const; 01013 virtual void printFull(std::ostream& out) const {print(out);} 01014 virtual void getTableNames(std::set<std::string>& plist) const; 01015 01016 private: 01017 std::string prefix; 01018 ibis::array_t<double> values; 01019 }; // class ibis::qAnyAny 01020 01021 inline void ibis::qContinuousRange::foldBoundaries() { 01022 switch (left_op) { 01023 case ibis::qExpr::OP_LT: 01024 lower = floor(lower); 01025 break; 01026 case ibis::qExpr::OP_LE: 01027 lower = ceil(lower); 01028 break; 01029 case ibis::qExpr::OP_GT: 01030 lower = ceil(lower); 01031 break; 01032 case ibis::qExpr::OP_GE: 01033 lower = floor(lower); 01034 break; 01035 case ibis::qExpr::OP_EQ: 01036 if (lower != floor(lower)) 01037 left_op = ibis::qExpr::OP_UNDEFINED; 01038 break; 01039 default: 01040 break; 01041 } 01042 switch (right_op) { 01043 case ibis::qExpr::OP_LT: 01044 upper = ceil(upper); 01045 break; 01046 case ibis::qExpr::OP_LE: 01047 upper = floor(upper); 01048 break; 01049 case ibis::qExpr::OP_GT: 01050 upper = floor(upper); 01051 break; 01052 case ibis::qExpr::OP_GE: 01053 upper = ceil(upper); 01054 break; 01055 case ibis::qExpr::OP_EQ: 01056 if (upper != floor(upper)) 01057 right_op = ibis::qExpr::OP_UNDEFINED; 01058 break; 01059 default: 01060 break; 01061 } 01062 } //ibis::qContinuousRange::foldBoundaries 01063 01064 inline void ibis::qContinuousRange::foldUnsignedBoundaries() { 01065 switch (left_op) { 01066 case ibis::qExpr::OP_LT: 01067 if (lower >= 0.0) { 01068 lower = floor(lower); 01069 } 01070 else { 01071 left_op = ibis::qExpr::OP_LE; 01072 lower = 0.0; 01073 } 01074 break; 01075 case ibis::qExpr::OP_LE: 01076 if (lower >= 0.0) 01077 lower = ceil(lower); 01078 else 01079 lower = 0.0; 01080 break; 01081 case ibis::qExpr::OP_GT: 01082 lower = ceil(lower); 01083 break; 01084 case ibis::qExpr::OP_GE: 01085 lower = floor(lower); 01086 break; 01087 case ibis::qExpr::OP_EQ: 01088 if (lower != floor(lower) || lower < 0.0) 01089 left_op = ibis::qExpr::OP_UNDEFINED; 01090 break; 01091 default: 01092 break; 01093 } 01094 switch (right_op) { 01095 case ibis::qExpr::OP_LT: 01096 upper = ceil(upper); 01097 break; 01098 case ibis::qExpr::OP_LE: 01099 upper = floor(upper); 01100 break; 01101 case ibis::qExpr::OP_GT: 01102 if (upper > 0.0) { 01103 upper = floor(upper); 01104 } 01105 else { 01106 right_op = ibis::qExpr::OP_GE; 01107 upper = 0.0; 01108 } 01109 break; 01110 case ibis::qExpr::OP_GE: 01111 if (upper >= 0.0) 01112 upper = ceil(upper); 01113 else 01114 upper = 0.0; 01115 break; 01116 case ibis::qExpr::OP_EQ: 01117 if (upper != floor(upper) || upper < 0.0) 01118 right_op = ibis::qExpr::OP_UNDEFINED; 01119 break; 01120 default: 01121 break; 01122 } 01123 } //ibis::qContinuousRange::foldUnsignedBoundaries 01124 01126 inline bool ibis::qContinuousRange::operator< 01127 (const ibis::qContinuousRange& y) const { 01128 int cmp = strcmp(colName(), y.colName()); 01129 if (cmp < 0) 01130 return true; 01131 else if (cmp > 0) 01132 return false; 01133 else if (left_op < y.left_op) 01134 return true; 01135 else if (left_op > y.left_op) 01136 return false; 01137 else if (right_op < y.right_op) 01138 return true; 01139 else if (right_op > y.right_op) 01140 return false; 01141 else if (lower < y.lower) 01142 return true; 01143 else if (lower > y.lower) 01144 return false; 01145 else if (upper < y.upper) 01146 return true; 01147 else 01148 return false; 01149 } // ibis::qContinuousRange::operator< 01150 01151 inline bool ibis::compRange::isSimpleRange() const { 01152 bool res = false; 01153 if (expr3 == 0 && getLeft() != 0) 01154 res = ((static_cast<const ibis::math::term*>(getLeft())-> 01155 termType()==ibis::math::VARIABLE && 01156 static_cast<const ibis::math::term*>(getRight())-> 01157 termType()==ibis::math::NUMBER) || 01158 (static_cast<const ibis::math::term*>(getLeft())-> 01159 termType()==ibis::math::NUMBER && 01160 static_cast<const ibis::math::term*>(getRight())-> 01161 termType()==ibis::math::VARIABLE)); 01162 else if (expr3 != 0 && expr3->termType()==ibis::math::NUMBER) 01163 res = (getLeft() == 0 && 01164 static_cast<const ibis::math::term*>(getRight())->termType() 01165 == ibis::math::VARIABLE) || 01166 (static_cast<const ibis::math::term*>(getLeft())-> 01167 termType()==ibis::math::NUMBER && 01168 static_cast<const ibis::math::term*>(getRight())-> 01169 termType()==ibis::math::VARIABLE); 01170 return res; 01171 } // ibis::compRange::isSimpleRange 01172 01173 inline bool ibis::compRange::maybeStringCompare() const { 01174 return (expr3 == 0 && op12==OP_EQ && getLeft() != 0 && getRight() != 0 && 01175 (static_cast<const ibis::math::term*>(getLeft())->termType() 01176 ==ibis::math::VARIABLE || 01177 static_cast<const ibis::math::term*>(getLeft())->termType() 01178 ==ibis::math::STRING) && 01179 (static_cast<const ibis::math::term*>(getRight())->termType() 01180 ==ibis::math::VARIABLE || 01181 static_cast<const ibis::math::term*>(getRight())->termType() 01182 ==ibis::math::STRING)); 01183 } // ibis::compRange::maybeStringCompare 01184 01187 inline bool ibis::compRange::inRange() const { 01188 if (getRight() == 0) return false; 01189 01190 const double tm2 = 01191 static_cast<const ibis::math::term*>(getRight())->eval(); 01192 if (op12 == OP_UNDEFINED && op23 == OP_UNDEFINED) 01193 return (tm2 != 0.0); 01194 01195 bool res = true; 01196 if (getLeft() != 0 && op12 != OP_UNDEFINED) { 01197 const double tm1 = 01198 static_cast<const ibis::math::term*>(getLeft())->eval(); 01199 switch (op12) { 01200 case OP_LT: res = (tm1 < tm2); break; 01201 case OP_LE: res = (tm1 <= tm2); break; 01202 case OP_GT: res = (tm1 > tm2); break; 01203 case OP_GE: res = (tm1 >= tm2); break; 01204 case OP_EQ: res = (tm1 == tm2); break; 01205 default: break; 01206 } 01207 } 01208 if (expr3 != 0 && op23 != OP_UNDEFINED && res == true) { 01209 const double tm3 = expr3->eval(); 01210 switch (op23) { 01211 case OP_LT: res = (tm2 < tm3); break; 01212 case OP_LE: res = (tm2 <= tm3); break; 01213 case OP_GT: res = (tm2 > tm3); break; 01214 case OP_GE: res = (tm2 >= tm3); break; 01215 case OP_EQ: res = (tm2 == tm3); break; 01216 default: break; 01217 } 01218 } 01219 return res; 01220 } // ibis::compRange::inRange 01221 01226 inline bool ibis::qDiscreteRange::inRange(double val) const { 01227 if (values.empty()) return false; 01228 if (val < values[0] || val > values.back()) return false; 01229 01230 uint32_t i = 0, j = values.size(); 01231 if (j < 32) { // sequential search 01232 // -- because the heavy branch prediction cost, linear search is 01233 // more efficient for fairly large range. 01234 for (i = 0; i < j; ++ i) 01235 if (values[i] == val) return true; 01236 return false; 01237 } 01238 else { // binary search 01239 uint32_t m = (i + j) / 2; 01240 while (i < m) { 01241 if (values[m] == val) return true; 01242 if (values[m] < val) 01243 i = m; 01244 else 01245 j = m; 01246 m = (i + j) / 2; 01247 } 01248 return (values[m] == val); 01249 } 01250 } // ibis::qDiscreteRange::inRange 01251 01256 inline bool ibis::qIntHod::inRange(double val) const { 01257 if (values.empty()) return false; 01258 if (val < values[0] || val > values.back()) return false; 01259 01260 uint32_t i = 0, j = values.size(); 01261 if (j < 32) { // sequential search 01262 // -- because the heavy branch prediction cost, linear search is 01263 // more efficient for fairly large range. 01264 for (i = 0; i < j; ++ i) 01265 if (values[i] == val) return true; 01266 return false; 01267 } 01268 else { // binary search 01269 uint32_t m = (i + j) / 2; 01270 while (i < m) { 01271 if (values[m] == val) return true; 01272 if (values[m] < val) 01273 i = m; 01274 else 01275 j = m; 01276 m = (i + j) / 2; 01277 } 01278 return (values[m] == val); 01279 } 01280 } // ibis::qIntHod::inRange 01281 01286 inline bool ibis::qUIntHod::inRange(double val) const { 01287 if (values.empty()) return false; 01288 if (val < values[0] || val > values.back()) return false; 01289 01290 uint32_t i = 0, j = values.size(); 01291 if (j < 32) { // sequential search 01292 // -- because the heavy branch prediction cost, linear search is 01293 // more efficient for fairly large range. 01294 for (i = 0; i < j; ++ i) 01295 if (values[i] == val) return true; 01296 return false; 01297 } 01298 else { // binary search 01299 uint32_t m = (i + j) / 2; 01300 while (i < m) { 01301 if (values[m] == val) return true; 01302 if (values[m] < val) 01303 i = m; 01304 else 01305 j = m; 01306 m = (i + j) / 2; 01307 } 01308 return (values[m] == val); 01309 } 01310 } // ibis::qUIntHod::inRange 01311 01316 inline bool ibis::qIntHod::inRange(int64_t val) const { 01317 if (values.empty()) return false; 01318 if (val < values[0] || val > values.back()) return false; 01319 01320 uint32_t i = 0, j = values.size(); 01321 if (j < 32) { // sequential search 01322 // -- because the heavy branch prediction cost, linear search is 01323 // more efficient for fairly large range. 01324 for (i = 0; i < j; ++ i) 01325 if (values[i] == val) return true; 01326 return false; 01327 } 01328 else { // binary search 01329 uint32_t m = (i + j) / 2; 01330 while (i < m) { 01331 if (values[m] == val) return true; 01332 if (values[m] < val) 01333 i = m; 01334 else 01335 j = m; 01336 m = (i + j) / 2; 01337 } 01338 return (values[m] == val); 01339 } 01340 } // ibis::qIntHod::inRange 01341 01346 inline bool ibis::qUIntHod::inRange(uint64_t val) const { 01347 if (values.empty()) return false; 01348 if (val < values[0] || val > values.back()) return false; 01349 01350 uint32_t i = 0, j = values.size(); 01351 if (j < 32) { // sequential search 01352 // -- because the heavy branch prediction cost, linear search is 01353 // more efficient for fairly large range. 01354 for (i = 0; i < j; ++ i) 01355 if (values[i] == val) return true; 01356 return false; 01357 } 01358 else { // binary search 01359 uint32_t m = (i + j) / 2; 01360 while (i < m) { 01361 if (values[m] == val) return true; 01362 if (values[m] < val) 01363 i = m; 01364 else 01365 j = m; 01366 m = (i + j) / 2; 01367 } 01368 return (values[m] == val); 01369 } 01370 } // ibis::qUIntHod::inRange 01371 01375 inline uint32_t ibis::math::barrel::recordVariable(const char* name) { 01376 uint32_t ind = varmap.size(); 01377 termMap::const_iterator it = varmap.find(name); 01378 if (it == varmap.end()) { 01379 varmap[name] = ind; 01380 namelist.push_back(name); 01381 varvalues.push_back(0.0); 01382 } 01383 else { 01384 ind = (*it).second; 01385 } 01386 return ind; 01387 } // ibis::math::barrel::recordVariable 01388 01389 namespace std { 01390 inline ostream& operator<<(ostream&, const ibis::qExpr&); 01391 inline ostream& operator<<(ostream&, const ibis::qExpr::COMPARE&); 01392 } 01393 01397 inline std::ostream& std::operator<<(std::ostream& out, const ibis::qExpr& pn) { 01398 if (ibis::gVerbose > 5) 01399 pn.printFull(out); 01400 else 01401 pn.print(out); 01402 return out; 01403 } // std::operator<< 01404 01406 inline std::ostream& std::operator<<(std::ostream& out, 01407 const ibis::qExpr::COMPARE& op) { 01408 switch (op) { 01409 default: 01410 case ibis::qExpr::OP_UNDEFINED: 01411 out << "??"; break; 01412 case ibis::qExpr::OP_LT: 01413 out << "<"; break; 01414 case ibis::qExpr::OP_LE: 01415 out << "<="; break; 01416 case ibis::qExpr::OP_GT: 01417 out << ">"; break; 01418 case ibis::qExpr::OP_GE: 01419 out << ">="; break; 01420 case ibis::qExpr::OP_EQ: 01421 out << "=="; break; 01422 } 01423 return out; 01424 } // std::operator<< 01425 #endif // IBIS_EXPR_H
![]() |