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
![]() |