tree.h

Go to the documentation of this file.

//  STL-like templated tree class.
//
// Copyright (C) 2001-2011 Kasper Peeters <kasper* @phi-sci.com>
// Distributed under the GNU General Public License version 3.
//
// When used together with the htmlcxx library to create
// HTML::Node template instances, the GNU Lesser General Public
// version 2 applies. Special permission to use tree.hh under
// the LGPL for other projects can be requested from the author.

#ifndef TREE_H
#define TREE_H

#include <cassert>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <set>
#include <queue>
#include <algorithm>
#include <cstddef>

namespace GiNaCRA
{


template<class T>
class tree_node_ // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
{
public:
    tree_node_( );
    tree_node_( const T& );

    tree_node_<T> *parent;
    tree_node_<T> *first_child, *last_child;
    tree_node_<T> *prev_sibling, *next_sibling;
    T data;
}; // __attribute__((packed));

template<class T>
tree_node_<T>
::tree_node_( )
: parent( 0 ), first_child( 0 ), last_child( 0 ), prev_sibling( 0 ), next_sibling( 0 ){ }

template<class T>
tree_node_<T>
::tree_node_( const T& val )
: parent( 0 ), first_child( 0 ), last_child( 0 ), prev_sibling( 0 ), next_sibling( 0 ), data( val ){ }

template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
class tree
{
protected:
    typedef tree_node_<T> tree_node;
public:
    typedef T value_type;

    class iterator_base;
    class pre_order_iterator;
    class post_order_iterator;
    class sibling_iterator;
    class leaf_iterator;

    tree( );
    tree( const T& );
    tree( const iterator_base& );
    tree( const tree<T, tree_node_allocator>& );
    ~tree( );
    tree<T, tree_node_allocator>& operator=( const tree<T, tree_node_allocator>& );

#ifdef __SGI_STL_PORT

    class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t>
    {
#else

    class iterator_base
    {
#endif
    public:
        typedef T value_type;
        typedef T* pointer;
        typedef T& reference;
        typedef size_t size_type;
        typedef ptrdiff_t difference_type;
        typedef std::bidirectional_iterator_tag iterator_category;

        iterator_base( );
        iterator_base( tree_node* );

        T& operator*( ) const;
        T* operator->( ) const;

        void skip_children( );
        void skip_children( bool skip );
        unsigned int number_of_children( ) const;

        sibling_iterator begin( ) const;
        sibling_iterator end( ) const;

        tree_node* node;
    protected:
        bool skip_current_children_;
    };


    class pre_order_iterator : public iterator_base
    {
    public:
        pre_order_iterator( );
        pre_order_iterator( tree_node* );
        pre_order_iterator( const iterator_base& );
        pre_order_iterator( const sibling_iterator& );

        bool operator==( const pre_order_iterator& ) const;
        bool operator!=( const pre_order_iterator& ) const;
        pre_order_iterator& operator++( );
        pre_order_iterator& operator--( );
        pre_order_iterator operator++( int );
        pre_order_iterator operator--( int );
        pre_order_iterator& operator+=( unsigned int );
        pre_order_iterator& operator-=( unsigned int );
    };


    class post_order_iterator : public iterator_base
    {
    public:
        post_order_iterator( );
        post_order_iterator( tree_node* );
        post_order_iterator( const iterator_base& );
        post_order_iterator( const sibling_iterator& );

        bool operator==( const post_order_iterator& ) const;
        bool operator!=( const post_order_iterator& ) const;
        post_order_iterator& operator++( );
        post_order_iterator& operator--( );
        post_order_iterator operator++( int );
        post_order_iterator operator--( int );
        post_order_iterator& operator+=( unsigned int );
        post_order_iterator& operator-=( unsigned int );

        void descend_all( );
    };


    class breadth_first_queued_iterator : public iterator_base
    {
    public:
        breadth_first_queued_iterator( );
        breadth_first_queued_iterator( tree_node* );
        breadth_first_queued_iterator( const iterator_base& );

        bool operator==( const breadth_first_queued_iterator& ) const;
        bool operator!=( const breadth_first_queued_iterator& ) const;
        breadth_first_queued_iterator& operator++( );
        breadth_first_queued_iterator operator++( int );
        breadth_first_queued_iterator& operator+=( unsigned int );

    private:
        std::queue<tree_node*> traversal_queue;
    };

    typedef pre_order_iterator iterator;
    typedef breadth_first_queued_iterator breadth_first_iterator;


    class fixed_depth_iterator : public iterator_base
    {
    public:
        fixed_depth_iterator( );
        fixed_depth_iterator( tree_node* );
        fixed_depth_iterator( const iterator_base& );
        fixed_depth_iterator( const sibling_iterator& );
        fixed_depth_iterator( const fixed_depth_iterator& );

        bool operator==( const fixed_depth_iterator& ) const;
        bool operator!=( const fixed_depth_iterator& ) const;
        fixed_depth_iterator& operator++( );
        fixed_depth_iterator& operator--( );
        fixed_depth_iterator operator++( int );
        fixed_depth_iterator operator--( int );
        fixed_depth_iterator& operator+=( unsigned int );
        fixed_depth_iterator& operator-=( unsigned int );

        tree_node* top_node;
    };


    class sibling_iterator : public iterator_base
    {
    public:
        sibling_iterator( );
        sibling_iterator( tree_node* );
        sibling_iterator( const sibling_iterator& );
        sibling_iterator( const iterator_base& );

        bool operator==( const sibling_iterator& ) const;
        bool operator!=( const sibling_iterator& ) const;
        sibling_iterator& operator++( );
        sibling_iterator& operator--( );
        sibling_iterator operator++( int );
        sibling_iterator operator--( int );
        sibling_iterator& operator+=( unsigned int );
        sibling_iterator& operator-=( unsigned int );

        tree_node* range_first( ) const;
        tree_node* range_last( ) const;
        tree_node* parent_;
    private:
        void set_parent_( );
    };


    class leaf_iterator : public iterator_base
    {
    public:
        leaf_iterator( );
        leaf_iterator( tree_node*, tree_node* top = 0 );
        leaf_iterator( const sibling_iterator& );
        leaf_iterator( const iterator_base& );

        bool operator==( const leaf_iterator& ) const;
        bool operator!=( const leaf_iterator& ) const;
        leaf_iterator& operator++( );
        leaf_iterator& operator--( );
        leaf_iterator operator++( int );
        leaf_iterator operator--( int );
        leaf_iterator& operator+=( unsigned int );
        leaf_iterator& operator-=( unsigned int );
    private:
        tree_node* top_node;
    };

    inline pre_order_iterator begin( ) const;
    inline pre_order_iterator end( ) const;
    post_order_iterator begin_post( ) const;
    post_order_iterator end_post( ) const;
    fixed_depth_iterator begin_fixed( const iterator_base&, unsigned int ) const;
    fixed_depth_iterator end_fixed( const iterator_base&, unsigned int ) const;
    breadth_first_queued_iterator begin_breadth_first( ) const;
    breadth_first_queued_iterator end_breadth_first( ) const;
    sibling_iterator begin( const iterator_base& ) const;
    sibling_iterator end( const iterator_base& ) const;
    leaf_iterator begin_leaf( ) const;
    leaf_iterator end_leaf( ) const;
    leaf_iterator begin_leaf( const iterator_base& top ) const;
    leaf_iterator end_leaf( const iterator_base& top ) const;

    template<typename iter> static iter parent( iter );
    template<typename iter> iter previous_sibling( iter ) const;
    template<typename iter> iter next_sibling( iter ) const;
    template<typename iter> iter next_at_same_depth( iter ) const;

    void clear( );
    template<typename iter> iter erase( iter );
    void erase_children( const iterator_base& );

    template<typename iter> iter append_child( iter position );
    template<typename iter> iter prepend_child( iter position );
    template<typename iter> iter append_child( iter position, const T& x );
    template<typename iter> iter prepend_child( iter position, const T& x );
    template<typename iter> iter append_child( iter position, iter other_position );
    template<typename iter> iter prepend_child( iter position, iter other_position );
    template<typename iter> iter append_children( iter position, sibling_iterator from, sibling_iterator to );
    template<typename iter> iter prepend_children( iter position, sibling_iterator from, sibling_iterator to );

