1
2 // STL-like templated tree class.
3 //
4 // Copyright (C) 2001-2020 Kasper Peeters <kasper@phi-sci.com>
5 // Distributed under the GNU General Public License version 3.
6 //
7 // Special permission to use tree.hh under the conditions of a
8 // different license can be requested from the author.
9
10 /** \mainpage tree.hh
11 \author Kasper Peeters
12 \version 3.17
13 \date 07-Nov-2020
14 \see http://tree.phi-sci.com/
15 \see http://github.com/kpeeters/tree.hh/
16
17 The tree.hh library for C++ provides an STL-like container class
18 for n-ary trees, templated over the data stored at the
19 nodes. Various types of iterators are provided (post-order,
20 pre-order, and others). Where possible the access methods are
21 compatible with the STL or alternative algorithms are
22 available.
23 */
24
25
26 #ifndef tree_hh_
27 #define tree_hh_
28
29 #include <cassert>
30 #include <memory>
31 #include <stdexcept>
32 #include <iterator>
33 #include <set>
34 #include <queue>
35 #include <algorithm>
36 #include <cstddef>
37
38
39 /// A node in the tree, combining links to other nodes as well as the actual data.
40 template<class T>
41 class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
42 public:
43 tree_node_();
44 tree_node_(const T&);
45 tree_node_(T&&);
46
47 tree_node_<T> *parent;
48 tree_node_<T> *first_child, *last_child;
49 tree_node_<T> *prev_sibling, *next_sibling;
50 T data;
51 };
52
53 template<class T>
tree_node_()54 tree_node_<T>::tree_node_()
55 : parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0)
56 {
57 }
58
59 template<class T>
tree_node_(const T & val)60 tree_node_<T>::tree_node_(const T& val)
61 : parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0), data(val)
62 {
63 }
64
65 template<class T>
tree_node_(T && val)66 tree_node_<T>::tree_node_(T&& val)
67 : parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0), data(val)
68 {
69 }
70
71 // Throw an exception with a stacktrace.
72
73 //template <class E>
74 //void throw_with_trace(const E& e)
75 // {
76 // throw boost::enable_error_info(e)
77 // << traced(boost::stacktrace::stacktrace());
78 // }
79
80 class navigation_error : public std::logic_error {
81 public:
navigation_error(const std::string & s)82 navigation_error(const std::string& s) : std::logic_error(s)
83 {
84 // assert(1==0);
85 // std::ostringstream str;
86 // std::cerr << boost::stacktrace::stacktrace() << std::endl;
87 // str << boost::stacktrace::stacktrace();
88 // stacktrace=str.str();
89 };
90
91 // virtual const char *what() const noexcept override
92 // {
93 // return (std::logic_error::what()+std::string("; ")+stacktrace).c_str();
94 // }
95 //
96 // std::string stacktrace;
97 };
98
99 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
100 class tree {
101 protected:
102 typedef tree_node_<T> tree_node;
103 public:
104 /// Value of the data stored at a node.
105 typedef T value_type;
106
107 class iterator_base;
108 class pre_order_iterator;
109 class post_order_iterator;
110 class sibling_iterator;
111 class leaf_iterator;
112
113 tree(); // empty constructor
114 tree(const T&); // constructor setting given element as head
115 tree(const iterator_base&);
116 tree(const tree<T, tree_node_allocator>&); // copy constructor
117 tree(tree<T, tree_node_allocator>&&); // move constructor
118 ~tree();
119 tree<T,tree_node_allocator>& operator=(const tree<T, tree_node_allocator>&); // copy assignment
120 tree<T,tree_node_allocator>& operator=(tree<T, tree_node_allocator>&&); // move assignment
121
122 /// Base class for iterators, only pointers stored, no traversal logic.
123 #ifdef __SGI_STL_PORT
124 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
125 #else
126 class iterator_base {
127 #endif
128 public:
129 typedef T value_type;
130 typedef T* pointer;
131 typedef T& reference;
132 typedef size_t size_type;
133 typedef ptrdiff_t difference_type;
134 typedef std::bidirectional_iterator_tag iterator_category;
135
136 iterator_base();
137 iterator_base(tree_node *);
138
139 T& operator*() const;
140 T* operator->() const;
141
142 /// When called, the next increment/decrement skips children of this node.
143 void skip_children();
144 void skip_children(bool skip);
145 /// Number of children of the node pointed to by the iterator.
146 unsigned int number_of_children() const;
147
148 sibling_iterator begin() const;
149 sibling_iterator end() const;
150
151 tree_node *node;
152 protected:
153 bool skip_current_children_;
154 };
155
156 /// Depth-first iterator, first accessing the node, then its children.
157 class pre_order_iterator : public iterator_base {
158 public:
159 pre_order_iterator();
160 pre_order_iterator(tree_node *);
161 pre_order_iterator(const iterator_base&);
162 pre_order_iterator(const sibling_iterator&);
163
164 bool operator==(const pre_order_iterator&) const;
165 bool operator!=(const pre_order_iterator&) const;
166 pre_order_iterator& operator++();
167 pre_order_iterator& operator--();
168 pre_order_iterator operator++(int);
169 pre_order_iterator operator--(int);
170 pre_order_iterator& operator+=(unsigned int);
171 pre_order_iterator& operator-=(unsigned int);
172
173 pre_order_iterator& next_skip_children();
174 };
175
176 /// Depth-first iterator, first accessing the children, then the node itself.
177 class post_order_iterator : public iterator_base {
178 public:
179 post_order_iterator();
180 post_order_iterator(tree_node *);
181 post_order_iterator(const iterator_base&);
182 post_order_iterator(const sibling_iterator&);
183
184 bool operator==(const post_order_iterator&) const;
185 bool operator!=(const post_order_iterator&) const;
186 post_order_iterator& operator++();
187 post_order_iterator& operator--();
188 post_order_iterator operator++(int);
189 post_order_iterator operator--(int);
190 post_order_iterator& operator+=(unsigned int);
191 post_order_iterator& operator-=(unsigned int);
192
193 /// Set iterator to the first child as deep as possible down the tree.
194 void descend_all();
195 };
196
197 /// Breadth-first iterator, using a queue
198 class breadth_first_queued_iterator : public iterator_base {
199 public:
200 breadth_first_queued_iterator();
201 breadth_first_queued_iterator(tree_node *);
202 breadth_first_queued_iterator(const iterator_base&);
203
204 bool operator==(const breadth_first_queued_iterator&) const;
205 bool operator!=(const breadth_first_queued_iterator&) const;
206 breadth_first_queued_iterator& operator++();
207 breadth_first_queued_iterator operator++(int);
208 breadth_first_queued_iterator& operator+=(unsigned int);
209
210 private:
211 std::queue<tree_node *> traversal_queue;
212 };
213
214 /// The default iterator types throughout the tree class.
215 typedef pre_order_iterator iterator;
216 typedef breadth_first_queued_iterator breadth_first_iterator;
217
218 /// Iterator which traverses only the nodes at a given depth from the root.
219 class fixed_depth_iterator : public iterator_base {
220 public:
221 fixed_depth_iterator();
222 fixed_depth_iterator(tree_node *);
223 fixed_depth_iterator(const iterator_base&);
224 fixed_depth_iterator(const sibling_iterator&);
225 fixed_depth_iterator(const fixed_depth_iterator&);
226
227 bool operator==(const fixed_depth_iterator&) const;
228 bool operator!=(const fixed_depth_iterator&) const;
229 fixed_depth_iterator& operator++();
230 fixed_depth_iterator& operator--();
231 fixed_depth_iterator operator++(int);
232 fixed_depth_iterator operator--(int);
233 fixed_depth_iterator& operator+=(unsigned int);
234 fixed_depth_iterator& operator-=(unsigned int);
235
236 tree_node *top_node;
237 };
238
239 /// Iterator which traverses only the nodes which are siblings of each other.
240 class sibling_iterator : public iterator_base {
241 public:
242 sibling_iterator();
243 sibling_iterator(tree_node *);
244 sibling_iterator(const sibling_iterator&);
245 sibling_iterator(const iterator_base&);
246
247 bool operator==(const sibling_iterator&) const;
248 bool operator!=(const sibling_iterator&) const;
249 sibling_iterator& operator++();
250 sibling_iterator& operator--();
251 sibling_iterator operator++(int);
252 sibling_iterator operator--(int);
253 sibling_iterator& operator+=(unsigned int);
254 sibling_iterator& operator-=(unsigned int);
255
256 tree_node *range_first() const;
257 tree_node *range_last() const;
258 tree_node *parent_;
259 private:
260 void set_parent_();
261 };
262
263 /// Iterator which traverses only the leaves.
264 class leaf_iterator : public iterator_base {
265 public:
266 leaf_iterator();
267 leaf_iterator(tree_node *, tree_node *top=0);
268 leaf_iterator(const sibling_iterator&);
269 leaf_iterator(const iterator_base&);
270
271 bool operator==(const leaf_iterator&) const;
272 bool operator!=(const leaf_iterator&) const;
273 leaf_iterator& operator++();
274 leaf_iterator& operator--();
275 leaf_iterator operator++(int);
276 leaf_iterator operator--(int);
277 leaf_iterator& operator+=(unsigned int);
278 leaf_iterator& operator-=(unsigned int);
279 private:
280 tree_node *top_node;
281 };
282
283 /// Return iterator to the beginning of the tree.
284 inline pre_order_iterator begin() const;
285 /// Return iterator to the end of the tree.
286 inline pre_order_iterator end() const;
287 /// Return post-order iterator to the beginning of the tree.
288 post_order_iterator begin_post() const;
289 /// Return post-order end iterator of the tree.
290 post_order_iterator end_post() const;
291 /// Return fixed-depth iterator to the first node at a given depth from the given iterator.
292 /// If 'walk_back=true', a depth=0 iterator will be taken from the beginning of the sibling
293 /// range, not the current node.
294 fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int, bool walk_back=true) const;
295 /// Return fixed-depth end iterator.
296 fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
297 /// Return breadth-first iterator to the first node at a given depth.
298 breadth_first_queued_iterator begin_breadth_first() const;
299 /// Return breadth-first end iterator.
300 breadth_first_queued_iterator end_breadth_first() const;
301 /// Return sibling iterator to the first child of given node.
302 static sibling_iterator begin(const iterator_base&);
303 /// Return sibling end iterator for children of given node.
304 static sibling_iterator end(const iterator_base&);
305 /// Return leaf iterator to the first leaf of the tree.
306 leaf_iterator begin_leaf() const;
307 /// Return leaf end iterator for entire tree.
308 leaf_iterator end_leaf() const;
309 /// Return leaf iterator to the first leaf of the subtree at the given node.
310 leaf_iterator begin_leaf(const iterator_base& top) const;
311 /// Return leaf end iterator for the subtree at the given node.
312 leaf_iterator end_leaf(const iterator_base& top) const;
313
314 typedef std::vector<int> path_t;
315 /// Return a path (to be taken from the 'top' node) corresponding to a node in the tree.
316 /// The first integer in path_t is the number of steps you need to go 'right' in the sibling
317 /// chain (so 0 if we go straight to the children).
318 path_t path_from_iterator(const iterator_base& iter, const iterator_base& top) const;
319 /// Return an iterator given a path from the 'top' node.
320 iterator iterator_from_path(const path_t&, const iterator_base& top) const;
321
322 /// Return iterator to the parent of a node. Throws a `navigation_error` if the node
323 /// does not have a parent.
324 template<typename iter> static iter parent(iter);
325 /// Return iterator to the previous sibling of a node.
326 template<typename iter> static iter previous_sibling(iter);
327 /// Return iterator to the next sibling of a node.
328 template<typename iter> static iter next_sibling(iter);
329 /// Return iterator to the next node at a given depth.
330 template<typename iter> iter next_at_same_depth(iter) const;
331
332 /// Erase all nodes of the tree.
333 void clear();
334 /// Erase element at position pointed to by iterator, return incremented iterator.
335 template<typename iter> iter erase(iter);
336 /// Erase all children of the node pointed to by iterator.
337 void erase_children(const iterator_base&);
338 /// Erase all siblings to the right of the iterator.
339 void erase_right_siblings(const iterator_base&);
340 /// Erase all siblings to the left of the iterator.
341 void erase_left_siblings(const iterator_base&);
342
343 /// Insert empty node as last/first child of node pointed to by position.
344 template<typename iter> iter append_child(iter position);
345 template<typename iter> iter prepend_child(iter position);
346 /// Insert node as last/first child of node pointed to by position.
347 template<typename iter> iter append_child(iter position, const T& x);
348 template<typename iter> iter append_child(iter position, T&& x);
349 template<typename iter> iter prepend_child(iter position, const T& x);
350 template<typename iter> iter prepend_child(iter position, T&& x);
351 /// Append the node (plus its children) at other_position as last/first child of position.
352 template<typename iter> iter append_child(iter position, iter other_position);
353 template<typename iter> iter prepend_child(iter position, iter other_position);
354 /// Append the nodes in the from-to range (plus their children) as last/first children of position.
355 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
356 template<typename iter> iter prepend_children(iter position, sibling_iterator from, sibling_iterator to);
357
358 /// Short-hand to insert topmost node in otherwise empty tree.
359 pre_order_iterator set_head(const T& x);
360 pre_order_iterator set_head(T&& x);
361 /// Insert node as previous sibling of node pointed to by position.
362 template<typename iter> iter insert(iter position, const T& x);
363 template<typename iter> iter insert(iter position, T&& x);
364 /// Specialisation of previous member.
365 sibling_iterator insert(sibling_iterator position, const T& x);
366 /// Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.
367 /// Does not change the subtree itself (use move_in or move_in_below for that).
368 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
369 /// Insert node as next sibling of node pointed to by position.
370 template<typename iter> iter insert_after(iter position, const T& x);
371 template<typename iter> iter insert_after(iter position, T&& x);
372 /// Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.
373 template<typename iter> iter insert_subtree_after(iter position, const iterator_base& subtree);
374
375 /// Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
376 template<typename iter> iter replace(iter position, const T& x);
377 /// Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
378 template<typename iter> iter replace(iter position, const iterator_base& from);
379 /// Replace string of siblings (plus their children) with copy of a new string (with children); see above
380 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
381 sibling_iterator new_begin, sibling_iterator new_end);
382
383 /// Move all children of node at 'position' to be siblings, returns position.
384 template<typename iter> iter flatten(iter position);
385 /// Move nodes in range to be children of 'position'.
386 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
387 /// Move all child nodes of 'from' to be children of 'position'.
388 template<typename iter> iter reparent(iter position, iter from);
389
390 /// Replace node with a new node, making the old node (plus subtree) a child of the new node.
391 template<typename iter> iter wrap(iter position, const T& x);
392 /// Replace the range of sibling nodes (plus subtrees), making these children of the new node.
393 template<typename iter> iter wrap(iter from, iter to, const T& x);
394
395 /// Move 'source' node (plus its children) to become the next sibling of 'target'.
396 template<typename iter> iter move_after(iter target, iter source);
397 /// Move 'source' node (plus its children) to become the previous sibling of 'target'.
398 template<typename iter> iter move_before(iter target, iter source);
399 sibling_iterator move_before(sibling_iterator target, sibling_iterator source);
400 /// Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
401 template<typename iter> iter move_ontop(iter target, iter source);
402
403 /// Extract the subtree starting at the indicated node, removing it from the original tree.
404 tree move_out(iterator);
405 /// Inverse of take_out: inserts the given tree as previous sibling of indicated node by a
406 /// move operation, that is, the given tree becomes empty. Returns iterator to the top node.
407 template<typename iter> iter move_in(iter, tree&);
408 /// As above, but now make the tree the last child of the indicated node.
409 template<typename iter> iter move_in_below(iter, tree&);
410 /// As above, but now make the tree the nth child of the indicated node (if possible).
411 template<typename iter> iter move_in_as_nth_child(iter, size_t, tree&);
412
413 /// Merge with other tree, creating new branches and leaves only if they are not already present.
414 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
415 bool duplicate_leaves=false);
416 /// As above, but using two trees with a single top node at the 'to' and 'from' positions.
417 void merge(iterator to, iterator from, bool duplicate_leaves);
418 /// Sort (std::sort only moves values of nodes, this one moves children as well).
419 void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
420 template<class StrictWeakOrdering>
421 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
422 /// Compare two ranges of nodes (compares nodes as well as tree structure).
423 template<typename iter>
424 bool equal(const iter& one, const iter& two, const iter& three) const;
425 template<typename iter, class BinaryPredicate>
426 bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
427 template<typename iter>
428 bool equal_subtree(const iter& one, const iter& two) const;
429 template<typename iter, class BinaryPredicate>
430 bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
431 /// Extract a new tree formed by the range of siblings plus all their children.
432 tree subtree(sibling_iterator from, sibling_iterator to) const;
433 void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
434 /// Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
435 void swap(sibling_iterator it);
436 /// Exchange two nodes (plus subtrees). The iterators will remain valid and keep
437 /// pointing to the same nodes, which now sit at different locations in the tree.
438 void swap(iterator, iterator);
439
440 /// Count the total number of nodes.
441 size_t size() const;
442 /// Count the total number of nodes below the indicated node (plus one).
443 size_t size(const iterator_base&) const;
444 /// Check if tree is empty.
445 bool empty() const;
446 /// Compute the depth to the root or to a fixed other iterator.
447 static int depth(const iterator_base&);
448 static int depth(const iterator_base&, const iterator_base&);
449 /// Compute the depth to the root, counting all levels for which predicate returns true.
450 template<class Predicate>
451 static int depth(const iterator_base&, Predicate p);
452 /// Compute the depth distance between two nodes, counting all levels for which predicate returns true.
453 template<class Predicate>
454 static int distance(const iterator_base& top, const iterator_base& bottom, Predicate p);
455 /// Determine the maximal depth of the tree. An empty tree has max_depth=-1.
456 int max_depth() const;
457 /// Determine the maximal depth of the tree with top node at the given position.
458 int max_depth(const iterator_base&) const;
459 /// Count the number of children of node at position.
460 static unsigned int number_of_children(const iterator_base&);
461 /// Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.
462 unsigned int number_of_siblings(const iterator_base&) const;
463 /// Determine whether node at position is in the subtrees with indicated top node.
464 bool is_in_subtree(const iterator_base& position, const iterator_base& top) const;
465 /// Determine whether node at position is in the subtrees with root in the range.
466 bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
467 const iterator_base& end) const;
468 /// Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
469 bool is_valid(const iterator_base&) const;
470 /// Determine whether the iterator is one of the 'head' nodes at the top level, i.e. has no parent.
471 static bool is_head(const iterator_base&);
472 /// Find the lowest common ancestor of two nodes, that is, the deepest node such that
473 /// both nodes are descendants of it.
474 iterator lowest_common_ancestor(const iterator_base&, const iterator_base &) const;
475
476 /// Determine the index of a node in the range of siblings to which it belongs.
477 unsigned int index(sibling_iterator it) const;
478 /// Inverse of 'index': return the n-th child of the node at position.
479 static sibling_iterator child(const iterator_base& position, unsigned int);
480 /// Return iterator to the sibling indicated by index
481 sibling_iterator sibling(const iterator_base& position, unsigned int) const;
482
483 /// For debugging only: verify internal consistency by inspecting all pointers in the tree
484 /// (which will also trigger a valgrind error in case something got corrupted).
485 void debug_verify_consistency() const;
486
487 /// Comparator class for iterators (compares pointer values; why doesn't this work automatically?)
488 class iterator_base_less {
489 public:
operator ()(const typename tree<T,tree_node_allocator>::iterator_base & one,const typename tree<T,tree_node_allocator>::iterator_base & two) const490 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
491 const typename tree<T, tree_node_allocator>::iterator_base& two) const
492 {
493 return one.node < two.node;
494 }
495 };
496 tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
497 private:
498 tree_node_allocator alloc_;
499 void head_initialise_();
500 void copy_(const tree<T, tree_node_allocator>& other);
501
502 /// Comparator class for two nodes of a tree (used for sorting and searching).
503 template<class StrictWeakOrdering>
504 class compare_nodes {
505 public:
compare_nodes(StrictWeakOrdering comp)506 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
507
operator ()(const tree_node * a,const tree_node * b)508 bool operator()(const tree_node *a, const tree_node *b)
509 {
510 return comp_(a->data, b->data);
511 }
512 private:
513 StrictWeakOrdering comp_;
514 };
515 };
516
517 //template <class T, class tree_node_allocator>
518 //class iterator_base_less {
519 // public:
520 // bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
521 // const typename tree<T, tree_node_allocator>::iterator_base& two) const
522 // {
523 // txtout << "operatorclass<" << one.node < two.node << std::endl;
524 // return one.node < two.node;
525 // }
526 //};
527
528 // template <class T, class tree_node_allocator>
529 // bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
530 // const typename tree<T, tree_node_allocator>::iterator& two)
531 // {
532 // txtout << "operator< " << one.node < two.node << std::endl;
533 // if(one.node < two.node) return true;
534 // return false;
535 // }
536 //
537 // template <class T, class tree_node_allocator>
538 // bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
539 // const typename tree<T, tree_node_allocator>::iterator& two)
540 // {
541 // txtout << "operator== " << one.node == two.node << std::endl;
542 // if(one.node == two.node) return true;
543 // return false;
544 // }
545 //
546 // template <class T, class tree_node_allocator>
547 // bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
548 // const typename tree<T, tree_node_allocator>::iterator_base& two)
549 // {
550 // txtout << "operator> " << one.node < two.node << std::endl;
551 // if(one.node > two.node) return true;
552 // return false;
553 // }
554
555
556
557 // Tree
558
559 template <class T, class tree_node_allocator>
tree()560 tree<T, tree_node_allocator>::tree()
561 {
562 head_initialise_();
563 }
564
565 template <class T, class tree_node_allocator>
tree(const T & x)566 tree<T, tree_node_allocator>::tree(const T& x)
567 {
568 head_initialise_();
569 set_head(x);
570 }
571
572 template <class T, class tree_node_allocator>
tree(tree<T,tree_node_allocator> && x)573 tree<T, tree_node_allocator>::tree(tree<T, tree_node_allocator>&& x)
574 {
575 head_initialise_();
576 if(x.head->next_sibling!=x.feet) { // move tree if non-empty only
577 head->next_sibling=x.head->next_sibling;
578 feet->prev_sibling=x.feet->prev_sibling;
579 x.head->next_sibling->prev_sibling=head;
580 x.feet->prev_sibling->next_sibling=feet;
581 x.head->next_sibling=x.feet;
582 x.feet->prev_sibling=x.head;
583 }
584 }
585
586 template <class T, class tree_node_allocator>
tree(const iterator_base & other)587 tree<T, tree_node_allocator>::tree(const iterator_base& other)
588 {
589 head_initialise_();
590 set_head((*other));
591 replace(begin(), other);
592 }
593
594 template <class T, class tree_node_allocator>
~tree()595 tree<T, tree_node_allocator>::~tree()
596 {
597 clear();
598 std::allocator_traits<decltype(alloc_)>::destroy(alloc_, head);
599 std::allocator_traits<decltype(alloc_)>::destroy(alloc_, feet);
600 std::allocator_traits<decltype(alloc_)>::deallocate(alloc_, head, 1);
601 std::allocator_traits<decltype(alloc_)>::deallocate(alloc_, feet, 1);
602 }
603
604 template <class T, class tree_node_allocator>
head_initialise_()605 void tree<T, tree_node_allocator>::head_initialise_()
606 {
607 head = std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
608 feet = std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
609 std::allocator_traits<decltype(alloc_)>::construct(alloc_, head, tree_node_<T>());
610 std::allocator_traits<decltype(alloc_)>::construct(alloc_, feet, tree_node_<T>());
611
612 head->parent=0;
613 head->first_child=0;
614 head->last_child=0;
615 head->prev_sibling=0; //head;
616 head->next_sibling=feet; //head;
617
618 feet->parent=0;
619 feet->first_child=0;
620 feet->last_child=0;
621 feet->prev_sibling=head;
622 feet->next_sibling=0;
623 }
624
625 template <class T, class tree_node_allocator>
operator =(const tree<T,tree_node_allocator> & other)626 tree<T,tree_node_allocator>& tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
627 {
628 if(this != &other)
629 copy_(other);
630 return *this;
631 }
632
633 template <class T, class tree_node_allocator>
operator =(tree<T,tree_node_allocator> && x)634 tree<T,tree_node_allocator>& tree<T, tree_node_allocator>::operator=(tree<T, tree_node_allocator>&& x)
635 {
636 if(this != &x) {
637 clear(); // clear any existing data.
638
639 head->next_sibling=x.head->next_sibling;
640 feet->prev_sibling=x.feet->prev_sibling;
641 x.head->next_sibling->prev_sibling=head;
642 x.feet->prev_sibling->next_sibling=feet;
643 x.head->next_sibling=x.feet;
644 x.feet->prev_sibling=x.head;
645 }
646 return *this;
647 }
648
649 template <class T, class tree_node_allocator>
tree(const tree<T,tree_node_allocator> & other)650 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
651 {
652 head_initialise_();
653 copy_(other);
654 }
655
656 template <class T, class tree_node_allocator>
copy_(const tree<T,tree_node_allocator> & other)657 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
658 {
659 clear();
660 pre_order_iterator it=other.begin(), to=begin();
661 while(it!=other.end()) {
662 to=insert(to, (*it));
663 it.skip_children();
664 ++it;
665 }
666 to=begin();
667 it=other.begin();
668 while(it!=other.end()) {
669 to=replace(to, it);
670 to.skip_children();
671 it.skip_children();
672 ++to;
673 ++it;
674 }
675 }
676
677 template <class T, class tree_node_allocator>
clear()678 void tree<T, tree_node_allocator>::clear()
679 {
680 if(head)
681 while(head->next_sibling!=feet)
682 erase(pre_order_iterator(head->next_sibling));
683 }
684
685 template<class T, class tree_node_allocator>
erase_children(const iterator_base & it)686 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
687 {
688 // std::cout << "erase_children " << it.node << std::endl;
689 if(it.node==0) return;
690
691 tree_node *cur=it.node->first_child;
692 tree_node *prev=0;
693
694 while(cur!=0) {
695 prev=cur;
696 cur=cur->next_sibling;
697 erase_children(pre_order_iterator(prev));
698 std::allocator_traits<decltype(alloc_)>::destroy(alloc_, prev);
699 std::allocator_traits<decltype(alloc_)>::deallocate(alloc_, prev, 1);
700 }
701 it.node->first_child=0;
702 it.node->last_child=0;
703 // std::cout << "exit" << std::endl;
704 }
705
706 template<class T, class tree_node_allocator>
erase_right_siblings(const iterator_base & it)707 void tree<T, tree_node_allocator>::erase_right_siblings(const iterator_base& it)
708 {
709 if(it.node==0) return;
710
711 tree_node *cur=it.node->next_sibling;
712 tree_node *prev=0;
713
714 while(cur!=0) {
715 prev=cur;
716 cur=cur->next_sibling;
717 erase_children(pre_order_iterator(prev));
718 std::allocator_traits<decltype(alloc_)>::destroy(alloc_, prev);
719 std::allocator_traits<decltype(alloc_)>::deallocate(alloc_, prev, 1);
720 }
721 it.node->next_sibling=0;
722 if(it.node->parent!=0)
723 it.node->parent->last_child=it.node;
724 }
725
726 template<class T, class tree_node_allocator>
erase_left_siblings(const iterator_base & it)727 void tree<T, tree_node_allocator>::erase_left_siblings(const iterator_base& it)
728 {
729 if(it.node==0) return;
730
731 tree_node *cur=it.node->prev_sibling;
732 tree_node *prev=0;
733
734 while(cur!=0) {
735 prev=cur;
736 cur=cur->prev_sibling;
737 erase_children(pre_order_iterator(prev));
738 std::allocator_traits<decltype(alloc_)>::destroy(alloc_, prev);
739 std::allocator_traits<decltype(alloc_)>::deallocate(alloc_, prev, 1);
740 }
741 it.node->prev_sibling=0;
742 if(it.node->parent!=0)
743 it.node->parent->first_child=it.node;
744 }
745
746 template<class T, class tree_node_allocator>
747 template<class iter>
erase(iter it)748 iter tree<T, tree_node_allocator>::erase(iter it)
749 {
750 tree_node *cur=it.node;
751 assert(cur!=head);
752 iter ret=it;
753 ret.skip_children();
754 ++ret;
755 erase_children(it);
756 if(cur->prev_sibling==0) {
757 cur->parent->first_child=cur->next_sibling;
758 }
759 else {
760 cur->prev_sibling->next_sibling=cur->next_sibling;
761 }
762 if(cur->next_sibling==0) {
763 cur->parent->last_child=cur->prev_sibling;
764 }
765 else {
766 cur->next_sibling->prev_sibling=cur->prev_sibling;
767 }
768
769 std::allocator_traits<decltype(alloc_)>::destroy(alloc_, cur);
770 std::allocator_traits<decltype(alloc_)>::deallocate(alloc_, cur, 1);
771 return ret;
772 }
773
774 template <class T, class tree_node_allocator>
begin() const775 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
776 {
777 return pre_order_iterator(head->next_sibling);
778 }
779
780 template <class T, class tree_node_allocator>
end() const781 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
782 {
783 return pre_order_iterator(feet);
784 }
785
786 template <class T, class tree_node_allocator>
begin_breadth_first() const787 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const
788 {
789 return breadth_first_queued_iterator(head->next_sibling);
790 }
791
792 template <class T, class tree_node_allocator>
end_breadth_first() const793 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const
794 {
795 return breadth_first_queued_iterator();
796 }
797
798 template <class T, class tree_node_allocator>
begin_post() const799 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
800 {
801 tree_node *tmp=head->next_sibling;
802 if(tmp!=feet) {
803 while(tmp->first_child)
804 tmp=tmp->first_child;
805 }
806 return post_order_iterator(tmp);
807 }
808
809 template <class T, class tree_node_allocator>
end_post() const810 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
811 {
812 return post_order_iterator(feet);
813 }
814
815 template <class T, class tree_node_allocator>
begin_fixed(const iterator_base & pos,unsigned int dp,bool walk_back) const816 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp, bool walk_back) const
817 {
818 typename tree<T, tree_node_allocator>::fixed_depth_iterator ret;
819 ret.top_node=pos.node;
820
821 tree_node *tmp=pos.node;
822 unsigned int curdepth=0;
823 while(curdepth<dp) { // go down one level
824 while(tmp->first_child==0) {
825 if(tmp->next_sibling==0) {
826 // try to walk up and then right again
827 do {
828 if(tmp==ret.top_node)
829 throw std::range_error("tree: begin_fixed out of range");
830 tmp=tmp->parent;
831 if(tmp==0)
832 throw std::range_error("tree: begin_fixed out of range");
833 --curdepth;
834 } while(tmp->next_sibling==0);
835 }
836 tmp=tmp->next_sibling;
837 }
838 tmp=tmp->first_child;
839 ++curdepth;
840 }
841
842 // Now walk back to the first sibling in this range.
843 if(walk_back)
844 while(tmp->prev_sibling!=0)
845 tmp=tmp->prev_sibling;
846
847 ret.node=tmp;
848 return ret;
849 }
850
851 template <class T, class tree_node_allocator>
end_fixed(const iterator_base & pos,unsigned int dp) const852 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
853 {
854 assert(1==0); // FIXME: not correct yet: use is_valid() as a temporary workaround
855 tree_node *tmp=pos.node;
856 unsigned int curdepth=1;
857 while(curdepth<dp) { // go down one level
858 while(tmp->first_child==0) {
859 tmp=tmp->next_sibling;
860 if(tmp==0)
861 throw std::range_error("tree: end_fixed out of range");
862 }
863 tmp=tmp->first_child;
864 ++curdepth;
865 }
866 return tmp;
867 }
868
869 template <class T, class tree_node_allocator>
begin(const iterator_base & pos)870 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos)
871 {
872 assert(pos.node!=0);
873 if(pos.node->first_child==0) {
874 return end(pos);
875 }
876 return pos.node->first_child;
877 }
878
879 template <class T, class tree_node_allocator>
end(const iterator_base & pos)880 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos)
881 {
882 sibling_iterator ret(0);
883 ret.parent_=pos.node;
884 return ret;
885 }
886
887 template <class T, class tree_node_allocator>
begin_leaf() const888 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf() const
889 {
890 tree_node *tmp=head->next_sibling;
891 if(tmp!=feet) {
892 while(tmp->first_child)
893 tmp=tmp->first_child;
894 }
895 return leaf_iterator(tmp);
896 }
897
898 template <class T, class tree_node_allocator>
end_leaf() const899 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf() const
900 {
901 return leaf_iterator(feet);
902 }
903
904 template <class T, class tree_node_allocator>
path_from_iterator(const iterator_base & iter,const iterator_base & top) const905 typename tree<T, tree_node_allocator>::path_t tree<T, tree_node_allocator>::path_from_iterator(const iterator_base& iter, const iterator_base& top) const
906 {
907 path_t path;
908 tree_node *walk=iter.node;
909
910 do {
911 if(path.size()>0)
912 walk=walk->parent;
913 int num=0;
914 while(walk!=top.node && walk->prev_sibling!=0 && walk->prev_sibling!=head) {
915 ++num;
916 walk=walk->prev_sibling;
917 }
918 path.push_back(num);
919 }
920 while(walk->parent!=0 && walk!=top.node);
921
922 std::reverse(path.begin(), path.end());
923 return path;
924 }
925
926 template <class T, class tree_node_allocator>
iterator_from_path(const path_t & path,const iterator_base & top) const927 typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::iterator_from_path(const path_t& path, const iterator_base& top) const
928 {
929 iterator it=top;
930 tree_node *walk=it.node;
931
932 for(size_t step=0; step<path.size(); ++step) {
933 if(step>0)
934 walk=walk->first_child;
935 if(walk==0)
936 throw std::range_error("tree::iterator_from_path: no more nodes at step "+std::to_string(step));
937
938 for(int i=0; i<path[step]; ++i) {
939 walk=walk->next_sibling;
940 if(walk==0)
941 throw std::range_error("tree::iterator_from_path: out of siblings at step "+std::to_string(step));
942 }
943 }
944 it.node=walk;
945 return it;
946 }
947
948 template <class T, class tree_node_allocator>
begin_leaf(const iterator_base & top) const949 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf(const iterator_base& top) const
950 {
951 tree_node *tmp=top.node;
952 while(tmp->first_child)
953 tmp=tmp->first_child;
954 return leaf_iterator(tmp, top.node);
955 }
956
957 template <class T, class tree_node_allocator>
end_leaf(const iterator_base & top) const958 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf(const iterator_base& top) const
959 {
960 return leaf_iterator(top.node, top.node);
961 }
962
963 template <class T, class tree_node_allocator>
964 template <typename iter>
parent(iter position)965 iter tree<T, tree_node_allocator>::parent(iter position)
966 {
967 if(position.node==0)
968 throw navigation_error("tree: attempt to navigate from null iterator.");
969
970 if(position.node->parent==0)
971 throw navigation_error("tree: attempt to navigate up past head node.");
972
973 return iter(position.node->parent);
974 }
975
976 template <class T, class tree_node_allocator>
977 template <typename iter>
previous_sibling(iter position)978 iter tree<T, tree_node_allocator>::previous_sibling(iter position)
979 {
980 assert(position.node!=0);
981 iter ret(position);
982 ret.node=position.node->prev_sibling;
983 return ret;
984 }
985
986 template <class T, class tree_node_allocator>
987 template <typename iter>
next_sibling(iter position)988 iter tree<T, tree_node_allocator>::next_sibling(iter position)
989 {
990 assert(position.node!=0);
991 iter ret(position);
992 ret.node=position.node->next_sibling;
993 return ret;
994 }
995
996 template <class T, class tree_node_allocator>
997 template <typename iter>
next_at_same_depth(iter position) const998 iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
999 {
1000 // We make use of a temporary fixed_depth iterator to implement this.
1001
1002 typename tree<T, tree_node_allocator>::fixed_depth_iterator tmp(position.node);
1003
1004 ++tmp;
1005 return iter(tmp);
1006
1007 // assert(position.node!=0);
1008 // iter ret(position);
1009 //
1010 // if(position.node->next_sibling) {
1011 // ret.node=position.node->next_sibling;
1012 // }
1013 // else {
1014 // int relative_depth=0;
1015 // upper:
1016 // do {
1017 // ret.node=ret.node->parent;
1018 // if(ret.node==0) return ret;
1019 // --relative_depth;
1020 // } while(ret.node->next_sibling==0);
1021 // lower:
1022 // ret.node=ret.node->next_sibling;
1023 // while(ret.node->first_child==0) {
1024 // if(ret.node->next_sibling==0)
1025 // goto upper;
1026 // ret.node=ret.node->next_sibling;
1027 // if(ret.node==0) return ret;
1028 // }
1029 // while(relative_depth<0 && ret.node->first_child!=0) {
1030 // ret.node=ret.node->first_child;
1031 // ++relative_depth;
1032 // }
1033 // if(relative_depth<0) {
1034 // if(ret.node->next_sibling==0) goto upper;
1035 // else goto lower;
1036 // }
1037 // }
1038 // return ret;
1039 }
1040
1041 template <class T, class tree_node_allocator>
1042 template <typename iter>
append_child(iter position)1043 iter tree<T, tree_node_allocator>::append_child(iter position)
1044 {
1045 assert(position.node!=head);
1046 assert(position.node!=feet);
1047 assert(position.node);
1048
1049 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1050 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, tree_node_<T>());
1051 tmp->first_child=0;
1052 tmp->last_child=0;
1053
1054 tmp->parent=position.node;
1055 if(position.node->last_child!=0) {
1056 position.node->last_child->next_sibling=tmp;
1057 }
1058 else {
1059 position.node->first_child=tmp;
1060 }
1061 tmp->prev_sibling=position.node->last_child;
1062 position.node->last_child=tmp;
1063 tmp->next_sibling=0;
1064 return tmp;
1065 }
1066
1067 template <class T, class tree_node_allocator>
1068 template <typename iter>
prepend_child(iter position)1069 iter tree<T, tree_node_allocator>::prepend_child(iter position)
1070 {
1071 assert(position.node!=head);
1072 assert(position.node!=feet);
1073 assert(position.node);
1074
1075 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1076 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, tree_node_<T>());
1077 tmp->first_child=0;
1078 tmp->last_child=0;
1079
1080 tmp->parent=position.node;
1081 if(position.node->first_child!=0) {
1082 position.node->first_child->prev_sibling=tmp;
1083 }
1084 else {
1085 position.node->last_child=tmp;
1086 }
1087 tmp->next_sibling=position.node->first_child;
1088 position.node->prev_child=tmp;
1089 tmp->prev_sibling=0;
1090 return tmp;
1091 }
1092
1093 template <class T, class tree_node_allocator>
1094 template <class iter>
append_child(iter position,const T & x)1095 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
1096 {
1097 // If your program fails here you probably used 'append_child' to add the top
1098 // node to an empty tree. From version 1.45 the top element should be added
1099 // using 'insert'. See the documentation for further information, and sorry about
1100 // the API change.
1101 assert(position.node!=head);
1102 assert(position.node!=feet);
1103 assert(position.node);
1104
1105 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1106 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, x);
1107 tmp->first_child=0;
1108 tmp->last_child=0;
1109
1110 tmp->parent=position.node;
1111 if(position.node->last_child!=0) {
1112 position.node->last_child->next_sibling=tmp;
1113 }
1114 else {
1115 position.node->first_child=tmp;
1116 }
1117 tmp->prev_sibling=position.node->last_child;
1118 position.node->last_child=tmp;
1119 tmp->next_sibling=0;
1120 return tmp;
1121 }
1122
1123 template <class T, class tree_node_allocator>
1124 template <class iter>
append_child(iter position,T && x)1125 iter tree<T, tree_node_allocator>::append_child(iter position, T&& x)
1126 {
1127 assert(position.node!=head);
1128 assert(position.node!=feet);
1129 assert(position.node);
1130
1131 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1132 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp); // Here is where the move semantics kick in
1133 std::swap(tmp->data, x);
1134
1135 tmp->first_child=0;
1136 tmp->last_child=0;
1137
1138 tmp->parent=position.node;
1139 if(position.node->last_child!=0) {
1140 position.node->last_child->next_sibling=tmp;
1141 }
1142 else {
1143 position.node->first_child=tmp;
1144 }
1145 tmp->prev_sibling=position.node->last_child;
1146 position.node->last_child=tmp;
1147 tmp->next_sibling=0;
1148 return tmp;
1149 }
1150
1151 template <class T, class tree_node_allocator>
1152 template <class iter>
prepend_child(iter position,const T & x)1153 iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
1154 {
1155 assert(position.node!=head);
1156 assert(position.node!=feet);
1157 assert(position.node);
1158
1159 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1160 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, x);
1161 tmp->first_child=0;
1162 tmp->last_child=0;
1163
1164 tmp->parent=position.node;
1165 if(position.node->first_child!=0) {
1166 position.node->first_child->prev_sibling=tmp;
1167 }
1168 else {
1169 position.node->last_child=tmp;
1170 }
1171 tmp->next_sibling=position.node->first_child;
1172 position.node->first_child=tmp;
1173 tmp->prev_sibling=0;
1174 return tmp;
1175 }
1176
1177 template <class T, class tree_node_allocator>
1178 template <class iter>
prepend_child(iter position,T && x)1179 iter tree<T, tree_node_allocator>::prepend_child(iter position, T&& x)
1180 {
1181 assert(position.node!=head);
1182 assert(position.node!=feet);
1183 assert(position.node);
1184
1185 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1186 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp);
1187 std::swap(tmp->data, x);
1188
1189 tmp->first_child=0;
1190 tmp->last_child=0;
1191
1192 tmp->parent=position.node;
1193 if(position.node->first_child!=0) {
1194 position.node->first_child->prev_sibling=tmp;
1195 }
1196 else {
1197 position.node->last_child=tmp;
1198 }
1199 tmp->next_sibling=position.node->first_child;
1200 position.node->first_child=tmp;
1201 tmp->prev_sibling=0;
1202 return tmp;
1203 }
1204
1205 template <class T, class tree_node_allocator>
1206 template <class iter>
append_child(iter position,iter other)1207 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
1208 {
1209 assert(position.node!=head);
1210 assert(position.node!=feet);
1211 assert(position.node);
1212
1213 sibling_iterator aargh=append_child(position, value_type());
1214 return replace(aargh, other);
1215 }
1216
1217 template <class T, class tree_node_allocator>
1218 template <class iter>
prepend_child(iter position,iter other)1219 iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
1220 {
1221 assert(position.node!=head);
1222 assert(position.node!=feet);
1223 assert(position.node);
1224
1225 sibling_iterator aargh=prepend_child(position, value_type());
1226 return replace(aargh, other);
1227 }
1228
1229 template <class T, class tree_node_allocator>
1230 template <class iter>
append_children(iter position,sibling_iterator from,sibling_iterator to)1231 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
1232 {
1233 assert(position.node!=head);
1234 assert(position.node!=feet);
1235 assert(position.node);
1236
1237 iter ret=from;
1238
1239 while(from!=to) {
1240 insert_subtree(position.end(), from);
1241 ++from;
1242 }
1243 return ret;
1244 }
1245
1246 template <class T, class tree_node_allocator>
1247 template <class iter>
prepend_children(iter position,sibling_iterator from,sibling_iterator to)1248 iter tree<T, tree_node_allocator>::prepend_children(iter position, sibling_iterator from, sibling_iterator to)
1249 {
1250 assert(position.node!=head);
1251 assert(position.node!=feet);
1252 assert(position.node);
1253
1254 if(from==to) return from; // should return end of tree?
1255
1256 iter ret;
1257 do {
1258 --to;
1259 ret=insert_subtree(position.begin(), to);
1260 }
1261 while(to!=from);
1262
1263 return ret;
1264 }
1265
1266 template <class T, class tree_node_allocator>
set_head(const T & x)1267 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
1268 {
1269 assert(head->next_sibling==feet);
1270 return insert(iterator(feet), x);
1271 }
1272
1273 template <class T, class tree_node_allocator>
set_head(T && x)1274 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(T&& x)
1275 {
1276 assert(head->next_sibling==feet);
1277 return insert(iterator(feet), x);
1278 }
1279
1280 template <class T, class tree_node_allocator>
1281 template <class iter>
insert(iter position,const T & x)1282 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
1283 {
1284 if(position.node==0) {
1285 position.node=feet; // Backward compatibility: when calling insert on a null node,
1286 // insert before the feet.
1287 }
1288 assert(position.node!=head); // Cannot insert before head.
1289
1290 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1291 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, x);
1292 tmp->first_child=0;
1293 tmp->last_child=0;
1294
1295 tmp->parent=position.node->parent;
1296 tmp->next_sibling=position.node;
1297 tmp->prev_sibling=position.node->prev_sibling;
1298 position.node->prev_sibling=tmp;
1299
1300 if(tmp->prev_sibling==0) {
1301 if(tmp->parent) // when inserting nodes at the head, there is no parent
1302 tmp->parent->first_child=tmp;
1303 }
1304 else
1305 tmp->prev_sibling->next_sibling=tmp;
1306 return tmp;
1307 }
1308
1309 template <class T, class tree_node_allocator>
1310 template <class iter>
insert(iter position,T && x)1311 iter tree<T, tree_node_allocator>::insert(iter position, T&& x)
1312 {
1313 if(position.node==0) {
1314 position.node=feet; // Backward compatibility: when calling insert on a null node,
1315 // insert before the feet.
1316 }
1317 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1318 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp);
1319 std::swap(tmp->data, x); // Move semantics
1320 tmp->first_child=0;
1321 tmp->last_child=0;
1322
1323 tmp->parent=position.node->parent;
1324 tmp->next_sibling=position.node;
1325 tmp->prev_sibling=position.node->prev_sibling;
1326 position.node->prev_sibling=tmp;
1327
1328 if(tmp->prev_sibling==0) {
1329 if(tmp->parent) // when inserting nodes at the head, there is no parent
1330 tmp->parent->first_child=tmp;
1331 }
1332 else
1333 tmp->prev_sibling->next_sibling=tmp;
1334 return tmp;
1335 }
1336
1337 template <class T, class tree_node_allocator>
insert(sibling_iterator position,const T & x)1338 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
1339 {
1340 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1341 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, x);
1342 tmp->first_child=0;
1343 tmp->last_child=0;
1344
1345 tmp->next_sibling=position.node;
1346 if(position.node==0) { // iterator points to end of a subtree
1347 tmp->parent=position.parent_;
1348 tmp->prev_sibling=position.range_last();
1349 tmp->parent->last_child=tmp;
1350 }
1351 else {
1352 tmp->parent=position.node->parent;
1353 tmp->prev_sibling=position.node->prev_sibling;
1354 position.node->prev_sibling=tmp;
1355 }
1356
1357 if(tmp->prev_sibling==0) {
1358 if(tmp->parent) // when inserting nodes at the head, there is no parent
1359 tmp->parent->first_child=tmp;
1360 }
1361 else
1362 tmp->prev_sibling->next_sibling=tmp;
1363 return tmp;
1364 }
1365
1366 template <class T, class tree_node_allocator>
1367 template <class iter>
insert_after(iter position,const T & x)1368 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
1369 {
1370 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1371 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, x);
1372 tmp->first_child=0;
1373 tmp->last_child=0;
1374
1375 tmp->parent=position.node->parent;
1376 tmp->prev_sibling=position.node;
1377 tmp->next_sibling=position.node->next_sibling;
1378 position.node->next_sibling=tmp;
1379
1380 if(tmp->next_sibling==0) {
1381 if(tmp->parent) // when inserting nodes at the head, there is no parent
1382 tmp->parent->last_child=tmp;
1383 }
1384 else {
1385 tmp->next_sibling->prev_sibling=tmp;
1386 }
1387 return tmp;
1388 }
1389
1390 template <class T, class tree_node_allocator>
1391 template <class iter>
insert_after(iter position,T && x)1392 iter tree<T, tree_node_allocator>::insert_after(iter position, T&& x)
1393 {
1394 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1395 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp);
1396 std::swap(tmp->data, x); // move semantics
1397 tmp->first_child=0;
1398 tmp->last_child=0;
1399
1400 tmp->parent=position.node->parent;
1401 tmp->prev_sibling=position.node;
1402 tmp->next_sibling=position.node->next_sibling;
1403 position.node->next_sibling=tmp;
1404
1405 if(tmp->next_sibling==0) {
1406 if(tmp->parent) // when inserting nodes at the head, there is no parent
1407 tmp->parent->last_child=tmp;
1408 }
1409 else {
1410 tmp->next_sibling->prev_sibling=tmp;
1411 }
1412 return tmp;
1413 }
1414
1415 template <class T, class tree_node_allocator>
1416 template <class iter>
insert_subtree(iter position,const iterator_base & subtree)1417 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
1418 {
1419 // insert dummy
1420 iter it=insert(position, value_type());
1421 // replace dummy with subtree
1422 return replace(it, subtree);
1423 }
1424
1425 template <class T, class tree_node_allocator>
1426 template <class iter>
insert_subtree_after(iter position,const iterator_base & subtree)1427 iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const iterator_base& subtree)
1428 {
1429 // insert dummy
1430 iter it=insert_after(position, value_type());
1431 // replace dummy with subtree
1432 return replace(it, subtree);
1433 }
1434
1435 // template <class T, class tree_node_allocator>
1436 // template <class iter>
1437 // iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
1438 // {
1439 // // insert dummy
1440 // iter it(insert(position, value_type()));
1441 // // replace dummy with subtree
1442 // return replace(it, subtree);
1443 // }
1444
1445 template <class T, class tree_node_allocator>
1446 template <class iter>
replace(iter position,const T & x)1447 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
1448 {
1449 // kp::destructor(&position.node->data);
1450 // kp::constructor(&position.node->data, x);
1451 position.node->data=x;
1452 // alloc_.destroy(position.node);
1453 // alloc_.construct(position.node, x);
1454 return position;
1455 }
1456
1457 template <class T, class tree_node_allocator>
1458 template <class iter>
replace(iter position,const iterator_base & from)1459 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
1460 {
1461 assert(position.node!=head);
1462 tree_node *current_from=from.node;
1463 tree_node *start_from=from.node;
1464 tree_node *current_to =position.node;
1465
1466 // replace the node at position with head of the replacement tree at from
1467 // std::cout << "warning!" << position.node << std::endl;
1468 erase_children(position);
1469 // std::cout << "no warning!" << std::endl;
1470 tree_node *tmp=std::allocator_traits<decltype(alloc_)>::allocate(alloc_, 1, 0);
1471 std::allocator_traits<decltype(alloc_)>::construct(alloc_, tmp, (*from));
1472 tmp->first_child=0;
1473 tmp->last_child=0;
1474 if(current_to->prev_sibling==0) {
1475 if(current_to->parent!=0)
1476 current_to->parent->first_child=tmp;
1477 }
1478 else {
1479 current_to->prev_sibling->next_sibling=tmp;
1480 }
1481 tmp->prev_sibling=current_to->prev_sibling;
1482 if(current_to->next_sibling==0) {
1483 if(current_to->parent!=0)
1484 current_to->parent->last_child=tmp;
1485 }
1486 else {
1487 current_to->next_sibling->prev_sibling=tmp;
1488 }
1489 tmp->next_sibling=current_to->next_sibling;
1490 tmp->parent=current_to->parent;
1491 // kp::destructor(¤t_to->data);
1492 std::allocator_traits<decltype(alloc_)>::destroy(alloc_, current_to);
1493 std::allocator_traits<decltype(alloc_)>::deallocate(alloc_, current_to, 1);
1494 current_to=tmp;
1495
1496 // only at this stage can we fix 'last'
1497 tree_node *last=from.node->next_sibling;
1498
1499 pre_order_iterator toit=tmp;
1500 // copy all children
1501 do {
1502 assert(current_from!=0);
1503 if(current_from->first_child != 0) {
1504 current_from=current_from->first_child;
1505 toit=append_child(toit, current_from->data);
1506 }
1507 else {
1508 while(current_from->next_sibling==0 && current_from!=start_from) {
1509 current_from=current_from->parent;
1510 toit=parent(toit);
1511 assert(current_from!=0);
1512 }
1513 current_from=current_from->next_sibling;
1514 if(current_from!=last) {
1515 toit=append_child(parent(toit), current_from->data);
1516 }
1517 }
1518 }
1519 while(current_from!=last);
1520
1521 return current_to;
1522 }
1523
1524 template <class T, class tree_node_allocator>
replace(sibling_iterator orig_begin,sibling_iterator orig_end,sibling_iterator new_begin,sibling_iterator new_end)1525 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
1526 sibling_iterator orig_begin,
1527 sibling_iterator orig_end,
1528 sibling_iterator new_begin,
1529 sibling_iterator new_end)
1530 {
1531 tree_node *orig_first=orig_begin.node;
1532 tree_node *new_first=new_begin.node;
1533 tree_node *orig_last=orig_first;
1534 while((++orig_begin)!=orig_end)
1535 orig_last=orig_last->next_sibling;
1536 tree_node *new_last=new_first;
1537 while((++new_begin)!=new_end)
1538 new_last=new_last->next_sibling;
1539
1540 // insert all siblings in new_first..new_last before orig_first
1541 bool first=true;
1542 pre_order_iterator ret;
1543 while(1==1) {
1544 pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
1545 if(first) {
1546 ret=tt;
1547 first=false;
1548 }
1549 if(new_first==new_last)
1550 break;
1551 new_first=new_first->next_sibling;
1552 }
1553
1554 // erase old range of siblings
1555 bool last=false;
1556 tree_node *next=orig_first;
1557 while(1==1) {
1558 if(next==orig_last)
1559 last=true;
1560 next=next->next_sibling;
1561 erase((pre_order_iterator)orig_first);
1562 if(last)
1563 break;
1564 orig_first=next;
1565 }
1566 return ret;
1567 }
1568
1569 template <class T, class tree_node_allocator>
1570 template <typename iter>
flatten(iter position)1571 iter tree<T, tree_node_allocator>::flatten(iter position)
1572 {
1573 if(position.node->first_child==0)
1574 return position;
1575
1576 tree_node *tmp=position.node->first_child;
1577 while(tmp) {
1578 tmp->parent=position.node->parent;
1579 tmp=tmp->next_sibling;
1580 }
1581 if(position.node->next_sibling) {
1582 position.node->last_child->next_sibling=position.node->next_sibling;
1583 position.node->next_sibling->prev_sibling=position.node->last_child;
1584 }
1585 else {
1586 position.node->parent->last_child=position.node->last_child;
1587 }
1588 position.node->next_sibling=position.node->first_child;
1589 position.node->next_sibling->prev_sibling=position.node;
1590 position.node->first_child=0;
1591 position.node->last_child=0;
1592
1593 return position;
1594 }
1595
1596
1597 template <class T, class tree_node_allocator>
1598 template <typename iter>
reparent(iter position,sibling_iterator begin,sibling_iterator end)1599 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
1600 {
1601 tree_node *first=begin.node;
1602 tree_node *last=first;
1603
1604 assert(first!=position.node);
1605
1606 if(begin==end) return begin;
1607 // determine last node
1608 while((++begin)!=end) {
1609 last=last->next_sibling;
1610 }
1611 // move subtree
1612 if(first->prev_sibling==0) {
1613 first->parent->first_child=last->next_sibling;
1614 }
1615 else {
1616 first->prev_sibling->next_sibling=last->next_sibling;
1617 }
1618 if(last->next_sibling==0) {
1619 last->parent->last_child=first->prev_sibling;
1620 }
1621 else {
1622 last->next_sibling->prev_sibling=first->prev_sibling;
1623 }
1624 if(position.node->first_child==0) {
1625 position.node->first_child=first;
1626 position.node->last_child=last;
1627 first->prev_sibling=0;
1628 }
1629 else {
1630 position.node->last_child->next_sibling=first;
1631 first->prev_sibling=position.node->last_child;
1632 position.node->last_child=last;
1633 }
1634 last->next_sibling=0;
1635
1636 tree_node *pos=first;
1637 for(;;) {
1638 pos->parent=position.node;
1639 if(pos==last) break;
1640 pos=pos->next_sibling;
1641 }
1642
1643 return first;
1644 }
1645
1646 template <class T, class tree_node_allocator>
reparent(iter position,iter from)1647 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
1648 {
1649 if(from.node->first_child==0) return position;
1650 return reparent(position, from.node->first_child, end(from));
1651 }
1652
1653 template <class T, class tree_node_allocator>
wrap(iter position,const T & x)1654 template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter position, const T& x)
1655 {
1656 assert(position.node!=0);
1657 sibling_iterator fr=position, to=position;
1658 ++to;
1659 iter ret = insert(position, x);
1660 reparent(ret, fr, to);
1661 return ret;
1662 }
1663
1664 template <class T, class tree_node_allocator>
wrap(iter from,iter to,const T & x)1665 template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter from, iter to, const T& x)
1666 {
1667 assert(from.node!=0);
1668 iter ret = insert(from, x);
1669 reparent(ret, from, to);
1670 return ret;
1671 }
1672
1673 template <class T, class tree_node_allocator>
move_after(iter target,iter source)1674 template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
1675 {
1676 tree_node *dst=target.node;
1677 tree_node *src=source.node;
1678 assert(dst);
1679 assert(src);
1680
1681 if(dst==src) return source;
1682 if(dst->next_sibling)
1683 if(dst->next_sibling==src) // already in the right spot
1684 return source;
1685
1686 // take src out of the tree
1687 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1688 else src->parent->first_child=src->next_sibling;
1689 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1690 else src->parent->last_child=src->prev_sibling;
1691
1692 // connect it to the new point
1693 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
1694 else dst->parent->last_child=src;
1695 src->next_sibling=dst->next_sibling;
1696 dst->next_sibling=src;
1697 src->prev_sibling=dst;
1698 src->parent=dst->parent;
1699 return src;
1700 }
1701
1702 template <class T, class tree_node_allocator>
move_before(iter target,iter source)1703 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
1704 {
1705 tree_node *dst=target.node;
1706 tree_node *src=source.node;
1707 assert(dst);
1708 assert(src);
1709
1710 if(dst==src) return source;
1711 if(dst->prev_sibling)
1712 if(dst->prev_sibling==src) // already in the right spot
1713 return source;
1714
1715 // take src out of the tree
1716 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1717 else src->parent->first_child=src->next_sibling;
1718 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1719 else src->parent->last_child=src->prev_sibling;
1720
1721 // connect it to the new point
1722 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1723 else dst->parent->first_child=src;
1724 src->prev_sibling=dst->prev_sibling;
1725 dst->prev_sibling=src;
1726 src->next_sibling=dst;
1727 src->parent=dst->parent;
1728 return src;
1729 }
1730
1731 // specialisation for sibling_iterators
1732 template <class T, class tree_node_allocator>
move_before(sibling_iterator target,sibling_iterator source)1733 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::move_before(sibling_iterator target,
1734 sibling_iterator source)
1735 {
1736 tree_node *dst=target.node;
1737 tree_node *src=source.node;
1738 tree_node *dst_prev_sibling;
1739 if(dst==0) { // must then be an end iterator
1740 dst_prev_sibling=target.parent_->last_child;
1741 assert(dst_prev_sibling);
1742 }
1743 else dst_prev_sibling=dst->prev_sibling;
1744 assert(src);
1745
1746 if(dst==src) return source;
1747 if(dst_prev_sibling)
1748 if(dst_prev_sibling==src) // already in the right spot
1749 return source;
1750
1751 // take src out of the tree
1752 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1753 else src->parent->first_child=src->next_sibling;
1754 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1755 else src->parent->last_child=src->prev_sibling;
1756
1757 // connect it to the new point
1758 if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
1759 else target.parent_->first_child=src;
1760 src->prev_sibling=dst_prev_sibling;
1761 if(dst) {
1762 dst->prev_sibling=src;
1763 src->parent=dst->parent;
1764 }
1765 else {
1766 src->parent=dst_prev_sibling->parent;
1767 }
1768 src->next_sibling=dst;
1769 return src;
1770 }
1771
1772 template <class T, class tree_node_allocator>
move_ontop(iter target,iter source)1773 template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
1774 {
1775 tree_node *dst=target.node;
1776 tree_node *src=source.node;
1777 assert(dst);
1778 assert(src);
1779
1780 if(dst==src) return source;
1781
1782 // if(dst==src->prev_sibling) {
1783 //
1784 // }
1785
1786 // remember connection points
1787 tree_node *b_prev_sibling=dst->prev_sibling;
1788 tree_node *b_next_sibling=dst->next_sibling;
1789 tree_node *b_parent=dst->parent;
1790
1791 // remove target
1792 erase(target);
1793
1794 // take src out of the tree
1795 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1796 else {
1797 assert(src->parent!=0);
1798 src->parent->first_child=src->next_sibling;
1799 }
1800 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1801 else {
1802 assert(src->parent!=0);
1803 src->parent->last_child=src->prev_sibling;
1804 }
1805
1806 // connect it to the new point
1807 if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
1808 else {
1809 assert(b_parent!=0);
1810 b_parent->first_child=src;
1811 }
1812 if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
1813 else {
1814 assert(b_parent!=0);
1815 b_parent->last_child=src;
1816 }
1817 src->prev_sibling=b_prev_sibling;
1818 src->next_sibling=b_next_sibling;
1819 src->parent=b_parent;
1820 return src;
1821 }
1822
1823
1824 template <class T, class tree_node_allocator>
move_out(iterator source)1825 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::move_out(iterator source)
1826 {
1827 tree ret;
1828
1829 // Move source node into the 'ret' tree.
1830 ret.head->next_sibling = source.node;
1831 ret.feet->prev_sibling = source.node;
1832 source.node->parent=0;
1833
1834 // Close the links in the current tree.
1835 if(source.node->prev_sibling!=0)
1836 source.node->prev_sibling->next_sibling = source.node->next_sibling;
1837
1838 if(source.node->next_sibling!=0)
1839 source.node->next_sibling->prev_sibling = source.node->prev_sibling;
1840
1841 // Fix source prev/next links.
1842 source.node->prev_sibling = ret.head;
1843 source.node->next_sibling = ret.feet;
1844
1845 return ret; // A good compiler will move this, not copy.
1846 }
1847
1848 template <class T, class tree_node_allocator>
move_in(iter loc,tree & other)1849 template<typename iter> iter tree<T, tree_node_allocator>::move_in(iter loc, tree& other)
1850 {
1851 if(other.head->next_sibling==other.feet) return loc; // other tree is empty
1852
1853 tree_node *other_first_head = other.head->next_sibling;
1854 tree_node *other_last_head = other.feet->prev_sibling;
1855
1856 sibling_iterator prev(loc);
1857 --prev;
1858
1859 prev.node->next_sibling = other_first_head;
1860 loc.node->prev_sibling = other_last_head;
1861 other_first_head->prev_sibling = prev.node;
1862 other_last_head->next_sibling = loc.node;
1863
1864 // Adjust parent pointers.
1865 tree_node *walk=other_first_head;
1866 while(true) {
1867 walk->parent=loc.node->parent;
1868 if(walk==other_last_head)
1869 break;
1870 walk=walk->next_sibling;
1871 }
1872
1873 // Close other tree.
1874 other.head->next_sibling=other.feet;
1875 other.feet->prev_sibling=other.head;
1876
1877 return other_first_head;
1878 }
1879
1880 template <class T, class tree_node_allocator>
move_in_below(iter loc,tree & other)1881 template<typename iter> iter tree<T, tree_node_allocator>::move_in_below(iter loc, tree& other)
1882 {
1883 if(other.head->next_sibling==other.feet) return loc; // other tree is empty
1884
1885 auto n = other.number_of_children(loc);
1886 return move_in_as_nth_child(loc, n, other);
1887 }
1888
1889 template <class T, class tree_node_allocator>
move_in_as_nth_child(iter loc,size_t n,tree & other)1890 template<typename iter> iter tree<T, tree_node_allocator>::move_in_as_nth_child(iter loc, size_t n, tree& other)
1891 {
1892 if(other.head->next_sibling==other.feet) return loc; // other tree is empty
1893
1894 tree_node *other_first_head = other.head->next_sibling;
1895 tree_node *other_last_head = other.feet->prev_sibling;
1896
1897 if(n==0) {
1898 if(loc.node->first_child==0) {
1899 loc.node->first_child=other_first_head;
1900 loc.node->last_child=other_last_head;
1901 other_last_head->next_sibling=0;
1902 other_first_head->prev_sibling=0;
1903 }
1904 else {
1905 loc.node->first_child->prev_sibling=other_last_head;
1906 other_last_head->next_sibling=loc.node->first_child;
1907 loc.node->first_child=other_first_head;
1908 other_first_head->prev_sibling=0;
1909 }
1910 }
1911 else {
1912 --n;
1913 tree_node *walk = loc.node->first_child;
1914 while(true) {
1915 if(walk==0)
1916 throw std::range_error("tree: move_in_as_nth_child position out of range");
1917 if(n==0)
1918 break;
1919 --n;
1920 walk = walk->next_sibling;
1921 }
1922 if(walk->next_sibling==0)
1923 loc.node->last_child=other_last_head;
1924 else
1925 walk->next_sibling->prev_sibling=other_last_head;
1926 other_last_head->next_sibling=walk->next_sibling;
1927 walk->next_sibling=other_first_head;
1928 other_first_head->prev_sibling=walk;
1929 }
1930
1931 // Adjust parent pointers.
1932 tree_node *walk=other_first_head;
1933 while(true) {
1934 walk->parent=loc.node;
1935 if(walk==other_last_head)
1936 break;
1937 walk=walk->next_sibling;
1938 }
1939
1940 // Close other tree.
1941 other.head->next_sibling=other.feet;
1942 other.feet->prev_sibling=other.head;
1943
1944 return other_first_head;
1945 }
1946
1947
1948 template <class T, class tree_node_allocator>
merge(sibling_iterator to1,sibling_iterator to2,sibling_iterator from1,sibling_iterator from2,bool duplicate_leaves)1949 void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
1950 sibling_iterator from1, sibling_iterator from2,
1951 bool duplicate_leaves)
1952 {
1953 sibling_iterator fnd;
1954 while(from1!=from2) {
1955 if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
1956 if(from1.begin()==from1.end()) { // full depth reached
1957 if(duplicate_leaves)
1958 append_child(parent(to1), (*from1));
1959 }
1960 else { // descend further
1961 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1962 }
1963 }
1964 else { // element missing
1965 insert_subtree(to2, from1);
1966 }
1967 ++from1;
1968 }
1969 }
1970
1971 template <class T, class tree_node_allocator>
merge(iterator to,iterator from,bool duplicate_leaves)1972 void tree<T, tree_node_allocator>::merge(iterator to, iterator from, bool duplicate_leaves)
1973 {
1974 sibling_iterator to1(to);
1975 sibling_iterator to2=to1;
1976 ++to2;
1977 sibling_iterator from1(from);
1978 sibling_iterator from2=from1;
1979 ++from2;
1980
1981 merge(to1, to2, from1, from2, duplicate_leaves);
1982 }
1983
1984
1985 template <class T, class tree_node_allocator>
sort(sibling_iterator from,sibling_iterator to,bool deep)1986 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
1987 {
1988 std::less<T> comp;
1989 sort(from, to, comp, deep);
1990 }
1991
1992 template <class T, class tree_node_allocator>
1993 template <class StrictWeakOrdering>
sort(sibling_iterator from,sibling_iterator to,StrictWeakOrdering comp,bool deep)1994 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
1995 StrictWeakOrdering comp, bool deep)
1996 {
1997 if(from==to) return;
1998 // make list of sorted nodes
1999 // CHECK: if multiset stores equivalent nodes in the order in which they
2000 // are inserted, then this routine should be called 'stable_sort'.
2001 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
2002 sibling_iterator it=from, it2=to;
2003 while(it != to) {
2004 nodes.insert(it.node);
2005 ++it;
2006 }
2007 // reassemble
2008 --it2;
2009
2010 // prev and next are the nodes before and after the sorted range
2011 tree_node *prev=from.node->prev_sibling;
2012 tree_node *next=it2.node->next_sibling;
2013 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
2014 if(prev==0) {
2015 if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
2016 (*nit)->parent->first_child=(*nit);
2017 }
2018 else prev->next_sibling=(*nit);
2019
2020 --eit;
2021 while(nit!=eit) {
2022 (*nit)->prev_sibling=prev;
2023 if(prev)
2024 prev->next_sibling=(*nit);
2025 prev=(*nit);
2026 ++nit;
2027 }
2028 // prev now points to the last-but-one node in the sorted range
2029 if(prev)
2030 prev->next_sibling=(*eit);
2031
2032 // eit points to the last node in the sorted range.
2033 (*eit)->next_sibling=next;
2034 (*eit)->prev_sibling=prev; // missed in the loop above
2035 if(next==0) {
2036 if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
2037 (*eit)->parent->last_child=(*eit);
2038 }
2039 else next->prev_sibling=(*eit);
2040
2041 if(deep) { // sort the children of each node too
2042 sibling_iterator bcs(*nodes.begin());
2043 sibling_iterator ecs(*eit);
2044 ++ecs;
2045 while(bcs!=ecs) {
2046 sort(begin(bcs), end(bcs), comp, deep);
2047 ++bcs;
2048 }
2049 }
2050 }
2051
2052 template <class T, class tree_node_allocator>
2053 template <typename iter>
equal(const iter & one_,const iter & two,const iter & three_) const2054 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
2055 {
2056 std::equal_to<T> comp;
2057 return equal(one_, two, three_, comp);
2058 }
2059
2060 template <class T, class tree_node_allocator>
2061 template <typename iter>
equal_subtree(const iter & one_,const iter & two_) const2062 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
2063 {
2064 std::equal_to<T> comp;
2065 return equal_subtree(one_, two_, comp);
2066 }
2067
2068 template <class T, class tree_node_allocator>
2069 template <typename iter, class BinaryPredicate>
equal(const iter & one_,const iter & two,const iter & three_,BinaryPredicate fun) const2070 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
2071 {
2072 pre_order_iterator one(one_), three(three_);
2073
2074 // if(one==two && is_valid(three) && three.number_of_children()!=0)
2075 // return false;
2076 while(one!=two && is_valid(three)) {
2077 if(!fun(*one,*three))
2078 return false;
2079 if(one.number_of_children()!=three.number_of_children())
2080 return false;
2081 ++one;
2082 ++three;
2083 }
2084 return true;
2085 }
2086
2087 template <class T, class tree_node_allocator>
2088 template <typename iter, class BinaryPredicate>
equal_subtree(const iter & one_,const iter & two_,BinaryPredicate fun) const2089 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
2090 {
2091 pre_order_iterator one(one_), two(two_);
2092
2093 if(!fun(*one,*two)) return false;
2094 if(number_of_children(one)!=number_of_children(two)) return false;
2095 return equal(begin(one),end(one),begin(two),fun);
2096 }
2097
2098 template <class T, class tree_node_allocator>
subtree(sibling_iterator from,sibling_iterator to) const2099 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
2100 {
2101 assert(from!=to); // if from==to, the range is empty, hence no tree to return.
2102
2103 tree tmp;
2104 tmp.set_head(value_type());
2105 tmp.replace(tmp.begin(), tmp.end(), from, to);
2106 return tmp;
2107 }
2108
2109 template <class T, class tree_node_allocator>
subtree(tree & tmp,sibling_iterator from,sibling_iterator to) const2110 void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
2111 {
2112 assert(from!=to); // if from==to, the range is empty, hence no tree to return.
2113
2114 tmp.set_head(value_type());
2115 tmp.replace(tmp.begin(), tmp.end(), from, to);
2116 }
2117
2118 template <class T, class tree_node_allocator>
size() const2119 size_t tree<T, tree_node_allocator>::size() const
2120 {
2121 size_t i=0;
2122 pre_order_iterator it=begin(), eit=end();
2123 while(it!=eit) {
2124 ++i;
2125 ++it;
2126 }
2127 return i;
2128 }
2129
2130 template <class T, class tree_node_allocator>
size(const iterator_base & top) const2131 size_t tree<T, tree_node_allocator>::size(const iterator_base& top) const
2132 {
2133 size_t i=0;
2134 pre_order_iterator it=top, eit=top;
2135 eit.skip_children();
2136 ++eit;
2137 while(it!=eit) {
2138 ++i;
2139 ++it;
2140 }
2141 return i;
2142 }
2143
2144 template <class T, class tree_node_allocator>
empty() const2145 bool tree<T, tree_node_allocator>::empty() const
2146 {
2147 pre_order_iterator it=begin(), eit=end();
2148 return (it==eit);
2149 }
2150
2151 template <class T, class tree_node_allocator>
depth(const iterator_base & it)2152 int tree<T, tree_node_allocator>::depth(const iterator_base& it)
2153 {
2154 tree_node* pos=it.node;
2155 assert(pos!=0);
2156 int ret=0;
2157 while(pos->parent!=0) {
2158 pos=pos->parent;
2159 ++ret;
2160 }
2161 return ret;
2162 }
2163
2164 template <class T, class tree_node_allocator>
depth(const iterator_base & it,const iterator_base & root)2165 int tree<T, tree_node_allocator>::depth(const iterator_base& it, const iterator_base& root)
2166 {
2167 tree_node* pos=it.node;
2168 assert(pos!=0);
2169 int ret=0;
2170 while(pos->parent!=0 && pos!=root.node) {
2171 pos=pos->parent;
2172 ++ret;
2173 }
2174 return ret;
2175 }
2176
2177 template <class T, class tree_node_allocator>
2178 template <class Predicate>
depth(const iterator_base & it,Predicate p)2179 int tree<T, tree_node_allocator>::depth(const iterator_base& it, Predicate p)
2180 {
2181 tree_node* pos=it.node;
2182 assert(pos!=0);
2183 int ret=0;
2184 while(pos->parent!=0) {
2185 pos=pos->parent;
2186 if(p(pos))
2187 ++ret;
2188 }
2189 return ret;
2190 }
2191
2192 template <class T, class tree_node_allocator>
2193 template <class Predicate>
distance(const iterator_base & top,const iterator_base & bottom,Predicate p)2194 int tree<T, tree_node_allocator>::distance(const iterator_base& top, const iterator_base& bottom, Predicate p)
2195 {
2196 tree_node* pos=bottom.node;
2197 assert(pos!=0);
2198 int ret=0;
2199 while(pos->parent!=0 && pos!=top.node) {
2200 pos=pos->parent;
2201 if(p(pos))
2202 ++ret;
2203 }
2204 return ret;
2205 }
2206
2207 template <class T, class tree_node_allocator>
max_depth() const2208 int tree<T, tree_node_allocator>::max_depth() const
2209 {
2210 int maxd=-1;
2211 for(tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)
2212 maxd=std::max(maxd, max_depth(it));
2213
2214 return maxd;
2215 }
2216
2217
2218 template <class T, class tree_node_allocator>
max_depth(const iterator_base & pos) const2219 int tree<T, tree_node_allocator>::max_depth(const iterator_base& pos) const
2220 {
2221 tree_node *tmp=pos.node;
2222
2223 if(tmp==0 || tmp==head || tmp==feet) return -1;
2224
2225 int curdepth=0, maxdepth=0;
2226 while(true) { // try to walk the bottom of the tree
2227 while(tmp->first_child==0) {
2228 if(tmp==pos.node) return maxdepth;
2229 if(tmp->next_sibling==0) {
2230 // try to walk up and then right again
2231 do {
2232 tmp=tmp->parent;
2233 if(tmp==0) return maxdepth;
2234 --curdepth;
2235 }
2236 while(tmp->next_sibling==0);
2237 }
2238 if(tmp==pos.node) return maxdepth;
2239 tmp=tmp->next_sibling;
2240 }
2241 tmp=tmp->first_child;
2242 ++curdepth;
2243 maxdepth=std::max(curdepth, maxdepth);
2244 }
2245 }
2246
2247 template <class T, class tree_node_allocator>
number_of_children(const iterator_base & it)2248 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it)
2249 {
2250 tree_node *pos=it.node->first_child;
2251 if(pos==0) return 0;
2252
2253 unsigned int ret=1;
2254 // while(pos!=it.node->last_child) {
2255 // ++ret;
2256 // pos=pos->next_sibling;
2257 // }
2258 while((pos=pos->next_sibling))
2259 ++ret;
2260 return ret;
2261 }
2262
2263 template <class T, class tree_node_allocator>
number_of_siblings(const iterator_base & it) const2264 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
2265 {
2266 tree_node *pos=it.node;
2267 unsigned int ret=0;
2268 // count forward
2269 while(pos->next_sibling &&
2270 pos->next_sibling!=head &&
2271 pos->next_sibling!=feet) {
2272 ++ret;
2273 pos=pos->next_sibling;
2274 }
2275 // count backward
2276 pos=it.node;
2277 while(pos->prev_sibling &&
2278 pos->prev_sibling!=head &&
2279 pos->prev_sibling!=feet) {
2280 ++ret;
2281 pos=pos->prev_sibling;
2282 }
2283
2284 return ret;
2285 }
2286
2287 template <class T, class tree_node_allocator>
swap(sibling_iterator it)2288 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
2289 {
2290 tree_node *nxt=it.node->next_sibling;
2291 if(nxt) {
2292 if(it.node->prev_sibling)
2293 it.node->prev_sibling->next_sibling=nxt;
2294 else
2295 it.node->parent->first_child=nxt;
2296 nxt->prev_sibling=it.node->prev_sibling;
2297 tree_node *nxtnxt=nxt->next_sibling;
2298 if(nxtnxt)
2299 nxtnxt->prev_sibling=it.node;
2300 else
2301 it.node->parent->last_child=it.node;
2302 nxt->next_sibling=it.node;
2303 it.node->prev_sibling=nxt;
2304 it.node->next_sibling=nxtnxt;
2305 }
2306 }
2307
2308 template <class T, class tree_node_allocator>
swap(iterator one,iterator two)2309 void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
2310 {
2311 // if one and two are adjacent siblings, use the sibling swap
2312 if(one.node->next_sibling==two.node) swap(one);
2313 else if(two.node->next_sibling==one.node) swap(two);
2314 else {
2315 tree_node *nxt1=one.node->next_sibling;
2316 tree_node *nxt2=two.node->next_sibling;
2317 tree_node *pre1=one.node->prev_sibling;
2318 tree_node *pre2=two.node->prev_sibling;
2319 tree_node *par1=one.node->parent;
2320 tree_node *par2=two.node->parent;
2321
2322 // reconnect
2323 one.node->parent=par2;
2324 one.node->next_sibling=nxt2;
2325 if(nxt2) nxt2->prev_sibling=one.node;
2326 else par2->last_child=one.node;
2327 one.node->prev_sibling=pre2;
2328 if(pre2) pre2->next_sibling=one.node;
2329 else par2->first_child=one.node;
2330
2331 two.node->parent=par1;
2332 two.node->next_sibling=nxt1;
2333 if(nxt1) nxt1->prev_sibling=two.node;
2334 else par1->last_child=two.node;
2335 two.node->prev_sibling=pre1;
2336 if(pre1) pre1->next_sibling=two.node;
2337 else par1->first_child=two.node;
2338 }
2339 }
2340
2341 // template <class BinaryPredicate>
2342 // tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
2343 // sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
2344 // BinaryPredicate fun) const
2345 // {
2346 // assert(1==0); // this routine is not finished yet.
2347 // while(from!=to) {
2348 // if(fun(*subfrom, *from)) {
2349 //
2350 // }
2351 // }
2352 // return to;
2353 // }
2354
2355 template <class T, class tree_node_allocator>
is_in_subtree(const iterator_base & it,const iterator_base & top) const2356 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& top) const
2357 {
2358 sibling_iterator first=top;
2359 sibling_iterator last=first;
2360 ++last;
2361 return is_in_subtree(it, first, last);
2362 }
2363
2364 template <class T, class tree_node_allocator>
is_in_subtree(const iterator_base & it,const iterator_base & begin,const iterator_base & end) const2365 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
2366 const iterator_base& end) const
2367 {
2368 // FIXME: this should be optimised.
2369 pre_order_iterator tmp=begin;
2370 while(tmp!=end) {
2371 if(tmp==it) return true;
2372 ++tmp;
2373 }
2374 return false;
2375 }
2376
2377 template <class T, class tree_node_allocator>
is_valid(const iterator_base & it) const2378 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
2379 {
2380 if(it.node==0 || it.node==feet || it.node==head) return false;
2381 else return true;
2382 }
2383
2384 template <class T, class tree_node_allocator>
is_head(const iterator_base & it)2385 bool tree<T, tree_node_allocator>::is_head(const iterator_base& it)
2386 {
2387 if(it.node->parent==0) return true;
2388 return false;
2389 }
2390
2391 template <class T, class tree_node_allocator>
lowest_common_ancestor(const iterator_base & one,const iterator_base & two) const2392 typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::lowest_common_ancestor(
2393 const iterator_base& one, const iterator_base& two) const
2394 {
2395 std::set<iterator, iterator_base_less> parents;
2396
2397 // Walk up from 'one' storing all parents.
2398 iterator walk=one;
2399 do {
2400 walk=parent(walk);
2401 parents.insert(walk);
2402 }
2403 while( walk.node->parent );
2404
2405 // Walk up from 'two' until we encounter a node in parents.
2406 walk=two;
2407 do {
2408 walk=parent(walk);
2409 if(parents.find(walk) != parents.end()) break;
2410 }
2411 while( walk.node->parent );
2412
2413 return walk;
2414 }
2415
2416 template <class T, class tree_node_allocator>
index(sibling_iterator it) const2417 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
2418 {
2419 unsigned int ind=0;
2420 if(it.node->parent==0) {
2421 while(it.node->prev_sibling!=head) {
2422 it.node=it.node->prev_sibling;
2423 ++ind;
2424 }
2425 }
2426 else {
2427 while(it.node->prev_sibling!=0) {
2428 it.node=it.node->prev_sibling;
2429 ++ind;
2430 }
2431 }
2432 return ind;
2433 }
2434
2435 template <class T, class tree_node_allocator>
sibling(const iterator_base & it,unsigned int num) const2436 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling(const iterator_base& it, unsigned int num) const
2437 {
2438 tree_node *tmp;
2439 if(it.node->parent==0) {
2440 tmp=head->next_sibling;
2441 while(num) {
2442 tmp = tmp->next_sibling;
2443 --num;
2444 }
2445 }
2446 else {
2447 tmp=it.node->parent->first_child;
2448 while(num) {
2449 assert(tmp!=0);
2450 tmp = tmp->next_sibling;
2451 --num;
2452 }
2453 }
2454 return tmp;
2455 }
2456
2457 template <class T, class tree_node_allocator>
debug_verify_consistency() const2458 void tree<T, tree_node_allocator>::debug_verify_consistency() const
2459 {
2460 iterator it=begin();
2461 while(it!=end()) {
2462 // std::cerr << *it << " (" << it.node << ")" << std::endl;
2463 if(it.node->parent!=0) {
2464 if(it.node->prev_sibling==0)
2465 assert(it.node->parent->first_child==it.node);
2466 else
2467 assert(it.node->prev_sibling->next_sibling==it.node);
2468 if(it.node->next_sibling==0)
2469 assert(it.node->parent->last_child==it.node);
2470 else
2471 assert(it.node->next_sibling->prev_sibling==it.node);
2472 }
2473 ++it;
2474 }
2475 }
2476
2477 template <class T, class tree_node_allocator>
child(const iterator_base & it,unsigned int num)2478 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num)
2479 {
2480 tree_node *tmp=it.node->first_child;
2481 while(num--) {
2482 assert(tmp!=0);
2483 tmp=tmp->next_sibling;
2484 }
2485 return tmp;
2486 }
2487
2488
2489
2490
2491 // Iterator base
2492
2493 template <class T, class tree_node_allocator>
iterator_base()2494 tree<T, tree_node_allocator>::iterator_base::iterator_base()
2495 : node(0), skip_current_children_(false)
2496 {
2497 }
2498
2499 template <class T, class tree_node_allocator>
iterator_base(tree_node * tn)2500 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
2501 : node(tn), skip_current_children_(false)
2502 {
2503 }
2504
2505 template <class T, class tree_node_allocator>
2506 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
2507 {
2508 return node->data;
2509 }
2510
2511 template <class T, class tree_node_allocator>
2512 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
2513 {
2514 return &(node->data);
2515 }
2516
2517 template <class T, class tree_node_allocator>
operator !=(const post_order_iterator & other) const2518 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
2519 {
2520 if(other.node!=this->node) return true;
2521 else return false;
2522 }
2523
2524 template <class T, class tree_node_allocator>
operator ==(const post_order_iterator & other) const2525 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
2526 {
2527 if(other.node==this->node) return true;
2528 else return false;
2529 }
2530
2531 template <class T, class tree_node_allocator>
operator !=(const pre_order_iterator & other) const2532 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
2533 {
2534 if(other.node!=this->node) return true;
2535 else return false;
2536 }
2537
2538 template <class T, class tree_node_allocator>
operator ==(const pre_order_iterator & other) const2539 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
2540 {
2541 if(other.node==this->node) return true;
2542 else return false;
2543 }
2544
2545 template <class T, class tree_node_allocator>
operator !=(const sibling_iterator & other) const2546 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
2547 {
2548 if(other.node!=this->node) return true;
2549 else return false;
2550 }
2551
2552 template <class T, class tree_node_allocator>
operator ==(const sibling_iterator & other) const2553 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
2554 {
2555 if(other.node==this->node) return true;
2556 else return false;
2557 }
2558
2559 template <class T, class tree_node_allocator>
operator !=(const leaf_iterator & other) const2560 bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator& other) const
2561 {
2562 if(other.node!=this->node) return true;
2563 else return false;
2564 }
2565
2566 template <class T, class tree_node_allocator>
operator ==(const leaf_iterator & other) const2567 bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator& other) const
2568 {
2569 if(other.node==this->node && other.top_node==this->top_node) return true;
2570 else return false;
2571 }
2572
2573 template <class T, class tree_node_allocator>
begin() const2574 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
2575 {
2576 if(node->first_child==0)
2577 return end();
2578
2579 sibling_iterator ret(node->first_child);
2580 ret.parent_=this->node;
2581 return ret;
2582 }
2583
2584 template <class T, class tree_node_allocator>
end() const2585 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
2586 {
2587 sibling_iterator ret(0);
2588 ret.parent_=node;
2589 return ret;
2590 }
2591
2592 template <class T, class tree_node_allocator>
skip_children()2593 void tree<T, tree_node_allocator>::iterator_base::skip_children()
2594 {
2595 skip_current_children_=true;
2596 }
2597
2598 template <class T, class tree_node_allocator>
skip_children(bool skip)2599 void tree<T, tree_node_allocator>::iterator_base::skip_children(bool skip)
2600 {
2601 skip_current_children_=skip;
2602 }
2603
2604 template <class T, class tree_node_allocator>
number_of_children() const2605 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
2606 {
2607 tree_node *pos=node->first_child;
2608 if(pos==0) return 0;
2609
2610 unsigned int ret=1;
2611 while(pos!=node->last_child) {
2612 ++ret;
2613 pos=pos->next_sibling;
2614 }
2615 return ret;
2616 }
2617
2618
2619
2620 // Pre-order iterator
2621
2622 template <class T, class tree_node_allocator>
pre_order_iterator()2623 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
2624 : iterator_base(0)
2625 {
2626 }
2627
2628 template <class T, class tree_node_allocator>
pre_order_iterator(tree_node * tn)2629 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
2630 : iterator_base(tn)
2631 {
2632 }
2633
2634 template <class T, class tree_node_allocator>
pre_order_iterator(const iterator_base & other)2635 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
2636 : iterator_base(other.node)
2637 {
2638 }
2639
2640 template <class T, class tree_node_allocator>
pre_order_iterator(const sibling_iterator & other)2641 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
2642 : iterator_base(other.node)
2643 {
2644 if(this->node==0) {
2645 if(other.range_last()!=0)
2646 this->node=other.range_last();
2647 else
2648 this->node=other.parent_;
2649 this->skip_children();
2650 ++(*this);
2651 }
2652 }
2653
2654 template <class T, class tree_node_allocator>
operator ++()2655 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
2656 {
2657 assert(this->node!=0);
2658 if(!this->skip_current_children_ && this->node->first_child != 0) {
2659 this->node=this->node->first_child;
2660 }
2661 else {
2662 this->skip_current_children_=false;
2663 while(this->node->next_sibling==0) {
2664 this->node=this->node->parent;
2665 if(this->node==0)
2666 return *this;
2667 }
2668 this->node=this->node->next_sibling;
2669 }
2670 return *this;
2671 }
2672
2673 template <class T, class tree_node_allocator>
operator --()2674 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
2675 {
2676 assert(this->node!=0);
2677 if(this->node->prev_sibling) {
2678 this->node=this->node->prev_sibling;
2679 while(this->node->last_child)
2680 this->node=this->node->last_child;
2681 }
2682 else {
2683 this->node=this->node->parent;
2684 if(this->node==0)
2685 return *this;
2686 }
2687 return *this;
2688 }
2689
2690 template <class T, class tree_node_allocator>
operator ++(int)2691 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int)
2692 {
2693 pre_order_iterator copy = *this;
2694 ++(*this);
2695 return copy;
2696 }
2697
2698 template <class T, class tree_node_allocator>
next_skip_children()2699 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::next_skip_children()
2700 {
2701 (*this).skip_children();
2702 (*this)++;
2703 return *this;
2704 }
2705
2706 template <class T, class tree_node_allocator>
operator --(int)2707 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int)
2708 {
2709 pre_order_iterator copy = *this;
2710 --(*this);
2711 return copy;
2712 }
2713
2714 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2715 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
2716 {
2717 while(num>0) {
2718 ++(*this);
2719 --num;
2720 }
2721 return (*this);
2722 }
2723
2724 template <class T, class tree_node_allocator>
operator -=(unsigned int num)2725 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
2726 {
2727 while(num>0) {
2728 --(*this);
2729 --num;
2730 }
2731 return (*this);
2732 }
2733
2734
2735
2736 // Post-order iterator
2737
2738 template <class T, class tree_node_allocator>
post_order_iterator()2739 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
2740 : iterator_base(0)
2741 {
2742 }
2743
2744 template <class T, class tree_node_allocator>
post_order_iterator(tree_node * tn)2745 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
2746 : iterator_base(tn)
2747 {
2748 }
2749
2750 template <class T, class tree_node_allocator>
post_order_iterator(const iterator_base & other)2751 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
2752 : iterator_base(other.node)
2753 {
2754 }
2755
2756 template <class T, class tree_node_allocator>
post_order_iterator(const sibling_iterator & other)2757 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
2758 : iterator_base(other.node)
2759 {
2760 if(this->node==0) {
2761 if(other.range_last()!=0)
2762 this->node=other.range_last();
2763 else
2764 this->node=other.parent_;
2765 this->skip_children();
2766 ++(*this);
2767 }
2768 }
2769
2770 template <class T, class tree_node_allocator>
operator ++()2771 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
2772 {
2773 assert(this->node!=0);
2774 if(this->node->next_sibling==0) {
2775 this->node=this->node->parent;
2776 this->skip_current_children_=false;
2777 }
2778 else {
2779 this->node=this->node->next_sibling;
2780 if(this->skip_current_children_) {
2781 this->skip_current_children_=false;
2782 }
2783 else {
2784 while(this->node->first_child)
2785 this->node=this->node->first_child;
2786 }
2787 }
2788 return *this;
2789 }
2790
2791 template <class T, class tree_node_allocator>
operator --()2792 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
2793 {
2794 assert(this->node!=0);
2795 if(this->skip_current_children_ || this->node->last_child==0) {
2796 this->skip_current_children_=false;
2797 while(this->node->prev_sibling==0)
2798 this->node=this->node->parent;
2799 this->node=this->node->prev_sibling;
2800 }
2801 else {
2802 this->node=this->node->last_child;
2803 }
2804 return *this;
2805 }
2806
2807 template <class T, class tree_node_allocator>
operator ++(int)2808 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
2809 {
2810 post_order_iterator copy = *this;
2811 ++(*this);
2812 return copy;
2813 }
2814
2815 template <class T, class tree_node_allocator>
operator --(int)2816 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
2817 {
2818 post_order_iterator copy = *this;
2819 --(*this);
2820 return copy;
2821 }
2822
2823
2824 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2825 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
2826 {
2827 while(num>0) {
2828 ++(*this);
2829 --num;
2830 }
2831 return (*this);
2832 }
2833
2834 template <class T, class tree_node_allocator>
operator -=(unsigned int num)2835 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
2836 {
2837 while(num>0) {
2838 --(*this);
2839 --num;
2840 }
2841 return (*this);
2842 }
2843
2844 template <class T, class tree_node_allocator>
descend_all()2845 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
2846 {
2847 assert(this->node!=0);
2848 while(this->node->first_child)
2849 this->node=this->node->first_child;
2850 }
2851
2852
2853 // Breadth-first iterator
2854
2855 template <class T, class tree_node_allocator>
breadth_first_queued_iterator()2856 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
2857 : iterator_base()
2858 {
2859 }
2860
2861 template <class T, class tree_node_allocator>
breadth_first_queued_iterator(tree_node * tn)2862 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)
2863 : iterator_base(tn)
2864 {
2865 traversal_queue.push(tn);
2866 }
2867
2868 template <class T, class tree_node_allocator>
breadth_first_queued_iterator(const iterator_base & other)2869 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const iterator_base& other)
2870 : iterator_base(other.node)
2871 {
2872 traversal_queue.push(other.node);
2873 }
2874
2875 template <class T, class tree_node_allocator>
operator !=(const breadth_first_queued_iterator & other) const2876 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_iterator& other) const
2877 {
2878 if(other.node!=this->node) return true;
2879 else return false;
2880 }
2881
2882 template <class T, class tree_node_allocator>
operator ==(const breadth_first_queued_iterator & other) const2883 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==(const breadth_first_queued_iterator& other) const
2884 {
2885 if(other.node==this->node) return true;
2886 else return false;
2887 }
2888
2889 template <class T, class tree_node_allocator>
operator ++()2890 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()
2891 {
2892 assert(this->node!=0);
2893
2894 // Add child nodes and pop current node
2895 sibling_iterator sib=this->begin();
2896 while(sib!=this->end()) {
2897 traversal_queue.push(sib.node);
2898 ++sib;
2899 }
2900 traversal_queue.pop();
2901 if(traversal_queue.size()>0)
2902 this->node=traversal_queue.front();
2903 else
2904 this->node=0;
2905 return (*this);
2906 }
2907
2908 template <class T, class tree_node_allocator>
operator ++(int)2909 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int)
2910 {
2911 breadth_first_queued_iterator copy = *this;
2912 ++(*this);
2913 return copy;
2914 }
2915
2916 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2917 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)
2918 {
2919 while(num>0) {
2920 ++(*this);
2921 --num;
2922 }
2923 return (*this);
2924 }
2925
2926
2927
2928 // Fixed depth iterator
2929
2930 template <class T, class tree_node_allocator>
fixed_depth_iterator()2931 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
2932 : iterator_base()
2933 {
2934 }
2935
2936 template <class T, class tree_node_allocator>
fixed_depth_iterator(tree_node * tn)2937 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
2938 : iterator_base(tn), top_node(0)
2939 {
2940 }
2941
2942 template <class T, class tree_node_allocator>
fixed_depth_iterator(const iterator_base & other)2943 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
2944 : iterator_base(other.node), top_node(0)
2945 {
2946 }
2947
2948 template <class T, class tree_node_allocator>
fixed_depth_iterator(const sibling_iterator & other)2949 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
2950 : iterator_base(other.node), top_node(0)
2951 {
2952 }
2953
2954 template <class T, class tree_node_allocator>
fixed_depth_iterator(const fixed_depth_iterator & other)2955 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
2956 : iterator_base(other.node), top_node(other.top_node)
2957 {
2958 }
2959
2960 template <class T, class tree_node_allocator>
operator ==(const fixed_depth_iterator & other) const2961 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const fixed_depth_iterator& other) const
2962 {
2963 if(other.node==this->node && other.top_node==top_node) return true;
2964 else return false;
2965 }
2966
2967 template <class T, class tree_node_allocator>
operator !=(const fixed_depth_iterator & other) const2968 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const fixed_depth_iterator& other) const
2969 {
2970 if(other.node!=this->node || other.top_node!=top_node) return true;
2971 else return false;
2972 }
2973
2974 template <class T, class tree_node_allocator>
operator ++()2975 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
2976 {
2977 assert(this->node!=0);
2978
2979 if(this->node->next_sibling) {
2980 this->node=this->node->next_sibling;
2981 }
2982 else {
2983 int relative_depth=0;
2984 upper:
2985 do {
2986 if(this->node==this->top_node) {
2987 this->node=0; // FIXME: return a proper fixed_depth end iterator once implemented
2988 return *this;
2989 }
2990 this->node=this->node->parent;
2991 if(this->node==0) return *this;
2992 --relative_depth;
2993 } while(this->node->next_sibling==0);
2994 lower:
2995 this->node=this->node->next_sibling;
2996 while(this->node->first_child==0) {
2997 if(this->node->next_sibling==0)
2998 goto upper;
2999 this->node=this->node->next_sibling;
3000 if(this->node==0) return *this;
3001 }
3002 while(relative_depth<0 && this->node->first_child!=0) {
3003 this->node=this->node->first_child;
3004 ++relative_depth;
3005 }
3006 if(relative_depth<0) {
3007 if(this->node->next_sibling==0) goto upper;
3008 else goto lower;
3009 }
3010 }
3011 return *this;
3012 }
3013
3014 template <class T, class tree_node_allocator>
operator --()3015 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
3016 {
3017 assert(this->node!=0);
3018
3019 if(this->node->prev_sibling) {
3020 this->node=this->node->prev_sibling;
3021 }
3022 else {
3023 int relative_depth=0;
3024 upper:
3025 do {
3026 if(this->node==this->top_node) {
3027 this->node=0;
3028 return *this;
3029 }
3030 this->node=this->node->parent;
3031 if(this->node==0) return *this;
3032 --relative_depth;
3033 } while(this->node->prev_sibling==0);
3034 lower:
3035 this->node=this->node->prev_sibling;
3036 while(this->node->last_child==0) {
3037 if(this->node->prev_sibling==0)
3038 goto upper;
3039 this->node=this->node->prev_sibling;
3040 if(this->node==0) return *this;
3041 }
3042 while(relative_depth<0 && this->node->last_child!=0) {
3043 this->node=this->node->last_child;
3044 ++relative_depth;
3045 }
3046 if(relative_depth<0) {
3047 if(this->node->prev_sibling==0) goto upper;
3048 else goto lower;
3049 }
3050 }
3051 return *this;
3052
3053 //
3054 //
3055 // assert(this->node!=0);
3056 // if(this->node->prev_sibling!=0) {
3057 // this->node=this->node->prev_sibling;
3058 // assert(this->node!=0);
3059 // if(this->node->parent==0 && this->node->prev_sibling==0) // head element
3060 // this->node=0;
3061 // }
3062 // else {
3063 // tree_node *par=this->node->parent;
3064 // do {
3065 // par=par->prev_sibling;
3066 // if(par==0) { // FIXME: need to keep track of this!
3067 // this->node=0;
3068 // return *this;
3069 // }
3070 // } while(par->last_child==0);
3071 // this->node=par->last_child;
3072 // }
3073 // return *this;
3074 }
3075
3076 template <class T, class tree_node_allocator>
operator ++(int)3077 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
3078 {
3079 fixed_depth_iterator copy = *this;
3080 ++(*this);
3081 return copy;
3082 }
3083
3084 template <class T, class tree_node_allocator>
operator --(int)3085 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
3086 {
3087 fixed_depth_iterator copy = *this;
3088 --(*this);
3089 return copy;
3090 }
3091
3092 template <class T, class tree_node_allocator>
operator -=(unsigned int num)3093 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
3094 {
3095 while(num>0) {
3096 --(*this);
3097 --(num);
3098 }
3099 return (*this);
3100 }
3101
3102 template <class T, class tree_node_allocator>
operator +=(unsigned int num)3103 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
3104 {
3105 while(num>0) {
3106 ++(*this);
3107 --(num);
3108 }
3109 return *this;
3110 }
3111
3112
3113 // Sibling iterator
3114
3115 template <class T, class tree_node_allocator>
sibling_iterator()3116 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
3117 : iterator_base()
3118 {
3119 set_parent_();
3120 }
3121
3122 template <class T, class tree_node_allocator>
sibling_iterator(tree_node * tn)3123 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
3124 : iterator_base(tn)
3125 {
3126 set_parent_();
3127 }
3128
3129 template <class T, class tree_node_allocator>
sibling_iterator(const iterator_base & other)3130 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
3131 : iterator_base(other.node)
3132 {
3133 set_parent_();
3134 }
3135
3136 template <class T, class tree_node_allocator>
sibling_iterator(const sibling_iterator & other)3137 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
3138 : iterator_base(other), parent_(other.parent_)
3139 {
3140 }
3141
3142 template <class T, class tree_node_allocator>
set_parent_()3143 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
3144 {
3145 parent_=0;
3146 if(this->node==0) return;
3147 if(this->node->parent!=0)
3148 parent_=this->node->parent;
3149 }
3150
3151 template <class T, class tree_node_allocator>
operator ++()3152 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
3153 {
3154 if(this->node)
3155 this->node=this->node->next_sibling;
3156 return *this;
3157 }
3158
3159 template <class T, class tree_node_allocator>
operator --()3160 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
3161 {
3162 if(this->node) this->node=this->node->prev_sibling;
3163 else {
3164 assert(parent_);
3165 this->node=parent_->last_child;
3166 }
3167 return *this;
3168 }
3169
3170 template <class T, class tree_node_allocator>
operator ++(int)3171 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
3172 {
3173 sibling_iterator copy = *this;
3174 ++(*this);
3175 return copy;
3176 }
3177
3178 template <class T, class tree_node_allocator>
operator --(int)3179 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
3180 {
3181 sibling_iterator copy = *this;
3182 --(*this);
3183 return copy;
3184 }
3185
3186 template <class T, class tree_node_allocator>
operator +=(unsigned int num)3187 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
3188 {
3189 while(num>0) {
3190 ++(*this);
3191 --num;
3192 }
3193 return (*this);
3194 }
3195
3196 template <class T, class tree_node_allocator>
operator -=(unsigned int num)3197 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
3198 {
3199 while(num>0) {
3200 --(*this);
3201 --num;
3202 }
3203 return (*this);
3204 }
3205
3206 template <class T, class tree_node_allocator>
range_first() const3207 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
3208 {
3209 tree_node *tmp=parent_->first_child;
3210 return tmp;
3211 }
3212
3213 template <class T, class tree_node_allocator>
range_last() const3214 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
3215 {
3216 return parent_->last_child;
3217 }
3218
3219 // Leaf iterator
3220
3221 template <class T, class tree_node_allocator>
leaf_iterator()3222 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()
3223 : iterator_base(0), top_node(0)
3224 {
3225 }
3226
3227 template <class T, class tree_node_allocator>
leaf_iterator(tree_node * tn,tree_node * top)3228 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn, tree_node *top)
3229 : iterator_base(tn), top_node(top)
3230 {
3231 }
3232
3233 template <class T, class tree_node_allocator>
leaf_iterator(const iterator_base & other)3234 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base &other)
3235 : iterator_base(other.node), top_node(0)
3236 {
3237 }
3238
3239 template <class T, class tree_node_allocator>
leaf_iterator(const sibling_iterator & other)3240 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const sibling_iterator& other)
3241 : iterator_base(other.node), top_node(0)
3242 {
3243 if(this->node==0) {
3244 if(other.range_last()!=0)
3245 this->node=other.range_last();
3246 else
3247 this->node=other.parent_;
3248 ++(*this);
3249 }
3250 }
3251
3252 template <class T, class tree_node_allocator>
operator ++()3253 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++()
3254 {
3255 assert(this->node!=0);
3256 if(this->node->first_child!=0) { // current node is no longer leaf (children got added)
3257 while(this->node->first_child)
3258 this->node=this->node->first_child;
3259 }
3260 else {
3261 while(this->node->next_sibling==0) {
3262 if (this->node->parent==0) return *this;
3263 this->node=this->node->parent;
3264 if (top_node != 0 && this->node==top_node) return *this;
3265 }
3266 this->node=this->node->next_sibling;
3267 while(this->node->first_child)
3268 this->node=this->node->first_child;
3269 }
3270 return *this;
3271 }
3272
3273 template <class T, class tree_node_allocator>
operator --()3274 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--()
3275 {
3276 assert(this->node!=0);
3277 while (this->node->prev_sibling==0) {
3278 if (this->node->parent==0) return *this;
3279 this->node=this->node->parent;
3280 if (top_node !=0 && this->node==top_node) return *this;
3281 }
3282 this->node=this->node->prev_sibling;
3283 while(this->node->last_child)
3284 this->node=this->node->last_child;
3285 return *this;
3286 }
3287
3288 template <class T, class tree_node_allocator>
operator ++(int)3289 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++(int)
3290 {
3291 leaf_iterator copy = *this;
3292 ++(*this);
3293 return copy;
3294 }
3295
3296 template <class T, class tree_node_allocator>
operator --(int)3297 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--(int)
3298 {
3299 leaf_iterator copy = *this;
3300 --(*this);
3301 return copy;
3302 }
3303
3304
3305 template <class T, class tree_node_allocator>
operator +=(unsigned int num)3306 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
3307 {
3308 while(num>0) {
3309 ++(*this);
3310 --num;
3311 }
3312 return (*this);
3313 }
3314
3315 template <class T, class tree_node_allocator>
operator -=(unsigned int num)3316 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
3317 {
3318 while(num>0) {
3319 --(*this);
3320 --num;
3321 }
3322 return (*this);
3323 }
3324
3325 #endif
3326
3327 // Local variables:
3328 // tab-width: 3
3329 // End:
3330