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 #include "tree.hpp"
10 #include <cassert>
11 
12 namespace quickbook
13 {
14     namespace detail
15     {
add_before(tree_base * t)16         void tree_node_base::add_before(tree_base* t)
17         {
18             assert(
19                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
20                 !t->root_->next_);
21             t->root_->parent_ = this->parent_;
22             t->root_->next_ = this;
23             if (this->prev_) {
24                 t->root_->prev_ = this->prev_;
25                 this->prev_->next_ = t->root_;
26             }
27             else {
28                 this->parent_->children_ = t->root_;
29             }
30             this->prev_ = t->root_;
31             t->root_ = 0;
32         }
33 
add_after(tree_base * t)34         void tree_node_base::add_after(tree_base* t)
35         {
36             assert(
37                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
38                 !t->root_->next_);
39             t->root_->parent_ = this->parent_;
40             t->root_->prev_ = this;
41             t->root_->next_ = this->next_;
42             if (this->next_) this->next_->prev_ = t->root_;
43             this->next_ = t->root_;
44             t->root_ = 0;
45         }
46 
add_first_child(tree_base * t)47         void tree_node_base::add_first_child(tree_base* t)
48         {
49             assert(
50                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
51                 !t->root_->next_);
52             t->root_->parent_ = this;
53             t->root_->next_ = this->children_;
54             if (this->children_) {
55                 this->children_->prev_ = t->root_;
56             }
57             this->children_ = t->root_;
58             t->root_ = 0;
59         }
60 
add_last_child(tree_base * t)61         void tree_node_base::add_last_child(tree_base* t)
62         {
63             assert(
64                 t->root_ && !t->root_->parent_ && !t->root_->prev_ &&
65                 !t->root_->next_);
66             t->root_->parent_ = this;
67             if (!this->children_) {
68                 this->children_ = t->root_;
69             }
70             else {
71                 auto it = this->children_;
72                 while (it->next_) {
73                     it = it->next_;
74                 }
75                 t->root_->prev_ = it;
76                 it->next_ = t->root_;
77             }
78             t->root_ = 0;
79         }
80 
tree_base()81         tree_base::tree_base() : root_(0) {}
tree_base(tree_node_base * r)82         tree_base::tree_base(tree_node_base* r) : root_(r) {}
~tree_base()83         tree_base::~tree_base() {}
84 
tree_base(tree_base && x)85         tree_base::tree_base(tree_base&& x) : root_(x.root_) { x.root_ = 0; }
86 
operator =(tree_base && x)87         tree_base& tree_base::operator=(tree_base&& x)
88         {
89             root_ = x.root_;
90             x.root_ = 0;
91             return *this;
92         }
93 
extract(tree_node_base * x)94         tree_node_base* tree_base::extract(tree_node_base* x)
95         {
96             if (!x->prev_) {
97                 if (x->parent_) {
98                     x->parent_->children_ = x->next_;
99                 }
100                 else {
101                     assert(x == root_);
102                     root_ = x->next_;
103                 }
104             }
105             else {
106                 x->prev_->next_ = x->next_;
107             }
108             if (x->next_) {
109                 x->next_->prev_ = x->prev_;
110             }
111             x->parent_ = 0;
112             x->next_ = 0;
113             x->prev_ = 0;
114             return x;
115         }
116 
tree_builder_base()117         tree_builder_base::tree_builder_base()
118             : tree_base(), current_(0), parent_(0)
119         {
120         }
121 
tree_builder_base(tree_builder_base && x)122         tree_builder_base::tree_builder_base(tree_builder_base&& x)
123             : tree_base(std::move(x)), current_(x.current_), parent_(x.parent_)
124         {
125             x.current_ = 0;
126             x.parent_ = 0;
127         }
128 
operator =(tree_builder_base && x)129         tree_builder_base& tree_builder_base::operator=(tree_builder_base&& x)
130         {
131             root_ = x.root_;
132             current_ = x.current_;
133             parent_ = x.parent_;
134             x.root_ = 0;
135             x.current_ = 0;
136             x.parent_ = 0;
137             return *this;
138         }
139 
140         // Nodes are deleted in the subclass, which knows their type.
~tree_builder_base()141         tree_builder_base::~tree_builder_base() {}
142 
extract(tree_node_base * x)143         tree_node_base* tree_builder_base::extract(tree_node_base* x)
144         {
145             if (!x->prev_) {
146                 if (x->parent_) {
147                     x->parent_->children_ = x->next_;
148                 }
149                 else {
150                     assert(x == root_);
151                     root_ = x->next_;
152                     parent_ = 0;
153                     current_ = root_;
154                 }
155             }
156             else {
157                 x->prev_->next_ = x->next_;
158             }
159             if (x->next_) {
160                 x->next_->prev_ = x->prev_;
161             }
162             x->parent_ = 0;
163             x->next_ = 0;
164             x->prev_ = 0;
165             return x;
166         }
167 
release()168         tree_node_base* tree_builder_base::release()
169         {
170             tree_node_base* n = root_;
171             root_ = 0;
172             current_ = 0;
173             parent_ = 0;
174             return n;
175         }
176 
add_element(tree_node_base * n)177         void tree_builder_base::add_element(tree_node_base* n)
178         {
179             n->parent_ = parent_;
180             n->prev_ = current_;
181             if (current_) {
182                 current_->next_ = n;
183             }
184             else if (parent_) {
185                 parent_->children_ = n;
186             }
187             else {
188                 root_ = n;
189             }
190             current_ = n;
191         }
192 
start_children()193         void tree_builder_base::start_children()
194         {
195             parent_ = current_;
196             current_ = 0;
197         }
198 
end_children()199         void tree_builder_base::end_children()
200         {
201             current_ = parent_;
202             parent_ = current_->parent_;
203         }
204     }
205 }
206