FastBit: ibin.h Source File

00001 //File: $Id$
00002 // Author: John Wu <John.Wu at ACM.org>
00003 //         Lawrence Berkeley National Laboratory
00004 // Copyright 2000-2009 the Regents of the University of California
00005 #ifndef IBIS_IBIN_H
00006 #define IBIS_IBIN_H
00013 #include "index.h"
00014 #if defined(_WIN32) && defined(_MSC_VER)
00015 #pragma warning(disable:4786)   // some identifier longer than 256 characters
00016 #undef min
00017 #undef max
00018 #endif
00019 
00027 class ibis::bin : public ibis::index {
00028 public:
00029 
00030     virtual ~bin() {clear();};
00031     bin(const ibis::bin& rhs);
00032     bin(const ibis::column* c=0, const char* f=0);
00033     bin(const ibis::column* c, ibis::fileManager::storage* st,
00034         uint32_t offset = 8);
00035     bin(const ibis::column* c, const char* f, const array_t<double>& bd);
00036     bin(const ibis::column* c, const char* f, const std::vector<double>& bd);
00037 
00038     virtual void print(std::ostream& out) const;
00039     virtual int write(const char* dt) const; // write to the named file
00040     virtual int read(const char* idxfile);
00041     virtual int read(ibis::fileManager::storage* st);
00042     virtual long append(const char* dt, const char* df, uint32_t nnew);
00043 
00044     virtual long evaluate(const ibis::qContinuousRange& expr,
00045                           ibis::bitvector& hits) const;
00046 //     virtual long evaluate(const ibis::qDiscreteRange& expr,
00047 //                        ibis::bitvector& hits) const;
00048 
00049     virtual void estimate(const ibis::qContinuousRange& expr,
00050                           ibis::bitvector& lower,
00051                           ibis::bitvector& upper) const;
00052     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00053     virtual float undecidable(const ibis::qContinuousRange& expr,
00054                               ibis::bitvector& iffy) const;
00055 
00057     virtual void estimate(const ibis::rangeJoin& expr,
00058                           ibis::bitvector64& lower,
00059                           ibis::bitvector64& upper) const;
00060     virtual void estimate(const ibis::rangeJoin& expr,
00061                           const ibis::bitvector& mask,
00062                           ibis::bitvector64& lower,
00063                           ibis::bitvector64& upper) const;
00064     virtual void estimate(const ibis::rangeJoin& expr,
00065                           const ibis::bitvector& mask,
00066                           const ibis::qRange* const range1,
00067                           const ibis::qRange* const range2,
00068                           ibis::bitvector64& lower,
00069                           ibis::bitvector64& upper) const;
00070     virtual int64_t estimate(const ibis::rangeJoin& expr,
00071                              const ibis::bitvector& mask,
00072                              const ibis::qRange* const range1,
00073                              const ibis::qRange* const range2) const;
00074 
00076     virtual void estimate(const ibis::bin& idx2,
00077                           const ibis::rangeJoin& expr,
00078                           ibis::bitvector64& lower,
00079                           ibis::bitvector64& upper) const;
00080     virtual void estimate(const ibis::bin& idx2,
00081                           const ibis::rangeJoin& expr,
00082                           const ibis::bitvector& mask,
00083                           ibis::bitvector64& lower,
00084                           ibis::bitvector64& upper) const;
00085     virtual void estimate(const ibis::bin& idx2,
00086                           const ibis::rangeJoin& expr,
00087                           const ibis::bitvector& mask,
00088                           const ibis::qRange* const range1,
00089                           const ibis::qRange* const range2,
00090                           ibis::bitvector64& lower,
00091                           ibis::bitvector64& upper) const;
00092     virtual int64_t estimate(const ibis::bin& idx2,
00093                              const ibis::rangeJoin& expr) const;
00094     virtual int64_t estimate(const ibis::bin& idx2,
00095                              const ibis::rangeJoin& expr,
00096                              const ibis::bitvector& mask) const;
00097     virtual int64_t estimate(const ibis::bin& idx2,
00098                              const ibis::rangeJoin& expr,
00099                              const ibis::bitvector& mask,
00100                              const ibis::qRange* const range1,
00101                              const ibis::qRange* const range2) const;
00102 
00103     virtual INDEX_TYPE type() const {return BINNING;}
00104     virtual const char* name() const {return "bin";}
00105     virtual uint32_t numBins() const {return (nobs>2?nobs-2:0);}
00106     // bin boundaries and counts of each bin
00107     virtual void binBoundaries(std::vector<double>&) const;
00108     virtual void binWeights(std::vector<uint32_t>&) const;
00109     // expand/contract the boundaries of a range condition
00110     virtual int  expandRange(ibis::qContinuousRange& rng) const;
00111     virtual int  contractRange(ibis::qContinuousRange& rng) const;
00112     virtual void speedTest(std::ostream& out) const;
00113     virtual double estimateCost(const ibis::qContinuousRange& expr) const;
00114     virtual double estimateCost(const ibis::qDiscreteRange& expr) const;
00115 
00116     virtual long getCumulativeDistribution(std::vector<double>& bds,
00117                                            std::vector<uint32_t>& cts) const;
00118     virtual long getDistribution(std::vector<double>& bbs,
00119                                  std::vector<uint32_t>& cts) const;
00120     virtual double getMin() const;
00121     virtual double getMax() const;
00122     virtual double getSum() const;
00123 
00125     int read(int fdes, uint32_t offset, const char *fname);
00127     long append(const ibis::bin& tail);
00129     long append(const array_t<uint32_t>& ind);
00130     array_t<uint32_t>* indices(const ibis::bitvector& mask) const;
00133     long checkBin(const ibis::qRange& cmp, uint32_t jbin,
00134                   ibis::bitvector& res) const;
00138     long checkBin(const ibis::qRange& cmp, uint32_t jbin,
00139                   const ibis::bitvector& mask, ibis::bitvector& res) const;
00140 
00155     struct granule {
00156         double min0, max0, min1, max1;
00157         ibis::bitvector* loc0;
00158         ibis::bitvector* loc1;
00159 
00160         // the default construct, user to explicitly allocated the bitvector
00161         granule() : min0(DBL_MAX), max0(-DBL_MAX), min1(DBL_MAX),
00162                     max1(-DBL_MAX), loc0(0), loc1(0) {};
00163         ~granule() {delete loc0; delete loc1;};
00164     };
00165     // key = target value
00166     typedef std::map< double, granule* > granuleMap;
00167 
00168 protected:
00169     // member variables shared by all derived classes -- the derived classes
00170     // are allowed to interpret the actual content differently.
00171     uint32_t nobs;              
00172     array_t<double> bounds;     
00173     array_t<double> maxval;     
00174     array_t<double> minval;     
00175 
00176     // a constructor to accommodate multicomponent encodings
00177     bin(const ibis::column* c, const uint32_t nbits,
00178         ibis::fileManager::storage* st, uint32_t offset = 8);
00179 
00181     void binning(const char* f, const std::vector<double>& bd);
00182     void binning(const char* f, const array_t<double>& bd);
00185     void binning(const char* f);
00188     template <typename E>
00189     void binningT(const char* fname);
00190     template <typename E>
00191     long checkBin0(const ibis::qRange& cmp, uint32_t jbin,
00192                    ibis::bitvector& res) const;
00193     template <typename E>
00194     long checkBin1(const ibis::qRange& cmp, uint32_t jbin,
00195                    const ibis::bitvector& mask, ibis::bitvector& res) const;
00197     template <typename E>
00198     long binOrderT(const char* fname) const;
00199     long binOrder(const char* fname) const;
00200 
00202     void setBoundaries(const char* f);
00203     void setBoundaries(array_t<double>& bnds,
00204                        const ibis::bin& bin0) const;
00205     void setBoundaries(array_t<double>& bnds,
00206                        const ibis::bin& idx1,
00207                        const array_t<uint32_t> cnt1,
00208                        const array_t<uint32_t> cnt0) const;
00209     // functions to deal with in-memory arrays
00210     template <typename E>
00211     void construct(const array_t<E>& varr);
00212     template <typename E>
00213     void binning(const array_t<E>& varr);
00214     template <typename E>
00215     void binning(const array_t<E>& varr, const array_t<double>& bd);
00216     template <typename E>
00217     void setBoundaries(const array_t<E>& varr);
00218     template <typename E>
00219     void scanAndPartition(const array_t<E>&, unsigned);
00220     template <typename E>
00221     void mapGranules(const array_t<E>&, granuleMap& gmap) const;
00222     void printGranules(std::ostream& out, const granuleMap& gmap) const;
00223     // Convert the granule map into binned index.  Destroy the content of
00224     // the granuleMap.
00225     void convertGranules(granuleMap& gmap);
00226 
00227     // read a file containing a list of floating-point numbers
00228     void readBinBoundaries(const char* name, uint32_t nb);
00229     // partition the range based on the (approximate) histogram of the data
00230     void scanAndPartition(const char*, unsigned, uint32_t nbins=0);
00231     // the function used by setBoudaries() to actually generate the bounds
00232     void addBounds(double lbd, double rbd, uint32_t nbins, uint32_t eqw);
00233     // parse the index specs to determine eqw and nbins
00234     uint32_t parseNbins() const;
00235     unsigned parseScale() const;
00236     // parse the index spec to extract precision
00237     unsigned parsePrec() const;
00238 
00239     // partition the bitmaps into groups of takes about the same amount of
00240     // storage.
00241     void divideBitmaps(const std::vector<ibis::bitvector*>& bms,
00242                        std::vector<unsigned>& parts) const;
00243 
00244     // compute the sum of values from the information in the index
00245     virtual double computeSum() const;
00246     // some common functions that work on the bitvectors
00247     virtual void adjustLength(uint32_t nrows);    // fill with zeros
00248     virtual uint32_t locate(const double& val) const; // bin containing val
00249     virtual void locate(const ibis::qContinuousRange& expr,
00250                         uint32_t& cand0, uint32_t& cand1) const;
00251     virtual void locate(const ibis::qContinuousRange& expr,
00252                         uint32_t& cand0, uint32_t& cand1,
00253                         uint32_t& hit0, uint32_t& hit1) const;
00254     void swap(bin& rhs) { // swap the content of the index
00255         const ibis::column* c = col;
00256         col = rhs.col;
00257         rhs.col = c;
00258         uint32_t tmp = nobs;
00259         nobs = rhs.nobs;
00260         rhs.nobs = tmp;
00261         tmp = nrows;
00262         nrows = rhs.nrows;
00263         rhs.nrows = tmp;
00264         bounds.swap(rhs.bounds);
00265         maxval.swap(rhs.maxval);
00266         minval.swap(rhs.minval);
00267         bits.swap(rhs.bits);
00268     } // swap
00269 
00270     // free current resources, re-initialize all member variables
00271     virtual void clear();
00272     int write(int fptr) const; // write to an open file
00273 
00274 private:
00275     // private member functions
00276     const bin& operator=(const bin&);
00277 
00278     unsigned parseScale(const char*) const;
00279 
00280     void print(std::ostream& out, const uint32_t tot,
00281                const double& lbound, const double& rbound) const;
00282 
00284     void equiJoin(ibis::bitvector64& lower,
00285                   ibis::bitvector64& iffy) const;
00286     void equiJoin(const ibis::bin& idx2,
00287                   ibis::bitvector64& lower,
00288                   ibis::bitvector64& iffy) const;
00289     void rangeJoin(const double& delta,
00290                    ibis::bitvector64& lower,
00291                    ibis::bitvector64& iffy) const;
00292     void rangeJoin(const ibis::bin& idx2,
00293                    const double& delta,
00294                    ibis::bitvector64& lower,
00295                    ibis::bitvector64& iffy) const;
00296     void compJoin(const ibis::math::term *expr,
00297                   ibis::bitvector64& lower,
00298                   ibis::bitvector64& iffy) const;
00299     void compJoin(const ibis::bin& idx2,
00300                   const ibis::math::term *expr,
00301                   ibis::bitvector64& lower,
00302                   ibis::bitvector64& iffy) const;
00303     void equiJoin(const ibis::bitvector& mask,
00304                   ibis::bitvector64& lower,
00305                   ibis::bitvector64& iffy) const;
00306     void equiJoin(const ibis::bin& idx2,
00307                   const ibis::bitvector& mask,
00308                   ibis::bitvector64& lower,
00309                   ibis::bitvector64& iffy) const;
00310     void rangeJoin(const double& delta,
00311                    const ibis::bitvector& mask,
00312                    ibis::bitvector64& lower,
00313                    ibis::bitvector64& iffy) const;
00314     void rangeJoin(const ibis::bin& idx2,
00315                    const double& delta,
00316                    const ibis::bitvector& mask,
00317                    ibis::bitvector64& lower,
00318                    ibis::bitvector64& iffy) const;
00319     void compJoin(const ibis::math::term *expr,
00320                   const ibis::bitvector& mask,
00321                   ibis::bitvector64& lower,
00322                   ibis::bitvector64& iffy) const;
00323     void compJoin(const ibis::bin& idx2,
00324                   const ibis::math::term *expr,
00325                   const ibis::bitvector& mask,
00326                   ibis::bitvector64& lower,
00327                   ibis::bitvector64& iffy) const;
00328 
00329     void equiJoin(const ibis::bitvector& mask,
00330                   const ibis::qRange* const range1,
00331                   const ibis::qRange* const range2,
00332                   ibis::bitvector64& sure,
00333                   ibis::bitvector64& iffy) const;
00334     void rangeJoin(const double& delta,
00335                    const ibis::bitvector& mask,
00336                    const ibis::qRange* const range1,
00337                    const ibis::qRange* const range2,
00338                    ibis::bitvector64& sure,
00339                    ibis::bitvector64& iffy) const;
00340     void compJoin(const ibis::math::term *delta,
00341                   const ibis::bitvector& mask,
00342                   const ibis::qRange* const range1,
00343                   const ibis::qRange* const range2,
00344                   ibis::bitvector64& sure,
00345                   ibis::bitvector64& iffy) const;
00346 
00347     int64_t equiJoin(const ibis::bitvector& mask,
00348                      const ibis::qRange* const range1,
00349                      const ibis::qRange* const range2) const;
00350     int64_t rangeJoin(const double& delta,
00351                       const ibis::bitvector& mask,
00352                       const ibis::qRange* const range1,
00353                       const ibis::qRange* const range2) const;
00354     int64_t compJoin(const ibis::math::term *delta,
00355                      const ibis::bitvector& mask,
00356                      const ibis::qRange* const range1,
00357                      const ibis::qRange* const range2) const;
00358 
00359     void equiJoin(const ibis::bin& idx2,
00360                   const ibis::bitvector& mask,
00361                   const ibis::qRange* const range1,
00362                   const ibis::qRange* const range2,
00363                   ibis::bitvector64& sure,
00364                   ibis::bitvector64& iffy) const;
00365     void rangeJoin(const ibis::bin& idx2,
00366                    const double& delta,
00367                    const ibis::bitvector& mask,
00368                    const ibis::qRange* const range1,
00369                    const ibis::qRange* const range2,
00370                    ibis::bitvector64& sure,
00371                    ibis::bitvector64& iffy) const;
00372     void compJoin(const ibis::bin& idx2,
00373                   const ibis::math::term *delta,
00374                   const ibis::bitvector& mask,
00375                   const ibis::qRange* const range1,
00376                   const ibis::qRange* const range2,
00377                   ibis::bitvector64& sure,
00378                   ibis::bitvector64& iffy) const;
00379 
00380     int64_t equiJoin(const ibis::bin& idx2,
00381                      const ibis::bitvector& mask,
00382                      const ibis::qRange* const range1,
00383                      const ibis::qRange* const range2) const;
00384     int64_t rangeJoin(const ibis::bin& idx2,
00385                       const double& delta,
00386                       const ibis::bitvector& mask,
00387                       const ibis::qRange* const range1,
00388                       const ibis::qRange* const range2) const;
00389     int64_t compJoin(const ibis::bin& idx2,
00390                      const ibis::math::term *delta,
00391                      const ibis::bitvector& mask,
00392                      const ibis::qRange* const range1,
00393                      const ibis::qRange* const range2) const;
00394 
00395     // need these friendships to access the protected member variables
00396     friend class ibis::mesa;
00397     friend class ibis::range;
00398     friend class ibis::ambit;
00399     friend class ibis::pack;
00400     friend class ibis::pale;
00401     friend class ibis::zone;
00402     friend class ibis::mesh;
00403     friend class ibis::band;
00404 }; // ibis::bin
00405 
00409 class ibis::range : public ibis::bin {
00410 public:
00411 
00412     virtual ~range() {};
00413     range(const ibis::column* c=0, const char* f=0);
00414     range(const ibis::column* c, ibis::fileManager::storage* st,
00415           uint32_t offset = 8);
00416     explicit range(const ibis::bin& rhs); // convert a bin to a range
00417 
00418     virtual int read(const char* idxfile);
00419     virtual int read(ibis::fileManager::storage* st);
00420     virtual int write(const char* dt) const; // write to the named file
00421     virtual void print(std::ostream& out) const;
00422     virtual long append(const char* dt, const char* df, uint32_t nnew);
00423 
00424     virtual long evaluate(const ibis::qContinuousRange& expr,
00425                           ibis::bitvector& hits) const;
00426 
00427     virtual void estimate(const ibis::qContinuousRange& expr,
00428                           ibis::bitvector& lower,
00429                           ibis::bitvector& upper) const;
00430     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00431     virtual float undecidable(const ibis::qContinuousRange& expr,
00432                               ibis::bitvector& iffy) const;
00433 
00434     virtual INDEX_TYPE type() const {return RANGE;}
00435     virtual const char* name() const {return "range";}
00436     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00437     // bin boundaries and counts of each bin
00438     virtual void binBoundaries(std::vector<double>&) const;
00439     virtual void binWeights(std::vector<uint32_t>&) const;
00440     // expand/contract the boundaries of a range condition
00441     virtual int  expandRange(ibis::qContinuousRange& range) const;
00442     virtual int  contractRange(ibis::qContinuousRange& range) const;
00443     virtual double getMax() const;
00444     virtual double getSum() const;
00445 
00447     int read(int fdes, uint32_t offset, const char *fname);
00448     long append(const ibis::range& tail);
00449     virtual void speedTest(std::ostream& out) const;
00450 
00451 protected:
00452     // protected member variables
00453     double max1, min1; // the min and max of the bin not explicitly tracked
00454 
00455     // have to have its own locate functions because a bin is not explicitly
00456     // stored
00457     virtual uint32_t locate(const double& val) const {
00458         return ibis::bin::locate(val);
00459     }
00460     virtual void locate(const ibis::qContinuousRange& expr,
00461                         uint32_t& cand0, uint32_t& cand1) const;
00462     virtual void locate(const ibis::qContinuousRange& expr,
00463                         uint32_t& cand0, uint32_t& cand1,
00464                         uint32_t& hit0, uint32_t& hit1) const;
00465     virtual double computeSum() const;
00466 
00467 private:
00468     // private member functions
00469     void construct(const char* f, const array_t<double>& bd);
00470     int write(int fptr) const; // write to the given stream
00471     void print(std::ostream& out, const uint32_t tot, const double& lbound,
00472                const double& rbound) const;
00473 
00474     friend class ibis::pale; // pale uses ibis::range
00475 }; // ibis::range
00476 
00479 class ibis::mesa : public ibis::bin {
00480 public:
00481     virtual ~mesa() {};
00482     mesa(const ibis::column* c=0, const char* f=0);
00483     mesa(const ibis::column* c, ibis::fileManager::storage* st,
00484          uint32_t offset = 8);
00485     explicit mesa(const ibis::bin& rhs); // convert a bin to a mesa
00486 
00487     virtual void print(std::ostream& out) const;
00488     virtual int write(const char* dt) const; // write to the named file
00489     virtual long append(const char* dt, const char* df, uint32_t nnew);
00490 
00491     virtual long evaluate(const ibis::qContinuousRange& expr,
00492                           ibis::bitvector& hits) const;
00493 
00494     virtual void estimate(const ibis::qContinuousRange& expr,
00495                           ibis::bitvector& lower,
00496                           ibis::bitvector& upper) const;
00497     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00498     virtual float undecidable(const ibis::qContinuousRange& expr,
00499                               ibis::bitvector& iffy) const;
00500 
00501     virtual INDEX_TYPE type() const {return MESA;}
00502     virtual const char* name() const {return "interval";}
00503     virtual uint32_t numBins() const {return (nobs>2?nobs-2:0);}
00504     // bin boundaries and counts of each bin
00505     virtual void binBoundaries(std::vector<double>&) const;
00506     virtual void binWeights(std::vector<uint32_t>&) const;
00507     virtual double getSum() const;
00508 
00509     virtual void speedTest(std::ostream& out) const;
00510     long append(const ibis::mesa& tail);
00511 
00512 protected:
00513     virtual double computeSum() const;
00514 
00515 private:
00516     // private member functions
00517     int write(int fptr) const; // write to the given stream
00518     //void print(std::ostream& out, const uint32_t tot, const double& lbound,
00519     //       const double& rbound) const;
00520 
00521     mesa(const mesa&);
00522     const mesa& operator=(const mesa&);
00523 }; // ibis::mesa
00524 
00527 class ibis::ambit : public ibis::bin {
00528 public:
00529     virtual ~ambit() {clear();};
00530     ambit(const ibis::column* c=0, const char* f=0);
00531     ambit(const ibis::column* c, ibis::fileManager::storage* st,
00532           uint32_t offset = 8);
00533     explicit ambit(const ibis::bin& rhs); // convert from a ibis::bin
00534 
00535     virtual int read(const char* idxfile);
00536     virtual int read(ibis::fileManager::storage* st);
00537     virtual int write(const char* dt) const;
00538     virtual void print(std::ostream& out) const;
00539     virtual long append(const char* dt, const char* df, uint32_t nnew);
00540 
00541     virtual long evaluate(const ibis::qContinuousRange& expr,
00542                           ibis::bitvector& hits) const;
00543 
00544     virtual void estimate(const ibis::qContinuousRange& expr,
00545                           ibis::bitvector& lower,
00546                           ibis::bitvector& upper) const;
00547     virtual float undecidable(const ibis::qContinuousRange& expr,
00548                               ibis::bitvector& iffy) const;
00549 
00550     virtual INDEX_TYPE type() const {return AMBIT;}
00551     virtual const char* name() const {return "range-range";}
00552     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00553     // bin boundaries and counts of each bin
00554     virtual void binBoundaries(std::vector<double>&) const;
00555     virtual void binWeights(std::vector<uint32_t>&) const;
00556     virtual void adjustLength(uint32_t nrows);
00557     virtual double getSum() const;
00558 
00559     virtual void speedTest(std::ostream& out) const;
00560     long append(const ibis::ambit& tail);
00561 
00562 protected:
00563     virtual double computeSum() const;
00564     virtual void clear();
00565 
00566 private:
00567     // min and max of range nobs (the one that is not explicitly recorded)
00568     double max1, min1;
00569     std::vector<ibis::ambit*> sub;
00570 
00571     // private member functions
00572     int write(int fptr) const;
00573     int read(int fdes, uint32_t offset, const char *fn);
00574     void print(std::ostream& out, const uint32_t tot, const double& lbound,
00575               const double& rbound) const;
00576     void construct(const char* f, const array_t<double>& bd);
00577 
00578     ambit(const ambit&);
00579     const ambit& operator=(const ambit&);
00580 }; // ibis::ambit
00581 
00584 class ibis::pale : public ibis::bin {
00585 public:
00586     virtual ~pale() {clear();};
00587     pale(const ibis::column* c, ibis::fileManager::storage* st,
00588          uint32_t offset = 8);
00589     explicit pale(const ibis::bin& rhs); // convert from a ibis::bin
00590 
00591     virtual int read(const char* idxfile);
00592     virtual int read(ibis::fileManager::storage* st);
00593     virtual int write(const char* dt) const;
00594     virtual void print(std::ostream& out) const;
00595     virtual long append(const char* dt, const char* df, uint32_t nnew);
00596 
00597     virtual long evaluate(const ibis::qContinuousRange& expr,
00598                           ibis::bitvector& hits) const;
00599 
00600     virtual void estimate(const ibis::qContinuousRange& expr,
00601                           ibis::bitvector& lower,
00602                           ibis::bitvector& upper) const;
00603     virtual float undecidable(const ibis::qContinuousRange& expr,
00604                               ibis::bitvector& iffy) const;
00605 
00606     virtual INDEX_TYPE type() const {return PALE;}
00607     virtual const char* name() const {return "equality-range";}
00608     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00609     // bin boundaries and counts of each bin
00610     virtual void binBoundaries(std::vector<double>&) const;
00611     virtual void binWeights(std::vector<uint32_t>&) const;
00612     virtual void adjustLength(uint32_t nrows);
00613 
00614     virtual void speedTest(std::ostream& out) const;
00615     long append(const ibis::pale& tail);
00616 
00617 protected:
00618     virtual void clear();
00619 
00620 private:
00621     // private member variables
00622     std::vector<ibis::range*> sub;
00623 
00624     // private member functions
00625     int write(int fptr) const;
00626 
00627     pale(const pale&);
00628     const pale& operator=(const pale&);
00629 }; // ibis::pale
00630 
00633 class ibis::pack : public ibis::bin {
00634 public:
00635     virtual ~pack() {clear();};
00636     pack(const ibis::column* c, ibis::fileManager::storage* st,
00637           uint32_t offset = 8);
00638     explicit pack(const ibis::bin& rhs); // convert from a ibis::bin
00639 
00640     virtual int read(const char* idxfile);
00641     virtual int read(ibis::fileManager::storage* st);
00642     virtual int write(const char* dt) const;
00643     virtual void print(std::ostream& out) const;
00644     virtual long append(const char* dt, const char* df, uint32_t nnew);
00645 
00646     virtual long evaluate(const ibis::qContinuousRange& expr,
00647                           ibis::bitvector& hits) const;
00648 
00649     virtual void estimate(const ibis::qContinuousRange& expr,
00650                           ibis::bitvector& lower,
00651                           ibis::bitvector& upper) const;
00652     virtual float undecidable(const ibis::qContinuousRange& expr,
00653                               ibis::bitvector& iffy) const;
00654 
00655     virtual INDEX_TYPE type() const {return PACK;}
00656     virtual const char* name() const {return "range-equality";}
00657     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00658     // bin boundaries and counts of each bin
00659     virtual void binBoundaries(std::vector<double>&) const;
00660     virtual void binWeights(std::vector<uint32_t>&) const;
00661     virtual void adjustLength(uint32_t nrows);
00662     virtual double getSum() const;
00663 
00664     virtual void speedTest(std::ostream& out) const;
00665     long append(const ibis::pack& tail);
00666 
00667 protected:
00668     virtual double computeSum() const;
00669     virtual void clear();
00670 
00671 private:
00672     // private member variables
00673     // min and max of range nobs (the one that is not explicitly recorded)
00674     double max1, min1;
00675     std::vector<ibis::bin*> sub;
00676 
00677     // private member functions
00678     int write(int fptr) const;
00679 
00680     pack(const pack&);
00681     const pack& operator=(const pack&);
00682 }; // ibis::pack
00683 
00686 class ibis::zone : public ibis::bin {
00687 public:
00688     virtual ~zone() {clear();};
00689     zone(const ibis::column* c, ibis::fileManager::storage* st,
00690          uint32_t offset = 8);
00691     explicit zone(const ibis::bin& rhs); // convert from a ibis::bin
00692 
00693     virtual int read(const char* idxfile);
00694     virtual int read(ibis::fileManager::storage* st);
00695     virtual int write(const char* dt) const;
00696     virtual void print(std::ostream& out) const;
00697     virtual long append(const char* dt, const char* df, uint32_t nnew);
00698 
00699     virtual long evaluate(const ibis::qContinuousRange& expr,
00700                           ibis::bitvector& hits) const;
00701 
00702     virtual void estimate(const ibis::qContinuousRange& expr,
00703                           ibis::bitvector& lower,
00704                           ibis::bitvector& upper) const;
00705     virtual float undecidable(const ibis::qContinuousRange& expr,
00706                               ibis::bitvector& iffy) const;
00707 
00708     virtual INDEX_TYPE type() const {return ZONE;}
00709     virtual const char* name() const {return "equality-equality";}
00710     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00711     // bin boundaries and counts of each bin
00712     virtual void binBoundaries(std::vector<double>&) const;
00713     virtual void binWeights(std::vector<uint32_t>&) const;
00714     virtual void adjustLength(uint32_t nrows);
00715 
00716     virtual void speedTest(std::ostream& out) const;
00717     long append(const ibis::zone& tail);
00718 
00719 protected:
00720     virtual void clear();
00721 
00722 private:
00723     // private member variable
00724     std::vector<ibis::bin*> sub;
00725 
00726     // private member functions
00727     int write(int fptr) const;
00728 
00729     zone(const zone&);
00730     const zone& operator=(const zone&);
00731 }; // ibis::zone
00732 
00738 class ibis::fuge : public ibis::bin {
00739 public:
00740     virtual ~fuge() {clear();};
00741     fuge(const ibis::column* c, ibis::fileManager::storage* st,
00742          uint32_t offset = 8);
00743     fuge(const ibis::column*, const char*);
00744     explicit fuge(const ibis::bin& rhs); // convert from a ibis::bin
00745 
00746     virtual int read(const char* idxfile);
00747     virtual int read(ibis::fileManager::storage* st);
00748     virtual void print(std::ostream& out) const;
00749     virtual int write(const char* dt) const;
00750     virtual long append(const char* dt, const char* df, uint32_t nnew);
00751 
00752     virtual long evaluate(const ibis::qContinuousRange& expr,
00753                           ibis::bitvector& hits) const;
00754 
00755     virtual void estimate(const ibis::qContinuousRange& expr,
00756                           ibis::bitvector& lower,
00757                           ibis::bitvector& upper) const;
00758 
00759     virtual INDEX_TYPE type() const {return FUGE;}
00760     virtual const char* name() const {return "interval-equality";}
00761     virtual void adjustLength(uint32_t nrows);
00762 
00763     long append(const ibis::fuge& tail);
00764 
00765 protected:
00766     virtual void clear() {clearCoarse(); ibis::bin::clear();}
00767 
00768 private:
00769     // private member variable
00770     mutable std::vector<ibis::bitvector*> cbits;
00771     array_t<uint32_t> cbounds;
00772     array_t<int32_t> coffsets;
00773 
00774     void coarsen(); // given fine level, add coarse level
00775     void activateCoarse() const; // activate all coarse level bitmaps
00776     void activateCoarse(uint32_t i) const; // activate one bitmap
00777     void activateCoarse(uint32_t i, uint32_t j) const;
00778 
00779     int writeCoarse(int fdes) const;
00780     int readCoarse(const char *fn);
00781     void clearCoarse();
00782 
00784     long coarseEstimate(uint32_t lo, uint32_t hi) const;
00786     long coarseEvaluate(uint32_t lo, uint32_t hi, ibis::bitvector& res) const;
00787 
00788     fuge(const fuge&);
00789     const fuge& operator=(const fuge&);
00790 }; // ibis::fuge
00791 
00795 class ibis::egale : public ibis::bin {
00796 public:
00797     virtual ~egale() {clear();};
00798     egale(const ibis::column* c = 0, const char* f = 0,
00799           const uint32_t nbase = 2);
00800     egale(const ibis::column* c, ibis::fileManager::storage* st,
00801           uint32_t offset = 8);
00802     egale(const ibis::bin& rhs, const uint32_t nbase = 2);
00803 
00804     virtual int read(const char* idxfile);
00805     virtual int read(ibis::fileManager::storage* st);
00806     virtual int write(const char* dt) const;
00807     virtual void print(std::ostream& out) const;
00808     virtual long append(const char* dt, const char* df, uint32_t nnew);
00809 
00810     virtual long evaluate(const ibis::qContinuousRange& expr,
00811                           ibis::bitvector& hits) const;
00812 
00813     virtual void estimate(const ibis::qContinuousRange& expr,
00814                           ibis::bitvector& lower,
00815                           ibis::bitvector& upper) const;
00816     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00817     virtual float undecidable(const ibis::qContinuousRange& expr,
00818                               ibis::bitvector& iffy) const;
00819 
00820     virtual INDEX_TYPE type() const {return EGALE;}
00821     virtual const char* name() const {return "MCBin";}
00822     // bin boundaries and counts of each bin
00823     virtual void binBoundaries(std::vector<double>& b) const;
00824     virtual void binWeights(std::vector<uint32_t>& b) const;
00825     virtual double getSum() const;
00826 
00827     virtual void speedTest(std::ostream& out) const;
00828     long append(const ibis::egale& tail);
00829     long append(const array_t<uint32_t>& ind);
00830 
00831 protected:
00832     // protected member variables
00833     uint32_t nbits;             // number of bitvectors, (size of bits)
00834     uint32_t nbases;            // size of array bases
00835     array_t<uint32_t> cnts;     // number of records in each bin
00836     array_t<uint32_t> bases;    // the size of the bases used
00837 
00838     // protected member functions
00839     egale(const ibis::column* c, const char* f, const array_t<double>& bd,
00840           const array_t<uint32_t> bs);
00841     void addBits_(uint32_t ib, uint32_t ie, ibis::bitvector& res) const;
00842     virtual double computeSum() const;
00843     virtual void clear() {
00844         cnts.clear(); bases.clear();
00845         ibis::bin::clear();
00846     }
00847 
00848     int write(int fdes) const;
00849     void construct(const char* f);
00850 
00851 private:
00852     // private member functions
00853     void setBit(const uint32_t i, const double val);
00854     void convert();
00855 
00856     void evalEQ(ibis::bitvector& res, uint32_t b) const;
00857     void evalLE(ibis::bitvector& res, uint32_t b) const;
00858     void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
00859 
00860     egale(const egale&);
00861     const egale& operator=(const egale&);
00862 }; // ibis::egale
00863 
00867 class ibis::moins : public ibis::egale {
00868 public:
00869     virtual int write(const char* dt) const;
00870     virtual void print(std::ostream& out) const;
00871     virtual long append(const char* dt, const char* df, uint32_t nnew);
00872 
00873     virtual long evaluate(const ibis::qContinuousRange& expr,
00874                           ibis::bitvector& hits) const;
00875 
00876     virtual void estimate(const ibis::qContinuousRange& expr,
00877                           ibis::bitvector& lower,
00878                           ibis::bitvector& upper) const;
00879     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00880     virtual INDEX_TYPE type() const {return MOINS;}
00881     virtual const char* name() const {return "MCBRange";}
00882 
00883     virtual ~moins() {clear();};
00884     moins(const ibis::column* c = 0, const char* f = 0,
00885           const uint32_t nbase = 2);
00886     moins(const ibis::column* c, ibis::fileManager::storage* st,
00887           uint32_t offset = 8);
00888     moins(const ibis::bin& rhs, const uint32_t nbase = 2);
00889 
00890     virtual void speedTest(std::ostream& out) const;
00891     virtual double getSum() const;
00892 
00893     long append(const ibis::moins& tail);
00894     long append(const array_t<uint32_t>& ind);
00895 
00896 protected:
00897     virtual double computeSum() const;
00898 
00899 private:
00900     // private member functions
00901     moins(const ibis::column* c, const char* f, const array_t<double>& bd,
00902           const array_t<uint32_t> bs);
00903     void convert();
00904 
00905     void evalEQ(ibis::bitvector& res, uint32_t b) const;
00906     void evalLE(ibis::bitvector& res, uint32_t b) const;
00907     void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
00908 
00909     moins(const moins&);
00910     const moins& operator=(const moins&);
00911 }; // ibis::moins
00912 
00916 class ibis::entre : public ibis::egale {
00917 public:
00918     virtual ~entre() {clear();};
00919     entre(const ibis::column* c = 0, const char* f = 0,
00920           const uint32_t nbase = 2);
00921     entre(const ibis::column* c, ibis::fileManager::storage* st,
00922           uint32_t offset = 8);
00923     entre(const ibis::bin& rhs, const uint32_t nbase = 2);
00924 
00925     virtual int write(const char* dt) const;
00926     virtual void print(std::ostream& out) const;
00927     virtual long append(const char* dt, const char* df, uint32_t nnew);
00928 
00929     virtual long evaluate(const ibis::qContinuousRange& expr,
00930                           ibis::bitvector& hits) const;
00931 
00932     virtual void estimate(const ibis::qContinuousRange& expr,
00933                           ibis::bitvector& lower,
00934                           ibis::bitvector& upper) const;
00935     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00936     virtual INDEX_TYPE type() const {return ENTRE;}
00937     virtual const char* name() const {return "MCBInterval";}
00938 
00939     virtual void speedTest(std::ostream& out) const;
00940     virtual double getSum() const;
00941 
00942     long append(const ibis::entre& tail);
00943     long append(const array_t<uint32_t>& ind);
00944 
00945 protected:
00946     virtual double computeSum() const;
00947 
00948 private:
00949     // private member functions
00950     entre(const ibis::column* c, const char* f, const array_t<double>& bd,
00951           const array_t<uint32_t> bs);
00952     void convert();
00953 
00954     void evalEQ(ibis::bitvector& res, uint32_t b) const;
00955     void evalLE(ibis::bitvector& res, uint32_t b) const;
00956     void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
00957 
00958     entre(const entre&);
00959     const entre& operator=(const entre&);
00960 }; // ibis::entre
00961 
00968 class ibis::bak : public ibis::bin {
00969 public:
00970     virtual ~bak() {clear();};
00971     bak(const ibis::column* c=0, const char* f=0);
00972     bak(const ibis::column* c, ibis::fileManager::storage* st,
00973         uint32_t offset = 8) : ibis::bin(c, st, offset) {};
00974 
00975     virtual void print(std::ostream& out) const;
00976     virtual int write(const char* dt) const; // write to the named file
00977     virtual int read(const char* idxfile);
00978     virtual long append(const char* dt, const char* df, uint32_t nnew);
00979     virtual INDEX_TYPE type() const {return BAK;}
00980     virtual const char* name() const
00981     {return "equality code on mapped values";}
00982     // bin boundaries and counts of each bin
00983     virtual void binBoundaries(std::vector<double>&) const;
00984     virtual void binWeights(std::vector<uint32_t>&) const;
00985     // expand/contract the boundaries of a range condition
00986     virtual int  expandRange(ibis::qContinuousRange& rng) const;
00987     virtual int  contractRange(ibis::qContinuousRange& rng) const;
00988 
00989     long append(const ibis::bin& tail);
00990 
00991     // a simple structure to record the position of the values mapped to the
00992     // same value.  The bitvector marked the locations of the values and the
00993     // min and max record the actual minimum and maximum value encountered.
00994     struct grain {
00995         double min, max;
00996         ibis::bitvector* loc;
00997 
00998         // the default construct, user to explicitly allocated the bitvector
00999         grain() : min(DBL_MAX), max(-DBL_MAX), loc(0) {}
01000         ~grain() {delete loc;}
01001     };
01002 
01003     typedef std::map< double, grain > bakMap;
01004 
01005 
01006 protected:
01007 
01008     // reads all values and records positions in bmap
01009     void mapValues(const char* f, bakMap& bmap) const;
01010     void printMap(std::ostream& out, const bakMap& bmap) const;
01011 
01012     virtual uint32_t locate(const double& val) const;
01013     virtual void locate(const ibis::qContinuousRange& expr,
01014                         uint32_t& cand0, uint32_t& cand1) const {
01015         ibis::bin::locate(expr, cand0, cand1);
01016     }
01017     virtual void locate(const ibis::qContinuousRange& expr,
01018                         uint32_t& cand0, uint32_t& cand1,
01019                         uint32_t& hit0, uint32_t& hit1) const {
01020         ibis::bin::locate(expr, cand0, cand1, hit0, hit1);
01021     }
01022 
01023 private:
01024     // coverts the std::map structure into the structure defined in ibis::bin
01025     void construct(bakMap& bmap);
01026 
01027     bak(const bak&);
01028     const bak& operator&=(const bak&);
01029 }; // ibis::bak
01030 
01036 class ibis::bak2 : public ibis::bin {
01037 public:
01038     virtual ~bak2() {clear();};
01039     bak2(const ibis::column* c=0, const char* f=0);
01040     bak2(const ibis::column* c, ibis::fileManager::storage* st,
01041          uint32_t offset = 8) : ibis::bin(c, st, offset) {};
01042 
01043     virtual void print(std::ostream& out) const;
01044     virtual int write(const char* dt) const; // write to the named file
01045     virtual int read(const char* idxfile);
01046     virtual long append(const char* dt, const char* df, uint32_t nnew);
01047     virtual INDEX_TYPE type() const {return BAK;}
01048     virtual const char* name() const
01049     {return "equality code on mapped values";}
01050     // bin boundaries and counts of each bin
01051     virtual void binBoundaries(std::vector<double>&) const;
01052     virtual void binWeights(std::vector<uint32_t>&) const;
01053     // expand/contract the boundaries of a range condition
01054     virtual int  expandRange(ibis::qContinuousRange& rng) const;
01055     virtual int  contractRange(ibis::qContinuousRange& rng) const;
01056 
01057     long append(const ibis::bin& tail);
01058 
01063     struct grain {
01064         double min0, max0, min1, max1;
01065         ibis::bitvector* loc0;
01066         ibis::bitvector* loc1;
01067 
01068         // the default construct, user to explicitly allocated the bitvector
01069         grain() : min0(DBL_MAX), max0(-DBL_MAX), min1(DBL_MAX), max1(-DBL_MAX),
01070                   loc0(0), loc1(0) {}
01071         ~grain() {delete loc0; delete loc1;}
01072     };
01073 
01074     typedef std::map< double, grain > bakMap;
01075 
01076 
01077 protected:
01078 
01080     void mapValues(const char* f, bakMap& bmap) const;
01081     void printMap(std::ostream& out, const bakMap& bmap) const;
01082 
01083     virtual uint32_t locate(const double& val) const;
01084     virtual void locate(const ibis::qContinuousRange& expr,
01085                         uint32_t& cand0, uint32_t& cand1) const {
01086         ibis::bin::locate(expr, cand0, cand1);
01087     }
01088     virtual void locate(const ibis::qContinuousRange& expr,
01089                         uint32_t& cand0, uint32_t& cand1,
01090                         uint32_t& hit0, uint32_t& hit1) const {
01091         ibis::bin::locate(expr, cand0, cand1, hit0, hit1);
01092     }
01093 
01094 private:
01097     void construct(bakMap& bmap);
01098 
01099     bak2(const bak2&);
01100     const bak2& operator=(const bak2&);
01101 }; // ibis::bak2
01102 
01103 #endif // IBIS_IBIN_H