Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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