--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/servlib/prophet/Util.h Thu Apr 21 14:57:45 2011 +0100
@@ -0,0 +1,272 @@
+/*
+ * Copyright 2007 Baylor University
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _PROPHET_UTIL_H_
+#define _PROPHET_UTIL_H_
+
+#include <string>
+#include <algorithm>
+#include <vector>
+
+namespace prophet
+{
+
+#define FOUR_BYTE_ALIGN(x) (((x) % 4) != 0) ? ((x) + (4 - ((x) % 4))) : (x)
+
+struct less_string : public std::less<std::string>
+{
+ bool operator() (const std::string& a, const std::string& b) const
+ {
+ return (a.compare(b) < 0);
+ }
+};
+
+template<typename T,typename size_type=size_t>
+struct DoNothing
+{
+ inline void operator()(T& t, size_type pos)
+ {
+ (void)t;
+ (void)pos;
+ }
+};
+
+#define PARENT(_x) (((_x) - 1) >> 1)
+#define LEFT(_x) (((_x) << 1) + 1)
+
+template <typename UnitType,
+ typename Sequence=std::vector<UnitType>,
+ typename Compare=std::less<typename Sequence::value_type>,
+ typename UpdateElem=DoNothing<UnitType,typename Sequence::size_type> >
+class Heap
+{
+public:
+ typedef typename Sequence::value_type value_type;
+ typedef typename Sequence::size_type size_type;
+ typedef typename Sequence::iterator iterator;
+ typedef typename Sequence::const_reference const_reference;
+
+ /**
+ * Default constructor
+ */
+ Heap()
+ {
+ comp_ = new Compare();
+ }
+
+ /**
+ * Heap assumes ownership of comp
+ */
+ Heap(Compare* comp)
+ : comp_(comp)
+ {
+ }
+
+ /**
+ * Destructor
+ */
+ virtual ~Heap() { delete comp_; }
+
+ /**
+ * Constant reference to current compare
+ */
+ inline
+ const Compare* compare() const { return comp_; }
+
+ /**
+ * Change to new compare and reorder heap
+ */
+ inline
+ void set_compare(Compare* comp) {
+ delete comp_;
+ comp_ = comp;
+ make_heap(0);
+ update_elements();
+ }
+
+ /**
+ * Verify heap order
+ */
+ inline
+ static bool is_heap(const Sequence& list, Compare& comp) {
+ size_type len = list.size();
+ size_type parent = 0;
+ for (size_type child = 1; child < len; child++) {
+ if ((comp)(list[parent],list[child]))
+ return false;
+ if ((child & 1) == 0)
+ parent++;
+ }
+ return true;
+ }
+
+ /**
+ * Pass over entire sequence to ensure each element's heap pointer
+ */
+ inline
+ void update_elements() {
+ size_type pos = size();
+ while (pos-- > 0)
+ (upd_)(seq_[pos],pos);
+ }
+
+ /**
+ * Return true if underlying sequence is empty
+ */
+ bool empty() const { return seq_.empty(); }
+
+ /**
+ * Return number of elements in underlying sequence
+ */
+ size_type size() const { return seq_.size(); }
+
+ /**
+ * Return read-only reference to top of heap
+ */
+ const_reference top() const { return seq_.front(); }
+
+ /**
+ * Add data to heap, return index of insertion point
+ */
+ inline
+ void add(value_type x) {
+ // first add value to end of underlying sequence
+ seq_.push_back(x);
+ // re-order sequence into heap
+ size_type pos = heap_up(size() - 1);
+ // update element with new heap position
+ (upd_)(seq_[pos],pos);
+ }
+
+ /**
+ * Remove element from heap by position, re-heap remaining
+ * elements
+ */
+ inline
+ void remove(size_t pos) {
+ // overwrite victim with last element
+ seq_[pos] = seq_[size()-1];
+ (upd_)(seq_[pos],pos);
+ // remove last element
+ seq_.pop_back();
+ // reheap everything down from pos
+ heap_down(pos);
+ }
+
+ /**
+ * Constant reference to underlying sequence
+ */
+ const Sequence& sequence() const { return seq_; }
+
+protected:
+ /**
+ * Assuming left and right subtrees are in heap order, push hole
+ * down the tree until it reaches heap order
+ */
+ inline
+ size_type heap_down(size_type hole) {
+
+ size_type top = hole;
+ size_type left = LEFT(top);
+ size_type right = left + 1;
+
+ while (left < size()) {
+
+ if ((*comp_)(seq_[hole],seq_[left]))
+ top = left;
+
+ if (right < size() && (*comp_)(seq_[top],seq_[right]))
+ top = right;
+
+ // heap order throughout, we're done
+ if (top == hole)
+ break;
+
+ // swap top and hole
+ swap(top,hole);
+
+ // reset values for next iteration
+ hole = top;
+ left = LEFT(top);
+ right = left + 1;
+ }
+ return top;
+ }
+
+ /**
+ * Assuming tree is heap order above last, bubble up last until
+ * the tree is in heap order
+ */
+ inline
+ size_type heap_up(size_type last) {
+
+ size_type parent = PARENT(last);
+
+ while (last > 0) {
+
+ // check for heap order
+ if (!(*comp_)(seq_[parent],seq_[last]))
+ break;
+
+ swap(parent,last);
+
+ last = parent;
+ parent = PARENT(last);
+ }
+ return last;
+ }
+
+ /**
+ * Begin with last node (a leaf, therefore a subtree of size 1,
+ * therefore a heap) and work upwards to build heap
+ */
+ inline
+ void make_heap(size_type first) {
+
+ // first scan down to a leaf node from first
+ size_type left = LEFT(first);
+ while (left < size() - 1)
+ left = LEFT(left);
+
+ // now work back up towards first
+ size_type parent = PARENT(left);
+ while (true) {
+ heap_down(parent);
+ if (parent == first) break;
+ parent--;
+ }
+ }
+
+ /**
+ * Swap function used by heap_up, heap_down
+ */
+ inline
+ void swap(size_type a, size_type b) {
+ std::iter_swap<iterator>(
+ seq_.begin() + a,
+ seq_.begin() + b);
+ (upd_)(seq_[a],a);
+ (upd_)(seq_[b],b);
+ }
+
+ Sequence seq_;
+ Compare* comp_;
+ UpdateElem upd_;
+}; //template<> class Heap
+
+}; //namespace prophet
+
+#endif // _PROPHET_UTIL_H_