Implementing Complete Tree by Layers

Question

I implement a complete tree as a layer for adding a hash, heap, and other things on top of it.

The Complete_tree_node templates can be reused regardless of the number of layers added to the tree.

This tree layer helps to hide the memory organization of the nodes from the algorithms. Currently, the Complete_tree uses an array to hold the content of the nodes.

Constructing the tree is kind of tedious because the tree does not own the data. I want to offer the option of the tree owning or not owning the data later...

Currently, the operations do not accept rvalue. So things like node.replace(tree[12]); doesn't work.

The fanpower template parameter is log₂(fanout).

Currently c++11 can build this but I don't mind using c++14.

The next step is to write:

1. a heap layer with a template parameter for selecting key from the content
2. A hash layer for keeping track of items inserted into the tree.

Is the design ok? How to make the api more convenient?

The the google tests and the code are at https://github.com/rzu512/algorithms

demo_complete_tree_traversal:

#include <iostream> #include <queue> #include <vector> #include <numeric> #include "complete_tree.h" int main() { // Construct tree typedef Complete_tree<std::vector<int>, 2> Tree; Tree tree(3); // fanout = 2^2 = 4. n_levels = 3. // Insert tree for (typename Tree::size_type i = 0; i < tree.capacity(); ++i) { tree.insert(int(i)); } std::cout << "tree size: " << tree.size() << "\n"; // Depth first traversal std::deque<typename Tree::node_type> q; q.push_back(tree.root()); std::cout << "\n"; while (!q.empty()) { auto n = q.back(); // copy construction n.content() -= 1; // change content of node. q.pop_back(); std::cout << "[" << n.index() << "]: "; if (!n.is_leaf()) { for (auto child : n.children()) { std::cout << child.index() << " "; q.push_back(child); } } else { std::cout << "leaf node"; } std::cout << "\n"; } } 

Demo result:

tree size: 21 [0]: 1 2 3 4 [4]: 17 18 19 20 [20]: leaf node [19]: leaf node [18]: leaf node [17]: leaf node [3]: 13 14 15 16 [16]: leaf node [15]: leaf node [14]: leaf node [13]: leaf node [2]: 9 10 11 12 [12]: leaf node [11]: leaf node [10]: leaf node [9]: leaf node [1]: 5 6 7 8 [8]: leaf node [7]: leaf node [6]: leaf node [5]: leaf node 

complete_tree.h:

