1 /*
2 * Tree.hpp
3 *
4 * Copyright (C) 2021 by RStudio, PBC
5 * Copyright (C) 2001-2011 Kasper Peeters <kasper@phi-sci.com>
6 *
7 * Unless you have received this program directly from RStudio pursuant
8 * to the terms of a commercial license agreement with RStudio, then
9 * this program is licensed to you under the terms of version 3 of the
10 * GNU Affero General Public License. This program is distributed WITHOUT
11 * ANY EXPRESS OR IMPLIED WARRANTY, INCLUDING THOSE OF NON-INFRINGEMENT,
12 * MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Please refer to the
13 * AGPL (http://www.gnu.org/licenses/agpl-3.0.txt) for more details.
14 *
15 */
16
17 // STL-like templated tree class.
18 //
19 // Copyright (C) 2001-2011 Kasper Peeters <kasper@phi-sci.com>
20 // Distributed under the GNU General Public License version 3.
21 //
22 // When used together with the htmlcxx library to create
23 // HTML::Node template instances, the GNU Lesser General Public
24 // version 2 applies. Special permission to use tree.hh under
25 // the LGPL for other projects can be requested from the author.
26 //
27 // If you have received this program directly from RStudio pursuant
28 // to the terms of a commercial license then tree.hh is covered
29 // under this same commerical license.
30 //
31
32 /** \mainpage tree.hh
33 \author Kasper Peeters
34 \version 2.81
35 \date 23-Aug-2011
36 \see http://tree.phi-sci.com/
37 \see http://tree.phi-sci.com/ChangeLog
38
39 The tree.hh library for C++ provides an STL-like container class
40 for n-ary trees, templated over the data stored at the
41 nodes. Various types of iterators are provided (post-order,
42 pre-order, and others). Where possible the access methods are
43 compatible with the STL or alternative algorithms are
44 available.
45 */
46
47
48 #ifndef tree_hh_
49 #define tree_hh_
50
51 #include <cassert>
52 #include <memory>
53 #include <stdexcept>
54 #include <iterator>
55 #include <set>
56 #include <queue>
57 #include <algorithm>
58 #include <cstddef>
59
60
61 /// A node in the tree, combining links to other nodes as well as the actual data.
62 template<class T>
63 class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
64 public:
65 tree_node_();
66 tree_node_(const T&);
67
68 tree_node_<T> *parent;
69 tree_node_<T> *first_child, *last_child;
70 tree_node_<T> *prev_sibling, *next_sibling;
71 T data;
72 }; // __attribute__((packed));
73
74 template<class T>
tree_node_()75 tree_node_<T>::tree_node_()
76 : parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0)
77 {
78 }
79
80 template<class T>
tree_node_(const T & val)81 tree_node_<T>::tree_node_(const T& val)
82 : parent(0), first_child(0), last_child(0), prev_sibling(0), next_sibling(0), data(val)
83 {
84 }
85
86 template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
87 class tree {
88 protected:
89 typedef tree_node_<T> tree_node;
90 public:
91 /// Value of the data stored at a node.
92 typedef T value_type;
93
94 class iterator_base;
95 class pre_order_iterator;
96 class post_order_iterator;
97 class sibling_iterator;
98 class leaf_iterator;
99
100 tree();
101 tree(const T&);
102 tree(const iterator_base&);
103 tree(const tree<T, tree_node_allocator>&);
104 ~tree();
105 tree<T,tree_node_allocator>& operator=(const tree<T, tree_node_allocator>&);
106
107 /// Base class for iterators, only pointers stored, no traversal logic.
108 #ifdef __SGI_STL_PORT
109 class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
110 #else
111 class iterator_base {
112 #endif
113 public:
114 typedef T value_type;
115 typedef T* pointer;
116 typedef T& reference;
117 typedef size_t size_type;
118 typedef ptrdiff_t difference_type;
119 typedef std::bidirectional_iterator_tag iterator_category;
120
121 iterator_base();
122 iterator_base(tree_node *);
123
124 T& operator*() const;
125 T* operator->() const;
126
127 /// When called, the next increment/decrement skips children of this node.
128 void skip_children();
129 void skip_children(bool skip);
130 /// Number of children of the node pointed to by the iterator.
131 unsigned int number_of_children() const;
132
133 sibling_iterator begin() const;
134 sibling_iterator end() const;
135
136 tree_node *node;
137 protected:
138 bool skip_current_children_;
139 };
140
141 /// Depth-first iterator, first accessing the node, then its children.
142 class pre_order_iterator : public iterator_base {
143 public:
144 pre_order_iterator();
145 pre_order_iterator(tree_node *);
146 pre_order_iterator(const iterator_base&);
147 pre_order_iterator(const sibling_iterator&);
148
149 bool operator==(const pre_order_iterator&) const;
150 bool operator!=(const pre_order_iterator&) const;
151 pre_order_iterator& operator++();
152 pre_order_iterator& operator--();
153 pre_order_iterator operator++(int);
154 pre_order_iterator operator--(int);
155 pre_order_iterator& operator+=(unsigned int);
156 pre_order_iterator& operator-=(unsigned int);
157 };
158
159 /// Depth-first iterator, first accessing the children, then the node itself.
160 class post_order_iterator : public iterator_base {
161 public:
162 post_order_iterator();
163 post_order_iterator(tree_node *);
164 post_order_iterator(const iterator_base&);
165 post_order_iterator(const sibling_iterator&);
166
167 bool operator==(const post_order_iterator&) const;
168 bool operator!=(const post_order_iterator&) const;
169 post_order_iterator& operator++();
170 post_order_iterator& operator--();
171 post_order_iterator operator++(int);
172 post_order_iterator operator--(int);
173 post_order_iterator& operator+=(unsigned int);
174 post_order_iterator& operator-=(unsigned int);
175
176 /// Set iterator to the first child as deep as possible down the tree.
177 void descend_all();
178 };
179
180 /// Breadth-first iterator, using a queue
181 class breadth_first_queued_iterator : public iterator_base {
182 public:
183 breadth_first_queued_iterator();
184 breadth_first_queued_iterator(tree_node *);
185 breadth_first_queued_iterator(const iterator_base&);
186
187 bool operator==(const breadth_first_queued_iterator&) const;
188 bool operator!=(const breadth_first_queued_iterator&) const;
189 breadth_first_queued_iterator& operator++();
190 breadth_first_queued_iterator operator++(int);
191 breadth_first_queued_iterator& operator+=(unsigned int);
192
193 private:
194 std::queue<tree_node *> traversal_queue;
195 };
196
197 /// The default iterator types throughout the tree class.
198 typedef pre_order_iterator iterator;
199 typedef breadth_first_queued_iterator breadth_first_iterator;
200
201 /// Iterator which traverses only the nodes at a given depth from the root.
202 class fixed_depth_iterator : public iterator_base {
203 public:
204 fixed_depth_iterator();
205 fixed_depth_iterator(tree_node *);
206 fixed_depth_iterator(const iterator_base&);
207 fixed_depth_iterator(const sibling_iterator&);
208 fixed_depth_iterator(const fixed_depth_iterator&);
209
210 bool operator==(const fixed_depth_iterator&) const;
211 bool operator!=(const fixed_depth_iterator&) const;
212 fixed_depth_iterator& operator++();
213 fixed_depth_iterator& operator--();
214 fixed_depth_iterator operator++(int);
215 fixed_depth_iterator operator--(int);
216 fixed_depth_iterator& operator+=(unsigned int);
217 fixed_depth_iterator& operator-=(unsigned int);
218
219 tree_node *top_node;
220 };
221
222 /// Iterator which traverses only the nodes which are siblings of each other.
223 class sibling_iterator : public iterator_base {
224 public:
225 sibling_iterator();
226 sibling_iterator(tree_node *);
227 sibling_iterator(const sibling_iterator&);
228 sibling_iterator(const iterator_base&);
229
230 bool operator==(const sibling_iterator&) const;
231 bool operator!=(const sibling_iterator&) const;
232 sibling_iterator& operator++();
233 sibling_iterator& operator--();
234 sibling_iterator operator++(int);
235 sibling_iterator operator--(int);
236 sibling_iterator& operator+=(unsigned int);
237 sibling_iterator& operator-=(unsigned int);
238
239 tree_node *range_first() const;
240 tree_node *range_last() const;
241 tree_node *parent_;
242 private:
243 void set_parent_();
244 };
245
246 /// Iterator which traverses only the leaves.
247 class leaf_iterator : public iterator_base {
248 public:
249 leaf_iterator();
250 leaf_iterator(tree_node *, tree_node *top=0);
251 leaf_iterator(const sibling_iterator&);
252 leaf_iterator(const iterator_base&);
253
254 bool operator==(const leaf_iterator&) const;
255 bool operator!=(const leaf_iterator&) const;
256 leaf_iterator& operator++();
257 leaf_iterator& operator--();
258 leaf_iterator operator++(int);
259 leaf_iterator operator--(int);
260 leaf_iterator& operator+=(unsigned int);
261 leaf_iterator& operator-=(unsigned int);
262 private:
263 tree_node *top_node;
264 };
265
266 /// Return iterator to the beginning of the tree.
267 inline pre_order_iterator begin() const;
268 /// Return iterator to the end of the tree.
269 inline pre_order_iterator end() const;
270 /// Return post-order iterator to the beginning of the tree.
271 post_order_iterator begin_post() const;
272 /// Return post-order end iterator of the tree.
273 post_order_iterator end_post() const;
274 /// Return fixed-depth iterator to the first node at a given depth from the given iterator.
275 fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
276 /// Return fixed-depth end iterator.
277 fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
278 /// Return breadth-first iterator to the first node at a given depth.
279 breadth_first_queued_iterator begin_breadth_first() const;
280 /// Return breadth-first end iterator.
281 breadth_first_queued_iterator end_breadth_first() const;
282 /// Return sibling iterator to the first child of given node.
283 sibling_iterator begin(const iterator_base&) const;
284 /// Return sibling end iterator for children of given node.
285 sibling_iterator end(const iterator_base&) const;
286 /// Return leaf iterator to the first leaf of the tree.
287 leaf_iterator begin_leaf() const;
288 /// Return leaf end iterator for entire tree.
289 leaf_iterator end_leaf() const;
290 /// Return leaf iterator to the first leaf of the subtree at the given node.
291 leaf_iterator begin_leaf(const iterator_base& top) const;
292 /// Return leaf end iterator for the subtree at the given node.
293 leaf_iterator end_leaf(const iterator_base& top) const;
294
295 /// Return iterator to the parent of a node.
296 template<typename iter> static iter parent(iter);
297 /// Return iterator to the previous sibling of a node.
298 template<typename iter> iter previous_sibling(iter) const;
299 /// Return iterator to the next sibling of a node.
300 template<typename iter> iter next_sibling(iter) const;
301 /// Return iterator to the next node at a given depth.
302 template<typename iter> iter next_at_same_depth(iter) const;
303
304 /// Erase all nodes of the tree.
305 void clear();
306 /// Erase element at position pointed to by iterator, return incremented iterator.
307 template<typename iter> iter erase(iter);
308 /// Erase all children of the node pointed to by iterator.
309 void erase_children(const iterator_base&);
310
311 /// Insert empty node as last/first child of node pointed to by position.
312 template<typename iter> iter append_child(iter position);
313 template<typename iter> iter prepend_child(iter position);
314 /// Insert node as last/first child of node pointed to by position.
315 template<typename iter> iter append_child(iter position, const T& x);
316 template<typename iter> iter prepend_child(iter position, const T& x);
317 /// Append the node (plus its children) at other_position as last/first child of position.
318 template<typename iter> iter append_child(iter position, iter other_position);
319 template<typename iter> iter prepend_child(iter position, iter other_position);
320 /// Append the nodes in the from-to range (plus their children) as last/first children of position.
321 template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
322 template<typename iter> iter prepend_children(iter position, sibling_iterator from, sibling_iterator to);
323
324 /// Short-hand to insert topmost node in otherwise empty tree.
325 pre_order_iterator set_head(const T& x);
326 /// Insert node as previous sibling of node pointed to by position.
327 template<typename iter> iter insert(iter position, const T& x);
328 /// Specialisation of previous member.
329 sibling_iterator insert(sibling_iterator position, const T& x);
330 /// Insert node (with children) pointed to by subtree as previous sibling of node pointed to by position.
331 template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
332 /// Insert node as next sibling of node pointed to by position.
333 template<typename iter> iter insert_after(iter position, const T& x);
334 /// Insert node (with children) pointed to by subtree as next sibling of node pointed to by position.
335 template<typename iter> iter insert_subtree_after(iter position, const iterator_base& subtree);
336
337 /// Replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
338 template<typename iter> iter replace(iter position, const T& x);
339 /// Replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
340 template<typename iter> iter replace(iter position, const iterator_base& from);
341 /// Replace string of siblings (plus their children) with copy of a new string (with children); see above
342 sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end,
343 sibling_iterator new_begin, sibling_iterator new_end);
344
345 /// Move all children of node at 'position' to be siblings, returns position.
346 template<typename iter> iter flatten(iter position);
347 /// Move nodes in range to be children of 'position'.
348 template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
349 /// Move all child nodes of 'from' to be children of 'position'.
350 template<typename iter> iter reparent(iter position, iter from);
351
352 /// Replace node with a new node, making the old node a child of the new node.
353 template<typename iter> iter wrap(iter position, const T& x);
354
355 /// Move 'source' node (plus its children) to become the next sibling of 'target'.
356 template<typename iter> iter move_after(iter target, iter source);
357 /// Move 'source' node (plus its children) to become the previous sibling of 'target'.
358 template<typename iter> iter move_before(iter target, iter source);
359 sibling_iterator move_before(sibling_iterator target, sibling_iterator source);
360 /// Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
361 template<typename iter> iter move_ontop(iter target, iter source);
362
363 /// Merge with other tree, creating new branches and leaves only if they are not already present.
364 void merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
365 bool duplicate_leaves=false);
366 /// Sort (std::sort only moves values of nodes, this one moves children as well).
367 void sort(sibling_iterator from, sibling_iterator to, bool deep=false);
368 template<class StrictWeakOrdering>
369 void sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
370 /// Compare two ranges of nodes (compares nodes as well as tree structure).
371 template<typename iter>
372 bool equal(const iter& one, const iter& two, const iter& three) const;
373 template<typename iter, class BinaryPredicate>
374 bool equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
375 template<typename iter>
376 bool equal_subtree(const iter& one, const iter& two) const;
377 template<typename iter, class BinaryPredicate>
378 bool equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
379 /// Extract a new tree formed by the range of siblings plus all their children.
380 tree subtree(sibling_iterator from, sibling_iterator to) const;
381 void subtree(tree&, sibling_iterator from, sibling_iterator to) const;
382 /// Exchange the node (plus subtree) with its sibling node (do nothing if no sibling present).
383 void swap(sibling_iterator it);
384 /// Exchange two nodes (plus subtrees)
385 void swap(iterator, iterator);
386
387 /// Count the total number of nodes.
388 size_t size() const;
389 /// Count the total number of nodes below the indicated node (plus one).
390 size_t size(const iterator_base&) const;
391 /// Check if tree is empty.
392 bool empty() const;
393 /// Compute the depth to the root or to a fixed other iterator.
394 static int depth(const iterator_base&);
395 static int depth(const iterator_base&, const iterator_base&);
396 /// Determine the maximal depth of the tree. An empty tree has max_depth=-1.
397 int max_depth() const;
398 /// Determine the maximal depth of the tree with top node at the given position.
399 int max_depth(const iterator_base&) const;
400 /// Count the number of children of node at position.
401 static unsigned int number_of_children(const iterator_base&);
402 /// Count the number of siblings (left and right) of node at iterator. Total nodes at this level is +1.
403 unsigned int number_of_siblings(const iterator_base&) const;
404 /// Determine whether node at position is in the subtrees with root in the range.
405 bool is_in_subtree(const iterator_base& position, const iterator_base& begin,
406 const iterator_base& end) const;
407 /// Determine whether the iterator is an 'end' iterator and thus not actually pointing to a node.
408 bool is_valid(const iterator_base&) const;
409 /// Find the lowest common ancestor of two nodes, that is, the deepest node such that
410 /// both nodes are descendants of it.
411 iterator lowest_common_ancestor(const iterator_base&, const iterator_base &) const;
412
413 /// Determine the index of a node in the range of siblings to which it belongs.
414 unsigned int index(sibling_iterator it) const;
415 /// Inverse of 'index': return the n-th child of the node at position.
416 static sibling_iterator child(const iterator_base& position, unsigned int);
417 /// Return iterator to the sibling indicated by index
418 sibling_iterator sibling(const iterator_base& position, unsigned int);
419
420 /// For debugging only: verify internal consistency by inspecting all pointers in the tree
421 /// (which will also trigger a valgrind error in case something got corrupted).
422 void debug_verify_consistency() const;
423
424 /// Comparator class for iterators (compares pointer values; why doesn't this work automatically?)
425 class iterator_base_less {
426 public:
operator ()(const typename tree<T,tree_node_allocator>::iterator_base & one,const typename tree<T,tree_node_allocator>::iterator_base & two) const427 bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
428 const typename tree<T, tree_node_allocator>::iterator_base& two) const
429 {
430 return one.node < two.node;
431 }
432 };
433 tree_node *head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
434 private:
435 tree_node_allocator alloc_;
436 void head_initialise_();
437 void copy_(const tree<T, tree_node_allocator>& other);
438
439 /// Comparator class for two nodes of a tree (used for sorting and searching).
440 template<class StrictWeakOrdering>
441 class compare_nodes {
442 public:
compare_nodes(StrictWeakOrdering comp)443 compare_nodes(StrictWeakOrdering comp) : comp_(comp) {}
444
operator ()(const tree_node * a,const tree_node * b) const445 bool operator()(const tree_node *a, const tree_node *b) const
446 {
447 return comp_(a->data, b->data);
448 }
449 private:
450 StrictWeakOrdering comp_;
451 };
452 };
453
454 //template <class T, class tree_node_allocator>
455 //class iterator_base_less {
456 // public:
457 // bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
458 // const typename tree<T, tree_node_allocator>::iterator_base& two) const
459 // {
460 // txtout << "operatorclass<" << one.node < two.node << std::endl;
461 // return one.node < two.node;
462 // }
463 //};
464
465 // template <class T, class tree_node_allocator>
466 // bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
467 // const typename tree<T, tree_node_allocator>::iterator& two)
468 // {
469 // txtout << "operator< " << one.node < two.node << std::endl;
470 // if(one.node < two.node) return true;
471 // return false;
472 // }
473 //
474 // template <class T, class tree_node_allocator>
475 // bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
476 // const typename tree<T, tree_node_allocator>::iterator& two)
477 // {
478 // txtout << "operator== " << one.node == two.node << std::endl;
479 // if(one.node == two.node) return true;
480 // return false;
481 // }
482 //
483 // template <class T, class tree_node_allocator>
484 // bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
485 // const typename tree<T, tree_node_allocator>::iterator_base& two)
486 // {
487 // txtout << "operator> " << one.node < two.node << std::endl;
488 // if(one.node > two.node) return true;
489 // return false;
490 // }
491
492
493
494 // Tree
495
496 template <class T, class tree_node_allocator>
tree()497 tree<T, tree_node_allocator>::tree()
498 {
499 head_initialise_();
500 }
501
502 template <class T, class tree_node_allocator>
tree(const T & x)503 tree<T, tree_node_allocator>::tree(const T& x)
504 {
505 head_initialise_();
506 set_head(x);
507 }
508
509 template <class T, class tree_node_allocator>
tree(const iterator_base & other)510 tree<T, tree_node_allocator>::tree(const iterator_base& other)
511 {
512 head_initialise_();
513 set_head((*other));
514 replace(begin(), other);
515 }
516
517 template <class T, class tree_node_allocator>
~tree()518 tree<T, tree_node_allocator>::~tree()
519 {
520 clear();
521 alloc_.destroy(head);
522 alloc_.destroy(feet);
523 alloc_.deallocate(head,1);
524 alloc_.deallocate(feet,1);
525 }
526
527 template <class T, class tree_node_allocator>
head_initialise_()528 void tree<T, tree_node_allocator>::head_initialise_()
529 {
530 head = alloc_.allocate(1,0); // MSVC does not have default second argument
531 feet = alloc_.allocate(1,0);
532 alloc_.construct(head, tree_node_<T>());
533 alloc_.construct(feet, tree_node_<T>());
534
535 head->parent=0;
536 head->first_child=0;
537 head->last_child=0;
538 head->prev_sibling=0; //head;
539 head->next_sibling=feet; //head;
540
541 feet->parent=0;
542 feet->first_child=0;
543 feet->last_child=0;
544 feet->prev_sibling=head;
545 feet->next_sibling=0;
546 }
547
548 template <class T, class tree_node_allocator>
operator =(const tree<T,tree_node_allocator> & other)549 tree<T,tree_node_allocator>& tree<T, tree_node_allocator>::operator=(const tree<T, tree_node_allocator>& other)
550 {
551 if(this != &other)
552 copy_(other);
553 return *this;
554 }
555
556 template <class T, class tree_node_allocator>
tree(const tree<T,tree_node_allocator> & other)557 tree<T, tree_node_allocator>::tree(const tree<T, tree_node_allocator>& other)
558 {
559 head_initialise_();
560 copy_(other);
561 }
562
563 template <class T, class tree_node_allocator>
copy_(const tree<T,tree_node_allocator> & other)564 void tree<T, tree_node_allocator>::copy_(const tree<T, tree_node_allocator>& other)
565 {
566 clear();
567 pre_order_iterator it=other.begin(), to=begin();
568 while(it!=other.end()) {
569 to=insert(to, (*it));
570 it.skip_children();
571 ++it;
572 }
573 to=begin();
574 it=other.begin();
575 while(it!=other.end()) {
576 to=replace(to, it);
577 to.skip_children();
578 it.skip_children();
579 ++to;
580 ++it;
581 }
582 }
583
584 template <class T, class tree_node_allocator>
clear()585 void tree<T, tree_node_allocator>::clear()
586 {
587 if(head)
588 while(head->next_sibling!=feet)
589 erase(pre_order_iterator(head->next_sibling));
590 }
591
592 template<class T, class tree_node_allocator>
erase_children(const iterator_base & it)593 void tree<T, tree_node_allocator>::erase_children(const iterator_base& it)
594 {
595 // std::cout << "erase_children " << it.node << std::endl;
596 if(it.node==0) return;
597
598 tree_node *cur=it.node->first_child;
599 tree_node *prev=0;
600
601 while(cur!=0) {
602 prev=cur;
603 cur=cur->next_sibling;
604 erase_children(pre_order_iterator(prev));
605 // kp::destructor(&prev->data);
606 alloc_.destroy(prev);
607 alloc_.deallocate(prev,1);
608 }
609 it.node->first_child=0;
610 it.node->last_child=0;
611 // std::cout << "exit" << std::endl;
612 }
613
614 template<class T, class tree_node_allocator>
615 template<class iter>
erase(iter it)616 iter tree<T, tree_node_allocator>::erase(iter it)
617 {
618 tree_node *cur=it.node;
619 assert(cur!=head);
620 iter ret=it;
621 ret.skip_children();
622 ++ret;
623 erase_children(it);
624 if(cur->prev_sibling==0) {
625 cur->parent->first_child=cur->next_sibling;
626 }
627 else {
628 cur->prev_sibling->next_sibling=cur->next_sibling;
629 }
630 if(cur->next_sibling==0) {
631 cur->parent->last_child=cur->prev_sibling;
632 }
633 else {
634 cur->next_sibling->prev_sibling=cur->prev_sibling;
635 }
636
637 // kp::destructor(&cur->data);
638 alloc_.destroy(cur);
639 alloc_.deallocate(cur,1);
640 return ret;
641 }
642
643 template <class T, class tree_node_allocator>
begin() const644 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::begin() const
645 {
646 return pre_order_iterator(head->next_sibling);
647 }
648
649 template <class T, class tree_node_allocator>
end() const650 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::end() const
651 {
652 return pre_order_iterator(feet);
653 }
654
655 template <class T, class tree_node_allocator>
begin_breadth_first() const656 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const
657 {
658 return breadth_first_queued_iterator(head->next_sibling);
659 }
660
661 template <class T, class tree_node_allocator>
end_breadth_first() const662 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const
663 {
664 return breadth_first_queued_iterator();
665 }
666
667 template <class T, class tree_node_allocator>
begin_post() const668 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::begin_post() const
669 {
670 tree_node *tmp=head->next_sibling;
671 if(tmp!=feet) {
672 while(tmp->first_child)
673 tmp=tmp->first_child;
674 }
675 return post_order_iterator(tmp);
676 }
677
678 template <class T, class tree_node_allocator>
end_post() const679 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::end_post() const
680 {
681 return post_order_iterator(feet);
682 }
683
684 template <class T, class tree_node_allocator>
begin_fixed(const iterator_base & pos,unsigned int dp) const685 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::begin_fixed(const iterator_base& pos, unsigned int dp) const
686 {
687 typename tree<T, tree_node_allocator>::fixed_depth_iterator ret;
688 ret.top_node=pos.node;
689
690 tree_node *tmp=pos.node;
691 unsigned int curdepth=0;
692 while(curdepth<dp) { // go down one level
693 while(tmp->first_child==0) {
694 if(tmp->next_sibling==0) {
695 // try to walk up and then right again
696 do {
697 if(tmp==ret.top_node)
698 throw std::range_error("tree: begin_fixed out of range");
699 tmp=tmp->parent;
700 if(tmp==0)
701 throw std::range_error("tree: begin_fixed out of range");
702 --curdepth;
703 } while(tmp->next_sibling==0);
704 }
705 tmp=tmp->next_sibling;
706 }
707 tmp=tmp->first_child;
708 ++curdepth;
709 }
710
711 ret.node=tmp;
712 return ret;
713 }
714
715 template <class T, class tree_node_allocator>
end_fixed(const iterator_base & pos,unsigned int dp) const716 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::end_fixed(const iterator_base& pos, unsigned int dp) const
717 {
718 assert(1==0); // FIXME: not correct yet: use is_valid() as a temporary workaround
719 tree_node *tmp=pos.node;
720 unsigned int curdepth=1;
721 while(curdepth<dp) { // go down one level
722 while(tmp->first_child==0) {
723 tmp=tmp->next_sibling;
724 if(tmp==0)
725 throw std::range_error("tree: end_fixed out of range");
726 }
727 tmp=tmp->first_child;
728 ++curdepth;
729 }
730 return tmp;
731 }
732
733 template <class T, class tree_node_allocator>
begin(const iterator_base & pos) const734 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(const iterator_base& pos) const
735 {
736 assert(pos.node!=0);
737 if(pos.node->first_child==0) {
738 return end(pos);
739 }
740 return pos.node->first_child;
741 }
742
743 template <class T, class tree_node_allocator>
end(const iterator_base & pos) const744 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::end(const iterator_base& pos) const
745 {
746 sibling_iterator ret(0);
747 ret.parent_=pos.node;
748 return ret;
749 }
750
751 template <class T, class tree_node_allocator>
begin_leaf() const752 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf() const
753 {
754 tree_node *tmp=head->next_sibling;
755 if(tmp!=feet) {
756 while(tmp->first_child)
757 tmp=tmp->first_child;
758 }
759 return leaf_iterator(tmp);
760 }
761
762 template <class T, class tree_node_allocator>
end_leaf() const763 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf() const
764 {
765 return leaf_iterator(feet);
766 }
767
768 template <class T, class tree_node_allocator>
begin_leaf(const iterator_base & top) const769 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::begin_leaf(const iterator_base& top) const
770 {
771 tree_node *tmp=top.node;
772 while(tmp->first_child)
773 tmp=tmp->first_child;
774 return leaf_iterator(tmp, top.node);
775 }
776
777 template <class T, class tree_node_allocator>
end_leaf(const iterator_base & top) const778 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::end_leaf(const iterator_base& top) const
779 {
780 return leaf_iterator(top.node, top.node);
781 }
782
783 template <class T, class tree_node_allocator>
784 template <typename iter>
parent(iter position)785 iter tree<T, tree_node_allocator>::parent(iter position)
786 {
787 assert(position.node!=0);
788 return iter(position.node->parent);
789 }
790
791 template <class T, class tree_node_allocator>
792 template <typename iter>
previous_sibling(iter position) const793 iter tree<T, tree_node_allocator>::previous_sibling(iter position) const
794 {
795 assert(position.node!=0);
796 iter ret(position);
797 ret.node=position.node->prev_sibling;
798 return ret;
799 }
800
801 template <class T, class tree_node_allocator>
802 template <typename iter>
next_sibling(iter position) const803 iter tree<T, tree_node_allocator>::next_sibling(iter position) const
804 {
805 assert(position.node!=0);
806 iter ret(position);
807 ret.node=position.node->next_sibling;
808 return ret;
809 }
810
811 template <class T, class tree_node_allocator>
812 template <typename iter>
next_at_same_depth(iter position) const813 iter tree<T, tree_node_allocator>::next_at_same_depth(iter position) const
814 {
815 // We make use of a temporary fixed_depth iterator to implement this.
816
817 typename tree<T, tree_node_allocator>::fixed_depth_iterator tmp(position.node);
818
819 ++tmp;
820 return iter(tmp);
821
822 // assert(position.node!=0);
823 // iter ret(position);
824 //
825 // if(position.node->next_sibling) {
826 // ret.node=position.node->next_sibling;
827 // }
828 // else {
829 // int relative_depth=0;
830 // upper:
831 // do {
832 // ret.node=ret.node->parent;
833 // if(ret.node==0) return ret;
834 // --relative_depth;
835 // } while(ret.node->next_sibling==0);
836 // lower:
837 // ret.node=ret.node->next_sibling;
838 // while(ret.node->first_child==0) {
839 // if(ret.node->next_sibling==0)
840 // goto upper;
841 // ret.node=ret.node->next_sibling;
842 // if(ret.node==0) return ret;
843 // }
844 // while(relative_depth<0 && ret.node->first_child!=0) {
845 // ret.node=ret.node->first_child;
846 // ++relative_depth;
847 // }
848 // if(relative_depth<0) {
849 // if(ret.node->next_sibling==0) goto upper;
850 // else goto lower;
851 // }
852 // }
853 // return ret;
854 }
855
856 template <class T, class tree_node_allocator>
857 template <typename iter>
append_child(iter position)858 iter tree<T, tree_node_allocator>::append_child(iter position)
859 {
860 assert(position.node!=head);
861 assert(position.node!=feet);
862 assert(position.node);
863
864 tree_node *tmp=alloc_.allocate(1,0);
865 alloc_.construct(tmp, tree_node_<T>());
866 // kp::constructor(&tmp->data);
867 tmp->first_child=0;
868 tmp->last_child=0;
869
870 tmp->parent=position.node;
871 if(position.node->last_child!=0) {
872 position.node->last_child->next_sibling=tmp;
873 }
874 else {
875 position.node->first_child=tmp;
876 }
877 tmp->prev_sibling=position.node->last_child;
878 position.node->last_child=tmp;
879 tmp->next_sibling=0;
880 return tmp;
881 }
882
883 template <class T, class tree_node_allocator>
884 template <typename iter>
prepend_child(iter position)885 iter tree<T, tree_node_allocator>::prepend_child(iter position)
886 {
887 assert(position.node!=head);
888 assert(position.node!=feet);
889 assert(position.node);
890
891 tree_node *tmp=alloc_.allocate(1,0);
892 alloc_.construct(tmp, tree_node_<T>());
893 // kp::constructor(&tmp->data);
894 tmp->first_child=0;
895 tmp->last_child=0;
896
897 tmp->parent=position.node;
898 if(position.node->first_child!=0) {
899 position.node->first_child->prev_sibling=tmp;
900 }
901 else {
902 position.node->last_child=tmp;
903 }
904 tmp->next_sibling=position.node->first_child;
905 position.node->prev_child=tmp;
906 tmp->prev_sibling=0;
907 return tmp;
908 }
909
910 template <class T, class tree_node_allocator>
911 template <class iter>
append_child(iter position,const T & x)912 iter tree<T, tree_node_allocator>::append_child(iter position, const T& x)
913 {
914 // If your program fails here you probably used 'append_child' to add the top
915 // node to an empty tree. From version 1.45 the top element should be added
916 // using 'insert'. See the documentation for further information, and sorry about
917 // the API change.
918 assert(position.node!=head);
919 assert(position.node!=feet);
920 assert(position.node);
921
922 tree_node* tmp = alloc_.allocate(1,0);
923 alloc_.construct(tmp, x);
924 // kp::constructor(&tmp->data, x);
925 tmp->first_child=0;
926 tmp->last_child=0;
927
928 tmp->parent=position.node;
929 if(position.node->last_child!=0) {
930 position.node->last_child->next_sibling=tmp;
931 }
932 else {
933 position.node->first_child=tmp;
934 }
935 tmp->prev_sibling=position.node->last_child;
936 position.node->last_child=tmp;
937 tmp->next_sibling=0;
938 return tmp;
939 }
940
941 template <class T, class tree_node_allocator>
942 template <class iter>
prepend_child(iter position,const T & x)943 iter tree<T, tree_node_allocator>::prepend_child(iter position, const T& x)
944 {
945 assert(position.node!=head);
946 assert(position.node!=feet);
947 assert(position.node);
948
949 tree_node* tmp = alloc_.allocate(1,0);
950 alloc_.construct(tmp, x);
951 // kp::constructor(&tmp->data, x);
952 tmp->first_child=0;
953 tmp->last_child=0;
954
955 tmp->parent=position.node;
956 if(position.node->first_child!=0) {
957 position.node->first_child->prev_sibling=tmp;
958 }
959 else {
960 position.node->last_child=tmp;
961 }
962 tmp->next_sibling=position.node->first_child;
963 position.node->first_child=tmp;
964 tmp->prev_sibling=0;
965 return tmp;
966 }
967
968 template <class T, class tree_node_allocator>
969 template <class iter>
append_child(iter position,iter other)970 iter tree<T, tree_node_allocator>::append_child(iter position, iter other)
971 {
972 assert(position.node!=head);
973 assert(position.node!=feet);
974 assert(position.node);
975
976 sibling_iterator aargh=append_child(position, value_type());
977 return replace(aargh, other);
978 }
979
980 template <class T, class tree_node_allocator>
981 template <class iter>
prepend_child(iter position,iter other)982 iter tree<T, tree_node_allocator>::prepend_child(iter position, iter other)
983 {
984 assert(position.node!=head);
985 assert(position.node!=feet);
986 assert(position.node);
987
988 sibling_iterator aargh=prepend_child(position, value_type());
989 return replace(aargh, other);
990 }
991
992 template <class T, class tree_node_allocator>
993 template <class iter>
append_children(iter position,sibling_iterator from,sibling_iterator to)994 iter tree<T, tree_node_allocator>::append_children(iter position, sibling_iterator from, sibling_iterator to)
995 {
996 assert(position.node!=head);
997 assert(position.node!=feet);
998 assert(position.node);
999
1000 iter ret=from;
1001
1002 while(from!=to) {
1003 insert_subtree(position.end(), from);
1004 ++from;
1005 }
1006 return ret;
1007 }
1008
1009 template <class T, class tree_node_allocator>
1010 template <class iter>
prepend_children(iter position,sibling_iterator from,sibling_iterator to)1011 iter tree<T, tree_node_allocator>::prepend_children(iter position, sibling_iterator from, sibling_iterator to)
1012 {
1013 assert(position.node!=head);
1014 assert(position.node!=feet);
1015 assert(position.node);
1016
1017 iter ret=from;
1018
1019 while(from!=to) {
1020 insert_subtree(position.begin(), from);
1021 ++from;
1022 }
1023 return ret;
1024 }
1025
1026 template <class T, class tree_node_allocator>
set_head(const T & x)1027 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::set_head(const T& x)
1028 {
1029 assert(head->next_sibling==feet);
1030 return insert(iterator(feet), x);
1031 }
1032
1033 template <class T, class tree_node_allocator>
1034 template <class iter>
insert(iter position,const T & x)1035 iter tree<T, tree_node_allocator>::insert(iter position, const T& x)
1036 {
1037 if(position.node==0) {
1038 position.node=feet; // Backward compatibility: when calling insert on a null node,
1039 // insert before the feet.
1040 }
1041 tree_node* tmp = alloc_.allocate(1,0);
1042 alloc_.construct(tmp, x);
1043 // kp::constructor(&tmp->data, x);
1044 tmp->first_child=0;
1045 tmp->last_child=0;
1046
1047 tmp->parent=position.node->parent;
1048 tmp->next_sibling=position.node;
1049 tmp->prev_sibling=position.node->prev_sibling;
1050 position.node->prev_sibling=tmp;
1051
1052 if(tmp->prev_sibling==0) {
1053 if(tmp->parent) // when inserting nodes at the head, there is no parent
1054 tmp->parent->first_child=tmp;
1055 }
1056 else
1057 tmp->prev_sibling->next_sibling=tmp;
1058 return tmp;
1059 }
1060
1061 template <class T, class tree_node_allocator>
insert(sibling_iterator position,const T & x)1062 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
1063 {
1064 tree_node* tmp = alloc_.allocate(1,0);
1065 alloc_.construct(tmp, x);
1066 // kp::constructor(&tmp->data, x);
1067 tmp->first_child=0;
1068 tmp->last_child=0;
1069
1070 tmp->next_sibling=position.node;
1071 if(position.node==0) { // iterator points to end of a subtree
1072 tmp->parent=position.parent_;
1073 tmp->prev_sibling=position.range_last();
1074 tmp->parent->last_child=tmp;
1075 }
1076 else {
1077 tmp->parent=position.node->parent;
1078 tmp->prev_sibling=position.node->prev_sibling;
1079 position.node->prev_sibling=tmp;
1080 }
1081
1082 if(tmp->prev_sibling==0) {
1083 if(tmp->parent) // when inserting nodes at the head, there is no parent
1084 tmp->parent->first_child=tmp;
1085 }
1086 else
1087 tmp->prev_sibling->next_sibling=tmp;
1088 return tmp;
1089 }
1090
1091 template <class T, class tree_node_allocator>
1092 template <class iter>
insert_after(iter position,const T & x)1093 iter tree<T, tree_node_allocator>::insert_after(iter position, const T& x)
1094 {
1095 tree_node* tmp = alloc_.allocate(1,0);
1096 alloc_.construct(tmp, x);
1097 // kp::constructor(&tmp->data, x);
1098 tmp->first_child=0;
1099 tmp->last_child=0;
1100
1101 tmp->parent=position.node->parent;
1102 tmp->prev_sibling=position.node;
1103 tmp->next_sibling=position.node->next_sibling;
1104 position.node->next_sibling=tmp;
1105
1106 if(tmp->next_sibling==0) {
1107 if(tmp->parent) // when inserting nodes at the head, there is no parent
1108 tmp->parent->last_child=tmp;
1109 }
1110 else {
1111 tmp->next_sibling->prev_sibling=tmp;
1112 }
1113 return tmp;
1114 }
1115
1116 template <class T, class tree_node_allocator>
1117 template <class iter>
insert_subtree(iter position,const iterator_base & subtree)1118 iter tree<T, tree_node_allocator>::insert_subtree(iter position, const iterator_base& subtree)
1119 {
1120 // insert dummy
1121 iter it=insert(position, value_type());
1122 // replace dummy with subtree
1123 return replace(it, subtree);
1124 }
1125
1126 template <class T, class tree_node_allocator>
1127 template <class iter>
insert_subtree_after(iter position,const iterator_base & subtree)1128 iter tree<T, tree_node_allocator>::insert_subtree_after(iter position, const iterator_base& subtree)
1129 {
1130 // insert dummy
1131 iter it=insert_after(position, value_type());
1132 // replace dummy with subtree
1133 return replace(it, subtree);
1134 }
1135
1136 // template <class T, class tree_node_allocator>
1137 // template <class iter>
1138 // iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
1139 // {
1140 // // insert dummy
1141 // iter it(insert(position, value_type()));
1142 // // replace dummy with subtree
1143 // return replace(it, subtree);
1144 // }
1145
1146 template <class T, class tree_node_allocator>
1147 template <class iter>
replace(iter position,const T & x)1148 iter tree<T, tree_node_allocator>::replace(iter position, const T& x)
1149 {
1150 // kp::destructor(&position.node->data);
1151 // kp::constructor(&position.node->data, x);
1152 position.node->data=x;
1153 // alloc_.destroy(position.node);
1154 // alloc_.construct(position.node, x);
1155 return position;
1156 }
1157
1158 template <class T, class tree_node_allocator>
1159 template <class iter>
replace(iter position,const iterator_base & from)1160 iter tree<T, tree_node_allocator>::replace(iter position, const iterator_base& from)
1161 {
1162 assert(position.node!=head);
1163 tree_node *current_from=from.node;
1164 tree_node *start_from=from.node;
1165 tree_node *current_to =position.node;
1166
1167 // replace the node at position with head of the replacement tree at from
1168 // std::cout << "warning!" << position.node << std::endl;
1169 erase_children(position);
1170 // std::cout << "no warning!" << std::endl;
1171 tree_node* tmp = alloc_.allocate(1,0);
1172 alloc_.construct(tmp, (*from));
1173 // kp::constructor(&tmp->data, (*from));
1174 tmp->first_child=0;
1175 tmp->last_child=0;
1176 if(current_to->prev_sibling==0) {
1177 if(current_to->parent!=0)
1178 current_to->parent->first_child=tmp;
1179 }
1180 else {
1181 current_to->prev_sibling->next_sibling=tmp;
1182 }
1183 tmp->prev_sibling=current_to->prev_sibling;
1184 if(current_to->next_sibling==0) {
1185 if(current_to->parent!=0)
1186 current_to->parent->last_child=tmp;
1187 }
1188 else {
1189 current_to->next_sibling->prev_sibling=tmp;
1190 }
1191 tmp->next_sibling=current_to->next_sibling;
1192 tmp->parent=current_to->parent;
1193 // kp::destructor(¤t_to->data);
1194 alloc_.destroy(current_to);
1195 alloc_.deallocate(current_to,1);
1196 current_to=tmp;
1197
1198 // only at this stage can we fix 'last'
1199 tree_node *last=from.node->next_sibling;
1200
1201 pre_order_iterator toit=tmp;
1202 // copy all children
1203 do {
1204 assert(current_from!=0);
1205 if(current_from->first_child != 0) {
1206 current_from=current_from->first_child;
1207 toit=append_child(toit, current_from->data);
1208 }
1209 else {
1210 while(current_from->next_sibling==0 && current_from!=start_from) {
1211 current_from=current_from->parent;
1212 toit=parent(toit);
1213 assert(current_from!=0);
1214 }
1215 current_from=current_from->next_sibling;
1216 if(current_from!=last) {
1217 toit=append_child(parent(toit), current_from->data);
1218 }
1219 }
1220 } while(current_from!=last);
1221
1222 return current_to;
1223 }
1224
1225 template <class T, class tree_node_allocator>
replace(sibling_iterator orig_begin,sibling_iterator orig_end,sibling_iterator new_begin,sibling_iterator new_end)1226 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::replace(
1227 sibling_iterator orig_begin,
1228 sibling_iterator orig_end,
1229 sibling_iterator new_begin,
1230 sibling_iterator new_end)
1231 {
1232 tree_node *orig_first=orig_begin.node;
1233 tree_node *new_first=new_begin.node;
1234 tree_node *orig_last=orig_first;
1235 while((++orig_begin)!=orig_end)
1236 orig_last=orig_last->next_sibling;
1237 tree_node *new_last=new_first;
1238 while((++new_begin)!=new_end)
1239 new_last=new_last->next_sibling;
1240
1241 // insert all siblings in new_first..new_last before orig_first
1242 bool first=true;
1243 pre_order_iterator ret;
1244 while(1==1) {
1245 pre_order_iterator tt=insert_subtree(pre_order_iterator(orig_first), pre_order_iterator(new_first));
1246 if(first) {
1247 ret=tt;
1248 first=false;
1249 }
1250 if(new_first==new_last)
1251 break;
1252 new_first=new_first->next_sibling;
1253 }
1254
1255 // erase old range of siblings
1256 bool last=false;
1257 tree_node *next=orig_first;
1258 while(1==1) {
1259 if(next==orig_last)
1260 last=true;
1261 next=next->next_sibling;
1262 erase((pre_order_iterator)orig_first);
1263 if(last)
1264 break;
1265 orig_first=next;
1266 }
1267 return ret;
1268 }
1269
1270 template <class T, class tree_node_allocator>
1271 template <typename iter>
flatten(iter position)1272 iter tree<T, tree_node_allocator>::flatten(iter position)
1273 {
1274 if(position.node->first_child==0)
1275 return position;
1276
1277 tree_node *tmp=position.node->first_child;
1278 while(tmp) {
1279 tmp->parent=position.node->parent;
1280 tmp=tmp->next_sibling;
1281 }
1282 if(position.node->next_sibling) {
1283 position.node->last_child->next_sibling=position.node->next_sibling;
1284 position.node->next_sibling->prev_sibling=position.node->last_child;
1285 }
1286 else {
1287 position.node->parent->last_child=position.node->last_child;
1288 }
1289 position.node->next_sibling=position.node->first_child;
1290 position.node->next_sibling->prev_sibling=position.node;
1291 position.node->first_child=0;
1292 position.node->last_child=0;
1293
1294 return position;
1295 }
1296
1297
1298 template <class T, class tree_node_allocator>
1299 template <typename iter>
reparent(iter position,sibling_iterator begin,sibling_iterator end)1300 iter tree<T, tree_node_allocator>::reparent(iter position, sibling_iterator begin, sibling_iterator end)
1301 {
1302 tree_node *first=begin.node;
1303 tree_node *last=first;
1304
1305 assert(first!=position.node);
1306
1307 if(begin==end) return begin;
1308 // determine last node
1309 while((++begin)!=end) {
1310 last=last->next_sibling;
1311 }
1312 // move subtree
1313 if(first->prev_sibling==0) {
1314 first->parent->first_child=last->next_sibling;
1315 }
1316 else {
1317 first->prev_sibling->next_sibling=last->next_sibling;
1318 }
1319 if(last->next_sibling==0) {
1320 last->parent->last_child=first->prev_sibling;
1321 }
1322 else {
1323 last->next_sibling->prev_sibling=first->prev_sibling;
1324 }
1325 if(position.node->first_child==0) {
1326 position.node->first_child=first;
1327 position.node->last_child=last;
1328 first->prev_sibling=0;
1329 }
1330 else {
1331 position.node->last_child->next_sibling=first;
1332 first->prev_sibling=position.node->last_child;
1333 position.node->last_child=last;
1334 }
1335 last->next_sibling=0;
1336
1337 tree_node *pos=first;
1338 for(;;) {
1339 pos->parent=position.node;
1340 if(pos==last) break;
1341 pos=pos->next_sibling;
1342 }
1343
1344 return first;
1345 }
1346
1347 template <class T, class tree_node_allocator>
reparent(iter position,iter from)1348 template <typename iter> iter tree<T, tree_node_allocator>::reparent(iter position, iter from)
1349 {
1350 if(from.node->first_child==0) return position;
1351 return reparent(position, from.node->first_child, end(from));
1352 }
1353
1354 template <class T, class tree_node_allocator>
wrap(iter position,const T & x)1355 template <typename iter> iter tree<T, tree_node_allocator>::wrap(iter position, const T& x)
1356 {
1357 assert(position.node!=0);
1358 sibling_iterator fr=position, to=position;
1359 ++to;
1360 iter ret = insert(position, x);
1361 reparent(ret, fr, to);
1362 return ret;
1363 }
1364
1365 template <class T, class tree_node_allocator>
move_after(iter target,iter source)1366 template <typename iter> iter tree<T, tree_node_allocator>::move_after(iter target, iter source)
1367 {
1368 tree_node *dst=target.node;
1369 tree_node *src=source.node;
1370 assert(dst);
1371 assert(src);
1372
1373 if(dst==src) return source;
1374 if(dst->next_sibling)
1375 if(dst->next_sibling==src) // already in the right spot
1376 return source;
1377
1378 // take src out of the tree
1379 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1380 else src->parent->first_child=src->next_sibling;
1381 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1382 else src->parent->last_child=src->prev_sibling;
1383
1384 // connect it to the new point
1385 if(dst->next_sibling!=0) dst->next_sibling->prev_sibling=src;
1386 else dst->parent->last_child=src;
1387 src->next_sibling=dst->next_sibling;
1388 dst->next_sibling=src;
1389 src->prev_sibling=dst;
1390 src->parent=dst->parent;
1391 return src;
1392 }
1393
1394 template <class T, class tree_node_allocator>
move_before(iter target,iter source)1395 template <typename iter> iter tree<T, tree_node_allocator>::move_before(iter target, iter source)
1396 {
1397 tree_node *dst=target.node;
1398 tree_node *src=source.node;
1399 assert(dst);
1400 assert(src);
1401
1402 if(dst==src) return source;
1403 if(dst->prev_sibling)
1404 if(dst->prev_sibling==src) // already in the right spot
1405 return source;
1406
1407 // take src out of the tree
1408 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1409 else src->parent->first_child=src->next_sibling;
1410 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1411 else src->parent->last_child=src->prev_sibling;
1412
1413 // connect it to the new point
1414 if(dst->prev_sibling!=0) dst->prev_sibling->next_sibling=src;
1415 else dst->parent->first_child=src;
1416 src->prev_sibling=dst->prev_sibling;
1417 dst->prev_sibling=src;
1418 src->next_sibling=dst;
1419 src->parent=dst->parent;
1420 return src;
1421 }
1422
1423 // specialisation for sibling_iterators
1424 template <class T, class tree_node_allocator>
move_before(sibling_iterator target,sibling_iterator source)1425 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::move_before(sibling_iterator target,
1426 sibling_iterator source)
1427 {
1428 tree_node *dst=target.node;
1429 tree_node *src=source.node;
1430 tree_node *dst_prev_sibling;
1431 if(dst==0) { // must then be an end iterator
1432 dst_prev_sibling=target.parent_->last_child;
1433 assert(dst_prev_sibling);
1434 }
1435 else dst_prev_sibling=dst->prev_sibling;
1436 assert(src);
1437
1438 if(dst==src) return source;
1439 if(dst_prev_sibling)
1440 if(dst_prev_sibling==src) // already in the right spot
1441 return source;
1442
1443 // take src out of the tree
1444 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1445 else src->parent->first_child=src->next_sibling;
1446 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1447 else src->parent->last_child=src->prev_sibling;
1448
1449 // connect it to the new point
1450 if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
1451 else target.parent_->first_child=src;
1452 src->prev_sibling=dst_prev_sibling;
1453 if(dst) {
1454 dst->prev_sibling=src;
1455 src->parent=dst->parent;
1456 }
1457 src->next_sibling=dst;
1458 return src;
1459 }
1460
1461 template <class T, class tree_node_allocator>
move_ontop(iter target,iter source)1462 template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
1463 {
1464 tree_node *dst=target.node;
1465 tree_node *src=source.node;
1466 assert(dst);
1467 assert(src);
1468
1469 if(dst==src) return source;
1470
1471 // if(dst==src->prev_sibling) {
1472 //
1473 // }
1474
1475 // remember connection points
1476 tree_node *b_prev_sibling=dst->prev_sibling;
1477 tree_node *b_next_sibling=dst->next_sibling;
1478 tree_node *b_parent=dst->parent;
1479
1480 // remove target
1481 erase(target);
1482
1483 // take src out of the tree
1484 if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
1485 else src->parent->first_child=src->next_sibling;
1486 if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
1487 else src->parent->last_child=src->prev_sibling;
1488
1489 // connect it to the new point
1490 if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
1491 else b_parent->first_child=src;
1492 if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
1493 else b_parent->last_child=src;
1494 src->prev_sibling=b_prev_sibling;
1495 src->next_sibling=b_next_sibling;
1496 src->parent=b_parent;
1497 return src;
1498 }
1499
1500 template <class T, class tree_node_allocator>
merge(sibling_iterator to1,sibling_iterator to2,sibling_iterator from1,sibling_iterator from2,bool duplicate_leaves)1501 void tree<T, tree_node_allocator>::merge(sibling_iterator to1, sibling_iterator to2,
1502 sibling_iterator from1, sibling_iterator from2,
1503 bool duplicate_leaves)
1504 {
1505 sibling_iterator fnd;
1506 while(from1!=from2) {
1507 if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
1508 if(from1.begin()==from1.end()) { // full depth reached
1509 if(duplicate_leaves)
1510 append_child(parent(to1), (*from1));
1511 }
1512 else { // descend further
1513 merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
1514 }
1515 }
1516 else { // element missing
1517 insert_subtree(to2, from1);
1518 }
1519 ++from1;
1520 }
1521 }
1522
1523
1524 template <class T, class tree_node_allocator>
sort(sibling_iterator from,sibling_iterator to,bool deep)1525 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
1526 {
1527 std::less<T> comp;
1528 sort(from, to, comp, deep);
1529 }
1530
1531 template <class T, class tree_node_allocator>
1532 template <class StrictWeakOrdering>
sort(sibling_iterator from,sibling_iterator to,StrictWeakOrdering comp,bool deep)1533 void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to,
1534 StrictWeakOrdering comp, bool deep)
1535 {
1536 if(from==to) return;
1537 // make list of sorted nodes
1538 // CHECK: if multiset stores equivalent nodes in the order in which they
1539 // are inserted, then this routine should be called 'stable_sort'.
1540 std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
1541 sibling_iterator it=from, it2=to;
1542 while(it != to) {
1543 nodes.insert(it.node);
1544 ++it;
1545 }
1546 // reassemble
1547 --it2;
1548
1549 // prev and next are the nodes before and after the sorted range
1550 tree_node *prev=from.node->prev_sibling;
1551 tree_node *next=it2.node->next_sibling;
1552 typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
1553 if(prev==0) {
1554 if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1555 (*nit)->parent->first_child=(*nit);
1556 }
1557 else prev->next_sibling=(*nit);
1558
1559 --eit;
1560 while(nit!=eit) {
1561 (*nit)->prev_sibling=prev;
1562 if(prev)
1563 prev->next_sibling=(*nit);
1564 prev=(*nit);
1565 ++nit;
1566 }
1567 // prev now points to the last-but-one node in the sorted range
1568 if(prev)
1569 prev->next_sibling=(*eit);
1570
1571 // eit points to the last node in the sorted range.
1572 (*eit)->next_sibling=next;
1573 (*eit)->prev_sibling=prev; // missed in the loop above
1574 if(next==0) {
1575 if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
1576 (*eit)->parent->last_child=(*eit);
1577 }
1578 else next->prev_sibling=(*eit);
1579
1580 if(deep) { // sort the children of each node too
1581 sibling_iterator bcs(*nodes.begin());
1582 sibling_iterator ecs(*eit);
1583 ++ecs;
1584 while(bcs!=ecs) {
1585 sort(begin(bcs), end(bcs), comp, deep);
1586 ++bcs;
1587 }
1588 }
1589 }
1590
1591 template <class T, class tree_node_allocator>
1592 template <typename iter>
equal(const iter & one_,const iter & two,const iter & three_) const1593 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
1594 {
1595 std::equal_to<T> comp;
1596 return equal(one_, two, three_, comp);
1597 }
1598
1599 template <class T, class tree_node_allocator>
1600 template <typename iter>
equal_subtree(const iter & one_,const iter & two_) const1601 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
1602 {
1603 std::equal_to<T> comp;
1604 return equal_subtree(one_, two_, comp);
1605 }
1606
1607 template <class T, class tree_node_allocator>
1608 template <typename iter, class BinaryPredicate>
equal(const iter & one_,const iter & two,const iter & three_,BinaryPredicate fun) const1609 bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
1610 {
1611 pre_order_iterator one(one_), three(three_);
1612
1613 // if(one==two && is_valid(three) && three.number_of_children()!=0)
1614 // return false;
1615 while(one!=two && is_valid(three)) {
1616 if(!fun(*one,*three))
1617 return false;
1618 if(one.number_of_children()!=three.number_of_children())
1619 return false;
1620 ++one;
1621 ++three;
1622 }
1623 return true;
1624 }
1625
1626 template <class T, class tree_node_allocator>
1627 template <typename iter, class BinaryPredicate>
equal_subtree(const iter & one_,const iter & two_,BinaryPredicate fun) const1628 bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_, BinaryPredicate fun) const
1629 {
1630 pre_order_iterator one(one_), two(two_);
1631
1632 if(!fun(*one,*two)) return false;
1633 if(number_of_children(one)!=number_of_children(two)) return false;
1634 return equal(begin(one),end(one),begin(two),fun);
1635 }
1636
1637 template <class T, class tree_node_allocator>
subtree(sibling_iterator from,sibling_iterator to) const1638 tree<T, tree_node_allocator> tree<T, tree_node_allocator>::subtree(sibling_iterator from, sibling_iterator to) const
1639 {
1640 tree tmp;
1641 tmp.set_head(value_type());
1642 tmp.replace(tmp.begin(), tmp.end(), from, to);
1643 return tmp;
1644 }
1645
1646 template <class T, class tree_node_allocator>
subtree(tree & tmp,sibling_iterator from,sibling_iterator to) const1647 void tree<T, tree_node_allocator>::subtree(tree& tmp, sibling_iterator from, sibling_iterator to) const
1648 {
1649 tmp.set_head(value_type());
1650 tmp.replace(tmp.begin(), tmp.end(), from, to);
1651 }
1652
1653 template <class T, class tree_node_allocator>
size() const1654 size_t tree<T, tree_node_allocator>::size() const
1655 {
1656 size_t i=0;
1657 pre_order_iterator it=begin(), eit=end();
1658 while(it!=eit) {
1659 ++i;
1660 ++it;
1661 }
1662 return i;
1663 }
1664
1665 template <class T, class tree_node_allocator>
size(const iterator_base & top) const1666 size_t tree<T, tree_node_allocator>::size(const iterator_base& top) const
1667 {
1668 size_t i=0;
1669 pre_order_iterator it=top, eit=top;
1670 eit.skip_children();
1671 ++eit;
1672 while(it!=eit) {
1673 ++i;
1674 ++it;
1675 }
1676 return i;
1677 }
1678
1679 template <class T, class tree_node_allocator>
empty() const1680 bool tree<T, tree_node_allocator>::empty() const
1681 {
1682 pre_order_iterator it=begin(), eit=end();
1683 return (it==eit);
1684 }
1685
1686 template <class T, class tree_node_allocator>
depth(const iterator_base & it)1687 int tree<T, tree_node_allocator>::depth(const iterator_base& it)
1688 {
1689 tree_node* pos=it.node;
1690 assert(pos!=0);
1691 int ret=0;
1692 while(pos->parent!=0) {
1693 pos=pos->parent;
1694 ++ret;
1695 }
1696 return ret;
1697 }
1698
1699 template <class T, class tree_node_allocator>
depth(const iterator_base & it,const iterator_base & root)1700 int tree<T, tree_node_allocator>::depth(const iterator_base& it, const iterator_base& root)
1701 {
1702 tree_node* pos=it.node;
1703 assert(pos!=0);
1704 int ret=0;
1705 while(pos->parent!=0 && pos!=root.node) {
1706 pos=pos->parent;
1707 ++ret;
1708 }
1709 return ret;
1710 }
1711
1712 template <class T, class tree_node_allocator>
max_depth() const1713 int tree<T, tree_node_allocator>::max_depth() const
1714 {
1715 int maxd=-1;
1716 for(tree_node *it = head->next_sibling; it!=feet; it=it->next_sibling)
1717 maxd=std::max(maxd, max_depth(it));
1718
1719 return maxd;
1720 }
1721
1722
1723 template <class T, class tree_node_allocator>
max_depth(const iterator_base & pos) const1724 int tree<T, tree_node_allocator>::max_depth(const iterator_base& pos) const
1725 {
1726 tree_node *tmp=pos.node;
1727
1728 if(tmp==0 || tmp==head || tmp==feet) return -1;
1729
1730 int curdepth=0, maxdepth=0;
1731 while(true) { // try to walk the bottom of the tree
1732 while(tmp->first_child==0) {
1733 if(tmp==pos.node) return maxdepth;
1734 if(tmp->next_sibling==0) {
1735 // try to walk up and then right again
1736 do {
1737 tmp=tmp->parent;
1738 if(tmp==0) return maxdepth;
1739 --curdepth;
1740 } while(tmp->next_sibling==0);
1741 }
1742 if(tmp==pos.node) return maxdepth;
1743 tmp=tmp->next_sibling;
1744 }
1745 tmp=tmp->first_child;
1746 ++curdepth;
1747 maxdepth=std::max(curdepth, maxdepth);
1748 }
1749 }
1750
1751 template <class T, class tree_node_allocator>
number_of_children(const iterator_base & it)1752 unsigned int tree<T, tree_node_allocator>::number_of_children(const iterator_base& it)
1753 {
1754 tree_node *pos=it.node->first_child;
1755 if(pos==0) return 0;
1756
1757 unsigned int ret=1;
1758 // while(pos!=it.node->last_child) {
1759 // ++ret;
1760 // pos=pos->next_sibling;
1761 // }
1762 while((pos=pos->next_sibling))
1763 ++ret;
1764 return ret;
1765 }
1766
1767 template <class T, class tree_node_allocator>
number_of_siblings(const iterator_base & it) const1768 unsigned int tree<T, tree_node_allocator>::number_of_siblings(const iterator_base& it) const
1769 {
1770 tree_node *pos=it.node;
1771 unsigned int ret=0;
1772 // count forward
1773 while(pos->next_sibling &&
1774 pos->next_sibling!=head &&
1775 pos->next_sibling!=feet) {
1776 ++ret;
1777 pos=pos->next_sibling;
1778 }
1779 // count backward
1780 pos=it.node;
1781 while(pos->prev_sibling &&
1782 pos->prev_sibling!=head &&
1783 pos->prev_sibling!=feet) {
1784 ++ret;
1785 pos=pos->prev_sibling;
1786 }
1787
1788 return ret;
1789 }
1790
1791 template <class T, class tree_node_allocator>
swap(sibling_iterator it)1792 void tree<T, tree_node_allocator>::swap(sibling_iterator it)
1793 {
1794 tree_node *nxt=it.node->next_sibling;
1795 if(nxt) {
1796 if(it.node->prev_sibling)
1797 it.node->prev_sibling->next_sibling=nxt;
1798 else
1799 it.node->parent->first_child=nxt;
1800 nxt->prev_sibling=it.node->prev_sibling;
1801 tree_node *nxtnxt=nxt->next_sibling;
1802 if(nxtnxt)
1803 nxtnxt->prev_sibling=it.node;
1804 else
1805 it.node->parent->last_child=it.node;
1806 nxt->next_sibling=it.node;
1807 it.node->prev_sibling=nxt;
1808 it.node->next_sibling=nxtnxt;
1809 }
1810 }
1811
1812 template <class T, class tree_node_allocator>
swap(iterator one,iterator two)1813 void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
1814 {
1815 // if one and two are adjacent siblings, use the sibling swap
1816 if(one.node->next_sibling==two.node) swap(one);
1817 else if(two.node->next_sibling==one.node) swap(two);
1818 else {
1819 tree_node *nxt1=one.node->next_sibling;
1820 tree_node *nxt2=two.node->next_sibling;
1821 tree_node *pre1=one.node->prev_sibling;
1822 tree_node *pre2=two.node->prev_sibling;
1823 tree_node *par1=one.node->parent;
1824 tree_node *par2=two.node->parent;
1825
1826 // reconnect
1827 one.node->parent=par2;
1828 one.node->next_sibling=nxt2;
1829 if(nxt2) nxt2->prev_sibling=one.node;
1830 else par2->last_child=one.node;
1831 one.node->prev_sibling=pre2;
1832 if(pre2) pre2->next_sibling=one.node;
1833 else par2->first_child=one.node;
1834
1835 two.node->parent=par1;
1836 two.node->next_sibling=nxt1;
1837 if(nxt1) nxt1->prev_sibling=two.node;
1838 else par1->last_child=two.node;
1839 two.node->prev_sibling=pre1;
1840 if(pre1) pre1->next_sibling=two.node;
1841 else par1->first_child=two.node;
1842 }
1843 }
1844
1845 // template <class BinaryPredicate>
1846 // tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
1847 // sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
1848 // BinaryPredicate fun) const
1849 // {
1850 // assert(1==0); // this routine is not finished yet.
1851 // while(from!=to) {
1852 // if(fun(*subfrom, *from)) {
1853 //
1854 // }
1855 // }
1856 // return to;
1857 // }
1858
1859 template <class T, class tree_node_allocator>
is_in_subtree(const iterator_base & it,const iterator_base & begin,const iterator_base & end) const1860 bool tree<T, tree_node_allocator>::is_in_subtree(const iterator_base& it, const iterator_base& begin,
1861 const iterator_base& end) const
1862 {
1863 // FIXME: this should be optimised.
1864 pre_order_iterator tmp=begin;
1865 while(tmp!=end) {
1866 if(tmp==it) return true;
1867 ++tmp;
1868 }
1869 return false;
1870 }
1871
1872 template <class T, class tree_node_allocator>
is_valid(const iterator_base & it) const1873 bool tree<T, tree_node_allocator>::is_valid(const iterator_base& it) const
1874 {
1875 if(it.node==0 || it.node==feet || it.node==head) return false;
1876 else return true;
1877 }
1878
1879 template <class T, class tree_node_allocator>
lowest_common_ancestor(const iterator_base & one,const iterator_base & two) const1880 typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::lowest_common_ancestor(
1881 const iterator_base& one, const iterator_base& two) const
1882 {
1883 std::set<iterator, iterator_base_less> parents;
1884
1885 // Walk up from 'one' storing all parents.
1886 iterator walk=one;
1887 do {
1888 walk=parent(walk);
1889 parents.insert(walk);
1890 } while( is_valid(parent(walk)) );
1891
1892 // Walk up from 'two' until we encounter a node in parents.
1893 walk=two;
1894 do {
1895 walk=parent(walk);
1896 if(parents.find(walk) != parents.end()) break;
1897 } while( is_valid(parent(walk)) );
1898
1899 return walk;
1900 }
1901
1902 template <class T, class tree_node_allocator>
index(sibling_iterator it) const1903 unsigned int tree<T, tree_node_allocator>::index(sibling_iterator it) const
1904 {
1905 unsigned int ind=0;
1906 if(it.node->parent==0) {
1907 while(it.node->prev_sibling!=head) {
1908 it.node=it.node->prev_sibling;
1909 ++ind;
1910 }
1911 }
1912 else {
1913 while(it.node->prev_sibling!=0) {
1914 it.node=it.node->prev_sibling;
1915 ++ind;
1916 }
1917 }
1918 return ind;
1919 }
1920
1921 template <class T, class tree_node_allocator>
sibling(const iterator_base & it,unsigned int num)1922 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling(const iterator_base& it, unsigned int num)
1923 {
1924 tree_node *tmp;
1925 if(it.node->parent==0) {
1926 tmp=head->next_sibling;
1927 while(num) {
1928 tmp = tmp->next_sibling;
1929 --num;
1930 }
1931 }
1932 else {
1933 tmp=it.node->parent->first_child;
1934 while(num) {
1935 assert(tmp!=0);
1936 tmp = tmp->next_sibling;
1937 --num;
1938 }
1939 }
1940 return tmp;
1941 }
1942
1943 template <class T, class tree_node_allocator>
debug_verify_consistency() const1944 void tree<T, tree_node_allocator>::debug_verify_consistency() const
1945 {
1946 iterator it=begin();
1947 while(it!=end()) {
1948 if(it.node->parent!=0) {
1949 if(it.node->prev_sibling==0)
1950 assert(it.node->parent->first_child==it.node);
1951 else
1952 assert(it.node->prev_sibling->next_sibling==it.node);
1953 if(it.node->next_sibling==0)
1954 assert(it.node->parent->last_child==it.node);
1955 else
1956 assert(it.node->next_sibling->prev_sibling==it.node);
1957 }
1958 ++it;
1959 }
1960 }
1961
1962 template <class T, class tree_node_allocator>
child(const iterator_base & it,unsigned int num)1963 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::child(const iterator_base& it, unsigned int num)
1964 {
1965 tree_node *tmp=it.node->first_child;
1966 while(num--) {
1967 assert(tmp!=0);
1968 tmp=tmp->next_sibling;
1969 }
1970 return tmp;
1971 }
1972
1973
1974
1975
1976 // Iterator base
1977
1978 template <class T, class tree_node_allocator>
iterator_base()1979 tree<T, tree_node_allocator>::iterator_base::iterator_base()
1980 : node(0), skip_current_children_(false)
1981 {
1982 }
1983
1984 template <class T, class tree_node_allocator>
iterator_base(tree_node * tn)1985 tree<T, tree_node_allocator>::iterator_base::iterator_base(tree_node *tn)
1986 : node(tn), skip_current_children_(false)
1987 {
1988 }
1989
1990 template <class T, class tree_node_allocator>
1991 T& tree<T, tree_node_allocator>::iterator_base::operator*() const
1992 {
1993 return node->data;
1994 }
1995
1996 template <class T, class tree_node_allocator>
1997 T* tree<T, tree_node_allocator>::iterator_base::operator->() const
1998 {
1999 return &(node->data);
2000 }
2001
2002 template <class T, class tree_node_allocator>
operator !=(const post_order_iterator & other) const2003 bool tree<T, tree_node_allocator>::post_order_iterator::operator!=(const post_order_iterator& other) const
2004 {
2005 if(other.node!=this->node) return true;
2006 else return false;
2007 }
2008
2009 template <class T, class tree_node_allocator>
operator ==(const post_order_iterator & other) const2010 bool tree<T, tree_node_allocator>::post_order_iterator::operator==(const post_order_iterator& other) const
2011 {
2012 if(other.node==this->node) return true;
2013 else return false;
2014 }
2015
2016 template <class T, class tree_node_allocator>
operator !=(const pre_order_iterator & other) const2017 bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=(const pre_order_iterator& other) const
2018 {
2019 if(other.node!=this->node) return true;
2020 else return false;
2021 }
2022
2023 template <class T, class tree_node_allocator>
operator ==(const pre_order_iterator & other) const2024 bool tree<T, tree_node_allocator>::pre_order_iterator::operator==(const pre_order_iterator& other) const
2025 {
2026 if(other.node==this->node) return true;
2027 else return false;
2028 }
2029
2030 template <class T, class tree_node_allocator>
operator !=(const sibling_iterator & other) const2031 bool tree<T, tree_node_allocator>::sibling_iterator::operator!=(const sibling_iterator& other) const
2032 {
2033 if(other.node!=this->node) return true;
2034 else return false;
2035 }
2036
2037 template <class T, class tree_node_allocator>
operator ==(const sibling_iterator & other) const2038 bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
2039 {
2040 if(other.node==this->node) return true;
2041 else return false;
2042 }
2043
2044 template <class T, class tree_node_allocator>
operator !=(const leaf_iterator & other) const2045 bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_iterator& other) const
2046 {
2047 if(other.node!=this->node) return true;
2048 else return false;
2049 }
2050
2051 template <class T, class tree_node_allocator>
operator ==(const leaf_iterator & other) const2052 bool tree<T, tree_node_allocator>::leaf_iterator::operator==(const leaf_iterator& other) const
2053 {
2054 if(other.node==this->node && other.top_node==this->top_node) return true;
2055 else return false;
2056 }
2057
2058 template <class T, class tree_node_allocator>
begin() const2059 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::begin() const
2060 {
2061 if(node->first_child==0)
2062 return end();
2063
2064 sibling_iterator ret(node->first_child);
2065 ret.parent_=this->node;
2066 return ret;
2067 }
2068
2069 template <class T, class tree_node_allocator>
end() const2070 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator_base::end() const
2071 {
2072 sibling_iterator ret(0);
2073 ret.parent_=node;
2074 return ret;
2075 }
2076
2077 template <class T, class tree_node_allocator>
skip_children()2078 void tree<T, tree_node_allocator>::iterator_base::skip_children()
2079 {
2080 skip_current_children_=true;
2081 }
2082
2083 template <class T, class tree_node_allocator>
skip_children(bool skip)2084 void tree<T, tree_node_allocator>::iterator_base::skip_children(bool skip)
2085 {
2086 skip_current_children_=skip;
2087 }
2088
2089 template <class T, class tree_node_allocator>
number_of_children() const2090 unsigned int tree<T, tree_node_allocator>::iterator_base::number_of_children() const
2091 {
2092 tree_node *pos=node->first_child;
2093 if(pos==0) return 0;
2094
2095 unsigned int ret=1;
2096 while(pos!=node->last_child) {
2097 ++ret;
2098 pos=pos->next_sibling;
2099 }
2100 return ret;
2101 }
2102
2103
2104
2105 // Pre-order iterator
2106
2107 template <class T, class tree_node_allocator>
pre_order_iterator()2108 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator()
2109 : iterator_base(0)
2110 {
2111 }
2112
2113 template <class T, class tree_node_allocator>
pre_order_iterator(tree_node * tn)2114 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
2115 : iterator_base(tn)
2116 {
2117 }
2118
2119 template <class T, class tree_node_allocator>
pre_order_iterator(const iterator_base & other)2120 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const iterator_base &other)
2121 : iterator_base(other.node)
2122 {
2123 }
2124
2125 template <class T, class tree_node_allocator>
pre_order_iterator(const sibling_iterator & other)2126 tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
2127 : iterator_base(other.node)
2128 {
2129 if(this->node==0) {
2130 if(other.range_last()!=0)
2131 this->node=other.range_last();
2132 else
2133 this->node=other.parent_;
2134 this->skip_children();
2135 ++(*this);
2136 }
2137 }
2138
2139 template <class T, class tree_node_allocator>
operator ++()2140 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
2141 {
2142 assert(this->node!=0);
2143 if(!this->skip_current_children_ && this->node->first_child != 0) {
2144 this->node=this->node->first_child;
2145 }
2146 else {
2147 this->skip_current_children_=false;
2148 while(this->node->next_sibling==0) {
2149 this->node=this->node->parent;
2150 if(this->node==0)
2151 return *this;
2152 }
2153 this->node=this->node->next_sibling;
2154 }
2155 return *this;
2156 }
2157
2158 template <class T, class tree_node_allocator>
operator --()2159 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
2160 {
2161 assert(this->node!=0);
2162 if(this->node->prev_sibling) {
2163 this->node=this->node->prev_sibling;
2164 while(this->node->last_child)
2165 this->node=this->node->last_child;
2166 }
2167 else {
2168 this->node=this->node->parent;
2169 if(this->node==0)
2170 return *this;
2171 }
2172 return *this;
2173 }
2174
2175 template <class T, class tree_node_allocator>
operator ++(int)2176 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int)
2177 {
2178 pre_order_iterator copy = *this;
2179 ++(*this);
2180 return copy;
2181 }
2182
2183 template <class T, class tree_node_allocator>
operator --(int)2184 typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int)
2185 {
2186 pre_order_iterator copy = *this;
2187 --(*this);
2188 return copy;
2189 }
2190
2191 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2192 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=(unsigned int num)
2193 {
2194 while(num>0) {
2195 ++(*this);
2196 --num;
2197 }
2198 return (*this);
2199 }
2200
2201 template <class T, class tree_node_allocator>
operator -=(unsigned int num)2202 typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=(unsigned int num)
2203 {
2204 while(num>0) {
2205 --(*this);
2206 --num;
2207 }
2208 return (*this);
2209 }
2210
2211
2212
2213 // Post-order iterator
2214
2215 template <class T, class tree_node_allocator>
post_order_iterator()2216 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()
2217 : iterator_base(0)
2218 {
2219 }
2220
2221 template <class T, class tree_node_allocator>
post_order_iterator(tree_node * tn)2222 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(tree_node *tn)
2223 : iterator_base(tn)
2224 {
2225 }
2226
2227 template <class T, class tree_node_allocator>
post_order_iterator(const iterator_base & other)2228 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const iterator_base &other)
2229 : iterator_base(other.node)
2230 {
2231 }
2232
2233 template <class T, class tree_node_allocator>
post_order_iterator(const sibling_iterator & other)2234 tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator(const sibling_iterator& other)
2235 : iterator_base(other.node)
2236 {
2237 if(this->node==0) {
2238 if(other.range_last()!=0)
2239 this->node=other.range_last();
2240 else
2241 this->node=other.parent_;
2242 this->skip_children();
2243 ++(*this);
2244 }
2245 }
2246
2247 template <class T, class tree_node_allocator>
operator ++()2248 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
2249 {
2250 assert(this->node!=0);
2251 if(this->node->next_sibling==0) {
2252 this->node=this->node->parent;
2253 this->skip_current_children_=false;
2254 }
2255 else {
2256 this->node=this->node->next_sibling;
2257 if(this->skip_current_children_) {
2258 this->skip_current_children_=false;
2259 }
2260 else {
2261 while(this->node->first_child)
2262 this->node=this->node->first_child;
2263 }
2264 }
2265 return *this;
2266 }
2267
2268 template <class T, class tree_node_allocator>
operator --()2269 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--()
2270 {
2271 assert(this->node!=0);
2272 if(this->skip_current_children_ || this->node->last_child==0) {
2273 this->skip_current_children_=false;
2274 while(this->node->prev_sibling==0)
2275 this->node=this->node->parent;
2276 this->node=this->node->prev_sibling;
2277 }
2278 else {
2279 this->node=this->node->last_child;
2280 }
2281 return *this;
2282 }
2283
2284 template <class T, class tree_node_allocator>
operator ++(int)2285 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++(int)
2286 {
2287 post_order_iterator copy = *this;
2288 ++(*this);
2289 return copy;
2290 }
2291
2292 template <class T, class tree_node_allocator>
operator --(int)2293 typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--(int)
2294 {
2295 post_order_iterator copy = *this;
2296 --(*this);
2297 return copy;
2298 }
2299
2300
2301 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2302 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=(unsigned int num)
2303 {
2304 while(num>0) {
2305 ++(*this);
2306 --num;
2307 }
2308 return (*this);
2309 }
2310
2311 template <class T, class tree_node_allocator>
operator -=(unsigned int num)2312 typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=(unsigned int num)
2313 {
2314 while(num>0) {
2315 --(*this);
2316 --num;
2317 }
2318 return (*this);
2319 }
2320
2321 template <class T, class tree_node_allocator>
descend_all()2322 void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
2323 {
2324 assert(this->node!=0);
2325 while(this->node->first_child)
2326 this->node=this->node->first_child;
2327 }
2328
2329
2330 // Breadth-first iterator
2331
2332 template <class T, class tree_node_allocator>
breadth_first_queued_iterator()2333 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator()
2334 : iterator_base()
2335 {
2336 }
2337
2338 template <class T, class tree_node_allocator>
breadth_first_queued_iterator(tree_node * tn)2339 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)
2340 : iterator_base(tn)
2341 {
2342 traversal_queue.push(tn);
2343 }
2344
2345 template <class T, class tree_node_allocator>
breadth_first_queued_iterator(const iterator_base & other)2346 tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const iterator_base& other)
2347 : iterator_base(other.node)
2348 {
2349 traversal_queue.push(other.node);
2350 }
2351
2352 template <class T, class tree_node_allocator>
operator !=(const breadth_first_queued_iterator & other) const2353 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_iterator& other) const
2354 {
2355 if(other.node!=this->node) return true;
2356 else return false;
2357 }
2358
2359 template <class T, class tree_node_allocator>
operator ==(const breadth_first_queued_iterator & other) const2360 bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==(const breadth_first_queued_iterator& other) const
2361 {
2362 if(other.node==this->node) return true;
2363 else return false;
2364 }
2365
2366 template <class T, class tree_node_allocator>
operator ++()2367 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()
2368 {
2369 assert(this->node!=0);
2370
2371 // Add child nodes and pop current node
2372 sibling_iterator sib=this->begin();
2373 while(sib!=this->end()) {
2374 traversal_queue.push(sib.node);
2375 ++sib;
2376 }
2377 traversal_queue.pop();
2378 if(traversal_queue.size()>0)
2379 this->node=traversal_queue.front();
2380 else
2381 this->node=0;
2382 return (*this);
2383 }
2384
2385 template <class T, class tree_node_allocator>
operator ++(int)2386 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++(int)
2387 {
2388 breadth_first_queued_iterator copy = *this;
2389 ++(*this);
2390 return copy;
2391 }
2392
2393 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2394 typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)
2395 {
2396 while(num>0) {
2397 ++(*this);
2398 --num;
2399 }
2400 return (*this);
2401 }
2402
2403
2404
2405 // Fixed depth iterator
2406
2407 template <class T, class tree_node_allocator>
fixed_depth_iterator()2408 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
2409 : iterator_base()
2410 {
2411 }
2412
2413 template <class T, class tree_node_allocator>
fixed_depth_iterator(tree_node * tn)2414 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(tree_node *tn)
2415 : iterator_base(tn), top_node(0)
2416 {
2417 }
2418
2419 template <class T, class tree_node_allocator>
fixed_depth_iterator(const iterator_base & other)2420 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const iterator_base& other)
2421 : iterator_base(other.node), top_node(0)
2422 {
2423 }
2424
2425 template <class T, class tree_node_allocator>
fixed_depth_iterator(const sibling_iterator & other)2426 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
2427 : iterator_base(other.node), top_node(0)
2428 {
2429 }
2430
2431 template <class T, class tree_node_allocator>
fixed_depth_iterator(const fixed_depth_iterator & other)2432 tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const fixed_depth_iterator& other)
2433 : iterator_base(other.node), top_node(other.top_node)
2434 {
2435 }
2436
2437 template <class T, class tree_node_allocator>
operator ==(const fixed_depth_iterator & other) const2438 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==(const fixed_depth_iterator& other) const
2439 {
2440 if(other.node==this->node && other.top_node==top_node) return true;
2441 else return false;
2442 }
2443
2444 template <class T, class tree_node_allocator>
operator !=(const fixed_depth_iterator & other) const2445 bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=(const fixed_depth_iterator& other) const
2446 {
2447 if(other.node!=this->node || other.top_node!=top_node) return true;
2448 else return false;
2449 }
2450
2451 template <class T, class tree_node_allocator>
operator ++()2452 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++()
2453 {
2454 assert(this->node!=0);
2455
2456 if(this->node->next_sibling) {
2457 this->node=this->node->next_sibling;
2458 }
2459 else {
2460 int relative_depth=0;
2461 upper:
2462 do {
2463 if(this->node==this->top_node) {
2464 this->node=0; // FIXME: return a proper fixed_depth end iterator once implemented
2465 return *this;
2466 }
2467 this->node=this->node->parent;
2468 if(this->node==0) return *this;
2469 --relative_depth;
2470 } while(this->node->next_sibling==0);
2471 lower:
2472 this->node=this->node->next_sibling;
2473 while(this->node->first_child==0) {
2474 if(this->node->next_sibling==0)
2475 goto upper;
2476 this->node=this->node->next_sibling;
2477 if(this->node==0) return *this;
2478 }
2479 while(relative_depth<0 && this->node->first_child!=0) {
2480 this->node=this->node->first_child;
2481 ++relative_depth;
2482 }
2483 if(relative_depth<0) {
2484 if(this->node->next_sibling==0) goto upper;
2485 else goto lower;
2486 }
2487 }
2488 return *this;
2489 }
2490
2491 template <class T, class tree_node_allocator>
operator --()2492 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--()
2493 {
2494 assert(this->node!=0);
2495
2496 if(this->node->prev_sibling) {
2497 this->node=this->node->prev_sibling;
2498 }
2499 else {
2500 int relative_depth=0;
2501 upper:
2502 do {
2503 if(this->node==this->top_node) {
2504 this->node=0;
2505 return *this;
2506 }
2507 this->node=this->node->parent;
2508 if(this->node==0) return *this;
2509 --relative_depth;
2510 } while(this->node->prev_sibling==0);
2511 lower:
2512 this->node=this->node->prev_sibling;
2513 while(this->node->last_child==0) {
2514 if(this->node->prev_sibling==0)
2515 goto upper;
2516 this->node=this->node->prev_sibling;
2517 if(this->node==0) return *this;
2518 }
2519 while(relative_depth<0 && this->node->last_child!=0) {
2520 this->node=this->node->last_child;
2521 ++relative_depth;
2522 }
2523 if(relative_depth<0) {
2524 if(this->node->prev_sibling==0) goto upper;
2525 else goto lower;
2526 }
2527 }
2528 return *this;
2529
2530 //
2531 //
2532 // assert(this->node!=0);
2533 // if(this->node->prev_sibling!=0) {
2534 // this->node=this->node->prev_sibling;
2535 // assert(this->node!=0);
2536 // if(this->node->parent==0 && this->node->prev_sibling==0) // head element
2537 // this->node=0;
2538 // }
2539 // else {
2540 // tree_node *par=this->node->parent;
2541 // do {
2542 // par=par->prev_sibling;
2543 // if(par==0) { // FIXME: need to keep track of this!
2544 // this->node=0;
2545 // return *this;
2546 // }
2547 // } while(par->last_child==0);
2548 // this->node=par->last_child;
2549 // }
2550 // return *this;
2551 }
2552
2553 template <class T, class tree_node_allocator>
operator ++(int)2554 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++(int)
2555 {
2556 fixed_depth_iterator copy = *this;
2557 ++(*this);
2558 return copy;
2559 }
2560
2561 template <class T, class tree_node_allocator>
operator --(int)2562 typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--(int)
2563 {
2564 fixed_depth_iterator copy = *this;
2565 --(*this);
2566 return copy;
2567 }
2568
2569 template <class T, class tree_node_allocator>
operator -=(unsigned int num)2570 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=(unsigned int num)
2571 {
2572 while(num>0) {
2573 --(*this);
2574 --(num);
2575 }
2576 return (*this);
2577 }
2578
2579 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2580 typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=(unsigned int num)
2581 {
2582 while(num>0) {
2583 ++(*this);
2584 --(num);
2585 }
2586 return *this;
2587 }
2588
2589
2590 // Sibling iterator
2591
2592 template <class T, class tree_node_allocator>
sibling_iterator()2593 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator()
2594 : iterator_base()
2595 {
2596 set_parent_();
2597 }
2598
2599 template <class T, class tree_node_allocator>
sibling_iterator(tree_node * tn)2600 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(tree_node *tn)
2601 : iterator_base(tn)
2602 {
2603 set_parent_();
2604 }
2605
2606 template <class T, class tree_node_allocator>
sibling_iterator(const iterator_base & other)2607 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const iterator_base& other)
2608 : iterator_base(other.node)
2609 {
2610 set_parent_();
2611 }
2612
2613 template <class T, class tree_node_allocator>
sibling_iterator(const sibling_iterator & other)2614 tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator(const sibling_iterator& other)
2615 : iterator_base(other), parent_(other.parent_)
2616 {
2617 }
2618
2619 template <class T, class tree_node_allocator>
set_parent_()2620 void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
2621 {
2622 parent_=0;
2623 if(this->node==0) return;
2624 if(this->node->parent!=0)
2625 parent_=this->node->parent;
2626 }
2627
2628 template <class T, class tree_node_allocator>
operator ++()2629 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++()
2630 {
2631 if(this->node)
2632 this->node=this->node->next_sibling;
2633 return *this;
2634 }
2635
2636 template <class T, class tree_node_allocator>
operator --()2637 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--()
2638 {
2639 if(this->node) this->node=this->node->prev_sibling;
2640 else {
2641 assert(parent_);
2642 this->node=parent_->last_child;
2643 }
2644 return *this;
2645 }
2646
2647 template <class T, class tree_node_allocator>
operator ++(int)2648 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++(int)
2649 {
2650 sibling_iterator copy = *this;
2651 ++(*this);
2652 return copy;
2653 }
2654
2655 template <class T, class tree_node_allocator>
operator --(int)2656 typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--(int)
2657 {
2658 sibling_iterator copy = *this;
2659 --(*this);
2660 return copy;
2661 }
2662
2663 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2664 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=(unsigned int num)
2665 {
2666 while(num>0) {
2667 ++(*this);
2668 --num;
2669 }
2670 return (*this);
2671 }
2672
2673 template <class T, class tree_node_allocator>
operator -=(unsigned int num)2674 typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=(unsigned int num)
2675 {
2676 while(num>0) {
2677 --(*this);
2678 --num;
2679 }
2680 return (*this);
2681 }
2682
2683 template <class T, class tree_node_allocator>
range_first() const2684 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_first() const
2685 {
2686 tree_node *tmp=parent_->first_child;
2687 return tmp;
2688 }
2689
2690 template <class T, class tree_node_allocator>
range_last() const2691 typename tree<T, tree_node_allocator>::tree_node *tree<T, tree_node_allocator>::sibling_iterator::range_last() const
2692 {
2693 return parent_->last_child;
2694 }
2695
2696 // Leaf iterator
2697
2698 template <class T, class tree_node_allocator>
leaf_iterator()2699 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator()
2700 : iterator_base(0), top_node(0)
2701 {
2702 }
2703
2704 template <class T, class tree_node_allocator>
leaf_iterator(tree_node * tn,tree_node * top)2705 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(tree_node *tn, tree_node *top)
2706 : iterator_base(tn), top_node(top)
2707 {
2708 }
2709
2710 template <class T, class tree_node_allocator>
leaf_iterator(const iterator_base & other)2711 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const iterator_base &other)
2712 : iterator_base(other.node), top_node(0)
2713 {
2714 }
2715
2716 template <class T, class tree_node_allocator>
leaf_iterator(const sibling_iterator & other)2717 tree<T, tree_node_allocator>::leaf_iterator::leaf_iterator(const sibling_iterator& other)
2718 : iterator_base(other.node), top_node(0)
2719 {
2720 if(this->node==0) {
2721 if(other.range_last()!=0)
2722 this->node=other.range_last();
2723 else
2724 this->node=other.parent_;
2725 ++(*this);
2726 }
2727 }
2728
2729 template <class T, class tree_node_allocator>
operator ++()2730 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++()
2731 {
2732 assert(this->node!=0);
2733 if(this->node->first_child!=0) { // current node is no longer leaf (children got added)
2734 while(this->node->first_child)
2735 this->node=this->node->first_child;
2736 }
2737 else {
2738 while(this->node->next_sibling==0) {
2739 if (this->node->parent==0) return *this;
2740 this->node=this->node->parent;
2741 if (top_node != 0 && this->node==top_node) return *this;
2742 }
2743 this->node=this->node->next_sibling;
2744 while(this->node->first_child)
2745 this->node=this->node->first_child;
2746 }
2747 return *this;
2748 }
2749
2750 template <class T, class tree_node_allocator>
operator --()2751 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--()
2752 {
2753 assert(this->node!=0);
2754 while (this->node->prev_sibling==0) {
2755 if (this->node->parent==0) return *this;
2756 this->node=this->node->parent;
2757 if (top_node !=0 && this->node==top_node) return *this;
2758 }
2759 this->node=this->node->prev_sibling;
2760 while(this->node->last_child)
2761 this->node=this->node->last_child;
2762 return *this;
2763 }
2764
2765 template <class T, class tree_node_allocator>
operator ++(int)2766 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++(int)
2767 {
2768 leaf_iterator copy = *this;
2769 ++(*this);
2770 return copy;
2771 }
2772
2773 template <class T, class tree_node_allocator>
operator --(int)2774 typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--(int)
2775 {
2776 leaf_iterator copy = *this;
2777 --(*this);
2778 return copy;
2779 }
2780
2781
2782 template <class T, class tree_node_allocator>
operator +=(unsigned int num)2783 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=(unsigned int num)
2784 {
2785 while(num>0) {
2786 ++(*this);
2787 --num;
2788 }
2789 return (*this);
2790 }
2791
2792 template <class T, class tree_node_allocator>
operator -=(unsigned int num)2793 typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=(unsigned int num)
2794 {
2795 while(num>0) {
2796 --(*this);
2797 --num;
2798 }
2799 return (*this);
2800 }
2801
2802 #endif
2803
2804 // Local variables:
2805 // default-tab-width: 3
2806 // End:
2807