1 /*============================================================================= 2 Copyright (c) 2017 Daniel James 3 4 Use, modification and distribution is subject to the Boost Software 5 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 6 http://www.boost.org/LICENSE_1_0.txt) 7 =============================================================================*/ 8 9 #if !defined(BOOST_QUICKBOOK_TREE_HPP) 10 #define BOOST_QUICKBOOK_TREE_HPP 11 12 #include <utility> 13 14 namespace quickbook 15 { 16 namespace detail 17 { 18 struct tree_node_base; 19 template <typename T> struct tree_node; 20 struct tree_base; 21 template <typename T> struct tree; 22 struct tree_builder_base; 23 template <typename T> struct tree_builder; 24 25 struct tree_node_base 26 { 27 friend struct tree_base; 28 friend struct tree_builder_base; 29 30 protected: 31 tree_node_base* parent_; 32 tree_node_base* children_; 33 tree_node_base* next_; 34 tree_node_base* prev_; 35 36 public: tree_node_basequickbook::detail::tree_node_base37 tree_node_base() : parent_(), children_(), next_(), prev_() {} 38 39 protected: 40 void add_before(tree_base*); 41 void add_after(tree_base*); 42 void add_first_child(tree_base*); 43 void add_last_child(tree_base*); 44 }; 45 46 template <typename T> struct tree_node : tree_node_base 47 { parentquickbook::detail::tree_node48 T* parent() const { return static_cast<T*>(parent_); } childrenquickbook::detail::tree_node49 T* children() const { return static_cast<T*>(children_); } nextquickbook::detail::tree_node50 T* next() const { return static_cast<T*>(next_); } prevquickbook::detail::tree_node51 T* prev() const { return static_cast<T*>(prev_); } 52 add_beforequickbook::detail::tree_node53 void add_before(tree<T>&& x) { tree_node_base::add_before(&x); } add_afterquickbook::detail::tree_node54 void add_after(tree<T>&& x) { tree_node_base::add_after(&x); } add_first_childquickbook::detail::tree_node55 void add_first_child(tree<T>&& x) 56 { 57 tree_node_base::add_first_child(&x); 58 } add_last_childquickbook::detail::tree_node59 void add_last_child(tree<T>&& x) 60 { 61 tree_node_base::add_last_child(&x); 62 } 63 }; 64 delete_nodes(Node * n)65 template <typename Node> void delete_nodes(Node* n) 66 { 67 while (n) { 68 Node* to_delete = n; 69 n = n->next(); 70 delete_nodes(to_delete->children()); 71 delete (to_delete); 72 } 73 } 74 75 struct tree_base 76 { 77 friend struct tree_node_base; 78 79 private: 80 tree_base(tree_base const&); 81 tree_base& operator=(tree_base const&); 82 83 protected: 84 tree_node_base* root_; 85 86 tree_base(); 87 explicit tree_base(tree_node_base*); 88 tree_base(tree_base&&); 89 tree_base& operator=(tree_base&&); 90 ~tree_base(); 91 92 tree_node_base* extract(tree_node_base*); 93 }; 94 95 template <typename T> struct tree : tree_base 96 { treequickbook::detail::tree97 tree() {} treequickbook::detail::tree98 explicit tree(T* r) : tree_base(r) {} treequickbook::detail::tree99 tree(tree<T>&& x) : tree_base(std::move(x)) {} ~treequickbook::detail::tree100 ~tree() { delete_nodes(root()); } operator =quickbook::detail::tree101 tree& operator=(tree<T>&& x) 102 { 103 tree_base::operator=(std::move(x)); 104 return *this; 105 } 106 extractquickbook::detail::tree107 tree extract(T* n) 108 { 109 return tree(static_cast<T*>(tree_base::extract(n))); 110 } rootquickbook::detail::tree111 T* root() const { return static_cast<T*>(root_); } 112 }; 113 114 struct tree_builder_base : tree_base 115 { 116 private: 117 tree_builder_base(tree_builder_base const&); 118 tree_builder_base& operator=(tree_builder_base const&); 119 120 protected: 121 tree_node_base* current_; 122 tree_node_base* parent_; 123 124 tree_builder_base(); 125 tree_builder_base(tree_builder_base&&); 126 tree_builder_base& operator=(tree_builder_base&& x); 127 ~tree_builder_base(); 128 129 tree_node_base* extract(tree_node_base*); 130 tree_node_base* release(); 131 void add_element(tree_node_base* n); 132 133 public: 134 void start_children(); 135 void end_children(); 136 }; 137 138 template <typename T> struct tree_builder : tree_builder_base 139 { 140 public: tree_builderquickbook::detail::tree_builder141 tree_builder() : tree_builder_base() {} tree_builderquickbook::detail::tree_builder142 tree_builder(tree_builder<T>&& x) : tree_builder_base(std::move(x)) 143 { 144 } ~tree_builderquickbook::detail::tree_builder145 ~tree_builder() { delete_nodes(root()); } operator =quickbook::detail::tree_builder146 tree_builder& operator=(tree_builder&& x) 147 { 148 return tree_builder_base::operator=(std::move(x)); 149 } 150 parentquickbook::detail::tree_builder151 T* parent() const { return static_cast<T*>(parent_); } currentquickbook::detail::tree_builder152 T* current() const { return static_cast<T*>(current_); } rootquickbook::detail::tree_builder153 T* root() const { return static_cast<T*>(root_); } extractquickbook::detail::tree_builder154 tree<T> extract(T* x) 155 { 156 return tree<T>(static_cast<T*>(tree_builder_base::extract(x))); 157 } releasequickbook::detail::tree_builder158 tree<T> release() 159 { 160 return tree<T>(static_cast<T*>(tree_builder_base::release())); 161 } add_elementquickbook::detail::tree_builder162 void add_element(T* n) { tree_builder_base::add_element(n); } 163 }; 164 } 165 } 166 167 #endif 168