FastBit: ibin.h Source File (ibis1.1.5)

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         size_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     using ibis::index::evaluate;
00045     using ibis::index::estimate;
00046     using ibis::index::estimateCost;
00047     virtual long evaluate(const ibis::qContinuousRange& expr,
00048                           ibis::bitvector& hits) const;
00049     virtual long evaluate(const ibis::qDiscreteRange& expr,
00050                           ibis::bitvector& hits) const {
00051         return ibis::index::evaluate(expr, hits);
00052     }
00053 
00054     virtual void estimate(const ibis::qContinuousRange& expr,
00055                           ibis::bitvector& lower,
00056                           ibis::bitvector& upper) const;
00057     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00058     virtual float undecidable(const ibis::qContinuousRange& expr,
00059                               ibis::bitvector& iffy) const;
00060 
00062     virtual void estimate(const ibis::rangeJoin& expr,
00063                           ibis::bitvector64& lower,
00064                           ibis::bitvector64& upper) const;
00065     virtual void estimate(const ibis::rangeJoin& expr,
00066                           const ibis::bitvector& mask,
00067                           ibis::bitvector64& lower,
00068                           ibis::bitvector64& upper) const;
00069     virtual void estimate(const ibis::rangeJoin& expr,
00070                           const ibis::bitvector& mask,
00071                           const ibis::qRange* const range1,
00072                           const ibis::qRange* const range2,
00073                           ibis::bitvector64& lower,
00074                           ibis::bitvector64& upper) const;
00075     virtual int64_t estimate(const ibis::rangeJoin& expr,
00076                              const ibis::bitvector& mask,
00077                              const ibis::qRange* const range1,
00078                              const ibis::qRange* const range2) const;
00079 
00081     virtual void estimate(const ibis::bin& idx2,
00082                           const ibis::rangeJoin& expr,
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                           ibis::bitvector64& lower,
00089                           ibis::bitvector64& upper) const;
00090     virtual void estimate(const ibis::bin& idx2,
00091                           const ibis::rangeJoin& expr,
00092                           const ibis::bitvector& mask,
00093                           const ibis::qRange* const range1,
00094                           const ibis::qRange* const range2,
00095                           ibis::bitvector64& lower,
00096                           ibis::bitvector64& upper) const;
00097     virtual int64_t estimate(const ibis::bin& idx2,
00098                              const ibis::rangeJoin& expr) const;
00099     virtual int64_t estimate(const ibis::bin& idx2,
00100                              const ibis::rangeJoin& expr,
00101                              const ibis::bitvector& mask) const;
00102     virtual int64_t estimate(const ibis::bin& idx2,
00103                              const ibis::rangeJoin& expr,
00104                              const ibis::bitvector& mask,
00105                              const ibis::qRange* const range1,
00106                              const ibis::qRange* const range2) const;
00107 
00108     virtual INDEX_TYPE type() const {return BINNING;}
00109     virtual const char* name() const {return "bin";}
00110     virtual uint32_t numBins() const {return (nobs>2?nobs-2:0);}
00111     // bin boundaries and counts of each bin
00112     virtual void binBoundaries(std::vector<double>&) const;
00113     virtual void binWeights(std::vector<uint32_t>&) const;
00114     // expand/contract the boundaries of a range condition
00115     virtual int  expandRange(ibis::qContinuousRange& rng) const;
00116     virtual int  contractRange(ibis::qContinuousRange& rng) const;
00117     virtual void speedTest(std::ostream& out) const;
00118     virtual double estimateCost(const ibis::qContinuousRange& expr) const;
00119     virtual double estimateCost(const ibis::qDiscreteRange& expr) const;
00120 
00121     virtual long getCumulativeDistribution(std::vector<double>& bds,
00122                                            std::vector<uint32_t>& cts) const;
00123     virtual long getDistribution(std::vector<double>& bbs,
00124                                  std::vector<uint32_t>& cts) const;
00125     virtual double getMin() const;
00126     virtual double getMax() const;
00127     virtual double getSum() const;
00128 
00130     int read(int fdes, size_t offset, const char *fname, const char *header);
00132     long append(const ibis::bin& tail);
00134     long append(const array_t<uint32_t>& ind);
00135     array_t<uint32_t>* indices(const ibis::bitvector& mask) const;
00138     long checkBin(const ibis::qRange& cmp, uint32_t jbin,
00139                   ibis::bitvector& res) const;
00143     long checkBin(const ibis::qRange& cmp, uint32_t jbin,
00144                   const ibis::bitvector& mask, ibis::bitvector& res) const;
00145 
00160     struct granule {
00161         double min0, max0, min1, max1;
00162         ibis::bitvector* loc0;
00163         ibis::bitvector* loc1;
00164 
00165         // the default construct, user to explicitly allocated the bitvector
00166         granule() : min0(DBL_MAX), max0(-DBL_MAX), min1(DBL_MAX),
00167                     max1(-DBL_MAX), loc0(0), loc1(0) {};
00168         ~granule() {delete loc0; delete loc1;};
00169     };
00170     // key = target value
00171     typedef std::map< double, granule* > granuleMap;
00172 
00173 protected:
00174     // member variables shared by all derived classes -- the derived classes
00175     // are allowed to interpret the actual content differently.
00176     uint32_t nobs;              
00177     array_t<double> bounds;     
00178     array_t<double> maxval;     
00179     array_t<double> minval;     
00180 
00182     bin(const ibis::column* c, const uint32_t nbits,
00183         ibis::fileManager::storage* st, size_t offset = 8);
00184 
00186     void construct(const char*);
00188     void binning(const char* f, const std::vector<double>& bd);
00189     void binning(const char* f, const array_t<double>& bd);
00192     void binning(const char* f);
00195     template <typename E>
00196     void binningT(const char* fname);
00197     template <typename E>
00198     long checkBin0(const ibis::qRange& cmp, uint32_t jbin,
00199                    ibis::bitvector& res) const;
00200     template <typename E>
00201     long checkBin1(const ibis::qRange& cmp, uint32_t jbin,
00202                    const ibis::bitvector& mask, ibis::bitvector& res) const;
00204     template <typename E>
00205     long binOrderT(const char* fname) const;
00206     long binOrder(const char* fname) const;
00207 
00209     void setBoundaries(const char* f);
00210     void setBoundaries(array_t<double>& bnds,
00211                        const ibis::bin& bin0) const;
00212     void setBoundaries(array_t<double>& bnds,
00213                        const ibis::bin& idx1,
00214                        const array_t<uint32_t> cnt1,
00215                        const array_t<uint32_t> cnt0) const;
00216     // functions to deal with in-memory arrays
00217     template <typename E>
00218     void construct(const array_t<E>& varr);
00219     template <typename E>
00220     void binning(const array_t<E>& varr);
00221     template <typename E>
00222     void binning(const array_t<E>& varr, const array_t<double>& bd);
00223     template <typename E>
00224     void setBoundaries(const array_t<E>& varr);
00225     template <typename E>
00226     void scanAndPartition(const array_t<E>&, unsigned);
00227     template <typename E>
00228     void mapGranules(const array_t<E>&, granuleMap& gmap) const;
00229     void printGranules(std::ostream& out, const granuleMap& gmap) const;
00232     void convertGranules(granuleMap& gmap);
00233 
00235     void readBinBoundaries(const char* name, uint32_t nb);
00237     void scanAndPartition(const char*, unsigned, uint32_t nbins=0);
00239     void addBounds(double lbd, double rbd, uint32_t nbins, uint32_t eqw);
00241     uint32_t parseNbins() const;
00243     unsigned parseScale() const;
00245     unsigned parsePrec() const;
00246 
00247     virtual size_t getSerialSize() const throw();
00250     void divideBitmaps(const std::vector<ibis::bitvector*>& bms,
00251                        std::vector<unsigned>& parts) const;
00252 
00254     virtual double computeSum() const;
00256     virtual void adjustLength(uint32_t nrows);
00258     virtual uint32_t locate(const double& val) const;
00260     virtual void locate(const ibis::qContinuousRange& expr,
00261                         uint32_t& cand0, uint32_t& cand1) const;
00263     virtual void locate(const ibis::qContinuousRange& expr,
00264                         uint32_t& cand0, uint32_t& cand1,
00265                         uint32_t& hit0, uint32_t& hit1) const;
00267     void swap(bin& rhs) {
00268         const ibis::column* c = col;
00269         col = rhs.col;
00270         rhs.col = c;
00271         uint32_t tmp = nobs;
00272         nobs = rhs.nobs;
00273         rhs.nobs = tmp;
00274         tmp = nrows;
00275         nrows = rhs.nrows;
00276         rhs.nrows = tmp;
00277         bounds.swap(rhs.bounds);
00278         maxval.swap(rhs.maxval);
00279         minval.swap(rhs.minval);
00280         bits.swap(rhs.bits);
00281     } // swap
00282 
00283     virtual void clear();
00284     int write32(int fptr) const;
00285     int write64(int fptr) const;
00286 
00287 private:
00288     // private member functions
00289     bin& operator=(const bin&);
00290 
00291     unsigned parseScale(const char*) const;
00292 
00293     void print(std::ostream& out, const uint32_t tot,
00294                const double& lbound, const double& rbound) const;
00295 
00297     void equiJoin(ibis::bitvector64& lower,
00298                   ibis::bitvector64& iffy) const;
00299     void equiJoin(const ibis::bin& idx2,
00300                   ibis::bitvector64& lower,
00301                   ibis::bitvector64& iffy) const;
00302     void rangeJoin(const double& delta,
00303                    ibis::bitvector64& lower,
00304                    ibis::bitvector64& iffy) const;
00305     void rangeJoin(const ibis::bin& idx2,
00306                    const double& delta,
00307                    ibis::bitvector64& lower,
00308                    ibis::bitvector64& iffy) const;
00309     void compJoin(const ibis::math::term *expr,
00310                   ibis::bitvector64& lower,
00311                   ibis::bitvector64& iffy) const;
00312     void compJoin(const ibis::bin& idx2,
00313                   const ibis::math::term *expr,
00314                   ibis::bitvector64& lower,
00315                   ibis::bitvector64& iffy) const;
00316     void equiJoin(const ibis::bitvector& mask,
00317                   ibis::bitvector64& lower,
00318                   ibis::bitvector64& iffy) const;
00319     void equiJoin(const ibis::bin& idx2,
00320                   const ibis::bitvector& mask,
00321                   ibis::bitvector64& lower,
00322                   ibis::bitvector64& iffy) const;
00323     void rangeJoin(const double& delta,
00324                    const ibis::bitvector& mask,
00325                    ibis::bitvector64& lower,
00326                    ibis::bitvector64& iffy) const;
00327     void rangeJoin(const ibis::bin& idx2,
00328                    const double& delta,
00329                    const ibis::bitvector& mask,
00330                    ibis::bitvector64& lower,
00331                    ibis::bitvector64& iffy) const;
00332     void compJoin(const ibis::math::term *expr,
00333                   const ibis::bitvector& mask,
00334                   ibis::bitvector64& lower,
00335                   ibis::bitvector64& iffy) const;
00336     void compJoin(const ibis::bin& idx2,
00337                   const ibis::math::term *expr,
00338                   const ibis::bitvector& mask,
00339                   ibis::bitvector64& lower,
00340                   ibis::bitvector64& iffy) const;
00341 
00342     void equiJoin(const ibis::bitvector& mask,
00343                   const ibis::qRange* const range1,
00344                   const ibis::qRange* const range2,
00345                   ibis::bitvector64& sure,
00346                   ibis::bitvector64& iffy) const;
00347     void rangeJoin(const double& delta,
00348                    const ibis::bitvector& mask,
00349                    const ibis::qRange* const range1,
00350                    const ibis::qRange* const range2,
00351                    ibis::bitvector64& sure,
00352                    ibis::bitvector64& iffy) const;
00353     void compJoin(const ibis::math::term *delta,
00354                   const ibis::bitvector& mask,
00355                   const ibis::qRange* const range1,
00356                   const ibis::qRange* const range2,
00357                   ibis::bitvector64& sure,
00358                   ibis::bitvector64& iffy) const;
00359 
00360     int64_t equiJoin(const ibis::bitvector& mask,
00361                      const ibis::qRange* const range1,
00362                      const ibis::qRange* const range2) const;
00363     int64_t rangeJoin(const double& delta,
00364                       const ibis::bitvector& mask,
00365                       const ibis::qRange* const range1,
00366                       const ibis::qRange* const range2) const;
00367     int64_t compJoin(const ibis::math::term *delta,
00368                      const ibis::bitvector& mask,
00369                      const ibis::qRange* const range1,
00370                      const ibis::qRange* const range2) const;
00371 
00372     void equiJoin(const ibis::bin& idx2,
00373                   const ibis::bitvector& mask,
00374                   const ibis::qRange* const range1,
00375                   const ibis::qRange* const range2,
00376                   ibis::bitvector64& sure,
00377                   ibis::bitvector64& iffy) const;
00378     void rangeJoin(const ibis::bin& idx2,
00379                    const double& delta,
00380                    const ibis::bitvector& mask,
00381                    const ibis::qRange* const range1,
00382                    const ibis::qRange* const range2,
00383                    ibis::bitvector64& sure,
00384                    ibis::bitvector64& iffy) const;
00385     void compJoin(const ibis::bin& idx2,
00386                   const ibis::math::term *delta,
00387                   const ibis::bitvector& mask,
00388                   const ibis::qRange* const range1,
00389                   const ibis::qRange* const range2,
00390                   ibis::bitvector64& sure,
00391                   ibis::bitvector64& iffy) const;
00392 
00393     int64_t equiJoin(const ibis::bin& idx2,
00394                      const ibis::bitvector& mask,
00395                      const ibis::qRange* const range1,
00396                      const ibis::qRange* const range2) const;
00397     int64_t rangeJoin(const ibis::bin& idx2,
00398                       const double& delta,
00399                       const ibis::bitvector& mask,
00400                       const ibis::qRange* const range1,
00401                       const ibis::qRange* const range2) const;
00402     int64_t compJoin(const ibis::bin& idx2,
00403                      const ibis::math::term *delta,
00404                      const ibis::bitvector& mask,
00405                      const ibis::qRange* const range1,
00406                      const ibis::qRange* const range2) const;
00407 
00408     // need these friendships to access the protected member variables
00409     friend class ibis::mesa;
00410     friend class ibis::range;
00411     friend class ibis::ambit;
00412     friend class ibis::pack;
00413     friend class ibis::pale;
00414     friend class ibis::zone;
00415     friend class ibis::mesh;
00416     friend class ibis::band;
00417 }; // ibis::bin
00418 
00422 class ibis::range : public ibis::bin {
00423 public:
00424 
00425     virtual ~range() {};
00426     range(const ibis::column* c=0, const char* f=0);
00427     range(const ibis::column* c, ibis::fileManager::storage* st,
00428           size_t offset = 8);
00429     explicit range(const ibis::bin& rhs); // convert a bin to a range
00430 
00431     virtual int read(const char* idxfile);
00432     virtual int read(ibis::fileManager::storage* st);
00433     virtual int write(const char* dt) const; // write to the named file
00434     virtual void print(std::ostream& out) const;
00435     virtual long append(const char* dt, const char* df, uint32_t nnew);
00436 
00437     virtual long evaluate(const ibis::qContinuousRange& expr,
00438                           ibis::bitvector& hits) const;
00439     virtual long evaluate(const ibis::qDiscreteRange& expr,
00440                           ibis::bitvector& hits) const {
00441         return ibis::index::evaluate(expr, hits);
00442     }
00443 
00444     using ibis::bin::estimate;
00445     using ibis::bin::estimateCost;
00446     virtual void estimate(const ibis::qContinuousRange& expr,
00447                           ibis::bitvector& lower,
00448                           ibis::bitvector& upper) const;
00449     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00450     virtual float undecidable(const ibis::qContinuousRange& expr,
00451                               ibis::bitvector& iffy) const;
00452 
00453     virtual INDEX_TYPE type() const {return RANGE;}
00454     virtual const char* name() const {return "range";}
00455     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00456     // bin boundaries and counts of each bin
00457     virtual void binBoundaries(std::vector<double>&) const;
00458     virtual void binWeights(std::vector<uint32_t>&) const;
00459     // expand/contract the boundaries of a range condition
00460     virtual int  expandRange(ibis::qContinuousRange& range) const;
00461     virtual int  contractRange(ibis::qContinuousRange& range) const;
00462     virtual double getMax() const;
00463     virtual double getSum() const;
00464 
00465     int read(int fdes, size_t offset, const char *fname, const char *);
00466     long append(const ibis::range& tail);
00467     virtual void speedTest(std::ostream& out) const;
00468 
00469 protected:
00470     // protected member variables
00471     double max1, min1; // the min and max of the bin not explicitly tracked
00472 
00473     // have to have its own locate functions because a bin is not explicitly
00474     // stored
00475     virtual uint32_t locate(const double& val) const {
00476         return ibis::bin::locate(val);
00477     }
00478     virtual void locate(const ibis::qContinuousRange& expr,
00479                         uint32_t& cand0, uint32_t& cand1) const;
00480     virtual void locate(const ibis::qContinuousRange& expr,
00481                         uint32_t& cand0, uint32_t& cand1,
00482                         uint32_t& hit0, uint32_t& hit1) const;
00483     virtual double computeSum() const;
00485     void construct(const char*);
00487     void construct(const char* f, const array_t<double>& bd);
00488     virtual size_t getSerialSize() const throw();
00489 
00490 private:
00491     // private member functions
00492     int write32(int fptr) const; // write to the given stream
00493     int write64(int fptr) const; // write to the given stream
00494     void print(std::ostream& out, const uint32_t tot, const double& lbound,
00495                const double& rbound) const;
00496 
00497     friend class ibis::pale; // pale uses ibis::range
00498 }; // ibis::range
00499 
00502 class ibis::mesa : public ibis::bin {
00503 public:
00504     virtual ~mesa() {};
00505     mesa(const ibis::column* c=0, const char* f=0);
00506     mesa(const ibis::column* c, ibis::fileManager::storage* st,
00507          size_t offset = 8);
00508     explicit mesa(const ibis::bin& rhs); // convert a bin to a mesa
00509 
00510     virtual void print(std::ostream& out) const;
00511     virtual int write(const char* dt) const; // write to the named file
00512     virtual long append(const char* dt, const char* df, uint32_t nnew);
00513 
00514     virtual long evaluate(const ibis::qContinuousRange& expr,
00515                           ibis::bitvector& hits) const;
00516     virtual long evaluate(const ibis::qDiscreteRange& expr,
00517                           ibis::bitvector& hits) const {
00518         return ibis::index::evaluate(expr, hits);
00519     }
00520 
00521     using ibis::bin::estimate;
00522     using ibis::bin::estimateCost;
00523     virtual void estimate(const ibis::qContinuousRange& expr,
00524                           ibis::bitvector& lower,
00525                           ibis::bitvector& upper) const;
00526     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00527     virtual float undecidable(const ibis::qContinuousRange& expr,
00528                               ibis::bitvector& iffy) const;
00529 
00530     virtual INDEX_TYPE type() const {return MESA;}
00531     virtual const char* name() const {return "interval";}
00532     virtual uint32_t numBins() const {return (nobs>2?nobs-2:0);}
00533     // bin boundaries and counts of each bin
00534     virtual void binBoundaries(std::vector<double>&) const;
00535     virtual void binWeights(std::vector<uint32_t>&) const;
00536     virtual double getSum() const;
00537 
00538     virtual void speedTest(std::ostream& out) const;
00539     long append(const ibis::mesa& tail);
00540 
00541 protected:
00542     virtual double computeSum() const;
00544     void construct(const char*);
00545     virtual size_t getSerialSize() const throw();
00546 
00547 private:
00548     // private member functions
00549 
00550     mesa(const mesa&);
00551     mesa& operator=(const mesa&);
00552 }; // ibis::mesa
00553 
00556 class ibis::ambit : public ibis::bin {
00557 public:
00558     virtual ~ambit() {clear();};
00559     ambit(const ibis::column* c=0, const char* f=0);
00560     ambit(const ibis::column* c, ibis::fileManager::storage* st,
00561           size_t offset = 8);
00562     explicit ambit(const ibis::bin& rhs); // convert from a ibis::bin
00563 
00564     virtual int read(const char* idxfile);
00565     virtual int read(ibis::fileManager::storage* st);
00566     virtual int write(const char* dt) const;
00567     virtual void print(std::ostream& out) const;
00568     virtual long append(const char* dt, const char* df, uint32_t nnew);
00569 
00570     virtual long evaluate(const ibis::qContinuousRange& expr,
00571                           ibis::bitvector& hits) const;
00572     virtual long evaluate(const ibis::qDiscreteRange& expr,
00573                           ibis::bitvector& hits) const {
00574         return ibis::index::evaluate(expr, hits);
00575     }
00576 
00577     using ibis::bin::estimate;
00578     using ibis::bin::estimateCost;
00579     virtual void estimate(const ibis::qContinuousRange& expr,
00580                           ibis::bitvector& lower,
00581                           ibis::bitvector& upper) const;
00582     virtual float undecidable(const ibis::qContinuousRange& expr,
00583                               ibis::bitvector& iffy) const;
00584 
00585     virtual INDEX_TYPE type() const {return AMBIT;}
00586     virtual const char* name() const {return "range-range";}
00587     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00588     // bin boundaries and counts of each bin
00589     virtual void binBoundaries(std::vector<double>&) const;
00590     virtual void binWeights(std::vector<uint32_t>&) const;
00591     virtual void adjustLength(uint32_t nrows);
00592     virtual double getSum() const;
00593 
00594     virtual void speedTest(std::ostream& out) const;
00595     long append(const ibis::ambit& tail);
00596 
00597 protected:
00598     virtual double computeSum() const;
00599     virtual void clear();
00601     void construct(const char* f, const array_t<double>& bd);
00602     virtual size_t getSerialSize() const throw();
00603 
00604 private:
00605     // min and max of range nobs (the one that is not explicitly recorded)
00606     double max1, min1;
00607     std::vector<ibis::ambit*> sub;
00608 
00609     // private member functions
00610     int write32(int fptr) const;
00611     int write64(int fptr) const;
00612     int read(int fdes, size_t offset, const char *fn, const char *header);
00613     void print(std::ostream& out, const uint32_t tot, const double& lbound,
00614                const double& rbound) const;
00615 
00616     ambit(const ambit&);
00617     ambit& operator=(const ambit&);
00618 }; // ibis::ambit
00619 
00622 class ibis::pale : public ibis::bin {
00623 public:
00624     virtual ~pale() {clear();};
00625     pale(const ibis::column* c, ibis::fileManager::storage* st,
00626          size_t offset = 8);
00627     explicit pale(const ibis::bin& rhs); // convert from a ibis::bin
00628 
00629     virtual int read(const char* idxfile);
00630     virtual int read(ibis::fileManager::storage* st);
00631     virtual int write(const char* dt) const;
00632     virtual void print(std::ostream& out) const;
00633     virtual long append(const char* dt, const char* df, uint32_t nnew);
00634 
00635     virtual long evaluate(const ibis::qContinuousRange& expr,
00636                           ibis::bitvector& hits) const;
00637     virtual long evaluate(const ibis::qDiscreteRange& expr,
00638                           ibis::bitvector& hits) const {
00639         return ibis::index::evaluate(expr, hits);
00640     }
00641 
00642     using ibis::bin::estimate;
00643     virtual void estimate(const ibis::qContinuousRange& expr,
00644                           ibis::bitvector& lower,
00645                           ibis::bitvector& upper) const;
00646     virtual float undecidable(const ibis::qContinuousRange& expr,
00647                               ibis::bitvector& iffy) const;
00648 
00649     virtual INDEX_TYPE type() const {return PALE;}
00650     virtual const char* name() const {return "equality-range";}
00651     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00652     // bin boundaries and counts of each bin
00653     virtual void binBoundaries(std::vector<double>&) const;
00654     virtual void binWeights(std::vector<uint32_t>&) const;
00655     virtual void adjustLength(uint32_t nrows);
00656 
00657     virtual void speedTest(std::ostream& out) const;
00658     long append(const ibis::pale& tail);
00659 
00660 protected:
00661     virtual void clear();
00662     virtual size_t getSerialSize() const throw();
00663 
00664 private:
00665     // private member variables
00666     std::vector<ibis::range*> sub;
00667 
00668     // private member functions
00669     int write32(int fptr) const;
00670     int write64(int fptr) const;
00671 
00672     pale(const pale&);
00673     pale& operator=(const pale&);
00674 }; // ibis::pale
00675 
00678 class ibis::pack : public ibis::bin {
00679 public:
00680     virtual ~pack() {clear();};
00681     pack(const ibis::column* c, ibis::fileManager::storage* st,
00682           size_t offset = 8);
00683     explicit pack(const ibis::bin& rhs); // convert from a ibis::bin
00684 
00685     virtual int read(const char* idxfile);
00686     virtual int read(ibis::fileManager::storage* st);
00687     virtual int write(const char* dt) const;
00688     virtual void print(std::ostream& out) const;
00689     virtual long append(const char* dt, const char* df, uint32_t nnew);
00690 
00691     virtual long evaluate(const ibis::qContinuousRange& expr,
00692                           ibis::bitvector& hits) const;
00693     virtual long evaluate(const ibis::qDiscreteRange& expr,
00694                           ibis::bitvector& hits) const {
00695         return ibis::index::evaluate(expr, hits);
00696     }
00697 
00698     using ibis::bin::estimate;
00699     virtual void estimate(const ibis::qContinuousRange& expr,
00700                           ibis::bitvector& lower,
00701                           ibis::bitvector& upper) const;
00702     virtual float undecidable(const ibis::qContinuousRange& expr,
00703                               ibis::bitvector& iffy) const;
00704 
00705     virtual INDEX_TYPE type() const {return PACK;}
00706     virtual const char* name() const {return "range-equality";}
00707     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00708     // bin boundaries and counts of each bin
00709     virtual void binBoundaries(std::vector<double>&) const;
00710     virtual void binWeights(std::vector<uint32_t>&) const;
00711     virtual void adjustLength(uint32_t nrows);
00712     virtual double getSum() const;
00713 
00714     virtual void speedTest(std::ostream& out) const;
00715     long append(const ibis::pack& tail);
00716 
00717 protected:
00718     virtual double computeSum() const;
00719     virtual void clear();
00720     virtual size_t getSerialSize() const throw();
00721 
00722 private:
00723     // private member variables
00724     // min and max of range nobs (the one that is not explicitly recorded)
00725     double max1, min1;
00726     std::vector<ibis::bin*> sub;
00727 
00728     // private member functions
00729     int write32(int fptr) const;
00730     int write64(int fptr) const;
00731 
00732     pack(const pack&);
00733     pack& operator=(const pack&);
00734 }; // ibis::pack
00735 
00738 class ibis::zone : public ibis::bin {
00739 public:
00740     virtual ~zone() {clear();};
00741     zone(const ibis::column* c, ibis::fileManager::storage* st,
00742          size_t offset = 8);
00743     explicit zone(const ibis::bin& rhs); // convert from a ibis::bin
00744 
00745     virtual int read(const char* idxfile);
00746     virtual int read(ibis::fileManager::storage* st);
00747     virtual int write(const char* dt) const;
00748     virtual void print(std::ostream& out) const;
00749     virtual long append(const char* dt, const char* df, uint32_t nnew);
00750 
00751     virtual long evaluate(const ibis::qContinuousRange& expr,
00752                           ibis::bitvector& hits) const;
00753     virtual long evaluate(const ibis::qDiscreteRange& expr,
00754                           ibis::bitvector& hits) const {
00755         return ibis::index::evaluate(expr, hits);
00756     }
00757 
00758     using ibis::bin::estimate;
00759     virtual void estimate(const ibis::qContinuousRange& expr,
00760                           ibis::bitvector& lower,
00761                           ibis::bitvector& upper) const;
00762     virtual float undecidable(const ibis::qContinuousRange& expr,
00763                               ibis::bitvector& iffy) const;
00764 
00765     virtual INDEX_TYPE type() const {return ZONE;}
00766     virtual const char* name() const {return "equality-equality";}
00767     virtual uint32_t numBins() const {return (nobs>1?nobs-1:0);}
00768     // bin boundaries and counts of each bin
00769     virtual void binBoundaries(std::vector<double>&) const;
00770     virtual void binWeights(std::vector<uint32_t>&) const;
00771     virtual void adjustLength(uint32_t nrows);
00772 
00773     virtual void speedTest(std::ostream& out) const;
00774     long append(const ibis::zone& tail);
00775 
00776 protected:
00777     virtual void clear();
00778     virtual size_t getSerialSize() const throw();
00779 
00780 private:
00781     // private member variable
00782     std::vector<ibis::bin*> sub;
00783 
00784     // private member functions
00785     int write32(int fptr) const;
00786     int write64(int fptr) const;
00787 
00788     zone(const zone&);
00789     zone& operator=(const zone&);
00790 }; // ibis::zone
00791 
00797 class ibis::fuge : public ibis::bin {
00798 public:
00799     virtual ~fuge() {clear();};
00800     fuge(const ibis::column* c, ibis::fileManager::storage* st,
00801          size_t offset = 8);
00802     fuge(const ibis::column*, const char*);
00803     explicit fuge(const ibis::bin& rhs); // convert from a ibis::bin
00804 
00805     virtual int read(const char* idxfile);
00806     virtual int read(ibis::fileManager::storage* st);
00807     virtual void print(std::ostream& out) const;
00808     virtual int write(const char* dt) const;
00809     virtual long append(const char* dt, const char* df, uint32_t nnew);
00810 
00811     virtual long evaluate(const ibis::qContinuousRange& expr,
00812                           ibis::bitvector& hits) const;
00813     virtual long evaluate(const ibis::qDiscreteRange& expr,
00814                           ibis::bitvector& hits) const {
00815         return ibis::index::evaluate(expr, hits);
00816     }
00817 
00818     using ibis::bin::estimate;
00819     virtual void estimate(const ibis::qContinuousRange& expr,
00820                           ibis::bitvector& lower,
00821                           ibis::bitvector& upper) const;
00822 
00823     virtual INDEX_TYPE type() const {return FUGE;}
00824     virtual const char* name() const {return "interval-equality";}
00825     virtual void adjustLength(uint32_t nrows);
00826 
00827     long append(const ibis::fuge& tail);
00828 
00829 protected:
00830     virtual void clear() {clearCoarse(); ibis::bin::clear();}
00831     virtual size_t getSerialSize() const throw();
00832 
00833 private:
00834     // private member variable
00835     mutable std::vector<ibis::bitvector*> cbits;
00836     array_t<uint32_t> cbounds;
00837     mutable array_t<int32_t> coffset32;
00838     mutable array_t<int64_t> coffset64;
00839 
00840     void coarsen(); // given fine level, add coarse level
00841     void activateCoarse() const; // activate all coarse level bitmaps
00842     void activateCoarse(uint32_t i) const; // activate one bitmap
00843     void activateCoarse(uint32_t i, uint32_t j) const;
00844 
00845     int writeCoarse32(int fdes) const;
00846     int writeCoarse64(int fdes) const;
00847     int readCoarse(const char *fn);
00848     void clearCoarse();
00849 
00851     long coarseEstimate(uint32_t lo, uint32_t hi) const;
00853     long coarseEvaluate(uint32_t lo, uint32_t hi, ibis::bitvector& res) const;
00854 
00855     fuge(const fuge&);
00856     fuge& operator=(const fuge&);
00857 }; // ibis::fuge
00858 
00862 class ibis::egale : public ibis::bin {
00863 public:
00864     virtual ~egale() {clear();};
00865     egale(const ibis::column* c = 0, const char* f = 0,
00866           const uint32_t nbase = 2);
00867     egale(const ibis::column* c, ibis::fileManager::storage* st,
00868           size_t offset = 8);
00869     egale(const ibis::bin& rhs, const uint32_t nbase = 2);
00870 
00871     virtual int read(const char* idxfile);
00872     virtual int read(ibis::fileManager::storage* st);
00873     virtual int write(const char* dt) const;
00874     virtual void print(std::ostream& out) const;
00875     virtual long append(const char* dt, const char* df, uint32_t nnew);
00876 
00877     virtual long evaluate(const ibis::qContinuousRange& expr,
00878                           ibis::bitvector& hits) const;
00879     virtual long evaluate(const ibis::qDiscreteRange& expr,
00880                           ibis::bitvector& hits) const {
00881         return ibis::index::evaluate(expr, hits);
00882     }
00883 
00884     using ibis::bin::estimate;
00885     virtual void estimate(const ibis::qContinuousRange& expr,
00886                           ibis::bitvector& lower,
00887                           ibis::bitvector& upper) const;
00888     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00889     virtual float undecidable(const ibis::qContinuousRange& expr,
00890                               ibis::bitvector& iffy) const;
00891 
00892     virtual INDEX_TYPE type() const {return EGALE;}
00893     virtual const char* name() const {return "MCBin";}
00894     // bin boundaries and counts of each bin
00895     virtual void binBoundaries(std::vector<double>& b) const;
00896     virtual void binWeights(std::vector<uint32_t>& b) const;
00897     virtual double getSum() const;
00898 
00899     virtual void speedTest(std::ostream& out) const;
00900     long append(const ibis::egale& tail);
00901     long append(const array_t<uint32_t>& ind);
00902 
00903 protected:
00904     // protected member variables
00905     uint32_t nbits;             // number of bitvectors, (size of bits)
00906     uint32_t nbases;            // size of array bases
00907     array_t<uint32_t> cnts;     // number of records in each bin
00908     array_t<uint32_t> bases;    // the size of the bases used
00909 
00910     // protected member functions
00911     egale(const ibis::column* c, const char* f, const array_t<double>& bd,
00912           const array_t<uint32_t> bs);
00913     void addBits_(uint32_t ib, uint32_t ie, ibis::bitvector& res) const;
00914     virtual double computeSum() const;
00915     virtual void clear() {
00916         cnts.clear(); bases.clear();
00917         ibis::bin::clear();
00918     }
00919 
00920     int write32(int fdes) const;
00921     int write64(int fdes) const;
00922     void construct(const char* f);
00923     virtual size_t getSerialSize() const throw();
00924 
00925 private:
00926     // private member functions
00927     void setBit(const uint32_t i, const double val);
00928     void convert();
00929 
00930     void evalEQ(ibis::bitvector& res, uint32_t b) const;
00931     void evalLE(ibis::bitvector& res, uint32_t b) const;
00932     void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
00933 
00934     egale(const egale&);
00935     egale& operator=(const egale&);
00936 }; // ibis::egale
00937 
00941 class ibis::moins : public ibis::egale {
00942 public:
00943     virtual int write(const char* dt) const;
00944     virtual void print(std::ostream& out) const;
00945     virtual long append(const char* dt, const char* df, uint32_t nnew);
00946 
00947     virtual long evaluate(const ibis::qContinuousRange& expr,
00948                           ibis::bitvector& hits) const;
00949     virtual long evaluate(const ibis::qDiscreteRange& expr,
00950                           ibis::bitvector& hits) const {
00951         return ibis::index::evaluate(expr, hits);
00952     }
00953 
00954     using ibis::bin::estimate;
00955     virtual void estimate(const ibis::qContinuousRange& expr,
00956                           ibis::bitvector& lower,
00957                           ibis::bitvector& upper) const;
00958     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
00959     virtual INDEX_TYPE type() const {return MOINS;}
00960     virtual const char* name() const {return "MCBRange";}
00961 
00962     virtual ~moins() {clear();};
00963     moins(const ibis::column* c = 0, const char* f = 0,
00964           const uint32_t nbase = 2);
00965     moins(const ibis::column* c, ibis::fileManager::storage* st,
00966           size_t offset = 8);
00967     moins(const ibis::bin& rhs, const uint32_t nbase = 2);
00968 
00969     virtual void speedTest(std::ostream& out) const;
00970     virtual double getSum() const;
00971 
00972     long append(const ibis::moins& tail);
00973     long append(const array_t<uint32_t>& ind);
00974 
00975 protected:
00976     virtual double computeSum() const;
00977 
00978 private:
00979     // private member functions
00980     moins(const ibis::column* c, const char* f, const array_t<double>& bd,
00981           const array_t<uint32_t> bs);
00982     void convert();
00983 
00984     void evalEQ(ibis::bitvector& res, uint32_t b) const;
00985     void evalLE(ibis::bitvector& res, uint32_t b) const;
00986     void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
00987 
00988     moins(const moins&);
00989     moins& operator=(const moins&);
00990 }; // ibis::moins
00991 
00995 class ibis::entre : public ibis::egale {
00996 public:
00997     virtual ~entre() {clear();};
00998     entre(const ibis::column* c = 0, const char* f = 0,
00999           const uint32_t nbase = 2);
01000     entre(const ibis::column* c, ibis::fileManager::storage* st,
01001           size_t offset = 8);
01002     entre(const ibis::bin& rhs, const uint32_t nbase = 2);
01003 
01004     virtual int write(const char* dt) const;
01005     virtual void print(std::ostream& out) const;
01006     virtual long append(const char* dt, const char* df, uint32_t nnew);
01007 
01008     virtual long evaluate(const ibis::qContinuousRange& expr,
01009                           ibis::bitvector& hits) const;
01010     virtual long evaluate(const ibis::qDiscreteRange& expr,
01011                           ibis::bitvector& hits) const {
01012         return ibis::index::evaluate(expr, hits);
01013     }
01014 
01015     using ibis::bin::estimate;
01016     virtual void estimate(const ibis::qContinuousRange& expr,
01017                           ibis::bitvector& lower,
01018                           ibis::bitvector& upper) const;
01019     virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
01020     virtual INDEX_TYPE type() const {return ENTRE;}
01021     virtual const char* name() const {return "MCBInterval";}
01022 
01023     virtual void speedTest(std::ostream& out) const;
01024     virtual double getSum() const;
01025 
01026     long append(const ibis::entre& tail);
01027     long append(const array_t<uint32_t>& ind);
01028 
01029 protected:
01030     virtual double computeSum() const;
01031 
01032 private:
01033     // private member functions
01034     entre(const ibis::column* c, const char* f, const array_t<double>& bd,
01035           const array_t<uint32_t> bs);
01036     void convert();
01037 
01038     void evalEQ(ibis::bitvector& res, uint32_t b) const;
01039     void evalLE(ibis::bitvector& res, uint32_t b) const;
01040     void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
01041 
01042     entre(const entre&);
01043     entre& operator=(const entre&);
01044 }; // ibis::entre
01045 
01052 class ibis::bak : public ibis::bin {
01053 public:
01054     virtual ~bak() {clear();};
01055     bak(const ibis::column* c=0, const char* f=0);
01056     bak(const ibis::column* c, ibis::fileManager::storage* st,
01057         size_t offset = 8) : ibis::bin(c, st, offset) {};
01058 
01059     virtual void print(std::ostream& out) const;
01060     virtual int write(const char* dt) const; // write to the named file
01061     virtual int read(const char* idxfile);
01062     virtual long append(const char* dt, const char* df, uint32_t nnew);
01063     virtual INDEX_TYPE type() const {return BAK;}
01064     virtual const char* name() const
01065     {return "equality code on mapped values";}
01066     // bin boundaries and counts of each bin
01067     virtual void binBoundaries(std::vector<double>&) const;
01068     virtual void binWeights(std::vector<uint32_t>&) const;
01069     // expand/contract the boundaries of a range condition
01070     virtual int  expandRange(ibis::qContinuousRange& rng) const;
01071     virtual int  contractRange(ibis::qContinuousRange& rng) const;
01072 
01073     long append(const ibis::bin& tail);
01074 
01075     // a simple structure to record the position of the values mapped to the
01076     // same value.  The bitvector marked the locations of the values and the
01077     // min and max record the actual minimum and maximum value encountered.
01078     struct grain {
01079         double min, max;
01080         ibis::bitvector* loc;
01081 
01082         // the default construct, user to explicitly allocated the bitvector
01083         grain() : min(DBL_MAX), max(-DBL_MAX), loc(0) {}
01084         ~grain() {delete loc;}
01085     };
01086 
01087     typedef std::map< double, grain > bakMap;
01088 
01089 
01090 protected:
01091 
01092     // reads all values and records positions in bmap
01093     void mapValues(const char* f, bakMap& bmap) const;
01094     void printMap(std::ostream& out, const bakMap& bmap) const;
01095 
01096     virtual uint32_t locate(const double& val) const;
01097     virtual void locate(const ibis::qContinuousRange& expr,
01098                         uint32_t& cand0, uint32_t& cand1) const {
01099         ibis::bin::locate(expr, cand0, cand1);
01100     }
01101     virtual void locate(const ibis::qContinuousRange& expr,
01102                         uint32_t& cand0, uint32_t& cand1,
01103                         uint32_t& hit0, uint32_t& hit1) const {
01104         ibis::bin::locate(expr, cand0, cand1, hit0, hit1);
01105     }
01106 
01107 private:
01108     // coverts the std::map structure into the structure defined in ibis::bin
01109     void construct(bakMap& bmap);
01110 
01111     bak(const bak&);
01112     const bak& operator&=(const bak&);
01113 }; // ibis::bak
01114 
01120 class ibis::bak2 : public ibis::bin {
01121 public:
01122     virtual ~bak2() {clear();};
01123     bak2(const ibis::column* c=0, const char* f=0);
01124     bak2(const ibis::column* c, ibis::fileManager::storage* st,
01125          size_t offset = 8) : ibis::bin(c, st, offset) {};
01126 
01127     virtual void print(std::ostream& out) const;
01128     virtual int write(const char* dt) const; // write to the named file
01129     virtual int read(const char* idxfile);
01130     virtual long append(const char* dt, const char* df, uint32_t nnew);
01131     virtual INDEX_TYPE type() const {return BAK;}
01132     virtual const char* name() const
01133     {return "equality code on mapped values";}
01134     // bin boundaries and counts of each bin
01135     virtual void binBoundaries(std::vector<double>&) const;
01136     virtual void binWeights(std::vector<uint32_t>&) const;
01137     // expand/contract the boundaries of a range condition
01138     virtual int  expandRange(ibis::qContinuousRange& rng) const;
01139     virtual int  contractRange(ibis::qContinuousRange& rng) const;
01140 
01141     long append(const ibis::bin& tail);
01142 
01147     struct grain {
01148         double minm, maxm, minp, maxp;
01149         ibis::bitvector* locm; 
01150         ibis::bitvector* loce; 
01151         ibis::bitvector* locp; 
01152 
01153         // the default construct, user to explicitly allocated the bitvector
01154         grain() : minm(DBL_MAX), maxm(-DBL_MAX), minp(DBL_MAX), maxp(-DBL_MAX),
01155                   locm(0), loce(0), locp(0) {}
01156         ~grain() {delete locm; delete loce; delete locp;}
01157     };
01158 
01159     typedef std::map< double, grain > bakMap;
01160 
01161 
01162 protected:
01163 
01165     void mapValues(const char* f, bakMap& bmap) const;
01166     void printMap(std::ostream& out, const bakMap& bmap) const;
01167 
01168     virtual uint32_t locate(const double& val) const;
01169     virtual void locate(const ibis::qContinuousRange& expr,
01170                         uint32_t& cand0, uint32_t& cand1) const {
01171         ibis::bin::locate(expr, cand0, cand1);
01172     }
01173     virtual void locate(const ibis::qContinuousRange& expr,
01174                         uint32_t& cand0, uint32_t& cand1,
01175                         uint32_t& hit0, uint32_t& hit1) const {
01176         ibis::bin::locate(expr, cand0, cand1, hit0, hit1);
01177     }
01178 
01179 private:
01182     void construct(bakMap& bmap);
01183 
01184     bak2(const bak2&);
01185     bak2& operator=(const bak2&);
01186 }; // ibis::bak2
01187 
01188 #endif // IBIS_IBIN_H


	Contact us Disclaimers FastBit source code FastBit mailing list archive