utilidor.h
Go to the documentation of this file.
00001 // File: $Id$
00002 // Author: John Wu <John.Wu at ACM.org>
00003 // Copyright 2008-2012 the Regents of the University of California
00004 #ifndef IBIS_UTILIDOR_H
00005 #define IBIS_UTILIDOR_H
00006 
00019 #include <algorithm>
00020 #include "array_t.h"    // array_t
00021 
00022 namespace ibis {
00023     typedef array_t< rid_t > RIDSet;    // RIDSet
00024 
00025     namespace util {
00026 
00030         void FASTBIT_CXX_DLLSPEC sortRIDs(ibis::RIDSet&);
00032         void FASTBIT_CXX_DLLSPEC sortRIDsq(ibis::RIDSet&, uint32_t, uint32_t);
00034         void FASTBIT_CXX_DLLSPEC sortRIDsi(ibis::RIDSet&, uint32_t, uint32_t);
00036 
00038         template <typename T>
00039         void FASTBIT_CXX_DLLSPEC
00040         reorder(array_t<T> &arr, const array_t<uint32_t> &ind);
00041         void FASTBIT_CXX_DLLSPEC
00042         reorder(std::vector<std::string> &arr, const array_t<uint32_t> &ind);
00044         template <typename T>
00045         void FASTBIT_CXX_DLLSPEC
00046         reorder(array_t<T*> &arr, const array_t<uint32_t> &ind);
00050         template <typename T1, typename T2>
00051         void FASTBIT_CXX_DLLSPEC
00052         sortAll(array_t<T1>& arr1, array_t<T2>& arr2);
00053 
00055         int64_t FASTBIT_CXX_DLLSPEC
00056         sortMerge(std::vector<std::string>& valR, array_t<uint32_t>& indR,
00057                   std::vector<std::string>& valS, array_t<uint32_t>& indS);
00060         template <typename T> int64_t FASTBIT_CXX_DLLSPEC
00061         sortMerge(array_t<T>& valR, array_t<uint32_t>& indR,
00062                   array_t<T>& valS, array_t<uint32_t>& indS);
00066         template <typename T> int64_t FASTBIT_CXX_DLLSPEC
00067         sortMerge(array_t<T>& valR, array_t<uint32_t>& indR,
00068                   array_t<T>& valS, array_t<uint32_t>& indS,
00069                   double delta1, double delta2);
00070 
00073         template <typename T1, typename T2>
00074         void FASTBIT_CXX_DLLSPEC
00075         sortKeys(array_t<T1>& keys, array_t<T2>& vals);
00077         void FASTBIT_CXX_DLLSPEC
00078         sortStrings(std::vector<std::string>& keys, array_t<uint32_t>& vals);
00080         void FASTBIT_CXX_DLLSPEC
00081         sortStrings(array_t<const char*>& keys, array_t<uint32_t>& vals);
00082 
00084         template <typename T, class C>
00085         struct heap {
00087             std::vector<T*> data_;
00089             const C comp_;
00090 
00093             heap<T, C>() : data_(), comp_() {}
00094 
00096             bool empty() const {return data_.empty();}
00097 
00099             size_t size() const {return data_.size();}
00100 
00102             void reserve(size_t n) {data_.reserve(n);}
00103 
00105             T* top() const {return data_[0];}
00106 
00108             void push(T* v) {
00109                 data_.push_back(v);
00110                 std::push_heap(data_.begin(), data_.end(), comp_);
00111             }
00112 
00114             void pop() {
00115                 const size_t oldsize = data_.size();
00116                 std::pop_heap(data_.begin(), data_.end(), comp_);
00117                 data_.resize(oldsize-1);
00118             }
00119         }; // minheap
00120     } // namespace util
00121 } // namespace ibis
00122 #endif
00123 

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