Last active
September 30, 2017 17:21
-
-
Save mtao/9482d9df9f2a44e1dfe8b464055de040 to your computer and use it in GitHub Desktop.
contiguous binary tree implementation someone was curious to see
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #ifndef CONTIGUOUS_BINARY_TREE_HPP | |
| #define CONTIGUOUS_BINARY_TREE_HPP | |
| #include <cmath> | |
| #include <vector> | |
| template <typename T> | |
| struct CBinaryTree: public std::vector<T> { | |
| public: | |
| using BaseType = std::vector<T>; | |
| using BaseType::operator[]; | |
| using value_type = typename BaseType::value_type; | |
| using BaseType::begin; | |
| using BaseType::end; | |
| struct Node { | |
| public: | |
| Node(CBinaryTree<T>* t, int idx): m_tree(t), m_index(idx) {} | |
| const CBinaryTree<T>& tree() const { return *m_tree; } | |
| int index() const { return m_index; } | |
| value_type& operator()() { return (*m_tree)[m_index]; } | |
| const value_type& operator()() const { return (*m_tree)[m_index]; } | |
| operator bool() const { return m_index < m_tree->size(); } | |
| int depth() const { return std::floor(std::log2(m_index+1)); } | |
| Node left() const { return Node(m_tree,m_tree->left(m_index));} | |
| Node right() const { return Node(m_tree,m_tree->right(m_index));} | |
| Node parent() const { return Node(m_tree,m_tree->parent(m_index));} | |
| private: | |
| CBinaryTree<T>* m_tree; | |
| int m_index; | |
| }; | |
| CBinaryTree(int depth): BaseType(std::exp2(depth)-1), m_depth(depth) {} | |
| Node node(int idx=0) { return Node{this,idx}; } | |
| int depth() const { return m_depth; } | |
| #ifdef USE_BITSHIFTS | |
| static int left(int idx) { return (idx<<1)+1; } | |
| static int right(int idx) { return (idx<<1)+2; } | |
| static int parent(int idx) { return (idx-1)<<1; } | |
| #else | |
| static int left(int idx) { return 2*idx+1; } | |
| static int right(int idx) { return 2*idx+2; } | |
| static int parent(int idx) { return (idx-1)/2; } | |
| #endif | |
| private: | |
| int m_depth; | |
| }; | |
| #endif//CONTIGUOUS_BINARY_TREE_HPP |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include "contiguous_bin_tree.hpp" | |
| #include <iostream> | |
| using Tree = CBinaryTree<int>; | |
| using Node = Tree::Node; | |
| void traverse(const Node& n) { | |
| if(!n) { return; } | |
| for(int i = 0; i < n.depth(); ++i) { | |
| std::cout << ">"; | |
| } | |
| std::cout << n() << std::endl; | |
| traverse(n.left()); | |
| traverse(n.right()); | |
| }; | |
| int main() { | |
| Tree cbt(4); | |
| for(int i = 0; i < cbt.depth(); ++i) { | |
| int base = std::exp2(i)-1; | |
| for(int j = 0; j < std::exp2(i); ++j) { | |
| int idx = base + j; | |
| cbt[idx] = i * 100 + j; | |
| std:: cout << cbt[idx] << " = " << cbt.node(idx)() << std::endl; | |
| } | |
| } | |
| auto n = cbt.node(); | |
| traverse(cbt.node()); | |
| return 0; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment