qExpr.h
Go to the documentation of this file.
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

Make It A Bit Faster
Contact us
Disclaimers
FastBit source code
FastBit mailing list archive