qExpr.h

Go to the documentation of this file.

// File: $Id$
// Author: John Wu <John.Wu at nersc.gov>
//      Lawrence Berkeley National Laboratory
// Copyright 1998-2008 the Regents of the University of California
//
// Primary contact: John Wu <John.Wu at nersc.gov>
#ifndef IBIS_EXPR_H
#define IBIS_EXPR_H
#include "util.h"
#include <functional>   // std::less, std::binary_function<>

namespace ibis { // additional names related to qExpr
    class qRange;       
    class qContinuousRange;
    class qDiscreteRange;       
    class qString;      
    class qMultiString; 
    class compRange;    
    class rangeJoin;    
    class qAnyAny;      
}

class ibis::qExpr {
public:
    enum TYPE {
        LOGICAL_UNDEFINED, LOGICAL_NOT, LOGICAL_AND, LOGICAL_OR, LOGICAL_XOR,
        LOGICAL_MINUS, RANGE, DRANGE, STRING, MSTRING, COMPRANGE, MATHTERM,
        JOIN, TOPK, ANYANY
    };
    enum COMPARE {
        OP_UNDEFINED, OP_LT, OP_GT, OP_LE, OP_GE, OP_EQ
    };

    qExpr() : type(LOGICAL_UNDEFINED), left(0), right(0) {}

    explicit qExpr(TYPE op) : type(op), left(0), right(0) {}
    qExpr(TYPE op, qExpr* qe1, qExpr* qe2) : type(op), left(qe1),
                                             right(qe2) {}
    qExpr(const qExpr& qe) : type(qe.type),
                             left(qe.left ? qe.left->dup() : 0),
                             right(qe.right ? qe.right->dup() : 0) {}
    virtual ~qExpr() {delete right; delete left;}

    void setLeft(qExpr *expr) {delete left; left=expr;}
    void setRight(qExpr *expr) {delete right; right=expr;}
    qExpr*& getLeft() {return left;}
    qExpr*& getRight() {return right;}

    TYPE getType() const {return type;}
    const qExpr* getLeft() const {return left;}
    const qExpr* getRight() const {return right;}

    bool hasJoin() const;

    virtual void print(std::ostream&) const;

    virtual void printRange(std::ostream& out) const {
        if (left) left->printRange(out);
        if (right) right->printRange(out);
    };

    struct weight {
        virtual double operator()(const qExpr* ex) const = 0;
        virtual ~weight() {};
    };
    double reorder(const weight&); 
    // Duplicate this query expression.  Return the pointer to the new object.
    virtual qExpr* dup() const {
        qExpr* res = new qExpr(type);
        if (left)
            res->left = left->dup();
        if (right)
            res->right = right->dup();
        return res;
    }

    bool isTerminal() const {return (left==0 && right==0);}
    bool directEval() const
    {return (type==RANGE || type==STRING || type==COMPRANGE ||
             type==DRANGE || type==MSTRING || type==ANYANY ||
             (type==LOGICAL_NOT && left && left->directEval()));}

    virtual bool isSimple() const {
        if (left) {
            if (right) return left->isSimple() && right->isSimple();
            else return left->isSimple();
        }
        else if (right) {
            return right->isSimple();
        }
        else { // the derived classes essentially overrides this case.
            return true;
        }
    }

    int separateSimple(ibis::qExpr *&simple, ibis::qExpr *&tail) const;

    void extractJoins(std::vector<const rangeJoin*>& terms) const;
    qRange* findRange(const char* vname);

    static void simplify(ibis::qExpr*&);

    const qExpr& operator=(const qExpr& rhs) {
        delete left; delete right;
        type = rhs.type;
        left = (rhs.left != 0 ? rhs.left->dup() : 0);
        right = (rhs.right != 0 ? rhs.right->dup() : 0);
        return *this;
    }

private:
    TYPE   type;        // the type of node, logical operator, type of leaf
    qExpr* left;        // the left child
    qExpr* right;       // the right child

    // adjust the tree to favor the sequential evaluation order
    void adjust();
}; // ibis::qExpr

class ibis::qRange : public ibis::qExpr {
public:
    virtual const char* colName() const = 0;
    virtual bool inRange(double val) const = 0;

