Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/interval_trees/simple/simple_max.h
Go to the documentation of this file.
00001 #ifndef H_INTERVAL_TREES_SIMPLE_SIMPLE_MAX
00002 #define H_INTERVAL_TREES_SIMPLE_SIMPLE_MAX
00003 
00008 #include <vector>
00009 #include "utils/preconditions/preconditions.h"
00010 #include "interval_trees/utils/heap.h"
00011 
00012 namespace interval_trees {
00013 namespace simple {
00014 
00027 template<typename T>
00028 class SimpleMaxTree {
00029 
00033   typedef typename std::vector<T>::size_type SizeType;
00034  private:
00041     SizeType base;
00042 
00047     SizeType original_size;
00048 
00052     std::vector<T> data;
00053 
00054 
00055   public:
00056     SimpleMaxTree() {
00057       base = 0;
00058       _clear();
00059     }
00060 
00064     void _clear() {
00065       base = 0;
00066       original_size = 0;
00067       data.clear();
00068     }
00069 
00074     void initialize(SizeType size)
00075     {
00076       initialize(size, T());
00077     }
00078 
00082     void initialize(SizeType size_, const T& default_value) {
00083       _clear();
00084       Preconditions::check(size_ > 0, "size should be positive");
00085       SizeType s = heap::nextPowerOfTwo(size_);
00086       // We need twice the size of s to allocate,
00087       // check first it will fit into SizeType
00088       if (s >= std::numeric_limits<SizeType>::max() / 2) {
00089         throw std::overflow_error("Too big size");
00090       }
00091       data.resize(s * 2, default_value);
00092       // Note: these assigments should be *after* resize as
00093       // resize can throw an bad_alloc exception and in that case we
00094       // want to have size zero!
00095       base = s;
00096       original_size = size_;
00097     }
00098 
00102     T get(SizeType pos) {
00103       Preconditions::checkRange(pos, original_size);
00104       return data[pos + base];
00105     }
00106 
00110     void set(SizeType pos, T value) {
00111       Preconditions::checkRange(pos, original_size);
00112       pos += base; // leafs are indexed starting at "base"
00113       data[pos] = value;
00114 
00115       while (pos > 1) {
00116         pos = heap::parent(pos);
00117         // update this node
00118         data[pos] = std::max(data[heap::left(pos)], data[heap::right(pos)]);
00119       }
00120     }
00121 
00131     T get_max(SizeType left, SizeType right) {
00132       Preconditions::checkRange(left, original_size);
00133       // original_size <= SizeType max/2 and thus it won't overflow 
00134       Preconditions::checkRange(right, (SizeType)1, original_size + 1);
00135       Preconditions::check(left < right);
00136 
00137       // safe, right + base - 1 will fit into SizeType
00138       left += base;
00139       right += base - 1;
00140 
00141       // Note: if (at this point) left == right
00142       // we will maximize from two same values.
00143       // This is not a problem, but beware of this
00144       // corner case if you use other function (sum for example)
00145       T result = std::max(data[left], data[right]);
00146       while (heap::parent(left) != heap::parent(right)) {
00147         if (heap::isLeftChild(left)) {
00148           // include right sibling
00149           result = std::max(result, data[heap::sibling(left)]);
00150         }
00151         if (heap::isRightChild(right)) {
00152           // include left sibling
00153           result = std::max(result, data[heap::sibling(right)]);
00154         }
00155         left = heap::parent(left);
00156         right = heap::parent(right);
00157       }
00158       return result;
00159     }
00160 };
00161 
00162 } // namespace simple
00163 } // namespace interval_trees
00164 
00165 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines