libbase/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 /** \page 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, 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 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: