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-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

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