/// \file /// \brief Complete tree #ifndef ALGORITHMS_COMPLETE_TREE_H #define ALGORITHMS_COMPLETE_TREE_H #include <cassert> #include "range.h" #include "index_iterator.h" template<typename Container, typename Container::size_type> class Complete_tree; template<typename Tree> class Const_complete_tree_node { static_assert(!std::is_const<Tree>::value, "Template parameter Tree should not be const."); typedef Const_complete_tree_node<Tree> self_type; public: typedef typename Tree::content_type content_type; typedef typename Tree::size_type size_type; typedef typename Tree::const_children_range const_children_range; typedef const_children_range children_range; Const_complete_tree_node(const Tree& tree, const size_type ix) : tree_(tree), ix_(ix) {} bool is_root() const { return tree_.is_root(*this); } bool is_leaf() const { return tree_.is_leaf(*this); } constexpr size_type n_children() const { return tree_.fanout(*this); } const content_type& content() const { return tree_.content_array_[ix_]; } // Traversal operations self_type parent() const { return tree_.parent(*this); } void swap(self_type& b) { tree_.swap(*this, b); } const size_type& index() const { return ix_; } /// \brief Returns a range for all children of this node. /// \pre Assumes the node is not a leaf node const_children_range children() const { return tree_.children(*this); } protected: size_type& internal_index() { return ix_; } const Tree& tree_; size_type ix_; friend class Complete_tree<typename Tree::container_type, Tree::fanpower_>; }; template<typename Tree> class Complete_tree_node : public Const_complete_tree_node<Tree> { static_assert(!std::is_const<Tree>::value, "Template parameter Tree should not be const."); typedef Complete_tree_node<Tree> self_type; typedef Const_complete_tree_node<Tree> Base; public: typedef typename Tree::content_type content_type; typedef typename Tree::size_type size_type; typedef typename Tree::const_children_range const_children_range; typedef typename Tree::children_range children_range; Complete_tree_node(Tree& tree, const size_type ix) : Base(tree, ix), mutable_tree_(tree) {} using Base::content; content_type& content() { return mutable_tree_.content_array_[ix_]; } // Traversal operations void replace(const content_type& c) { mutable_tree_.replace(*this, c); } using Base::children; /// \brief Returns a range for all children of this node. /// \pre Assumes the node is not a leaf node children_range children() { return mutable_tree_.children(*this); } private: Tree& mutable_tree_; using Base::ix_; friend class Complete_tree<typename Tree::container_type, Tree::fanpower_>; }; template<typename T> constexpr T fanpower_to_fanout(const T fanpower) { return T(1) << fanpower; } /// \brief Find number of nodes in a complete tree /// \details \$f{n_nodes = (fanout^n_levels - 1) / (fanout - 1)}\$f /// \param[in] fanpower Fanout of the tree is \$f{2^fanpower}\$f /// \param[in] n_levels Number of levels in the tree. Can be 0, 1, 2 ... /// \return Number of nodes in the complete tree std::size_t complete_tree_size(const std::size_t fanpower, const std::size_t n_levels) { assert(fanpower > 0 && "fanpower cannot be zero."); if (n_levels == 0) return 0; std::size_t one(1); auto fanout = fanpower_to_fanout(fanpower); // fanout = 2^fanpower auto a = one << (fanpower * n_levels); // a = fanout^n_levels // sum of geometric series: // 1 + fanout + fanout^2 + ... = (fanout^n_levels - 1) / (fanout - 1) return (a - one) / (fanout - one); } /// \brief Check if n can be the number of nodes in a complete tree. /// \param[in] n_nodes Number of nodes /// \param[in] fanpower Fanout of the tree is \$f{2^fanpower}\$f /// \return Is n_nodes a possible number of nodes in such a tree? bool check_complete_tree_size(const std::size_t n_nodes, const std::size_t fanpower) { if (n_nodes <= std::size_t(1)) return true; assert(fanpower > 0 && "fanpower cannot be zero."); // n_nodes = (fanout^n_levels - 1) / (fanout - 1) // fanout^n_levels = n_nodes * (fanout - 1) + 1 auto fanout = fanpower_to_fanout(fanpower); auto t = n_nodes * (fanout - 1) + 1; return (__builtin_ctzll(t) % fanpower) == 0; } /// \brief Complete tree /// \details This is implemented over an array of content. /// \tparam Container Type of the underlying array of contents. /// \tparam fanpower The fanout of the tree is\f${2^fanpower}\f$ template<typename Container, typename Container::size_type fanpower> class Complete_tree { static_assert(fanpower > 0, "fanpower must be > 0."); typedef Complete_tree<Container, fanpower> self_type; typedef typename Container::const_iterator const_iterator; typedef typename Container::iterator iterator; public: typedef Complete_tree_node<self_type> node_type; typedef Const_complete_tree_node<self_type> const_node_type; typedef typename Container::value_type content_type; typedef Container container_type; typedef typename Container::size_type size_type; typedef typename Container::difference_type difference_type; typedef range<index_iterator<self_type, node_type, node_type>> children_range; typedef range<const_index_iterator<self_type, const_node_type, const_node_type>> const_children_range; /// \brief Move-construct from a container /// \param[in] content_array An array of contents. /// \pre Assumes the container's size is \ref complete_tree_size(\p /// fanpower, n_levels) for some n_levels. explicit Complete_tree(Container&& content_array) : content_array_(std::move(content_array)), // size after constructing the content_array, not before. capacity_(content_array_.size()), last_level_ix_(capacity_ >> fanpower) { assert(capacity_ > 0 && check_complete_tree_size(capacity_, fanpower) && "Size of the container is not a possible number of " && "nodes in a k-complete tree with k=fanout."); } explicit Complete_tree(const size_type n_levels) : content_array_(complete_tree_size(fanpower, n_levels)), capacity_(content_array_.size()), last_level_ix_(capacity_ >> fanpower) { assert(n_levels >= 1 && "n_levels should be >= 1"); assert(capacity_ > 0 && check_complete_tree_size(capacity_, fanpower) && "Internal error: Size of the container is not a possible " && "number of nodes in a k-complete tree with k=fanout."); } constexpr size_type fanout() const { return fanpower_to_fanout(fanpower_); } size_type size() const { return size_; } size_type capacity() const { return capacity_; } bool is_full() const { return size_ == capacity_; } void insert(const content_type& c) { assert(size_ < capacity_ && "Cannot insert to a full node array."); content_array_[size_] = c; ++size_; } node_type operator[](const size_type ix) { return node_type(*this, ix); } const const_node_type operator[](const size_type ix) const { return const_node_type(*this, ix); } // Layers self_type& memory_layer() { return *this; } // Tree traversal node_type root() { return (*this)[0]; } const_node_type root() const { return (*this)[0]; } bool is_leaf(const const_node_type& node) const { return node.index() >= last_level_ix_; } const_node_type parent(const const_node_type& node) const { assert(!node.is_root() && "Root node has no parent."); return const_node_type(*this, (node.index() - 1) >> fanpower_); } node_type parent(const node_type& node) { assert(!node.is_root() && "Root node has no parent."); return node_type(*this, (node.index() - 1) >> fanpower_); } bool is_root(const const_node_type& node) const { return node.index() == 0; } void swap(const_node_type& node0, const_node_type& node1) { std::swap(node0.internal_index(), node1.internal_index()); } void replace(node_type& node, const content_type& content) { content_array_[node.index()] = content; } children_range children(const node_type& node) { assert(!node.is_leaf() && "Leaf node has no const_children."); auto new_ix = node.index() << fanpower_; ++new_ix; typename children_range::begin_iterator a(*this, new_ix); return children_range(a, a + fanout()); } const_children_range children(const const_node_type& node) const { assert(!node.is_leaf() && "Leaf node has no const_children."); auto new_ix = node.index() << fanpower_; ++new_ix; typename const_children_range::begin_iterator a(*this, new_ix); return const_children_range(a, a + fanout()); } static constexpr size_type fanpower_ = fanpower; private: Container content_array_; const size_type capacity_; size_type size_{0}; const size_type last_level_ix_; friend node_type; friend const_node_type; }; #endif //ALGORITHMS_COMPLETE_TREE_H 

