Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_INTERVAL_TREES_FULL_BINARY_TREE_FULL_BINARY_TREE 00002 #define H_INTERVAL_TREES_FULL_BINARY_TREE_FULL_BINARY_TREE 00003 00008 #include <stdint.h> 00009 #include <vector> 00010 #include "utils/preconditions/preconditions.h" 00011 #include "interval_trees/utils/heap.h" 00012 00013 namespace interval_trees { 00014 00019 template<typename NodeType> 00020 class FullBinaryTree { 00021 private: 00026 std::vector<NodeType> data; 00027 00028 typedef size_t Tpos; 00029 public: 00030 FullBinaryTree() { 00031 _clear(); 00032 } 00033 00037 void _clear() { 00038 data.clear(); 00039 } 00040 00045 void initialize(Tpos size) 00046 { 00047 initialize(size, NodeType()); 00048 } 00049 00053 void initialize(Tpos size_, const Tpos& default_value) { 00054 _clear(); 00055 Preconditions::check(size_ > 0, "size should be positive"); 00056 Tpos s = heap::nextPowerOfTwo(size_); 00057 Preconditions::check(size_ == s, 00058 "Wrong size - should be power of two"); 00059 if (s >= std::numeric_limits<Tpos>::max() / 2) { 00060 throw std::overflow_error("Too big size"); 00061 } 00062 00063 data.resize(s * 2, default_value); 00064 } 00065 00066 00067 00068 class Traverser { 00069 private: 00070 std::vector<NodeType>* data_ptr; 00071 Tpos pos; 00072 Tpos r_left; 00073 Tpos r_right; 00074 public: 00075 explicit Traverser(std::vector<NodeType>* data_, 00076 Tpos pos_, Tpos left_, Tpos right_) { 00077 data_ptr = data_; 00078 pos = pos_; 00079 r_left = left_; 00080 r_right = right_; 00081 } 00082 00083 NodeType& operator *() { 00084 return (*data_ptr)[pos]; 00085 } 00086 00087 const NodeType& operator *() const { 00088 return (*data_ptr)[pos]; 00089 } 00090 00091 Traverser left() { 00092 Preconditions::check(pos < data_ptr->size() / 2, "already leaf"); 00093 // Note: left + right is max 00094 return Traverser(data_ptr, heap::left(pos), r_left, (r_left + r_right) / 2); 00095 } 00096 00097 Traverser right() { 00098 Preconditions::check(pos < data_ptr->size() /2, "already leaf"); 00099 return Traverser(data_ptr, heap::right(pos), (r_left + r_right) / 2, r_right); 00100 } 00101 00102 Traverser parent() { 00103 Preconditions::check(pos > 1, "already parent"); 00104 Tpos l,r; 00105 if (heap::isLeftChild(pos)) { 00106 l = r_left; 00107 r = 2 * r_right - r_left; 00108 } else { 00109 l = r_right - 2 * r_left; 00110 r = r_right; 00111 } 00112 return Traverser(data_ptr, heap::parent(pos), l, r); 00113 } 00114 00115 Tpos range_left() const { 00116 return r_left; 00117 } 00118 00119 Tpos range_right() const { 00120 return r_right; 00121 } 00122 00123 }; 00124 00125 Traverser root(){ 00126 return Traverser(&data, 1, 0, data.size() / 2); 00127 } 00128 00129 Traverser leaf(Tpos pos) { 00130 Preconditions::checkRange(pos, data.size() / 2); 00131 return Traverser(&data, data.size() / 2 + pos, pos, pos + 1); 00132 } 00133 00134 }; 00135 } // namespace interval_trees 00136 #endif