Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/interval_trees/full_binary_tree/full_binary_tree.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines