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