index_iterator.h:

/// \file /// \brief Random access iterators that iterate over a container C by index /// \details index_iterator<C, V, R> inherits from const_index_iterator /// <C, V, R>. This allows implicit conversion from the iterator to const /// iterator. Conversion in the opposite direction is forbidden. #ifndef ALGORITHMS_INDEX_ITERATOR_H #define ALGORITHMS_INDEX_ITERATOR_H #include <iterator> #include <cassert> /// \brief Random access const_iterator over a container with index operation /// \details The iterator stores an index as a difference_type and a pointer /// to the container. Dereferencing the iterator returns a const reference /// to container[index]. The iterator contains assert() that checks for /// indexing errors. /// \tparam C typename of the container /// \tparam Value This will be the value_type of this iterator, and the /// pointer type depends on this. /// \tparam Reference Dereferencing the iterator would return this type. /// This can be a reference (e.g. int&) or a value (int). This iterator /// automatically takes care of constness (e.g. const int& vs int&). /// \pre /// - Assumes the container C has an indexing operation, a .size() method, /// C::value_type, and C::difference_type. /// - Assumes difference_type can hold the size of the container, which is /// usually a size_type. /// - If \ref Reference is a value (e.g. int) instead of a reference (e.g. /// int&), the arrow operator (->) won't work unless the Reference type is a /// proxy. template<typename C, typename Value=typename C::value_type, typename Reference=Value&> class const_index_iterator { typedef const_index_iterator<C, Value, Reference> self_type; static_assert(!std::is_const<Value>::value, "The template parameter Value should not be const."); static_assert(!std::is_const<Reference>::value, "The template parameter Reference should not be const."); public: typedef Value value_type; typedef Reference reference; // Reference may be a reference type (e.g. int&) or a value type (e.g. // int). Setting const_reference is different for these two cases. // If it is actually a reference type (e.g. int&), std::add_const won't // work. using const_reference = typename std::conditional< std::is_reference<reference>::value, typename std::remove_reference<reference>::type const&, const typename std::remove_reference<reference>::type>::type; typedef const value_type* pointer; typedef typename C::difference_type difference_type; typedef std::random_access_iterator_tag iterator_category; const_index_iterator(const C& container, const difference_type ix) : container_(&container), ix_(ix) { check_ix(); } // Arithmetic self_type& operator++() { // prefix ++ ++ix_; check_ix(); return *this; } self_type operator++(int) { // postfix ++ self_type result(*this); ++(*this); return result; } self_type& operator+=(const difference_type n) { ix_ += n; check_ix(); return *this; } self_type operator+(const difference_type n) const { return self_type(*this) += n; } self_type& operator--() { // prefix -- --ix_; check_ix(); return *this; } self_type operator--(int) { // postfix -- self_type result(*this); --(*this); return result; } self_type& operator-=(const difference_type n) { return operator+=(-n); } self_type operator-(const difference_type n) const { return self_type(*this) -= n; } difference_type operator-(const self_type& other) const { return ix_ - other.ix_; } // Dereference const_reference operator[](const difference_type ix) const { check_dereference(ix_ + ix); return *(*this + ix); } const_reference operator*() const { check_dereference(); const_reference a = ref_a()[ix_]; return ref_a()[ix_]; // (*this)[ix_] } const pointer operator->() const { static_assert(std::is_reference<Reference>::value, "This operation is" " avaliable only if dereferencing this iterator returns a " "reference."); check_dereference(); return &(ref_a()[ix_]); } // Logical bool operator==(const self_type& rhs) const { return ix_ == rhs.ix_; } bool operator!=(const self_type& rhs) const { return !operator==(rhs); } bool operator>(const self_type& rhs) const { return ix_ > rhs.ix_; } bool operator<=(const self_type& rhs) const { return !operator>(rhs); } bool operator<(const self_type& rhs) const { return ix_ < rhs.ix_; } bool operator>=(const self_type& rhs) const { return !operator<(rhs); } difference_type index() const { return ix_; } protected: void check_ix() const { check_ix(ix_); } void check_ix(const difference_type ix) const { assert(ix >= 0 && ix <= check_container_size() && "Index is out of bounds."); } void check_dereference() const { check_dereference(ix_); } void check_dereference(const difference_type ix) const { assert(ix < check_container_size() && ix >= 0 && "The iterator cannot be dereferenced because it is out of " "bounds"); } difference_type check_container_size() const { typedef typename C::size_type container_size_type; auto y = (container_size_type) ((difference_type) (ref_a().size())); auto xx = (difference_type) (ref_a().size()); // if binary representations are different, trigger assertion failure. assert(!(xx ^ y) && "Difference type cannot hold size of the container."); return ref_a().size(); } const C& ref_a() const { return *container_; } const C* container_; difference_type ix_; }; template<typename C, typename V, typename R> const_index_iterator<C, V, R> operator+( const typename const_index_iterator<C, V, R>::difference_type n, const const_index_iterator<C, V, R>& a) { return a + n; } /// \brief Random access iterator over a container with index operation /// \details The iterator stores an index as a difference_type and a pointer /// to the container. Dereferencing the iterator returns a const reference /// to container[index]. The iterator contains assert() that checks for /// indexing errors. /// \tparam C typename of the container /// \tparam Value This will be the value_type of this iterator, and the /// pointer type depends on this. /// \tparam Reference Dereferencing the iterator would return this type. /// This can be a reference (e.g. int&) or a value (int). This iterator /// automatically takes care of constness (e.g. const int& vs int&). /// \pre /// - Assumes the container C has an indexing operation, a .size() method, /// C::value_type, and C::difference_type. /// - Assumes difference_type can hold the size of the container, which is /// usually a size_type. /// - If \ref Reference is a value (e.g. int) instead of a reference (e.g. /// int&), the arrow operator (->) won't work unless the Reference type is a /// proxy. template<typename C, typename Value=typename C::value_type, typename Reference=typename C::value_type&> class index_iterator : public const_index_iterator<C, Value, Reference> { // Inhertiance from const_index_iterator<C, Value, Reference> allows // implicit conversion from an index_iterator<C, Value, Reference> to a // const_index_iterator<C, Value, Reference> even during template // instantiation. // Conversion from a const_index_iterator to an index_iterator is // forbidden. static_assert(!std::is_const<Value>::value, "Value type should not be const."); static_assert(!std::is_const<Reference>::value, "Reference type should not be const."); typedef const_index_iterator<C, Value, Reference> Base; typedef index_iterator<C, Value, Reference> self_type; public: typedef typename Base::value_type value_type; typedef typename Base::reference reference; using const_reference = typename Base::const_reference; typedef value_type* pointer; typedef typename C::difference_type difference_type; typedef std::random_access_iterator_tag iterator_category; index_iterator(const C& container, const typename C::size_type ix) : Base::const_index_iterator(container, ix) { // warning: the container is mutable although the constructor // accepts container const C& container. } // Arithmetic self_type& operator++() { // prefix ++ ++ix_; check_ix(); return *this; } self_type operator++(int) { // postfix ++ self_type result(*this); ++(*this); return result; } self_type& operator+=(const difference_type n) { ix_ += n; check_ix(); return *this; } self_type operator+(const difference_type n) const { return self_type(*this) += n; } self_type& operator--() { // prefix -- --ix_; check_ix(); return *this; } self_type operator--(int) { // postfix -- self_type result(*this); --(*this); return result; } self_type& operator-=(const difference_type n) { return operator+=(-n); } self_type operator-(const difference_type n) const { return self_type(*this) -= n; } difference_type operator-(const self_type& other) const { return ix_ - other.ix_; } // Dereference using Base::operator*; using Base::operator->; reference operator[](const difference_type ix) const { check_dereference(ix_ + ix); return *(*this + ix); } reference operator*() const { check_dereference(); return mutable_a()[ix_]; } pointer operator->() const { static_assert(std::is_reference<Reference>::value, "This operation is " "avaliable only ifdereferencing this iterator returns a " "reference."); check_dereference(); return &(mutable_a()[ix_]); } private: C& mutable_a() const { return const_cast<C&>(ref_a()); } using Base::ref_a; using Base::container_; using Base::ix_; using Base::check_dereference; using Base::check_ix; }; template<typename C, typename V, typename R> index_iterator<C, V, R> operator+(const typename index_iterator<C, V, R>::difference_type n, const index_iterator<C, V, R>& a) { return a + n; } template<typename C, typename V, typename R> typename C::difference_type distance(const const_index_iterator<C, V, R>& a, const const_index_iterator<C, V, R>& b) { return a - b; } #endif //ALGORITHMS_INDEX_ITERATOR_H 

