ibin.h

Go to the documentation of this file.

//File: $Id$
// Author: John Wu <John.Wu at ACM.org>
//         Lawrence Berkeley National Laboratory
// Copyright 2000-2012 the Regents of the University of California
#ifndef IBIS_IBIN_H
#define IBIS_IBIN_H






#include "index.h"
#if defined(_WIN32) && defined(_MSC_VER)
#pragma warning(disable:4786)   // some identifier longer than 256 characters
#undef min
#undef max
#endif

class ibis::bin : public ibis::index {
public:

    virtual ~bin() {clear();};
    bin(const ibis::bin& rhs);
    bin(const ibis::column* c=0, const char* f=0);
    bin(const ibis::column* c, ibis::fileManager::storage* st,
        size_t offset = 8);
    bin(const ibis::column* c, const char* f, const array_t<double>& bd);
    bin(const ibis::column* c, const char* f, const std::vector<double>& bd);

    virtual void print(std::ostream& out) const;
    virtual int write(const char* dt) const; // write to the named file
    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    using ibis::index::evaluate;
    using ibis::index::estimate;
    using ibis::index::estimateCost;
    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    virtual long select(const ibis::qContinuousRange&, void*) const;
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const;

    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    using ibis::index::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual void estimate(const ibis::deprecatedJoin& expr,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    virtual void estimate(const ibis::deprecatedJoin& expr,
                          const ibis::bitvector& mask,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    virtual void estimate(const ibis::deprecatedJoin& expr,
                          const ibis::bitvector& mask,
                          const ibis::qRange* const range1,
                          const ibis::qRange* const range2,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    virtual int64_t estimate(const ibis::deprecatedJoin& expr,
                             const ibis::bitvector& mask,
                             const ibis::qRange* const range1,
                             const ibis::qRange* const range2) const;

    virtual void estimate(const ibis::bin& idx2,
                          const ibis::deprecatedJoin& expr,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    virtual void estimate(const ibis::bin& idx2,
                          const ibis::deprecatedJoin& expr,
                          const ibis::bitvector& mask,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    virtual void estimate(const ibis::bin& idx2,
                          const ibis::deprecatedJoin& expr,
                          const ibis::bitvector& mask,
                          const ibis::qRange* const range1,
                          const ibis::qRange* const range2,
                          ibis::bitvector64& lower,
                          ibis::bitvector64& upper) const;
    virtual int64_t estimate(const ibis::bin& idx2,
                             const ibis::deprecatedJoin& expr) const;
    virtual int64_t estimate(const ibis::bin& idx2,
                             const ibis::deprecatedJoin& expr,
                             const ibis::bitvector& mask) const;
    virtual int64_t estimate(const ibis::bin& idx2,
                             const ibis::deprecatedJoin& expr,
                             const ibis::bitvector& mask,
                             const ibis::qRange* const range1,
                             const ibis::qRange* const range2) const;

    virtual INDEX_TYPE type() const {return BINNING;}
    virtual const char* name() const {return "bin";}
    virtual uint32_t numBins() const {return (nobs>2?nobs-2:0);}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    // expand/contract the boundaries of a range condition
    virtual int  expandRange(ibis::qContinuousRange& rng) const;
    virtual int  contractRange(ibis::qContinuousRange& rng) const;
    virtual void speedTest(std::ostream& out) const;
    virtual double estimateCost(const ibis::qContinuousRange& expr) const;
    virtual double estimateCost(const ibis::qDiscreteRange& expr) const;

    virtual long getCumulativeDistribution(std::vector<double>& bds,
                                           std::vector<uint32_t>& cts) const;
    virtual long getDistribution(std::vector<double>& bbs,
                                 std::vector<uint32_t>& cts) const;
    virtual double getMin() const;
    virtual double getMax() const;
    virtual double getSum() const;

    int read(int fdes, size_t offset, const char *fname, const char *header);
    long append(const ibis::bin& tail);
    long append(const array_t<uint32_t>& ind);
    array_t<uint32_t>* indices(const ibis::bitvector& mask) const;
    long checkBin(const ibis::qRange& cmp, uint32_t jbin,
                  ibis::bitvector& res) const;
    long checkBin(const ibis::qRange& cmp, uint32_t jbin,
                  const ibis::bitvector& mask, ibis::bitvector& res) const;

    struct granule {
        double minm, maxm; // min and max of values less than the target
        double minp, maxp; // min and max of values greater than the target
        ibis::bitvector* loce; 
        ibis::bitvector* locm; 
        ibis::bitvector* locp; 

        granule() : minm(DBL_MAX), maxm(-DBL_MAX), minp(DBL_MAX),
                    maxp(-DBL_MAX), loce(0), locm(0), locp(0) {};
        ~granule() {delete loce; delete locm; delete locp;};
    private:
        granule(const granule&); // no copy constructor
        granule& operator=(const granule&); // no assignment
    };
    // key = target value
    typedef std::map< double, granule* > granuleMap;

    template <typename T>
    struct valpos {
        const T *vals;
        ibis::bitvector::indexSet ind;
        ibis::bitvector::word_t jv;
        ibis::bitvector::word_t ji;

        valpos<T>() : vals(0), jv(0), ji(0) {}
        valpos<T>(const array_t<T>& v, const bitvector& b)
        : vals(v.begin()), ind(b.firstIndexSet()), jv(0), ji(0) {
            if (ind.nIndices() > 0 && ind.isRange())
                ji = *(ind.indices());
        }

        bitvector::word_t position() const {
            if (ind.isRange())
                return ji;
            else
                return ind.indices()[ji];
        }

        T value() const {
            return vals[jv];
        }

        void next() {
            ++ jv;
            ++ ji;
            if (ind.isRange()) {
                if (ji >= ind.indices()[1]) {
                    ++ ind;
                    if (ind.nIndices() > 0 && ind.isRange())
                        ji = ind.indices()[0];
                    else
                        ji = 0;
                }
            }
            else if (ji >= ind.nIndices()) {
                ++ ind;
                if (ind.nIndices() > 0 && ind.isRange())
                    ji = ind.indices()[0];
                else
                    ji = 0;
            }
        }
    }; // valpos

    template<typename T>
    struct comparevalpos {
        bool operator()(const valpos<T>* x, const valpos<T>* y) {
            return (x->position() > y->position());
        }
    }; // comparevalpos

protected:
    // member variables shared by all derived classes -- the derived classes
    // are allowed to interpret the actual content differently.
    uint32_t nobs;              
    array_t<double> bounds;     
    array_t<double> maxval;     
    array_t<double> minval;     

    bin(const ibis::column* c, const uint32_t nbits,
        ibis::fileManager::storage* st, size_t offset = 8);

    void construct(const char*);
    void binning(const char* f, const std::vector<double>& bd);
    void binning(const char* f, const array_t<double>& bd);
    void binning(const char* f);
    template <typename E>
    void binningT(const char* fname);
    template <typename E>
    long checkBin0(const ibis::qRange& cmp, uint32_t jbin,
                   ibis::bitvector& res) const;
    template <typename E>
    long checkBin1(const ibis::qRange& cmp, uint32_t jbin,
                   const ibis::bitvector& mask, ibis::bitvector& res) const;
    template <typename E>
    long binOrderT(const char* fname) const;
    long binOrder(const char* fname) const;

    void setBoundaries(const char* f);
    void setBoundaries(array_t<double>& bnds,
                       const ibis::bin& bin0) const;
    void setBoundaries(array_t<double>& bnds,
                       const ibis::bin& idx1,
                       const array_t<uint32_t> cnt1,
                       const array_t<uint32_t> cnt0) const;
    // functions to deal with in-memory arrays
    template <typename E>
    void construct(const array_t<E>& varr);
    template <typename E>
    void binning(const array_t<E>& varr);
    template <typename E>
    void binning(const array_t<E>& varr, const array_t<double>& bd);
    template <typename E>
    void setBoundaries(const array_t<E>& varr);
    template <typename E>
    void scanAndPartition(const array_t<E>&, unsigned);
    template <typename E>
    void mapGranules(const array_t<E>&, granuleMap& gmap) const;
    void printGranules(std::ostream& out, const granuleMap& gmap) const;
    void convertGranules(granuleMap& gmap);

    void readBinBoundaries(const char* name, uint32_t nb);
    void scanAndPartition(const char*, unsigned, uint32_t nbins=0);
    void addBounds(double lbd, double rbd, uint32_t nbins, uint32_t eqw);
    uint32_t parseNbins() const;
    unsigned parseScale() const;
    unsigned parsePrec() const;

    virtual size_t getSerialSize() const throw();
    void divideBitmaps(const array_t<bitvector*>& bms,
                       std::vector<unsigned>& parts) const;

    virtual double computeSum() const;
    virtual void adjustLength(uint32_t nrows);
    virtual uint32_t locate(const double& val) const;
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1) const;
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1,
                        uint32_t& hit0, uint32_t& hit1) const;
    void swap(bin& rhs) {
        const ibis::column* c = col;
        col = rhs.col;
        rhs.col = c;
        uint32_t tmp = nobs;
        nobs = rhs.nobs;
        rhs.nobs = tmp;
        tmp = nrows;
        nrows = rhs.nrows;
        rhs.nrows = tmp;
        bounds.swap(rhs.bounds);
        maxval.swap(rhs.maxval);
        minval.swap(rhs.minval);
        bits.swap(rhs.bits);
    } // swap

    virtual void clear();
    int write32(int fptr) const;
    int write64(int fptr) const;

    template <typename T> long
    mergeValues(const ibis::qContinuousRange&, ibis::array_t<T>&) const;
    template <typename T> long
    mergeValues(const ibis::qContinuousRange&, ibis::array_t<T>&,
                ibis::bitvector&) const;

private:
    // private member functions
    bin& operator=(const bin&);

    unsigned parseScale(const char*) const;

    void print(std::ostream& out, const uint32_t tot,
               const double& lbound, const double& rbound) const;

    void equiJoin(ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;
    void equiJoin(const ibis::bin& idx2,
                  ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;
    void deprecatedJoin(const double& delta,
                   ibis::bitvector64& lower,
                   ibis::bitvector64& iffy) const;
    void deprecatedJoin(const ibis::bin& idx2,
                   const double& delta,
                   ibis::bitvector64& lower,
                   ibis::bitvector64& iffy) const;
    void compJoin(const ibis::math::term *expr,
                  ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;
    void compJoin(const ibis::bin& idx2,
                  const ibis::math::term *expr,
                  ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;
    void equiJoin(const ibis::bitvector& mask,
                  ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;
    void equiJoin(const ibis::bin& idx2,
                  const ibis::bitvector& mask,
                  ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;
    void deprecatedJoin(const double& delta,
                   const ibis::bitvector& mask,
                   ibis::bitvector64& lower,
                   ibis::bitvector64& iffy) const;
    void deprecatedJoin(const ibis::bin& idx2,
                   const double& delta,
                   const ibis::bitvector& mask,
                   ibis::bitvector64& lower,
                   ibis::bitvector64& iffy) const;
    void compJoin(const ibis::math::term *expr,
                  const ibis::bitvector& mask,
                  ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;
    void compJoin(const ibis::bin& idx2,
                  const ibis::math::term *expr,
                  const ibis::bitvector& mask,
                  ibis::bitvector64& lower,
                  ibis::bitvector64& iffy) const;

    void equiJoin(const ibis::bitvector& mask,
                  const ibis::qRange* const range1,
                  const ibis::qRange* const range2,
                  ibis::bitvector64& sure,
                  ibis::bitvector64& iffy) const;
    void deprecatedJoin(const double& delta,
                   const ibis::bitvector& mask,
                   const ibis::qRange* const range1,
                   const ibis::qRange* const range2,
                   ibis::bitvector64& sure,
                   ibis::bitvector64& iffy) const;
    void compJoin(const ibis::math::term *delta,
                  const ibis::bitvector& mask,
                  const ibis::qRange* const range1,
                  const ibis::qRange* const range2,
                  ibis::bitvector64& sure,
                  ibis::bitvector64& iffy) const;

    int64_t equiJoin(const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2) const;
    int64_t deprecatedJoin(const double& delta,
                      const ibis::bitvector& mask,
                      const ibis::qRange* const range1,
                      const ibis::qRange* const range2) const;
    int64_t compJoin(const ibis::math::term *delta,
                     const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2) const;

    void equiJoin(const ibis::bin& idx2,
                  const ibis::bitvector& mask,
                  const ibis::qRange* const range1,
                  const ibis::qRange* const range2,
                  ibis::bitvector64& sure,
                  ibis::bitvector64& iffy) const;
    void deprecatedJoin(const ibis::bin& idx2,
                   const double& delta,
                   const ibis::bitvector& mask,
                   const ibis::qRange* const range1,
                   const ibis::qRange* const range2,
                   ibis::bitvector64& sure,
                   ibis::bitvector64& iffy) const;
    void compJoin(const ibis::bin& idx2,
                  const ibis::math::term *delta,
                  const ibis::bitvector& mask,
                  const ibis::qRange* const range1,
                  const ibis::qRange* const range2,
                  ibis::bitvector64& sure,
                  ibis::bitvector64& iffy) const;

    int64_t equiJoin(const ibis::bin& idx2,
                     const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2) const;
    int64_t deprecatedJoin(const ibis::bin& idx2,
                      const double& delta,
                      const ibis::bitvector& mask,
                      const ibis::qRange* const range1,
                      const ibis::qRange* const range2) const;
    int64_t compJoin(const ibis::bin& idx2,
                     const ibis::math::term *delta,
                     const ibis::bitvector& mask,
                     const ibis::qRange* const range1,
                     const ibis::qRange* const range2) const;

    // need these friendships to access the protected member variables
    friend class ibis::mesa;
    friend class ibis::range;
    friend class ibis::ambit;
    friend class ibis::pack;
    friend class ibis::pale;
    friend class ibis::zone;
    friend class ibis::mesh;
    friend class ibis::band;
}; // ibis::bin

class ibis::range : public ibis::bin {
public:

    virtual ~range() {};
    range(const ibis::column* c=0, const char* f=0);
    range(const ibis::column* c, ibis::fileManager::storage* st,
          size_t offset = 8);
    explicit range(const ibis::bin& rhs); // convert a bin to a range

    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual int write(const char* dt) const; // write to the named file
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    using ibis::bin::estimate;
    using ibis::bin::estimateCost;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    using ibis::bin::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual INDEX_TYPE type() const {return RANGE;}
    virtual const char* name() const {return "range";}
    virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    // expand/contract the boundaries of a range condition
    virtual int  expandRange(ibis::qContinuousRange& range) const;
    virtual int  contractRange(ibis::qContinuousRange& range) const;
    virtual double getMax() const;
    virtual double getSum() const;

    int read(int fdes, size_t offset, const char *fname, const char *);
    long append(const ibis::range& tail);
    virtual void speedTest(std::ostream& out) const;

protected:
    // protected member variables
    double max1, min1; // the min and max of the bin not explicitly tracked

    // have to have its own locate functions because a bin is not explicitly
    // stored
    virtual uint32_t locate(const double& val) const {
        return ibis::bin::locate(val);
    }
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1) const;
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1,
                        uint32_t& hit0, uint32_t& hit1) const;
    virtual double computeSum() const;
    void construct(const char*);
    void construct(const char* f, const array_t<double>& bd);
    virtual size_t getSerialSize() const throw();

private:
    // private member functions
    int write32(int fptr) const; // write to the given stream
    int write64(int fptr) const; // write to the given stream
    void print(std::ostream& out, const uint32_t tot, const double& lbound,
               const double& rbound) const;

    friend class ibis::pale; // pale uses ibis::range
}; // ibis::range

class ibis::mesa : public ibis::bin {
public:
    virtual ~mesa() {};
    mesa(const ibis::column* c=0, const char* f=0);
    mesa(const ibis::column* c, ibis::fileManager::storage* st,
         size_t offset = 8);
    explicit mesa(const ibis::bin& rhs); // convert a bin to a mesa

    virtual void print(std::ostream& out) const;
    virtual int write(const char* dt) const; // write to the named file
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    using ibis::bin::estimate;
    using ibis::bin::estimateCost;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    using ibis::bin::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual INDEX_TYPE type() const {return MESA;}
    virtual const char* name() const {return "interval";}
    virtual uint32_t numBins() const {return (nobs>2?nobs-2:0);}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    virtual double getSum() const;

    virtual void speedTest(std::ostream& out) const;
    long append(const ibis::mesa& tail);

protected:
    virtual double computeSum() const;
    void construct(const char*);
    virtual size_t getSerialSize() const throw();

private:
    // private member functions

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

class ibis::ambit : public ibis::bin {
public:
    virtual ~ambit() {clear();};
    ambit(const ibis::column* c=0, const char* f=0);
    ambit(const ibis::column* c, ibis::fileManager::storage* st,
          size_t offset = 8);
    explicit ambit(const ibis::bin& rhs); // convert from a ibis::bin

    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    using ibis::bin::estimate;
    using ibis::bin::estimateCost;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    using ibis::bin::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual INDEX_TYPE type() const {return AMBIT;}
    virtual const char* name() const {return "range-range";}
    virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    virtual void adjustLength(uint32_t nrows);
    virtual double getSum() const;

    virtual void speedTest(std::ostream& out) const;
    long append(const ibis::ambit& tail);

protected:
    virtual double computeSum() const;
    virtual void clear();
    void construct(const char* f, const array_t<double>& bd);
    virtual size_t getSerialSize() const throw();

private:
    // min and max of range nobs (the one that is not explicitly recorded)
    double max1, min1;
    std::vector<ibis::ambit*> sub;

    // private member functions
    int write32(int fptr) const;
    int write64(int fptr) const;
    int read(int fdes, size_t offset, const char *fn, const char *header);
    void print(std::ostream& out, const uint32_t tot, const double& lbound,
               const double& rbound) const;

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

class ibis::pale : public ibis::bin {
public:
    virtual ~pale() {clear();};
    pale(const ibis::column* c, ibis::fileManager::storage* st,
         size_t offset = 8);
    explicit pale(const ibis::bin& rhs); // convert from a ibis::bin

    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    using ibis::bin::estimate;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    using ibis::bin::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual INDEX_TYPE type() const {return PALE;}
    virtual const char* name() const {return "equality-range";}
    virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    virtual void adjustLength(uint32_t nrows);

    virtual void speedTest(std::ostream& out) const;
    long append(const ibis::pale& tail);

protected:
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    // private member variables
    std::vector<ibis::range*> sub;

    // private member functions
    int write32(int fptr) const;
    int write64(int fptr) const;

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

class ibis::pack : public ibis::bin {
public:
    virtual ~pack() {clear();};
    pack(const ibis::column* c, ibis::fileManager::storage* st,
          size_t offset = 8);
    explicit pack(const ibis::bin& rhs); // convert from a ibis::bin

    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);}

    using ibis::bin::estimate;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    using ibis::bin::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual INDEX_TYPE type() const {return PACK;}
    virtual const char* name() const {return "range-equality";}
    virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    virtual void adjustLength(uint32_t nrows);
    virtual double getSum() const;

    virtual void speedTest(std::ostream& out) const;
    long append(const ibis::pack& tail);

protected:
    virtual double computeSum() const;
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    // private member variables
    // min and max of range nobs (the one that is not explicitly recorded)
    double max1, min1;
    std::vector<ibis::bin*> sub;

    // private member functions
    int write32(int fptr) const;
    int write64(int fptr) const;

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

class ibis::zone : public ibis::bin {
public:
    virtual ~zone() {clear();};
    zone(const ibis::column* c, ibis::fileManager::storage* st,
         size_t offset = 8);
    explicit zone(const ibis::bin& rhs); // convert from a ibis::bin

    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    using ibis::bin::estimate;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    using ibis::bin::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual INDEX_TYPE type() const {return ZONE;}
    virtual const char* name() const {return "equality-equality";}
    virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    virtual void adjustLength(uint32_t nrows);

    virtual void speedTest(std::ostream& out) const;
    long append(const ibis::zone& tail);

protected:
    virtual void clear();
    virtual size_t getSerialSize() const throw();

private:
    // private member variable
    std::vector<ibis::bin*> sub;

    // private member functions
    int write32(int fptr) const;
    int write64(int fptr) const;

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

class ibis::fuge : public ibis::bin {
public:
    virtual ~fuge() {clear();};
    fuge(const ibis::column* c, ibis::fileManager::storage* st,
         size_t offset = 8);
    fuge(const ibis::column*, const char*);
    explicit fuge(const ibis::bin& rhs); // convert from a ibis::bin

    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual void print(std::ostream& out) const;
    virtual int write(const char* dt) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    using ibis::bin::estimate;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;

    virtual INDEX_TYPE type() const {return FUGE;}
    virtual const char* name() const {return "interval-equality";}
    virtual void adjustLength(uint32_t nrows);

    long append(const ibis::fuge& tail);

protected:
    virtual void clear() {clearCoarse(); ibis::bin::clear();}
    virtual size_t getSerialSize() const throw();

private:
    // private member variable
    mutable array_t<bitvector*> cbits;
    array_t<uint32_t> cbounds;
    mutable array_t<int32_t> coffset32;
    mutable array_t<int64_t> coffset64;

    void coarsen(); // given fine level, add coarse level
    void activateCoarse() const; // activate all coarse level bitmaps
    void activateCoarse(uint32_t i) const; // activate one bitmap
    void activateCoarse(uint32_t i, uint32_t j) const;

    int writeCoarse32(int fdes) const;
    int writeCoarse64(int fdes) const;
    int readCoarse(const char *fn);
    void clearCoarse();

    long coarseEstimate(uint32_t lo, uint32_t hi) const;
    long coarseEvaluate(uint32_t lo, uint32_t hi, ibis::bitvector& res) const;

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

class ibis::egale : public ibis::bin {
public:
    virtual ~egale() {clear();};
    egale(const ibis::column* c = 0, const char* f = 0,
          const uint32_t nbase = 2);
    egale(const ibis::column* c, ibis::fileManager::storage* st,
          size_t offset = 8);
    egale(const ibis::bin& rhs, const uint32_t nbase = 2);

    virtual int read(const char* idxfile);
    virtual int read(ibis::fileManager::storage* st);
    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);
    }

    using ibis::bin::estimate;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    using ibis::bin::undecidable;
    virtual float undecidable(const ibis::qContinuousRange& expr,
                              ibis::bitvector& iffy) const;

    virtual INDEX_TYPE type() const {return EGALE;}
    virtual const char* name() const {return "MCBin";}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>& b) const;
    virtual void binWeights(std::vector<uint32_t>& b) const;
    virtual double getSum() const;

    virtual void speedTest(std::ostream& out) const;
    long append(const ibis::egale& tail);
    long append(const array_t<uint32_t>& ind);

protected:
    // protected member variables
    uint32_t nbits;             // number of bitvectors, (size of bits)
    uint32_t nbases;            // size of array bases
    array_t<uint32_t> cnts;     // number of records in each bin
    array_t<uint32_t> bases;    // the size of the bases used

    // protected member functions
    egale(const ibis::column* c, const char* f, const array_t<double>& bd,
          const array_t<uint32_t> bs);
    void addBits_(uint32_t ib, uint32_t ie, ibis::bitvector& res) const;
    virtual double computeSum() const;
    virtual void clear() {
        cnts.clear(); bases.clear();
        ibis::bin::clear();
    }

    int write32(int fdes) const;
    int write64(int fdes) const;
    void construct(const char* f);
    virtual size_t getSerialSize() const throw();

private:
    // private member functions
    void setBit(const uint32_t i, const double val);
    void convert();

    void evalEQ(ibis::bitvector& res, uint32_t b) const;
    void evalLE(ibis::bitvector& res, uint32_t b) const;
    void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;

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

class ibis::moins : public ibis::egale {
public:
    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);}

    using ibis::egale::estimate;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual INDEX_TYPE type() const {return MOINS;}
    virtual const char* name() const {return "MCBRange";}

    virtual ~moins() {clear();};
    moins(const ibis::column* c = 0, const char* f = 0,
          const uint32_t nbase = 2);
    moins(const ibis::column* c, ibis::fileManager::storage* st,
          size_t offset = 8);
    moins(const ibis::bin& rhs, const uint32_t nbase = 2);

    virtual void speedTest(std::ostream& out) const;
    virtual double getSum() const;

    long append(const ibis::moins& tail);
    long append(const array_t<uint32_t>& ind);

protected:
    virtual double computeSum() const;

private:
    // private member functions
    moins(const ibis::column* c, const char* f, const array_t<double>& bd,
          const array_t<uint32_t> bs);
    void convert();

    void evalEQ(ibis::bitvector& res, uint32_t b) const;
    void evalLE(ibis::bitvector& res, uint32_t b) const;
    void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;

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

class ibis::entre : public ibis::egale {
public:
    virtual ~entre() {clear();};
    entre(const ibis::column* c = 0, const char* f = 0,
          const uint32_t nbase = 2);
    entre(const ibis::column* c, ibis::fileManager::storage* st,
          size_t offset = 8);
    entre(const ibis::bin& rhs, const uint32_t nbase = 2);

    virtual int write(const char* dt) const;
    virtual void print(std::ostream& out) const;
    virtual long append(const char* dt, const char* df, uint32_t nnew);

    virtual long select(const ibis::qContinuousRange&, void*) const {
        return -1;}
    virtual long select(const ibis::qContinuousRange&, void*,
                        ibis::bitvector&) const {
        return -1;}

    virtual long evaluate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& hits) const;
    virtual long evaluate(const ibis::qDiscreteRange& expr,
                          ibis::bitvector& hits) const {
        return ibis::index::evaluate(expr, hits);}

    using ibis::egale::estimate;
    virtual void estimate(const ibis::qContinuousRange& expr,
                          ibis::bitvector& lower,
                          ibis::bitvector& upper) const;
    virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
    virtual INDEX_TYPE type() const {return ENTRE;}
    virtual const char* name() const {return "MCBInterval";}

    virtual void speedTest(std::ostream& out) const;
    virtual double getSum() const;

    long append(const ibis::entre& tail);
    long append(const array_t<uint32_t>& ind);

protected:
    virtual double computeSum() const;

private:
    // private member functions
    entre(const ibis::column* c, const char* f, const array_t<double>& bd,
          const array_t<uint32_t> bs);
    void convert();

    void evalEQ(ibis::bitvector& res, uint32_t b) const;
    void evalLE(ibis::bitvector& res, uint32_t b) const;
    void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;

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

class ibis::bak : public ibis::bin {
public:
    virtual ~bak() {clear();};
    bak(const ibis::column* c=0, const char* f=0);
    bak(const ibis::column* c, ibis::fileManager::storage* st,
        size_t offset = 8) : ibis::bin(c, st, offset) {};

    virtual void print(std::ostream& out) const;
    virtual int write(const char* dt) const; // write to the named file
    using ibis::bin::read;
    virtual int read(const char* idxfile);
    virtual long append(const char* dt, const char* df, uint32_t nnew);
    virtual INDEX_TYPE type() const {return BAK;}
    virtual const char* name() const
    {return "equality code on mapped values";}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    // expand/contract the boundaries of a range condition
    virtual int  expandRange(ibis::qContinuousRange& rng) const;
    virtual int  contractRange(ibis::qContinuousRange& rng) const;

    long append(const ibis::bin& tail);

    // a simple structure to record the position of the values mapped to the
    // same value.  The bitvector marked the locations of the values and the
    // min and max record the actual minimum and maximum value encountered.
    struct grain {
        double min, max;
        ibis::bitvector* loc;

        // the default construct, user to explicitly allocated the bitvector
        grain() : min(DBL_MAX), max(-DBL_MAX), loc(0) {}
        ~grain() {delete loc;}
    };

    typedef std::map< double, grain > bakMap;


protected:

    // reads all values and records positions in bmap
    void mapValues(const char* f, bakMap& bmap) const;
    void printMap(std::ostream& out, const bakMap& bmap) const;

    virtual uint32_t locate(const double& val) const;
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1) const {
        ibis::bin::locate(expr, cand0, cand1);
    }
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1,
                        uint32_t& hit0, uint32_t& hit1) const {
        ibis::bin::locate(expr, cand0, cand1, hit0, hit1);
    }

private:
    // coverts the std::map structure into the structure defined in ibis::bin
    void construct(bakMap& bmap);

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

class ibis::bak2 : public ibis::bin {
public:
    virtual ~bak2() {clear();};
    bak2(const ibis::column* c=0, const char* f=0);
    bak2(const ibis::column* c, ibis::fileManager::storage* st,
         size_t offset = 8) : ibis::bin(c, st, offset) {};

    virtual void print(std::ostream& out) const;
    virtual int write(const char* dt) const; // write to the named file
    using ibis::bin::read;
    virtual int read(const char* idxfile);
    virtual long append(const char* dt, const char* df, uint32_t nnew);
    virtual INDEX_TYPE type() const {return BAK;}
    virtual const char* name() const
    {return "equality code on mapped values";}
    // bin boundaries and counts of each bin
    virtual void binBoundaries(std::vector<double>&) const;
    virtual void binWeights(std::vector<uint32_t>&) const;
    // expand/contract the boundaries of a range condition
    virtual int  expandRange(ibis::qContinuousRange& rng) const;
    virtual int  contractRange(ibis::qContinuousRange& rng) const;

    long append(const ibis::bin& tail);

    struct grain {
        double minm, maxm, minp, maxp;
        ibis::bitvector* locm; 
        ibis::bitvector* loce; 
        ibis::bitvector* locp; 

        // the default construct, user to explicitly allocated the bitvector
        grain() : minm(DBL_MAX), maxm(-DBL_MAX), minp(DBL_MAX), maxp(-DBL_MAX),
                  locm(0), loce(0), locp(0) {}
        ~grain() {delete locm; delete loce; delete locp;}
    };

    typedef std::map< double, grain > bakMap;


protected:

    void mapValues(const char* f, bakMap& bmap) const;
    void printMap(std::ostream& out, const bakMap& bmap) const;

    virtual uint32_t locate(const double& val) const;
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1) const {
        ibis::bin::locate(expr, cand0, cand1);
    }
    virtual void locate(const ibis::qContinuousRange& expr,
                        uint32_t& cand0, uint32_t& cand1,
                        uint32_t& hit0, uint32_t& hit1) const {
        ibis::bin::locate(expr, cand0, cand1, hit0, hit1);
    }

private:
    void construct(bakMap& bmap);

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

#endif // IBIS_IBIN_H