    virtual void restrictRange(double left, double right) = 0;
    virtual const double& leftBound() const = 0;
    virtual const double& rightBound() const = 0;
    virtual bool empty() const = 0;

    virtual ~qRange() {}; // nothing to do

protected:
    // reduce the scope of the constructor
    qRange() : qExpr(RANGE) {};
    qRange(TYPE t) : qExpr(t) {};

private:
    qRange(const qRange&) {}; // no copy constructor allowed, must use dup
    const qRange& operator=(const qRange&);
}; // ibis::qRange

class ibis::qContinuousRange : public ibis::qRange {
public:
    qContinuousRange() : name(0), lower(0), upper(0), left_op(OP_UNDEFINED),
                         right_op(OP_UNDEFINED) {};
    qContinuousRange(const char* lstr, COMPARE lop, const char* prop,
                     COMPARE rop, const char* rstr);
    qContinuousRange(const char* col, COMPARE op, uint32_t val) :
        name(ibis::util::strnewdup(col)), lower(val),
        upper(DBL_MAX), left_op(op), right_op(OP_UNDEFINED) {};
    qContinuousRange(const qContinuousRange& rhs) :
        name(ibis::util::strnewdup(rhs.name)), lower(rhs.lower),
        upper(rhs.upper), left_op(rhs.left_op), right_op(rhs.right_op) {};
    qContinuousRange(double lv, COMPARE lop, const char* prop,
                     COMPARE rop, double rv)
        : name(ibis::util::strnewdup(prop)), lower(lv),
          upper(rv), left_op(lop), right_op(rop) {};
    qContinuousRange(const char* prop, COMPARE op, double val)
        : name(ibis::util::strnewdup(prop)), lower(-DBL_MAX),
          upper(val), left_op(OP_UNDEFINED), right_op(op) {
        // prefer to use the operator < and <= rather than > and >=
        if (right_op == ibis::qExpr::OP_GT) {
            right_op = ibis::qExpr::OP_UNDEFINED;
            left_op = ibis::qExpr::OP_LT;
            lower = upper;
            upper = DBL_MAX;
        }
        else if (right_op == ibis::qExpr::OP_GE) {
            right_op = ibis::qExpr::OP_UNDEFINED;
            left_op = ibis::qExpr::OP_LE;
            lower = upper;
            upper = DBL_MAX;
        }
    };

    virtual ~qContinuousRange() {delete [] name;}

    // provide read access to all private variables
    virtual const char *colName() const {return name;}
    COMPARE leftOperator() const {return left_op;}
    COMPARE rightOperator() const {return right_op;}
    virtual const double& leftBound() const {
        return (right_op != OP_EQ ? lower : upper);}
    virtual const double& rightBound() const {
        return (left_op != OP_EQ ? upper : lower);}
    // allow one to possibly change the left and right bounds, the left and
    // right operator
    double& leftBound() {return lower;}
    double& rightBound() {return upper;}
    COMPARE& leftOperator() {return left_op;}
    COMPARE& rightOperator() {return right_op;}

    // Fold the boundaries to integers.
    void foldBoundaries();
    // Fold the boundaries to unsigned integers.
    void foldUnsignedBoundaries();

    // duplicate *this
    virtual qContinuousRange* dup() const {return new qContinuousRange(*this);}
    // is val in the specified range
    inline virtual bool inRange(double val) const;
    virtual void restrictRange(double left, double right);
    virtual bool empty() const;

    // print the query expression
    virtual void print(std::ostream&) const;
    virtual void printRange(std::ostream& out) const;
    // an operator for comparing two query expressions
    inline bool operator<(const qContinuousRange& y) const;

private:
    char* name;
    double lower, upper;
    COMPARE left_op, right_op;

    const qContinuousRange& operator=(const qContinuousRange&);
    friend void ibis::qExpr::simplify(ibis::qExpr*&);
}; // ibis::qContinuousRange

class ibis::qDiscreteRange : public ibis::qRange {
public:
    qDiscreteRange() : qRange(DRANGE) {};
    qDiscreteRange(const char *col, const char *nums);
    qDiscreteRange(const char *col, const std::vector<uint32_t>& val);
    qDiscreteRange(const char *col, const std::vector<double>& val);

    qDiscreteRange(const qDiscreteRange& dr)
        : qRange(DRANGE), name(dr.name), values(dr.values) {}
    virtual ~qDiscreteRange() {}; // private variables automatically destructs

    // main access functions
    virtual const char* colName() const {return name.c_str();}
    const std::vector<double>& getValues() const {return values;}
    std::vector<double>& getValues() {return values;}

    virtual qDiscreteRange* dup() const {return new qDiscreteRange(*this);}
    inline virtual bool inRange(double val) const;
    virtual void restrictRange(double left, double right);
    virtual bool empty() const {return values.empty();}
    virtual const double& leftBound() const {return values.front();}
    virtual const double& rightBound() const {return values.back();}

    ibis::qExpr* convert() const;

    virtual void print(std::ostream& out) const;
    virtual void printRange(std::ostream& out) const;

private:
    std::string name;
    std::vector<double> values; 

    const qDiscreteRange& operator=(const qDiscreteRange&);
}; // ibis::qDiscreteRange

class ibis::qString : public ibis::qExpr {
public:
    // construct the qString from two strings
    qString() : lstr(0), rstr(0) {};
    qString(const char* ls, const char* rs);
    virtual ~qString() {delete [] rstr; delete [] lstr;}

    const char* leftString() const {return lstr;}
    const char* rightString() const {return rstr;}

    virtual qString* dup() const {return new qString(*this);}
    virtual void print(std::ostream&) const;

private:
    char* lstr;
    char* rstr;

    qString(const qString& rhs) : qExpr(STRING),
                                  lstr(ibis::util::strnewdup(rhs.lstr)),
                                  rstr(ibis::util::strnewdup(rhs.rstr)) {}
    const qString& operator=(const qString&);
}; // ibis::qString

// A data structure to hold the string-valued version of the IN expression,
// name IN ('aaa', 'bbb', ...).
class ibis::qMultiString : public ibis::qExpr {
public:
    qMultiString() : qExpr(MSTRING) {};
    qMultiString(const char *col, const char *sval);
    virtual ~qMultiString() {}; // name and values automatically destroyed

    virtual qMultiString* dup() const {return new qMultiString(*this);}
    virtual void print(std::ostream& out) const;

    const char* colName() const {return name.c_str();}
    const std::vector<std::string>& valueList() const {return values;}
    ibis::qExpr* convert() const;

private:
    std::string name;
    std::vector<std::string> values;
}; // ibis::qMultiString

class ibis::compRange : public ibis::qExpr {
public:
    // types of terms allowed in the mathematical expression
    enum TERM_TYPE {UNDEFINED, VARIABLE, NUMBER, STRING, OPERATOR,
                    STDFUNCTION1, STDFUNCTION2,
                    CUSTOMFUNCTION1, CUSTOMFUNCTION2};
    // all arithmetic operators (operador is Spainish for operator)
    enum OPERADOR {UNKNOWN=0, BITOR, BITAND,
                   PLUS, MINUS, MULTIPLY, DIVIDE, REMAINDER, NEGATE, POWER};
    // list standard 1-argument and 2-argument functions
    enum STDFUN1 {ACOS=0, ASIN, ATAN, CEIL, COS, COSH, EXP, FABS, FLOOR,
                  FREXP, LOG10, LOG, MODF, SIN, SINH, SQRT, TAN, TANH};
    enum STDFUN2 {ATAN2=0, FMOD, LDEXP, POW};

    static char* operator_name[];
    static char* stdfun1_name[];
    static char* stdfun2_name[];

    class term;
    class variable;
    class bediener;
    class barrel {
    public:
        // public member functions
        barrel() {};
        barrel(const term* const t) {recordVariable(t);}
        virtual ~barrel() {}; // member variables clean themselves

        // access functions to the names and values
        uint32_t size() const {return varmap.size();}
        const char* name(uint32_t i) const {return namelist[i];}
        const double& value(uint32_t i) const {return varvalues[i];}
        double& value(uint32_t i) {return varvalues[i];}

        void recordVariable(const term* const t);
        inline uint32_t recordVariable(const char* name);
        bool equivalent(const barrel& rhs) const;

    protected:
        // the data structure to store the variable names in a mathematical
        // expression
        typedef std::map< const char*, uint32_t, ibis::lessi > termMap;

        // functions used by the class variable for accessing values of the
        // variables
        friend class variable;
        double getValue(uint32_t i) const {return varvalues[i];}
        double getValue(const char* nm) const {
            termMap::const_iterator it = varmap.find(nm);
            if (it != varmap.end()) {
                uint32_t i = (*it).second;
                return varvalues[i];
            }
            else {
                return DBL_MAX;
            }
        }

        termMap varmap;
        std::vector< double > varvalues; 
        std::vector< const char* > namelist; 
    }; // class barrel

    class term : public ibis::qExpr { // abstract term class
    public:
        virtual ~term() {};

        virtual TERM_TYPE termType() const = 0;

        // Evaluate the term.
        virtual double eval() const = 0;
        // Make a duplicate copy of the term.
        virtual term* dup() const = 0;
        // Print a human readable version of the expression.
        virtual void print(std::ostream& out) const = 0;
        // Shorten the expression by evaluating the constants.  Return a
        // new pointer if the expression is changed, otherwise return the
        // pointer this.
        virtual term* reduce() {return this;};

    protected:
        term() : qExpr(MATHTERM) {}; // to be used by concrete derived classes
    }; // abstract term

    class variable : public term {
    public:
        // The constructor inserts the variable name to a list in expr and
        // record the position in private member variable (that is used
        // later to retrieve value from expr class).
        variable(const char* var)
            : name(ibis::util::strnewdup(var)), myBar(0), varind(0) {}
        variable(const variable& v)
            : name(ibis::util::strnewdup(v.name)), myBar(v.myBar),
              varind(v.varind) {}
        virtual ~variable() {delete [] name;}

        virtual TERM_TYPE termType() const {return VARIABLE;}
        virtual variable* dup() const {return new variable(*this);}
        virtual double eval() const {return myBar->getValue(varind);}
        virtual void print(std::ostream& out) const {out << name;}
        const char* variableName() const {return name;}

        void recordVariable(barrel& bar) const {
            varind = bar.recordVariable(name);
            myBar = &bar;
        }

    private:
        char* name;     // the variable name
        mutable barrel* myBar;  // the barrel containing this variable
        mutable uint32_t varind;// the token to retrieve value from myBar

        const variable& operator=(const variable&);
    }; // the variable term

    class number : public term {
    public:
        number(const char* num) : val(atof(num)) {};
        number(double v) : val(v) {};
        virtual ~number() {};

        virtual TERM_TYPE termType() const {return NUMBER;}
        virtual number* dup() const {return new number(val);}
        virtual double eval() const {return val;}
        virtual void print(std::ostream& out) const {out << val;}

        // to negate the value
        void negate() {val = -val;}
        // to invert the value
        void invert() {val = 1.0/val;}

    private:
        double val;
        friend class bediener;
        friend void ibis::qExpr::simplify(ibis::qExpr*&);
    }; // number

    class literal : public term {
    public:
        literal(const char* s) : str(ibis::util::strnewdup(s)) {};
        virtual ~literal() {delete [] str;}

        virtual TERM_TYPE termType() const {return ibis::compRange::STRING;}
        virtual literal* dup() const {return new literal(str);}
        virtual double eval() const {return 0.0;}
        virtual void print(std::ostream& out) const {out << str;}

    private:
        char* str;

        literal(const literal&);
        const literal& operator=(const literal&);
    }; // literal

    // An operator.  Bediener is German for operator.
    class bediener : public term {
    public:
        bediener(ibis::compRange::OPERADOR op) : operador(op) {};
        virtual ~bediener() {};

        virtual TERM_TYPE termType() const {return OPERATOR;}
        virtual bediener* dup() const {
            bediener *tmp = new bediener(operador);
            tmp->setRight(getRight()->dup());
            tmp->setLeft(getLeft()->dup());
            return tmp;
        }
        inline virtual double eval() const;
        virtual void print(std::ostream& out) const;
        virtual term* reduce();

