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