    pre_order_iterator set_head( const T& x );
    template<typename iter> iter insert( iter position, const T& x );
    sibling_iterator insert( sibling_iterator position, const T& x );
    template<typename iter> iter insert_subtree( iter position, const iterator_base& subtree );
    template<typename iter> iter insert_after( iter position, const T& x );
    template<typename iter> iter insert_subtree_after( iter position, const iterator_base& subtree );

    template<typename iter> iter replace( iter position, const T& x );
    template<typename iter> iter replace( iter position, const iterator_base& from );
    sibling_iterator replace( sibling_iterator orig_begin, sibling_iterator orig_end,
                              sibling_iterator new_begin, sibling_iterator new_end );

    template<typename iter> iter flatten( iter position );
    template<typename iter> iter reparent( iter position, sibling_iterator begin, sibling_iterator end );
    template<typename iter> iter reparent( iter position, iter from );

    template<typename iter> iter wrap( iter position, const T& x );

    template<typename iter> iter move_after( iter target, iter source );
    template<typename iter> iter move_before( iter target, iter source );
    sibling_iterator move_before( sibling_iterator target, sibling_iterator source );
    template<typename iter> iter move_ontop( iter target, iter source );

    void merge( sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator,
                bool duplicate_leaves = false );
    void sort( sibling_iterator from, sibling_iterator to, bool deep = false );
    template<class StrictWeakOrdering>
    void sort( sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep = false );
    template<typename iter>
    bool equal( const iter& one, const iter& two, const iter& three ) const;
    template<typename iter, class BinaryPredicate>
    bool equal( const iter& one, const iter& two, const iter& three, BinaryPredicate ) const;
    template<typename iter>
    bool equal_subtree( const iter& one, const iter& two ) const;
    template<typename iter, class BinaryPredicate>
    bool equal_subtree( const iter& one, const iter& two, BinaryPredicate ) const;
    tree subtree( sibling_iterator from, sibling_iterator to ) const;
    void subtree( tree&, sibling_iterator from, sibling_iterator to ) const;
    void swap( sibling_iterator it );
    void swap( iterator, iterator );

    size_t size( ) const;
    size_t size( const iterator_base& ) const;
    bool empty( ) const;
    static int depth( const iterator_base& );
    static int depth( const iterator_base&, const iterator_base& );
    int max_depth( ) const;
    int max_depth( const iterator_base& ) const;
    static unsigned int number_of_children( const iterator_base& );
    unsigned int number_of_siblings( const iterator_base& ) const;
    bool is_in_subtree( const iterator_base& position, const iterator_base& begin,
                        const iterator_base& end ) const;
    bool is_valid( const iterator_base& ) const;
    iterator lowest_common_ancestor( const iterator_base&, const iterator_base& ) const;

    unsigned int index( sibling_iterator it ) const;
    static sibling_iterator child( const iterator_base& position, unsigned int );
    sibling_iterator sibling( const iterator_base& position, unsigned int );

    void
    debug_verify_consistency( ) const;


    class iterator_base_less
    {
    public:

        bool operator( )( const typename tree<T, tree_node_allocator>::iterator_base& one,
                          const typename tree<T, tree_node_allocator>::iterator_base& two ) const
        {
            return one.node < two.node;
        }
    };
    tree_node* head, *feet; // head/feet are always dummy; if an iterator points to them it is invalid
private:
    tree_node_allocator alloc_;
    void head_initialise_( );
    void
    copy_( const tree<T, tree_node_allocator>& other );


    template<class StrictWeakOrdering>
    class compare_nodes
    {
    public:

        compare_nodes( StrictWeakOrdering comp ) : comp_( comp ){ };

        bool operator( )( const tree_node* a, const tree_node* b )
        {
            return comp_( a->data, b->data );
        }
    private:
        StrictWeakOrdering comp_;
    };
};

//template <class T, class tree_node_allocator>
//class iterator_base_less {
//  public:
//      bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
//                        const typename tree<T, tree_node_allocator>::iterator_base& two) const
//          {
//          txtout << "operatorclass<" << one.node < two.node << std::endl;
//          return one.node < two.node;
//          }
//};

// template <class T, class tree_node_allocator>
// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
//                  const typename tree<T, tree_node_allocator>::iterator& two)
//  {
//  txtout << "operator< " << one.node < two.node << std::endl;
//  if(one.node < two.node) return true;
//  return false;
//  }
//
// template <class T, class tree_node_allocator>
// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
//                  const typename tree<T, tree_node_allocator>::iterator& two)
//  {
//  txtout << "operator== " << one.node == two.node << std::endl;
//  if(one.node == two.node) return true;
//  return false;
//  }
//
// template <class T, class tree_node_allocator>
// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
//                  const typename tree<T, tree_node_allocator>::iterator_base& two)
//  {
//  txtout << "operator> " << one.node < two.node << std::endl;
//  if(one.node > two.node) return true;
//  return false;
//  }



// Tree

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::tree( )
{
    head_initialise_( );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::tree( const T& x )
{
    head_initialise_( );
    set_head( x );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::tree( const iterator_base& other )
{
    head_initialise_( );
    set_head( ( *other ) );
    replace( begin( ), other );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::~tree( )
{
    clear( );
    alloc_.destroy( head );
    alloc_.destroy( feet );
    alloc_.deallocate( head, 1 );
    alloc_.deallocate( feet, 1 );
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::head_initialise_( )
{
    head = alloc_.allocate( 1, 0 ); // MSVC does not have default second argument
    feet = alloc_.allocate( 1, 0 );
    alloc_.construct( head, tree_node_<T > ( ) );
    alloc_.construct( feet, tree_node_<T > ( ) );

    head->parent = 0;
    head->first_child = 0;
    head->last_child = 0;
    head->prev_sibling = 0; //head;
    head->next_sibling = feet; //head;

    feet->parent = 0;
    feet->first_child = 0;
    feet->last_child = 0;
    feet->prev_sibling = head;
    feet->next_sibling = 0;
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>& tree<T, tree_node_allocator>::operator=( const tree<T, tree_node_allocator>& other )
{
    if( this != &other )
        copy_( other );

    return *this;
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::tree( const tree<T, tree_node_allocator>& other )
{
    head_initialise_( );
    copy_( other );
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::copy_( const tree<T, tree_node_allocator>& other )
{
    clear( );
    pre_order_iterator it = other.begin( ), to = begin( );

    while( it != other.end( ) )
    {
        to = insert( to, ( *it ) );
        it.skip_children( );
        ++it;
    }

    to = begin( );
    it = other.begin( );

    while( it != other.end( ) )
    {
        to = replace( to, it );
        to.skip_children( );
        it.skip_children( );
        ++to;
        ++it;
    }
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::clear( )
{
    if( head )
        while( head->next_sibling != feet )
            erase( pre_order_iterator( head->next_sibling ) );
}

template<class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::erase_children( const iterator_base& it )
{
    //  std::cout << "erase_children " << it.node << std::endl;
    if( it.node == 0 ) return;

    tree_node* cur = it.node->first_child;
    tree_node* prev = 0;

    while( cur != 0 )
    {
        prev = cur;
        cur = cur->next_sibling;
        erase_children( pre_order_iterator( prev ) );
        //      kp::destructor(&prev->data);
        alloc_.destroy( prev );
        alloc_.deallocate( prev, 1 );
    }

    it.node->first_child = 0;
    it.node->last_child = 0;
    //  std::cout << "exit" << std::endl;
}

template<class T, class tree_node_allocator>
template<class iter>
iter tree<T, tree_node_allocator>
::erase( iter it )
{
    tree_node* cur = it.node;
    assert( cur != head );
    iter ret = it;
    ret.skip_children( );
    ++ret;
    erase_children( it );

    if( cur->prev_sibling == 0 )
    {
        cur->parent->first_child = cur->next_sibling;
    }

    else
    {
        cur->prev_sibling->next_sibling = cur->next_sibling;
    }

    if( cur->next_sibling == 0 )
    {
        cur->parent->last_child = cur->prev_sibling;
    }

    else
    {
        cur->next_sibling->prev_sibling = cur->prev_sibling;
    }

    //  kp::destructor(&cur->data);
    alloc_.destroy( cur );
    alloc_.deallocate( cur, 1 );
    return ret;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>
::begin( ) const
{
    return pre_order_iterator( head->next_sibling );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>
::end( ) const
{
    return pre_order_iterator( feet );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>
::begin_breadth_first( ) const
{
    return breadth_first_queued_iterator( head->next_sibling );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>
::end_breadth_first( ) const
{
    return breadth_first_queued_iterator( );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>
::begin_post( ) const
{
    tree_node* tmp = head->next_sibling;

    if( tmp != feet )
    {
        while( tmp->first_child )
            tmp = tmp->first_child;
    }

    return post_order_iterator( tmp );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>
::end_post( ) const
{
    return post_order_iterator( feet );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>
::begin_fixed( const iterator_base& pos, unsigned int dp ) const
{
    typename tree<T, tree_node_allocator>::fixed_depth_iterator ret;
    ret.top_node = pos.node;

    tree_node* tmp = pos.node;
    unsigned int curdepth = 0;

    while( curdepth < dp ) // go down one level
    {
        while( tmp->first_child == 0 )
        {
            if( tmp->next_sibling == 0 )
            {
                // try to walk up and then right again
                do
                {
                    if( tmp == ret.top_node )
                        throw std::range_error( "tree: begin_fixed out of range" );

                    tmp = tmp->parent;

                    if( tmp == 0 )
                        throw std::range_error( "tree: begin_fixed out of range" );

                    --curdepth;
                }
                while( tmp->next_sibling == 0 );
            }

            tmp = tmp->next_sibling;
        }

        tmp = tmp->first_child;
        ++curdepth;
    }

    ret.node = tmp;
    return ret;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>
::end_fixed( const iterator_base& pos, unsigned int dp ) const
{
    assert( 1 == 0 ); // FIXME: not correct yet: use is_valid() as a temporary workaround
    tree_node* tmp = pos.node;
    unsigned int curdepth = 1;

    while( curdepth < dp ) // go down one level
    {
        while( tmp->first_child == 0 )
        {
            tmp = tmp->next_sibling;

            if( tmp == 0 )
                throw std::range_error( "tree: end_fixed out of range" );
        }

        tmp = tmp->first_child;
        ++curdepth;
    }

    return tmp;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::begin( const iterator_base& pos ) const
{
    assert( pos.node != 0 );

    if( pos.node->first_child == 0 )
    {
        return end( pos );
    }

    return pos.node->first_child;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::end( const iterator_base& pos ) const
{
    sibling_iterator ret( 0 );
    ret.parent_ = pos.node;
    return ret;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>
::begin_leaf( ) const
{
    tree_node* tmp = head->next_sibling;

    if( tmp != feet )
    {
        while( tmp->first_child )
            tmp = tmp->first_child;
    }

    return leaf_iterator( tmp );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>
::end_leaf( ) const
{
    return leaf_iterator( feet );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>
::begin_leaf( const iterator_base& top ) const
{
    tree_node* tmp = top.node;

    while( tmp->first_child )
        tmp = tmp->first_child;

    return leaf_iterator( tmp, top.node );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>
::end_leaf( const iterator_base& top ) const
{
    return leaf_iterator( top.node, top.node );
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::parent( iter position )
{
    assert( position.node != 0 );
    return iter( position.node->parent );
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::previous_sibling( iter position ) const
{
    assert( position.node != 0 );
    iter ret( position );
    ret.node = position.node->prev_sibling;
    return ret;
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::next_sibling( iter position ) const
{
    assert( position.node != 0 );
    iter ret( position );
    ret.node = position.node->next_sibling;
    return ret;
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::next_at_same_depth( iter position ) const
{
    // We make use of a temporary fixed_depth iterator to implement this.

    typename tree<T, tree_node_allocator>::fixed_depth_iterator tmp( position.node );

    ++tmp;
    return iter( tmp );

    //  assert(position.node!=0);
    //  iter ret(position);
    //
    //  if(position.node->next_sibling) {
    //      ret.node=position.node->next_sibling;
    //      }
    //  else {
    //      int relative_depth=0;
    //     upper:
    //      do {
    //          ret.node=ret.node->parent;
    //          if(ret.node==0) return ret;
    //          --relative_depth;
    //          } while(ret.node->next_sibling==0);
    //     lower:
    //      ret.node=ret.node->next_sibling;
    //      while(ret.node->first_child==0) {
    //          if(ret.node->next_sibling==0)
    //              goto upper;
    //          ret.node=ret.node->next_sibling;
    //          if(ret.node==0) return ret;
    //          }
    //      while(relative_depth<0 && ret.node->first_child!=0) {
    //          ret.node=ret.node->first_child;
    //          ++relative_depth;
    //          }
    //      if(relative_depth<0) {
    //          if(ret.node->next_sibling==0) goto upper;
    //          else                          goto lower;
    //          }
    //      }
    //  return ret;
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::append_child( iter position )
{
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, tree_node_<T > ( ) );
    //  kp::constructor(&tmp->data);
    tmp->first_child = 0;
    tmp->last_child = 0;

    tmp->parent = position.node;

    if( position.node->last_child != 0 )
    {
        position.node->last_child->next_sibling = tmp;
    }

    else
    {
        position.node->first_child = tmp;
    }

    tmp->prev_sibling = position.node->last_child;
    position.node->last_child = tmp;
    tmp->next_sibling = 0;
    return tmp;
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::prepend_child( iter position )
{
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, tree_node_<T > ( ) );
    //  kp::constructor(&tmp->data);
    tmp->first_child = 0;
    tmp->last_child = 0;

    tmp->parent = position.node;

    if( position.node->first_child != 0 )
    {
        position.node->first_child->prev_sibling = tmp;
    }

    else
    {
        position.node->last_child = tmp;
    }

    tmp->next_sibling = position.node->first_child;
    position.node->prev_child = tmp;
    tmp->prev_sibling = 0;
    return tmp;
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::append_child( iter position, const T& x )
{
    // If your program fails here you probably used 'append_child' to add the top
    // node to an empty tree. From version 1.45 the top element should be added
    // using 'insert'. See the documentation for further information, and sorry about
    // the API change.
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, x );
    //  kp::constructor(&tmp->data, x);
    tmp->first_child = 0;
    tmp->last_child = 0;

    tmp->parent = position.node;

    if( position.node->last_child != 0 )
    {
        position.node->last_child->next_sibling = tmp;
    }

    else
    {
        position.node->first_child = tmp;
    }

    tmp->prev_sibling = position.node->last_child;
    position.node->last_child = tmp;
    tmp->next_sibling = 0;
    return tmp;
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::prepend_child( iter position, const T& x )
{
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, x );
    //  kp::constructor(&tmp->data, x);
    tmp->first_child = 0;
    tmp->last_child = 0;

    tmp->parent = position.node;

    if( position.node->first_child != 0 )
    {
        position.node->first_child->prev_sibling = tmp;
    }

    else
    {
        position.node->last_child = tmp;
    }

    tmp->next_sibling = position.node->first_child;
    position.node->first_child = tmp;
    tmp->prev_sibling = 0;
    return tmp;
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::append_child( iter position, iter other )
{
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    sibling_iterator aargh = append_child( position, value_type( ) );
    return replace( aargh, other );
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::prepend_child( iter position, iter other )
{
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    sibling_iterator aargh = prepend_child( position, value_type( ) );
    return replace( aargh, other );
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::append_children( iter position, sibling_iterator from, sibling_iterator to )
{
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    iter ret = from;

    while( from != to )
    {
        insert_subtree( position.end( ), from );
        ++from;
    }

    return ret;
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::prepend_children( iter position, sibling_iterator from, sibling_iterator to )
{
    assert( position.node != head );
    assert( position.node != feet );
    assert( position.node );

    iter ret = from;

    while( from != to )
    {
        insert_subtree( position.begin( ), from );
        ++from;
    }

    return ret;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>
::set_head( const T& x )
{
    assert( head->next_sibling == feet );
    return insert( iterator( feet ), x );
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::insert( iter position, const T& x )
{
    if( position.node == 0 )
    {
        position.node = feet; // Backward compatibility: when calling insert on a null node,
        // insert before the feet.
    }

    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, x );
    //  kp::constructor(&tmp->data, x);
    tmp->first_child = 0;
    tmp->last_child = 0;

    tmp->parent = position.node->parent;
    tmp->next_sibling = position.node;
    tmp->prev_sibling = position.node->prev_sibling;
    position.node->prev_sibling = tmp;

    if( tmp->prev_sibling == 0 )
    {
        if( tmp->parent ) // when inserting nodes at the head, there is no parent
            tmp->parent->first_child = tmp;
    }

    else
        tmp->prev_sibling->next_sibling = tmp;

    return tmp;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::insert( sibling_iterator position, const T& x )
{
    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, x );
    //  kp::constructor(&tmp->data, x);
    tmp->first_child = 0;
    tmp->last_child = 0;

    tmp->next_sibling = position.node;

    if( position.node == 0 ) // iterator points to end of a subtree
    {
        tmp->parent = position.parent_;
        tmp->prev_sibling = position.range_last( );
        tmp->parent->last_child = tmp;
    }

    else
    {
        tmp->parent = position.node->parent;
        tmp->prev_sibling = position.node->prev_sibling;
        position.node->prev_sibling = tmp;
    }

    if( tmp->prev_sibling == 0 )
    {
        if( tmp->parent ) // when inserting nodes at the head, there is no parent
            tmp->parent->first_child = tmp;
    }

    else
        tmp->prev_sibling->next_sibling = tmp;

    return tmp;
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::insert_after( iter position, const T& x )
{
    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, x );
    //  kp::constructor(&tmp->data, x);
    tmp->first_child = 0;
    tmp->last_child = 0;

    tmp->parent = position.node->parent;
    tmp->prev_sibling = position.node;
    tmp->next_sibling = position.node->next_sibling;
    position.node->next_sibling = tmp;

    if( tmp->next_sibling == 0 )
    {
        if( tmp->parent ) // when inserting nodes at the head, there is no parent
            tmp->parent->last_child = tmp;
    }

    else
    {
        tmp->next_sibling->prev_sibling = tmp;
    }

    return tmp;
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::insert_subtree( iter position, const iterator_base& subtree )
{
    // insert dummy
    iter it = insert( position, value_type( ) );
    // replace dummy with subtree
    return replace( it, subtree );
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::insert_subtree_after( iter position, const iterator_base& subtree )
{
    // insert dummy
    iter it = insert_after( position, value_type( ) );
    // replace dummy with subtree
    return replace( it, subtree );
}

// template <class T, class tree_node_allocator>
// template <class iter>
// iter tree<T, tree_node_allocator>::insert_subtree(sibling_iterator position, iter subtree)
//  {
//  // insert dummy
//  iter it(insert(position, value_type()));
//  // replace dummy with subtree
//  return replace(it, subtree);
//  }

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::replace( iter position, const T& x )
{
    //  kp::destructor(&position.node->data);
    //  kp::constructor(&position.node->data, x);
    position.node->data = x;
    //  alloc_.destroy(position.node);
    //  alloc_.construct(position.node, x);
    return position;
}

template <class T, class tree_node_allocator>
template <class iter>
iter tree<T, tree_node_allocator>
::replace( iter position, const iterator_base& from )
{
    assert( position.node != head );
    tree_node* current_from = from.node;
    tree_node* start_from = from.node;
    tree_node* current_to = position.node;

    // replace the node at position with head of the replacement tree at from
    //  std::cout << "warning!" << position.node << std::endl;
    erase_children( position );
    //  std::cout << "no warning!" << std::endl;
    tree_node* tmp = alloc_.allocate( 1, 0 );
    alloc_.construct( tmp, ( *from ) );
    //  kp::constructor(&tmp->data, (*from));
    tmp->first_child = 0;
    tmp->last_child = 0;

    if( current_to->prev_sibling == 0 )
    {
        if( current_to->parent != 0 )
            current_to->parent->first_child = tmp;
    }

    else
    {
        current_to->prev_sibling->next_sibling = tmp;
    }

    tmp->prev_sibling = current_to->prev_sibling;

    if( current_to->next_sibling == 0 )
    {
        if( current_to->parent != 0 )
            current_to->parent->last_child = tmp;
    }

    else
    {
        current_to->next_sibling->prev_sibling = tmp;
    }

    tmp->next_sibling = current_to->next_sibling;
    tmp->parent = current_to->parent;
    //  kp::destructor(&current_to->data);
    alloc_.destroy( current_to );
    alloc_.deallocate( current_to, 1 );
    current_to = tmp;

    // only at this stage can we fix 'last'
    tree_node* last = from.node->next_sibling;

    pre_order_iterator toit = tmp;

    // copy all children
    do
    {
        assert( current_from != 0 );

        if( current_from->first_child != 0 )
        {
            current_from = current_from->first_child;
            toit = append_child( toit, current_from->data );
        }

        else
        {
            while( current_from->next_sibling == 0 && current_from != start_from )
            {
                current_from = current_from->parent;
                toit = parent( toit );
                assert( current_from != 0 );
            }

            current_from = current_from->next_sibling;

            if( current_from != last )
            {
                toit = append_child( parent( toit ), current_from->data );
            }
        }
    }
    while( current_from != last );

    return current_to;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::replace(
         sibling_iterator orig_begin,
         sibling_iterator orig_end,
         sibling_iterator new_begin,
         sibling_iterator new_end )
{
    tree_node* orig_first = orig_begin.node;
    tree_node* new_first = new_begin.node;
    tree_node* orig_last = orig_first;

    while( ( ++orig_begin ) != orig_end )
        orig_last = orig_last->next_sibling;

    tree_node* new_last = new_first;

    while( ( ++new_begin ) != new_end )
        new_last = new_last->next_sibling;

    // insert all siblings in new_first..new_last before orig_first
    bool first = true;
    pre_order_iterator ret;

    while( 1 == 1 )
    {
        pre_order_iterator tt = insert_subtree( pre_order_iterator( orig_first ), pre_order_iterator( new_first ) );

        if( first )
        {
            ret = tt;
            first = false;
        }

        if( new_first == new_last )
            break;

        new_first = new_first->next_sibling;
    }

    // erase old range of siblings
    bool last = false;
    tree_node* next = orig_first;

    while( 1 == 1 )
    {
        if( next == orig_last )
            last = true;

        next = next->next_sibling;
        erase( ( pre_order_iterator ) orig_first );

        if( last )
            break;

        orig_first = next;
    }

    return ret;
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::flatten( iter position )
{
    if( position.node->first_child == 0 )
        return position;

    tree_node* tmp = position.node->first_child;

    while( tmp )
    {
        tmp->parent = position.node->parent;
        tmp = tmp->next_sibling;
    }

    if( position.node->next_sibling )
    {
        position.node->last_child->next_sibling = position.node->next_sibling;
        position.node->next_sibling->prev_sibling = position.node->last_child;
    }

    else
    {
        position.node->parent->last_child = position.node->last_child;
    }

    position.node->next_sibling = position.node->first_child;
    position.node->next_sibling->prev_sibling = position.node;
    position.node->first_child = 0;
    position.node->last_child = 0;

    return position;
}

template <class T, class tree_node_allocator>
template <typename iter>
iter tree<T, tree_node_allocator>
::reparent( iter position, sibling_iterator begin, sibling_iterator end )
{
    tree_node* first = begin.node;
    tree_node* last = first;

    assert( first != position.node );

    if( begin == end ) return begin;

    // determine last node
    while( ( ++begin ) != end )
    {
        last = last->next_sibling;
    }

    // move subtree
    if( first->prev_sibling == 0 )
    {
        first->parent->first_child = last->next_sibling;
    }

    else
    {
        first->prev_sibling->next_sibling = last->next_sibling;
    }

    if( last->next_sibling == 0 )
    {
        last->parent->last_child = first->prev_sibling;
    }

    else
    {
        last->next_sibling->prev_sibling = first->prev_sibling;
    }

    if( position.node->first_child == 0 )
    {
        position.node->first_child = first;
        position.node->last_child = last;
        first->prev_sibling = 0;
    }

    else
    {
        position.node->last_child->next_sibling = first;
        first->prev_sibling = position.node->last_child;
        position.node->last_child = last;
    }

    last->next_sibling = 0;

    tree_node* pos = first;

    for(;; )
    {
        pos->parent = position.node;

        if( pos == last ) break;

        pos = pos->next_sibling;
    }

    return first;
}

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>
::reparent( iter position, iter from )
{
    if( from.node->first_child == 0 ) return position;

    return reparent( position, from.node->first_child, end( from ) );
}

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>
::wrap( iter position, const T& x )
{
    assert( position.node != 0 );
    sibling_iterator fr = position, to = position;
    ++to;
    iter ret = insert( position, x );
    reparent( ret, fr, to );
    return ret;
}

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>
::move_after( iter target, iter source )
{
    tree_node* dst = target.node;
    tree_node* src = source.node;
    assert( dst );
    assert( src );

    if( dst == src ) return source;

    if( dst->next_sibling )
        if( dst->next_sibling == src ) // already in the right spot
            return source;

    // take src out of the tree
    if( src->prev_sibling != 0 ) src->prev_sibling->next_sibling = src->next_sibling;

    else src->parent->first_child = src->next_sibling;

    if( src->next_sibling != 0 ) src->next_sibling->prev_sibling = src->prev_sibling;

    else src->parent->last_child = src->prev_sibling;

    // connect it to the new point
    if( dst->next_sibling != 0 ) dst->next_sibling->prev_sibling = src;

    else dst->parent->last_child = src;

    src->next_sibling = dst->next_sibling;
    dst->next_sibling = src;
    src->prev_sibling = dst;
    src->parent = dst->parent;
    return src;
}

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>
::move_before( iter target, iter source )
{
    tree_node* dst = target.node;
    tree_node* src = source.node;
    assert( dst );
    assert( src );

    if( dst == src ) return source;

    if( dst->prev_sibling )
        if( dst->prev_sibling == src ) // already in the right spot
            return source;

    // take src out of the tree
    if( src->prev_sibling != 0 ) src->prev_sibling->next_sibling = src->next_sibling;

    else src->parent->first_child = src->next_sibling;

    if( src->next_sibling != 0 ) src->next_sibling->prev_sibling = src->prev_sibling;

    else src->parent->last_child = src->prev_sibling;

    // connect it to the new point
    if( dst->prev_sibling != 0 ) dst->prev_sibling->next_sibling = src;

    else dst->parent->first_child = src;

    src->prev_sibling = dst->prev_sibling;
    dst->prev_sibling = src;
    src->next_sibling = dst;
    src->parent = dst->parent;
    return src;
}

// specialisation for sibling_iterators

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::move_before( sibling_iterator target,
             sibling_iterator source )
{
    tree_node* dst = target.node;
    tree_node* src = source.node;
    tree_node* dst_prev_sibling;

    if( dst == 0 ) // must then be an end iterator
    {
        dst_prev_sibling = target.parent_->last_child;
        assert( dst_prev_sibling );
    }

    else dst_prev_sibling = dst->prev_sibling;

    assert( src );

    if( dst == src ) return source;

    if( dst_prev_sibling )
        if( dst_prev_sibling == src ) // already in the right spot
            return source;

    // take src out of the tree
    if( src->prev_sibling != 0 ) src->prev_sibling->next_sibling = src->next_sibling;

    else src->parent->first_child = src->next_sibling;

    if( src->next_sibling != 0 ) src->next_sibling->prev_sibling = src->prev_sibling;

    else src->parent->last_child = src->prev_sibling;

    // connect it to the new point
    if( dst_prev_sibling != 0 ) dst_prev_sibling->next_sibling = src;

    else target.parent_->first_child = src;

    src->prev_sibling = dst_prev_sibling;

    if( dst )
    {
        dst->prev_sibling = src;
        src->parent = dst->parent;
    }

    src->next_sibling = dst;
    return src;
}

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>
::move_ontop( iter target, iter source )
{
    tree_node* dst = target.node;
    tree_node* src = source.node;
    assert( dst );
    assert( src );

    if( dst == src ) return source;

    //  if(dst==src->prev_sibling) {
    //
    //      }

    // remember connection points
    tree_node* b_prev_sibling = dst->prev_sibling;
    tree_node* b_next_sibling = dst->next_sibling;
    tree_node* b_parent = dst->parent;

    // remove target
    erase( target );

    // take src out of the tree
    if( src->prev_sibling != 0 ) src->prev_sibling->next_sibling = src->next_sibling;

    else src->parent->first_child = src->next_sibling;

    if( src->next_sibling != 0 ) src->next_sibling->prev_sibling = src->prev_sibling;

    else src->parent->last_child = src->prev_sibling;

    // connect it to the new point
    if( b_prev_sibling != 0 ) b_prev_sibling->next_sibling = src;

    else b_parent->first_child = src;

    if( b_next_sibling != 0 ) b_next_sibling->prev_sibling = src;

    else b_parent->last_child = src;

    src->prev_sibling = b_prev_sibling;
    src->next_sibling = b_next_sibling;
    src->parent = b_parent;
    return src;
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::merge( sibling_iterator to1, sibling_iterator to2,
       sibling_iterator from1, sibling_iterator from2,
       bool duplicate_leaves )
{
    sibling_iterator fnd;

    while( from1 != from2 )
    {
        if( ( fnd = std::find( to1, to2, ( *from1 ) ) ) != to2 ) // element found
        {
            if( from1.begin( ) == from1.end( ) ) // full depth reached
            {
                if( duplicate_leaves )
                    append_child( parent( to1 ), ( *from1 ) );
            }

            else // descend further
            {
                merge( fnd.begin( ), fnd.end( ), from1.begin( ), from1.end( ), duplicate_leaves );
            }
        }

        else // element missing
        {
            insert_subtree( to2, from1 );
        }

        ++from1;
    }
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::sort( sibling_iterator from, sibling_iterator to, bool deep )
{
    std::less<T> comp;
    sort( from, to, comp, deep );
}

template <class T, class tree_node_allocator>
template <class StrictWeakOrdering>
void tree<T, tree_node_allocator>
::sort( sibling_iterator from, sibling_iterator to,
      StrictWeakOrdering comp, bool deep )
{
    if( from == to ) return;

    // make list of sorted nodes
    // CHECK: if multiset stores equivalent nodes in the order in which they
    // are inserted, then this routine should be called 'stable_sort'.
    std::multiset<tree_node*, compare_nodes<StrictWeakOrdering> > nodes( comp );
    sibling_iterator it = from, it2 = to;

    while( it != to )
    {
        nodes.insert( it.node );
        ++it;
    }

    // reassemble
    --it2;

    // prev and next are the nodes before and after the sorted range
    tree_node* prev = from.node->prev_sibling;
    tree_node* next = it2.node->next_sibling;
    typename std::multiset<tree_node*, compare_nodes<StrictWeakOrdering> >::iterator nit = nodes.begin( ), eit = nodes.end( );

    if( prev == 0 )
    {
        if( ( *nit )->parent != 0 ) // to catch "sorting the head" situations, when there is no parent
            ( *nit )->parent->first_child = ( *nit );
    }

    else prev->next_sibling = ( *nit );

    --eit;

    while( nit != eit )
    {
        ( *nit )->prev_sibling = prev;

        if( prev )
            prev->next_sibling = ( *nit );

        prev = ( *nit );
        ++nit;
    }

    // prev now points to the last-but-one node in the sorted range
    if( prev )
        prev->next_sibling = ( *eit );

    // eit points to the last node in the sorted range.
    ( *eit )->next_sibling = next;
    ( *eit )->prev_sibling = prev; // missed in the loop above

    if( next == 0 )
    {
        if( ( *eit )->parent != 0 ) // to catch "sorting the head" situations, when there is no parent
            ( *eit )->parent->last_child = ( *eit );
    }

    else next->prev_sibling = ( *eit );

    if( deep ) // sort the children of each node too
    {
        sibling_iterator bcs( *nodes.begin( ) );
        sibling_iterator ecs( *eit );
        ++ecs;

        while( bcs != ecs )
        {
            sort( begin( bcs ), end( bcs ), comp, deep );
            ++bcs;
        }
    }
}

template <class T, class tree_node_allocator>
template <typename iter>
bool tree<T, tree_node_allocator>
::equal( const iter& one_, const iter& two, const iter& three_ ) const
{
    std::equal_to<T> comp;
    return equal( one_, two, three_, comp );
}

template <class T, class tree_node_allocator>
template <typename iter>
bool tree<T, tree_node_allocator>
::equal_subtree( const iter& one_, const iter& two_ ) const
{
    std::equal_to<T> comp;
    return equal_subtree( one_, two_, comp );
}

template <class T, class tree_node_allocator>
template <typename iter, class BinaryPredicate>
bool tree<T, tree_node_allocator>
::equal( const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun ) const
{
    pre_order_iterator one( one_ ), three( three_ );

    //  if(one==two && is_valid(three) && three.number_of_children()!=0)
    //      return false;
    while( one != two && is_valid( three ) )
    {
        if( !fun( *one, *three ) )
            return false;

        if( one.number_of_children( ) != three.number_of_children( ) )
            return false;

        ++one;
        ++three;
    }

    return true;
}

template <class T, class tree_node_allocator>
template <typename iter, class BinaryPredicate>
bool tree<T, tree_node_allocator>
::equal_subtree( const iter& one_, const iter& two_, BinaryPredicate fun ) const
{
    pre_order_iterator one( one_ ), two( two_ );

    if( !fun( *one, *two ) ) return false;

    if( number_of_children( one ) != number_of_children( two ) ) return false;

    return equal( begin( one ), end( one ), begin( two ), fun );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator> tree<T, tree_node_allocator>
::subtree( sibling_iterator from, sibling_iterator to ) const
{
    tree tmp;
    tmp.set_head( value_type( ) );
    tmp.replace( tmp.begin( ), tmp.end( ), from, to );
    return tmp;
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::subtree( tree& tmp, sibling_iterator from, sibling_iterator to ) const
{
    tmp.set_head( value_type( ) );
    tmp.replace( tmp.begin( ), tmp.end( ), from, to );
}

template <class T, class tree_node_allocator>
size_t tree<T, tree_node_allocator>
::size( ) const
{
    size_t i = 0;
    pre_order_iterator it = begin( ), eit = end( );

    while( it != eit )
    {
        ++i;
        ++it;
    }

    return i;
}

template <class T, class tree_node_allocator>
size_t tree<T, tree_node_allocator>
::size( const iterator_base& top ) const
{
    size_t i = 0;
    pre_order_iterator it = top, eit = top;
    eit.skip_children( );
    ++eit;

    while( it != eit )
    {
        ++i;
        ++it;
    }

    return i;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>
::empty( ) const
{
    pre_order_iterator it = begin( ), eit = end( );
    return (it == eit );
}

template <class T, class tree_node_allocator>
int tree<T, tree_node_allocator>
::depth( const iterator_base& it )
{
    tree_node* pos = it.node;
    assert( pos != 0 );
    int ret = 0;

    while( pos->parent != 0 )
    {
        pos = pos->parent;
        ++ret;
    }

    return ret;
}

template <class T, class tree_node_allocator>
int tree<T, tree_node_allocator>
::depth( const iterator_base& it, const iterator_base& root )
{
    tree_node* pos = it.node;
    assert( pos != 0 );
    int ret = 0;

    while( pos->parent != 0 && pos != root.node )
    {
        pos = pos->parent;
        ++ret;
    }

    return ret;
}

template <class T, class tree_node_allocator>
int tree<T, tree_node_allocator>
::max_depth( ) const
{
    int maxd = -1;

    for( tree_node* it = head->next_sibling; it != feet; it = it->next_sibling )
        maxd = std::max( maxd, max_depth( it ) );

    return maxd;
}

template <class T, class tree_node_allocator>
int tree<T, tree_node_allocator>
::max_depth( const iterator_base& pos ) const
{
    tree_node* tmp = pos.node;

    if( tmp == 0 || tmp == head || tmp == feet ) return -1;

    int curdepth = 0, maxdepth = 0;

    while( true ) // try to walk the bottom of the tree
    {
        while( tmp->first_child == 0 )
        {
            if( tmp == pos.node ) return maxdepth;

            if( tmp->next_sibling == 0 )
            {
                // try to walk up and then right again
                do
                {
                    tmp = tmp->parent;

                    if( tmp == 0 ) return maxdepth;

                    --curdepth;
                }
                while( tmp->next_sibling == 0 );
            }

            if( tmp == pos.node ) return maxdepth;

            tmp = tmp->next_sibling;
        }

        tmp = tmp->first_child;
        ++curdepth;
        maxdepth = std::max( curdepth, maxdepth );
    }
}

template <class T, class tree_node_allocator>
unsigned int tree<T, tree_node_allocator>
::number_of_children( const iterator_base& it )
{
    tree_node* pos = it.node->first_child;

    if( pos == 0 ) return 0;

    unsigned int ret = 1;

    //    while(pos!=it.node->last_child) {
    //        ++ret;
    //        pos=pos->next_sibling;
    //        }
    while( ( pos = pos->next_sibling ) )
        ++ret;

    return ret;
}

template <class T, class tree_node_allocator>
unsigned int tree<T, tree_node_allocator>
::number_of_siblings( const iterator_base& it ) const
{
    tree_node* pos = it.node;
    unsigned int ret = 0;

    // count forward
    while( pos->next_sibling &&
           pos->next_sibling != head &&
           pos->next_sibling != feet )
    {
        ++ret;
        pos = pos->next_sibling;
    }

    // count backward
    pos = it.node;

    while( pos->prev_sibling &&
           pos->prev_sibling != head &&
           pos->prev_sibling != feet )
    {
        ++ret;
        pos = pos->prev_sibling;
    }

    return ret;
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::swap( sibling_iterator it )
{
    tree_node* nxt = it.node->next_sibling;

    if( nxt )
    {
        if( it.node->prev_sibling )
            it.node->prev_sibling->next_sibling = nxt;

        else
            it.node->parent->first_child = nxt;

        nxt->prev_sibling = it.node->prev_sibling;
        tree_node* nxtnxt = nxt->next_sibling;

        if( nxtnxt )
            nxtnxt->prev_sibling = it.node;

        else
            it.node->parent->last_child = it.node;

        nxt->next_sibling = it.node;
        it.node->prev_sibling = nxt;
        it.node->next_sibling = nxtnxt;
    }
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::swap( iterator one, iterator two )
{
    // if one and two are adjacent siblings, use the sibling swap
    if( one.node->next_sibling == two.node ) swap( one );

    else if( two.node->next_sibling == one.node ) swap( two );

    else
    {
        tree_node* nxt1 = one.node->next_sibling;
        tree_node* nxt2 = two.node->next_sibling;
        tree_node* pre1 = one.node->prev_sibling;
        tree_node* pre2 = two.node->prev_sibling;
        tree_node* par1 = one.node->parent;
        tree_node* par2 = two.node->parent;

        // reconnect
        one.node->parent = par2;
        one.node->next_sibling = nxt2;

        if( nxt2 ) nxt2->prev_sibling = one.node;

        else par2->last_child = one.node;

        one.node->prev_sibling = pre2;

        if( pre2 ) pre2->next_sibling = one.node;

        else par2->first_child = one.node;

        two.node->parent = par1;
        two.node->next_sibling = nxt1;

        if( nxt1 ) nxt1->prev_sibling = two.node;

        else par1->last_child = two.node;

        two.node->prev_sibling = pre1;

        if( pre1 ) pre1->next_sibling = two.node;

        else par1->first_child = two.node;
    }
}

// template <class BinaryPredicate>
// tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::find_subtree(
//  sibling_iterator subfrom, sibling_iterator subto, iterator from, iterator to,
//  BinaryPredicate fun) const
//  {
//  assert(1==0); // this routine is not finished yet.
//  while(from!=to) {
//      if(fun(*subfrom, *from)) {
//
//          }
//      }
//  return to;
//  }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>
::is_in_subtree( const iterator_base& it, const iterator_base& begin,
               const iterator_base& end ) const
{
    // FIXME: this should be optimised.
    pre_order_iterator tmp = begin;

    while( tmp != end )
    {
        if( tmp == it ) return true;

        ++tmp;
    }

    return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>
::is_valid( const iterator_base& it ) const
{
    if( it.node == 0 || it.node == feet || it.node == head ) return false;

    else return true;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>
::lowest_common_ancestor(
                        const iterator_base& one, const iterator_base& two ) const
{
    std::set<iterator, iterator_base_less> parents;

    // Walk up from 'one' storing all parents.
    iterator walk = one;

    do
    {
        walk = parent( walk );
        parents.insert( walk );
    }
    while( is_valid( parent( walk ) ) );

    // Walk up from 'two' until we encounter a node in parents.
    walk = two;

    do
    {
        walk = parent( walk );

        if( parents.find( walk ) != parents.end( ) ) break;
    }
    while( is_valid( parent( walk ) ) );

    return walk;
}

template <class T, class tree_node_allocator>
unsigned int tree<T, tree_node_allocator>
::index( sibling_iterator it ) const
{
    unsigned int ind = 0;

    if( it.node->parent == 0 )
    {
        while( it.node->prev_sibling != head )
        {
            it.node = it.node->prev_sibling;
            ++ind;
        }
    }

    else
    {
        while( it.node->prev_sibling != 0 )
        {
            it.node = it.node->prev_sibling;
            ++ind;
        }
    }

    return ind;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::sibling( const iterator_base& it, unsigned int num )
{
    tree_node* tmp;

    if( it.node->parent == 0 )
    {
        tmp = head->next_sibling;

        while( num )
        {
            tmp = tmp->next_sibling;
            --num;
        }
    }

    else
    {
        tmp = it.node->parent->first_child;

        while( num )
        {
            assert( tmp != 0 );
            tmp = tmp->next_sibling;
            --num;
        }
    }

    return tmp;
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::debug_verify_consistency( ) const
{
    iterator it = begin( );

    while( it != end( ) )
    {
        if( it.node->parent != 0 )
        {
            if( it.node->prev_sibling == 0 )
                assert( it.node->parent->first_child == it.node );

            else
                assert( it.node->prev_sibling->next_sibling == it.node );

            if( it.node->next_sibling == 0 )
                assert( it.node->parent->last_child == it.node );

            else
                assert( it.node->next_sibling->prev_sibling == it.node );
        }

        ++it;
    }
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::child( const iterator_base& it, unsigned int num )
{
    tree_node* tmp = it.node->first_child;

    while( num-- )
    {
        assert( tmp != 0 );
        tmp = tmp->next_sibling;
    }

    return tmp;
}




// Iterator base

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::iterator_base::iterator_base( )
: node( 0 ), skip_current_children_( false ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::iterator_base::iterator_base( tree_node* tn )
: node( tn ), skip_current_children_( false ){ }

template <class T, class tree_node_allocator>
T& tree<T, tree_node_allocator>::iterator_base::operator*( ) const
{
    return node->data;
}

template <class T, class tree_node_allocator>
T* tree<T, tree_node_allocator>::iterator_base::operator->( ) const
{
    return &( node->data );
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::post_order_iterator::operator!=( const post_order_iterator& other ) const
{
    if( other.node != this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::post_order_iterator::operator==( const post_order_iterator& other ) const
{
    if( other.node == this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::pre_order_iterator::operator!=( const pre_order_iterator& other ) const
{
    if( other.node != this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::pre_order_iterator::operator==( const pre_order_iterator& other ) const
{
    if( other.node == this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::sibling_iterator::operator!=( const sibling_iterator& other ) const
{
    if( other.node != this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::sibling_iterator::operator==( const sibling_iterator& other ) const
{
    if( other.node == this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::leaf_iterator::operator!=( const leaf_iterator& other ) const
{
    if( other.node != this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::leaf_iterator::operator==( const leaf_iterator& other ) const
{
    if( other.node == this->node && other.top_node == this->top_node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::iterator_base::begin( ) const
{
    if( node->first_child == 0 )
        return end( );

    sibling_iterator ret( node->first_child );
    ret.parent_ = this->node;
    return ret;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>
::iterator_base::end( ) const
{
    sibling_iterator ret( 0 );
    ret.parent_ = node;
    return ret;
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::iterator_base::skip_children( )
{
    skip_current_children_ = true;
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::iterator_base::skip_children( bool skip )
{
    skip_current_children_ = skip;
}

template <class T, class tree_node_allocator>
unsigned int tree<T, tree_node_allocator>
::iterator_base::number_of_children( ) const
{
    tree_node* pos = node->first_child;

    if( pos == 0 ) return 0;

    unsigned int ret = 1;

    while( pos != node->last_child )
    {
        ++ret;
        pos = pos->next_sibling;
    }

    return ret;
}



// Pre-order iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::pre_order_iterator::pre_order_iterator( )
: iterator_base( 0 ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::pre_order_iterator::pre_order_iterator( tree_node* tn )
: iterator_base( tn ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::pre_order_iterator::pre_order_iterator( const iterator_base& other )
: iterator_base( other.node ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::pre_order_iterator::pre_order_iterator( const sibling_iterator& other )
: iterator_base( other.node )
{
    if( this->node == 0 )
    {
        if( other.range_last( ) != 0 )
            this->node = other.range_last( );

        else
            this->node = other.parent_;

        this->skip_children( );
        ++( *this );
    }
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++( )
{
    assert( this->node != 0 );

    if( !this->skip_current_children_ && this->node->first_child != 0 )
    {
        this->node = this->node->first_child;
    }

    else
    {
        this->skip_current_children_ = false;

        while( this->node->next_sibling == 0 )
        {
            this->node = this->node->parent;

            if( this->node == 0 )
                return *this;
        }

        this->node = this->node->next_sibling;
    }

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--( )
{
    assert( this->node != 0 );

    if( this->node->prev_sibling )
    {
        this->node = this->node->prev_sibling;

        while( this->node->last_child )
            this->node = this->node->last_child;
    }

    else
    {
        this->node = this->node->parent;

        if( this->node == 0 )
            return *this;
    }

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++( int )
{
    pre_order_iterator copy = *this;
    ++( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--( int )
{
    pre_order_iterator copy = *this;
    --( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator+=( unsigned int num )
{
    while( num > 0 )
    {
        ++( *this );
        --num;
    }

    return (*this );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator-=( unsigned int num )
{
    while( num > 0 )
    {
        --( *this );
        --num;
    }

    return (*this );
}



// Post-order iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::post_order_iterator::post_order_iterator( )
: iterator_base( 0 ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::post_order_iterator::post_order_iterator( tree_node* tn )
: iterator_base( tn ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::post_order_iterator::post_order_iterator( const iterator_base& other )
: iterator_base( other.node ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::post_order_iterator::post_order_iterator( const sibling_iterator& other )
: iterator_base( other.node )
{
    if( this->node == 0 )
    {
        if( other.range_last( ) != 0 )
            this->node = other.range_last( );

        else
            this->node = other.parent_;

        this->skip_children( );
        ++( *this );
    }
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++( )
{
    assert( this->node != 0 );

    if( this->node->next_sibling == 0 )
    {
        this->node = this->node->parent;
        this->skip_current_children_ = false;
    }

    else
    {
        this->node = this->node->next_sibling;

        if( this->skip_current_children_ )
        {
            this->skip_current_children_ = false;
        }

        else
        {
            while( this->node->first_child )
                this->node = this->node->first_child;
        }
    }

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator--( )
{
    assert( this->node != 0 );

    if( this->skip_current_children_ || this->node->last_child == 0 )
    {
        this->skip_current_children_ = false;

        while( this->node->prev_sibling == 0 )
            this->node = this->node->parent;

        this->node = this->node->prev_sibling;
    }

    else
    {
        this->node = this->node->last_child;
    }

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator++( int )
{
    post_order_iterator copy = *this;
    ++( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator tree<T, tree_node_allocator>::post_order_iterator::operator--( int )
{
    post_order_iterator copy = *this;
    --( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator+=( unsigned int num )
{
    while( num > 0 )
    {
        ++( *this );
        --num;
    }

    return (*this );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator-=( unsigned int num )
{
    while( num > 0 )
    {
        --( *this );
        --num;
    }

    return (*this );
}

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::post_order_iterator::descend_all( )
{
    assert( this->node != 0 );

    while( this->node->first_child )
        this->node = this->node->first_child;
}


// Breadth-first iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::breadth_first_queued_iterator::breadth_first_queued_iterator( )
: iterator_base( ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::breadth_first_queued_iterator::breadth_first_queued_iterator( tree_node* tn )
: iterator_base( tn )
{
    traversal_queue.push( tn );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::breadth_first_queued_iterator::breadth_first_queued_iterator( const iterator_base& other )
: iterator_base( other.node )
{
    traversal_queue.push( other.node );
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=( const breadth_first_queued_iterator& other ) const
{
    if( other.node != this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator==( const breadth_first_queued_iterator& other ) const
{
    if( other.node == this->node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++( )
{
    assert( this->node != 0 );

    // Add child nodes and pop current node
    sibling_iterator sib = this->begin( );

    while( sib != this->end( ) )
    {
        traversal_queue.push( sib.node );
        ++sib;
    }

    traversal_queue.pop( );

    if( traversal_queue.size( ) > 0 )
        this->node = traversal_queue.front( );

    else
        this->node = 0;

    return (*this );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++( int )
{
    breadth_first_queued_iterator copy = *this;
    ++( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=( unsigned int num )
{
    while( num > 0 )
    {
        ++( *this );
        --num;
    }

    return (*this );
}



// Fixed depth iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::fixed_depth_iterator::fixed_depth_iterator( )
: iterator_base( ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::fixed_depth_iterator::fixed_depth_iterator( tree_node* tn )
: iterator_base( tn ), top_node( 0 ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::fixed_depth_iterator::fixed_depth_iterator( const iterator_base& other )
: iterator_base( other.node ), top_node( 0 ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::fixed_depth_iterator::fixed_depth_iterator( const sibling_iterator& other )
: iterator_base( other.node ), top_node( 0 ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::fixed_depth_iterator::fixed_depth_iterator( const fixed_depth_iterator& other )
: iterator_base( other.node ), top_node( other.top_node ){ }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator==( const fixed_depth_iterator& other ) const
{
    if( other.node == this->node && other.top_node == top_node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::fixed_depth_iterator::operator!=( const fixed_depth_iterator& other ) const
{
    if( other.node != this->node || other.top_node != top_node ) return true;

    else return false;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator++( )
{
    assert( this->node != 0 );

    if( this->node->next_sibling )
    {
        this->node = this->node->next_sibling;
    }

    else
    {
        int relative_depth = 0;
upper:

        do
        {
            if( this->node == this->top_node )
            {
                this->node = 0; // FIXME: return a proper fixed_depth end iterator once implemented
                return *this;
            }

            this->node = this->node->parent;

            if( this->node == 0 ) return *this;

            --relative_depth;
        }
        while( this->node->next_sibling == 0 );

lower:
        this->node = this->node->next_sibling;

        while( this->node->first_child == 0 )
        {
            if( this->node->next_sibling == 0 )
                goto upper;

            this->node = this->node->next_sibling;

            if( this->node == 0 ) return *this;
        }

        while( relative_depth < 0 && this->node->first_child != 0 )
        {
            this->node = this->node->first_child;
            ++relative_depth;
        }

        if( relative_depth < 0 )
        {
            if( this->node->next_sibling == 0 ) goto upper;

            else goto lower;
        }
    }

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator--( )
{
    assert( this->node != 0 );

    if( this->node->prev_sibling )
    {
        this->node = this->node->prev_sibling;
    }

    else
    {
        int relative_depth = 0;
upper:

        do
        {
            if( this->node == this->top_node )
            {
                this->node = 0;
                return *this;
            }

            this->node = this->node->parent;

            if( this->node == 0 ) return *this;

            --relative_depth;
        }
        while( this->node->prev_sibling == 0 );

lower:
        this->node = this->node->prev_sibling;

        while( this->node->last_child == 0 )
        {
            if( this->node->prev_sibling == 0 )
                goto upper;

            this->node = this->node->prev_sibling;

            if( this->node == 0 ) return *this;
        }

        while( relative_depth < 0 && this->node->last_child != 0 )
        {
            this->node = this->node->last_child;
            ++relative_depth;
        }

        if( relative_depth < 0 )
        {
            if( this->node->prev_sibling == 0 ) goto upper;

            else goto lower;
        }
    }

    return *this;

    //
    //
    //  assert(this->node!=0);
    //  if(this->node->prev_sibling!=0) {
    //      this->node=this->node->prev_sibling;
    //      assert(this->node!=0);
    //      if(this->node->parent==0 && this->node->prev_sibling==0) // head element
    //          this->node=0;
    //      }
    //  else {
    //      tree_node *par=this->node->parent;
    //      do {
    //          par=par->prev_sibling;
    //          if(par==0) { // FIXME: need to keep track of this!
    //              this->node=0;
    //              return *this;
    //              }
    //          } while(par->last_child==0);
    //      this->node=par->last_child;
    //      }
    //  return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator++( int )
{
    fixed_depth_iterator copy = *this;
    ++( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator tree<T, tree_node_allocator>::fixed_depth_iterator::operator--( int )
{
    fixed_depth_iterator copy = *this;
    --( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator-=( unsigned int num )
{
    while( num > 0 )
    {
        --( *this );
        --( num );
    }

    return (*this );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::fixed_depth_iterator& tree<T, tree_node_allocator>::fixed_depth_iterator::operator+=( unsigned int num )
{
    while( num > 0 )
    {
        ++( *this );
        --( num );
    }

    return *this;
}


// Sibling iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::sibling_iterator::sibling_iterator( )
: iterator_base( )
{
    set_parent_( );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::sibling_iterator::sibling_iterator( tree_node* tn )
: iterator_base( tn )
{
    set_parent_( );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::sibling_iterator::sibling_iterator( const iterator_base& other )
: iterator_base( other.node )
{
    set_parent_( );
}

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::sibling_iterator::sibling_iterator( const sibling_iterator& other )
: iterator_base( other ), parent_( other.parent_ ){ }

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>
::sibling_iterator::set_parent_( )
{
    parent_ = 0;

    if( this->node == 0 ) return;

    if( this->node->parent != 0 )
        parent_ = this->node->parent;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++( )
{
    if( this->node )
        this->node = this->node->next_sibling;

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator--( )
{
    if( this->node ) this->node = this->node->prev_sibling;

    else
    {
        assert( parent_ );
        this->node = parent_->last_child;
    }

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator++( int )
{
    sibling_iterator copy = *this;
    ++( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::sibling_iterator::operator--( int )
{
    sibling_iterator copy = *this;
    --( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator+=( unsigned int num )
{
    while( num > 0 )
    {
        ++( *this );
        --num;
    }

    return (*this );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator-=( unsigned int num )
{
    while( num > 0 )
    {
        --( *this );
        --num;
    }

    return (*this );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::tree_node* tree<T, tree_node_allocator>
::sibling_iterator::range_first( ) const
{
    tree_node* tmp = parent_->first_child;
    return tmp;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::tree_node* tree<T, tree_node_allocator>
::sibling_iterator::range_last( ) const
{
    return parent_->last_child;
}

// Leaf iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::leaf_iterator::leaf_iterator( )
: iterator_base( 0 ), top_node( 0 ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::leaf_iterator::leaf_iterator( tree_node* tn, tree_node* top )
: iterator_base( tn ), top_node( top ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::leaf_iterator::leaf_iterator( const iterator_base& other )
: iterator_base( other.node ), top_node( 0 ){ }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>
::leaf_iterator::leaf_iterator( const sibling_iterator& other )
: iterator_base( other.node ), top_node( 0 )
{
    if( this->node == 0 )
    {
        if( other.range_last( ) != 0 )
            this->node = other.range_last( );

        else
            this->node = other.parent_;

        ++( *this );
    }
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator++( )
{
    assert( this->node != 0 );

    if( this->node->first_child != 0 ) // current node is no longer leaf (children got added)
    {
        while( this->node->first_child )
            this->node = this->node->first_child;
    }

    else
    {
        while( this->node->next_sibling == 0 )
        {
            if( this->node->parent == 0 ) return *this;

            this->node = this->node->parent;

            if( top_node != 0 && this->node == top_node ) return *this;
        }

        this->node = this->node->next_sibling;

        while( this->node->first_child )
            this->node = this->node->first_child;
    }

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator--( )
{
    assert( this->node != 0 );

    while( this->node->prev_sibling == 0 )
    {
        if( this->node->parent == 0 ) return *this;

        this->node = this->node->parent;

        if( top_node != 0 && this->node == top_node ) return *this;
    }

    this->node = this->node->prev_sibling;

    while( this->node->last_child )
        this->node = this->node->last_child;

    return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator++( int )
{
    leaf_iterator copy = *this;
    ++( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator tree<T, tree_node_allocator>::leaf_iterator::operator--( int )
{
    leaf_iterator copy = *this;
    --( *this );
    return copy;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator+=( unsigned int num )
{
    while( num > 0 )
    {
        ++( *this );
        --num;
    }

    return (*this );
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::leaf_iterator& tree<T, tree_node_allocator>::leaf_iterator::operator-=( unsigned int num )
{
    while( num > 0 )
    {
        --( *this );
        --num;
    }

    return (*this );
}

}

#endif

// Local variables:
// default-tab-width: 3
// End: