cppconsui/tree.hh

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