    private:
        ibis::compRange::OPERADOR operador; // Spanish for operator

        void reorder(); // reorder the tree of operators
        // place the operands into the list of terms if the operator
        // matches the specified one.
        void linearize(const ibis::compRange::OPERADOR op,
                       std::vector<ibis::compRange::term*>& terms);
        // If the right operand is a constant, change operator from - to +
        // or from / to *.
        void convertConstants();
        friend void ibis::qExpr::simplify(ibis::qExpr*&);
    }; // bediener

    class stdFunction1 : public term {
    public:
        stdFunction1(const char* name);
        stdFunction1(const STDFUN1 ft) : ftype(ft) {}
        virtual ~stdFunction1() {}

        virtual stdFunction1* dup() const {
            stdFunction1 *tmp = new stdFunction1(ftype);
            tmp->setLeft(getLeft()->dup());
            return tmp;
        }
        virtual TERM_TYPE termType() const {return STDFUNCTION1;}
        inline virtual double eval() const;
        virtual void print(std::ostream& out) const;
        inline virtual term* reduce();

    private:
        STDFUN1 ftype;
    }; // stdFunction1

    class stdFunction2 : public term {
    public:
        stdFunction2(const char* name);
        stdFunction2(const STDFUN2 ft) : ftype(ft) {}
        virtual ~stdFunction2() {}

        virtual stdFunction2* dup() const {
            stdFunction2 *tmp = new stdFunction2(ftype);
            tmp->setRight(getRight()->dup());
            tmp->setLeft(getLeft()->dup());
            return tmp;
        }
        virtual TERM_TYPE termType() const {return STDFUNCTION2;}
        inline virtual double eval() const;
        virtual void print(std::ostream& out) const;
        inline virtual term* reduce();

    private:
        STDFUN2 ftype;
    }; // stdFunction2


    // construct the range from strings
    compRange() : qExpr(ibis::qExpr::COMPRANGE), expr3(0),
                  op12(ibis::qExpr::OP_UNDEFINED),
                  op23(ibis::qExpr::OP_UNDEFINED) {;}
    compRange(ibis::compRange::term* me1, COMPARE lop,
              ibis::compRange::term* me2)
        : qExpr(ibis::qExpr::COMPRANGE, me1, me2), expr3(0),
          op12(lop), op23(ibis::qExpr::OP_UNDEFINED) {;}
    compRange(ibis::compRange::term* me1, ibis::qExpr::COMPARE lop,
              ibis::compRange::term* me2, ibis::qExpr::COMPARE rop,
              ibis::compRange::term* me3)
        : qExpr(ibis::qExpr::COMPRANGE, me1, me2), expr3(me3),
          op12(lop), op23(rop) {;}
    // copy constructor -- actually copy the math expressions
    compRange(const compRange& rhs) :
        ibis::qExpr(rhs), expr3(rhs.expr3 ? rhs.expr3->dup() : 0),
        op12(rhs.op12), op23(rhs.op23) {};
    virtual ~compRange() {delete expr3;}

    // provide read access to the operators
    ibis::qExpr::COMPARE leftOperator() const {return op12;}
    ibis::qExpr::COMPARE rightOperator() const {return op23;}
    term* getTerm3() {return expr3;}
    const term* getTerm3() const {return expr3;}
    void setTerm3(term* t) {delete expr3; expr3 = t;}

    virtual qExpr* dup() const {return new compRange(*this);}
    inline bool inRange() const;
    virtual void print(std::ostream&) const;

    virtual bool isSimple() const {return isSimpleRange();}
    inline bool isSimpleRange() const;

    bool maybeStringCompare() const;

    // convert a simple expression to qContinuousRange
    ibis::qContinuousRange* simpleRange() const;

private:
    ibis::compRange::term *expr3;       // the right most expression
    ibis::qExpr::COMPARE op12;  // between qExpr::left and qExpr::right
    ibis::qExpr::COMPARE op23;  // between qExpr::right and expr3
}; // ibis::compRange

class ibis::rangeJoin : public ibis::qExpr {
public:
    rangeJoin(const char* n1, const char *n2)
        : ibis::qExpr(ibis::qExpr::JOIN), name1(n1), name2(n2), expr(0) {};
    rangeJoin(const char* n1, const char *n2, ibis::compRange::term *x) : 
        ibis::qExpr(ibis::qExpr::JOIN), name1(n1), name2(n2), expr(x) {};
    virtual ~rangeJoin() {delete expr;};

    virtual void print(std::ostream& out) const;
    virtual rangeJoin* dup() const
    {return new rangeJoin(name1.c_str(), name2.c_str(), expr->dup());};

    const char* getName1() const {return name1.c_str();}
    const char* getName2() const {return name2.c_str();}
    ibis::compRange::term* getRange() {return expr;}
    const ibis::compRange::term* getRange() const {return expr;}
    void setRange(ibis::compRange::term *t) {delete expr; expr = t;}

private:
    std::string name1;
    std::string name2;
    ibis::compRange::term *expr;

    rangeJoin(const rangeJoin&);
    const rangeJoin& operator=(const rangeJoin&);
}; // class ibis::rangeJoin

class ibis::qAnyAny : public ibis::qExpr {
public:
    qAnyAny() : qExpr(ANYANY) {};
    qAnyAny(const char *pre, const char *val);
    ~qAnyAny() {}; // all data members can delete themselves.

    const char* getPrefix() const {return prefix.c_str();}
    const std::vector<double>& getValues() const {return values;}

    // Use the compiler generated copy constructor to perform duplication.
    virtual qExpr* dup() const {return new qAnyAny(*this);}

    virtual void print(std::ostream& out) const;
    virtual void printRange(std::ostream& out) const;

private:
    std::string prefix; 
    std::vector<double> values; 
}; // class ibis::qAnyAny

// return 1 if the incoming value is in the specified range
inline bool ibis::qContinuousRange::inRange(double val) const {
    volatile bool res0 = true; 
    volatile bool res1 = true; 
    switch (left_op) {
    case OP_LT: res0 = (lower < val); break;
    case OP_LE: res0 = (lower <= val); break;
    case OP_GT: res0 = (lower > val); break;
    case OP_GE: res0 = (lower >= val); break;
    case OP_EQ: res0 = (lower == val); break;
    default: break;
    } // switch (left_op)
    switch (right_op) {
    case OP_LT: res1 = (val < upper); break;
    case OP_LE: res1 = (val <= upper); break;
    case OP_GT: res1 = (val > upper); break;
    case OP_GE: res1 = (val >= upper); break;
    case OP_EQ: res1 = (val == upper); break;
    default:    break;
    }
    return res0 && res1;
} // bool qContinuousRange::inRange(double val)

inline void ibis::qContinuousRange::foldBoundaries() {
    switch (left_op) {
    case ibis::qExpr::OP_LT:
        lower = floor(lower);
        break;
    case ibis::qExpr::OP_LE:
        lower = ceil(lower);
        break;
    case ibis::qExpr::OP_GT:
        lower = ceil(lower);
        break;
    case ibis::qExpr::OP_GE:
        lower = floor(lower);
        break;
    case ibis::qExpr::OP_EQ:
        if (lower != floor(lower))
            left_op = ibis::qExpr::OP_UNDEFINED;
        break;
    default:
        break;
    }
    switch (right_op) {
    case ibis::qExpr::OP_LT:
        upper = ceil(upper);
        break;
    case ibis::qExpr::OP_LE:
        upper = floor(upper);
        break;
    case ibis::qExpr::OP_GT:
        upper = floor(upper);
        break;
    case ibis::qExpr::OP_GE:
        upper = ceil(upper);
        break;
    case ibis::qExpr::OP_EQ:
        if (upper != floor(upper))
            right_op = ibis::qExpr::OP_UNDEFINED;
        break;
    default:
        break;
    }
} //ibis::qContinuousRange::foldBoundaries