range.h:

/// \file Implements range, which is a pair of iterators. #ifndef ALGORITHMS_RANGE_H #define ALGORITHMS_RANGE_H #include <cassert> /// \brief A pair of iterators template<typename Begin_iterator, typename End_iterator=Begin_iterator> class range { public: typedef Begin_iterator begin_iterator; typedef End_iterator end_iterator; typedef typename Begin_iterator::value_type value_type; typedef typename Begin_iterator::difference_type difference_type; range(const Begin_iterator& first, const End_iterator& last) : begin_iterator_(first), end_iterator_(last) {} Begin_iterator begin() { return begin_iterator_; } Begin_iterator begin() const { return begin_iterator_; } End_iterator end() { return end_iterator_; } End_iterator end() const { return end_iterator_; } private: Begin_iterator begin_iterator_; // copy the iterators End_iterator end_iterator_; }; template <typename C> using container_range = range<typename C::iterator>; template <typename C> using const_container_range = range<typename C::const_iterator>; template<typename it_begin, typename it_end> range<it_begin, it_end> make_range(const it_begin& begin, const it_end& end) { return range<it_begin, it_end>(begin, end); } /// \brief Make a range from a container template <typename C> container_range<C> make_range(C& c) { return container_range<C>(c.begin(), c.end()); } /// \brief Make a const_range from a container template<typename C> const_container_range<C> make_const_range(const C& c) { return const_container_range<C>(c.cbegin(), c.cend()); } /// \brief Make a const_range from a container template<typename C> const_container_range<C> make_range(const C& c) { return make_const_range(c); } /// \brief Make a range from a container template <typename C> container_range<C> make_range(C& c, typename C::size_type offset, typename C::size_type size) { assert(c.size() >= offset + size && offset >= 0 && size >= 0 && "Offset and size are out of bounds of the container."); return container_range<C>(c.begin() + offset, c.begin() + offset + size); } /// \brief Make a const_range from a container template<typename C> const_container_range<C> make_const_range( const C& c, typename C::size_type offset, typename C::size_type size) { assert(c.size() >= offset + size && offset >= 0 && size >= 0 && offset + size >= offset && "Offset and size are out of bounds of the container."); return const_container_range<C>( c.begin() + offset, c.begin() + offset + size); } /// \brief Make a const_range from a container template<typename C> const_container_range<C> make_range(const C& c, typename C::size_type offset, typename C::size_type size) { return make_const_range(c, offset, size); } #endif //ALGORITHMS_RANGE_H 

Answer 1

The code looks good, without any major red flags.

---

#include <cassert> 

C-style assert will be used? Searching…

assert(fanpower > 0 && "fanpower cannot be zero."); 

OK, make that a std::invalid_parameter exception instead.

if (n_nodes <= std::size_t(1)) 

Do you really get a warning if you write: n_nodes <= 1 ? The compiler should see that the literal constant 1 is within the domain of size_t and not give a warning.

---

In general, use the uniform initialization style, not ye olde syntax.

I don’t know what __builtin_ctzll(t) is, and it is non-portable.

return (__builtin_ctzll(t) % fanpower) == 0; 

Write a function in your program that has a readable name for what it does. Use #if to implement it as the special builtin on GCC; an equivalent intrinsic on MSVC, or portable code (just a comment and #error if you have no need for the portable version). (I think _mm_tzcnt_64 or _BitScanForward64.)

Division (and modulo) are very expensive operations in the CPU. If you could structure your test to use multiplication instead of division, or work with the powers rather than the total number, it will be better.

typedef typename Container::iterator iterator; ⋮ 

In general, make these using instead of typedef. (T/43)

index iterator

If you have to create an iterator, start by using Boost.Iterator library. Either iterator_facade or iterator_adaptor will fix you up nicely. Not only do you not have to write all the details of what makes an iterator, but it will certainly be right, saving a very picky review against the std iterator requirements.

This will save you a lot of code!

---

range in the global namespace is too generic, as there are a lot of kinds of ranges in a program. Boost.Range already understands a pair of iterators as being a range. In Range.v3 this is called iterator_range.