00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef _PROPHET_UTIL_H_
00018 #define _PROPHET_UTIL_H_
00019
00020 #include <string>
00021 #include <algorithm>
00022 #include <vector>
00023
00024 namespace prophet
00025 {
00026
00027 #define FOUR_BYTE_ALIGN(x) (((x) % 4) != 0) ? ((x) + (4 - ((x) % 4))) : (x)
00028
00029 struct less_string : public std::less<std::string>
00030 {
00031 bool operator() (const std::string& a, const std::string& b) const
00032 {
00033 return (a.compare(b) < 0);
00034 }
00035 };
00036
00037 template<typename T,typename size_type=size_t>
00038 struct DoNothing
00039 {
00040 inline void operator()(T& t, size_type pos)
00041 {
00042 (void)t;
00043 (void)pos;
00044 }
00045 };
00046
00047 #define PARENT(_x) (((_x) - 1) >> 1)
00048 #define LEFT(_x) (((_x) << 1) + 1)
00049
00050 template <typename UnitType,
00051 typename Sequence=std::vector<UnitType>,
00052 typename Compare=std::less<typename Sequence::value_type>,
00053 typename UpdateElem=DoNothing<UnitType,typename Sequence::size_type> >
00054 class Heap
00055 {
00056 public:
00057 typedef typename Sequence::value_type value_type;
00058 typedef typename Sequence::size_type size_type;
00059 typedef typename Sequence::iterator iterator;
00060 typedef typename Sequence::const_reference const_reference;
00061
00065 Heap()
00066 {
00067 comp_ = new Compare();
00068 }
00069
00073 Heap(Compare* comp)
00074 : comp_(comp)
00075 {
00076 }
00077
00081 virtual ~Heap() { delete comp_; }
00082
00086 inline
00087 const Compare* compare() const { return comp_; }
00088
00092 inline
00093 void set_compare(Compare* comp) {
00094 delete comp_;
00095 comp_ = comp;
00096 make_heap(0);
00097 update_elements();
00098 }
00099
00103 inline
00104 static bool is_heap(const Sequence& list, Compare& comp) {
00105 size_type len = list.size();
00106 size_type parent = 0;
00107 for (size_type child = 1; child < len; child++) {
00108 if ((comp)(list[parent],list[child]))
00109 return false;
00110 if ((child & 1) == 0)
00111 parent++;
00112 }
00113 return true;
00114 }
00115
00119 inline
00120 void update_elements() {
00121 size_type pos = size();
00122 while (pos-- > 0)
00123 (upd_)(seq_[pos],pos);
00124 }
00125
00129 bool empty() const { return seq_.empty(); }
00130
00134 size_type size() const { return seq_.size(); }
00135
00139 const_reference top() const { return seq_.front(); }
00140
00144 inline
00145 void add(value_type x) {
00146
00147 seq_.push_back(x);
00148
00149 size_type pos = heap_up(size() - 1);
00150
00151 (upd_)(seq_[pos],pos);
00152 }
00153
00158 inline
00159 void remove(size_t pos) {
00160
00161 seq_[pos] = seq_[size()-1];
00162 (upd_)(seq_[pos],pos);
00163
00164 seq_.pop_back();
00165
00166 heap_down(pos);
00167 }
00168
00172 const Sequence& sequence() const { return seq_; }
00173
00174 protected:
00179 inline
00180 size_type heap_down(size_type hole) {
00181
00182 size_type top = hole;
00183 size_type left = LEFT(top);
00184 size_type right = left + 1;
00185
00186 while (left < size()) {
00187
00188 if ((*comp_)(seq_[hole],seq_[left]))
00189 top = left;
00190
00191 if (right < size() && (*comp_)(seq_[top],seq_[right]))
00192 top = right;
00193
00194
00195 if (top == hole)
00196 break;
00197
00198
00199 swap(top,hole);
00200
00201
00202 hole = top;
00203 left = LEFT(top);
00204 right = left + 1;
00205 }
00206 return top;
00207 }
00208
00213 inline
00214 size_type heap_up(size_type last) {
00215
00216 size_type parent = PARENT(last);
00217
00218 while (last > 0) {
00219
00220
00221 if (!(*comp_)(seq_[parent],seq_[last]))
00222 break;
00223
00224 swap(parent,last);
00225
00226 last = parent;
00227 parent = PARENT(last);
00228 }
00229 return last;
00230 }
00231
00236 inline
00237 void make_heap(size_type first) {
00238
00239
00240 size_type left = LEFT(first);
00241 while (left < size() - 1)
00242 left = LEFT(left);
00243
00244
00245 size_type parent = PARENT(left);
00246 while (true) {
00247 heap_down(parent);
00248 if (parent == first) break;
00249 parent--;
00250 }
00251 }
00252
00256 inline
00257 void swap(size_type a, size_type b) {
00258 std::iter_swap<iterator>(
00259 seq_.begin() + a,
00260 seq_.begin() + b);
00261 (upd_)(seq_[a],a);
00262 (upd_)(seq_[b],b);
00263 }
00264
00265 Sequence seq_;
00266 Compare* comp_;
00267 UpdateElem upd_;
00268 };
00269
00270 };
00271
00272 #endif // _PROPHET_UTIL_H_