inline void ibis::qContinuousRange::foldUnsignedBoundaries() {
    switch (left_op) {
    case ibis::qExpr::OP_LT:
        if (lower >= 0.0) {
            lower = floor(lower);
        }
        else {
            left_op = ibis::qExpr::OP_LE;
            lower = 0.0;
        }
        break;
    case ibis::qExpr::OP_LE:
        if (lower >= 0.0)
            lower = ceil(lower);
        else
            lower = 0.0;
        break;
    case ibis::qExpr::OP_GT:
        lower = ceil(lower);
        break;
    case ibis::qExpr::OP_GE:
        lower = floor(lower);
        break;
    case ibis::qExpr::OP_EQ:
        if (lower != floor(lower) || lower < 0.0)
            left_op = ibis::qExpr::OP_UNDEFINED;
        break;
    default:
        break;
    }
    switch (right_op) {
    case ibis::qExpr::OP_LT:
        upper = ceil(upper);
        break;
    case ibis::qExpr::OP_LE:
        upper = floor(upper);
        break;
    case ibis::qExpr::OP_GT:
        if (upper > 0.0) {
            upper = floor(upper);
        }
        else {
            right_op = ibis::qExpr::OP_GE;
            upper = 0.0;
        }
        break;
    case ibis::qExpr::OP_GE:
        if (upper >= 0.0)
            upper = ceil(upper);
        else
            upper = 0.0;
        break;
    case ibis::qExpr::OP_EQ:
        if (upper != floor(upper) || upper < 0.0)
            right_op = ibis::qExpr::OP_UNDEFINED;
        break;
    default:
        break;
    }
} //ibis::qContinuousRange::foldUnsignedBoundaries

// incorrect implementation !! still need to decide how to fill the values
inline bool ibis::compRange::inRange() const {
    volatile bool res = false;
    volatile double tm1 =
        static_cast<const ibis::compRange::term*>(getLeft())->eval();
    volatile double tm2 =
        static_cast<const ibis::compRange::term*>(getRight())->eval();
    switch (op12) {
    case OP_LT: res = (tm1 < tm2); break;
    case OP_LE: res = (tm1 <= tm2); break;
    case OP_GT: res = (tm1 > tm2); break;
    case OP_GE: res = (tm1 >= tm2); break;
    case OP_EQ: res = (tm1 == tm2); break;
    default:    break;
    }
    if (expr3) {
        tm1 = expr3->eval();
        switch (op23) {
        case OP_LT: res = res && (tm2 < tm1); break;
        case OP_LE: res = res && (tm2 <= tm1); break;
        case OP_GT: res = res && (tm2 > tm1); break;
        case OP_GE: res = res && (tm2 >= tm1); break;
        case OP_EQ: res = res && (tm2 == tm1); break;
        default:    break;
        }
    }
    return res;
} // bool ibis::compRange::inRange(double val)

inline bool ibis::qContinuousRange::operator<
    (const ibis::qContinuousRange& y) const {
    int cmp = strcmp(colName(), y.colName());
    if (cmp < 0)
        return true;
    else if (cmp > 0)
        return false;
    else if (left_op < y.left_op)
        return true;
    else if (left_op > y.left_op)
        return false;
    else if (right_op < y.right_op)
        return true;
    else if (right_op > y.right_op)
        return false;
    else if (lower < y.lower)
        return true;
    else if (lower > y.lower)
        return false;
    else if (upper < y.upper)
        return true;
    else
        return false;
} // bool ibis::qContinuousRange::operator<

inline bool ibis::qDiscreteRange::inRange(double val) const {
    if (values.empty()) return false;
    if (val < values[0] || val > values.back()) return false;

    uint32_t i = 0, j = values.size();
    if (j < 32) { // sequential search
        // -- because the heavy branch prediction cost, linear search is
        // more efficient for fairly large range.
        for (i = 0; i < j; ++ i)
            if (values[i] == val) return true;
    }
    else { // binary search
        uint32_t m = (i + j) / 2;
        while (i < m) {
            if (values[m] == val) return true;
            if (values[m] < val)
                i = m;
            else
                j = m;
            m = (i + j) / 2;
        }
        // upon exiting the while loop, values[i] < val and values[j] > val
        // if values[j] exist.
    }
    return false;
} // ibis::qDiscreteRange::inRange

inline uint32_t ibis::compRange::barrel::recordVariable(