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