tree.hh

/* 

   $Id: tree.hh,v 1.1 2002/10/17 20:04:35 benoitg Exp $

        STL-like templated tree class.
        Copyright (C) 2001  Kasper Peeters <k.peeters@damtp.cam.ac.uk>

   See 
  
      http://www.damtp.cam.ac.uk/user/kp229/tree/

   for more information and documentation. See the Changelog file for
        other credits.

        This program is free software; you can redistribute it and/or modify
        it under the terms of the GNU General Public License as published by
        the Free Software Foundation; version 2.
        
        This program is distributed in the hope that it will be useful,
        but WITHOUT ANY WARRANTY; without even the implied warranty of
        MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        GNU General Public License for more details.
        
        You should have received a copy of the GNU General Public License
        along with this program; if not, write to the Free Software
        Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
        
*/

#ifndef tree_hh_
#define tree_hh_

#include <cassert>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <set>

// HP-style construct/destroy have gone from the standard,
// so here is a copy.

template <class T1, class T2>
inline void constructor(T1* p, T2& val) 
        {
        new ((void *) p) T1(val);
        }

template <class T1>
inline void constructor(T1* p) 
        {
        new ((void *) p) T1;
        }

template <class T1>
inline void destructor(T1* p)
        {
        p->~T1();
        }


template<class T>
struct tree_node_ {
                tree_node_<T> *parent;
           tree_node_<T> *first_child, *last_child;
                tree_node_<T> *prev_sibling, *next_sibling;
                T data;
};

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;
                class sibling_iterator;

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

                class iterator { 
                        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();
                                iterator(tree_node *);
                                iterator(const sibling_iterator&);

                                iterator&  operator++(void);
                           iterator&  operator--(void);
                                iterator&  operator+=(unsigned int);
                                iterator&  operator-=(unsigned int);
                                T&         operator*(void) const;
                                T*         operator->(void) const;
                                bool       operator==(const iterator&) const;
                                bool       operator!=(const iterator&) const;
                                iterator   operator+(int) const;

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

                                void skip_children(); // do not iterate over children of this node
                                bool is_valid() const;
                                unsigned int number_of_children() const;

                                tree_node *node;
                        private:
                                bool increment_();
                                bool decrement_();
                                bool skip_current_children_;
                };

                class sibling_iterator {
                        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;

                                sibling_iterator();
                                sibling_iterator(tree_node *);
                                sibling_iterator(const sibling_iterator&);
                                sibling_iterator(const iterator&);

                                sibling_iterator&  operator++(void);
                                sibling_iterator&  operator--(void);
                                sibling_iterator&  operator+=(unsigned int);
                                sibling_iterator&  operator-=(unsigned int);
                                T&                 operator*(void) const;
                                T*                 operator->(void) const;
                                bool               operator==(const sibling_iterator&) const;
                                bool               operator!=(const sibling_iterator&) const;
                                sibling_iterator   operator+(int) const;

                                bool       is_valid() const;
                                tree_node *range_first() const;
                                tree_node *range_last() const;

                                tree_node *node;

                                friend class tree<T, tree_node_allocator>;
                                friend class tree<T, tree_node_allocator>::iterator;
                        private:
                                void set_parent_();
                                tree_node *parent_;
                };

                // begin/end of tree
                iterator begin() const;
                iterator end() const;
                // begin/end of children of node
                sibling_iterator begin(iterator) const;
                sibling_iterator end(iterator) const;
                iterator parent(iterator) const;
                iterator previous_sibling(iterator) const;
                iterator next_sibling(iterator) const;
                void     clear();
                // erase element at position pointed to by iterator, increment iterator
                iterator erase(iterator);
                // erase all children of the node pointed to by iterator
                void     erase_children(iterator);

                // insert node as last child of node pointed to by position
                iterator append_child(iterator position); 
                iterator append_child(iterator position, const T& x);
                iterator append_child(iterator position, iterator other_position);

                // short-hand to insert topmost node in otherwise empty tree
                iterator set_head(const T& x);
                // insert node as previous sibling of node pointed to by position
                iterator insert(iterator position, const T& x);
                // insert node as previous sibling of node pointed to by position
                iterator insert(sibling_iterator position, const T& x);
                // insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
                iterator insert(iterator position, iterator subtree);
                // insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
                iterator insert(sibling_iterator position, iterator subtree);
                // insert node as next sibling of node pointed to by position
                iterator insert_after(iterator position, const T& x);

                // replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
                iterator replace(iterator position, const T& x);
                // replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
                iterator replace(iterator position, iterator from);
                // replace string of siblings (plus their children) with copy of a new string (with children); see above
                iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, 
                                                          sibling_iterator new_begin,  sibling_iterator new_end); 

                // move all children of node at 'position' to be siblings, returns position
                iterator flatten(iterator position);
                // move nodes in range to be children of 'position'
                iterator reparent(iterator position, sibling_iterator begin, sibling_iterator end);
                // ditto, the range being all children of the 'from' node
                iterator reparent(iterator position, iterator from);
                // merge with other tree, creating new branches and leaves only if they are not already present
                void     merge(iterator position, iterator other, bool duplicate_leaves=false);
                // sort (std::sort only moves values of nodes, this one moves children as well)
                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);
                // compare two ranges of nodes (compares nodes as well as tree structure)
                template<class BinaryPredicate>
                bool     equal(iterator one, iterator two, iterator three, BinaryPredicate) const;
                // extract a new tree formed by the range of siblings plus all their children
                tree     subtree(sibling_iterator from, sibling_iterator to) const;
                void     subtree(tree&, sibling_iterator from, sibling_iterator to) const;
                // exchange the node (plus subtree) with its sibling node (do nothing if no sibling present)
                void     swap(sibling_iterator it);
                
                // count the total number of nodes
                int      size() const;
                // compute the depth to the root
                int      depth(iterator) const;
                // count the number of children of node at position
                unsigned int number_of_children(iterator) const;
                // count the number of 'next' siblings of node at iterator
                unsigned int number_of_siblings(iterator) const;
                // determine whether node at position is in the subtrees with root in the range
                bool     is_in_subtree(iterator position, iterator begin, iterator end) const;

                // return the n-th child of the node at position
                T&       child(iterator position, unsigned int) const;
        private:
                tree_node_allocator alloc_;
                tree_node *head;    // head is always a dummy; if an iterator points to head it is invalid
                void head_initialise_();
                void copy_(const tree<T, tree_node_allocator>& other);
                template<class StrictWeakOrdering>
                class compare_nodes {
                        public:
                                bool operator()(const tree_node*, const tree_node *);
                };
};



// 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(iterator other)
        {
        head_initialise_();
        set_head((*other));
        replace(begin(), other);
        }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::~tree()
        {
        clear();
        alloc_.deallocate(head,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 

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

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

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();
        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!=head)
                        erase(head->next_sibling);
        }

template<class T, class tree_node_allocator> 
void tree<T, tree_node_allocator>::erase_children(iterator it)
        {
        tree_node *cur=it.node->first_child;
        tree_node *prev=0;

        while(cur!=0) {
                prev=cur;
                cur=cur->next_sibling;
                erase_children(prev);
                destructor(&prev->data);
                alloc_.deallocate(prev,1);
                }
        it.node->first_child=0;
        it.node->last_child=0;
        }

template<class T, class tree_node_allocator> 
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::erase(iterator it)
        {
        tree_node *cur=it.node;
        assert(cur!=head);
        iterator 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;
                }

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

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

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::begin(iterator pos) const
        {
        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(iterator 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>::iterator tree<T, tree_node_allocator>::parent(iterator position) const
        {
        assert(position.node!=0);
        return iterator(position.node->parent);
        }

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::next_sibling(iterator position) const
        {
        assert(position.node!=0);
        if(position.node->next_sibling==0)
                return end(position.node->parent);
        else
                return iterator(position.node->next_sibling);
        }

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

        tree_node* tmp = alloc_.allocate(1,0);
        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>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::append_child(iterator 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);

        tree_node* tmp = alloc_.allocate(1,0);
        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>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::append_child(iterator position, iterator other)
        {
        assert(position.node!=head);

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::set_head(const T& x)
        {
        assert(begin()==end());
        return insert(begin(), x);
        }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::insert(iterator position, const T& x)
        {
        tree_node* tmp = alloc_.allocate(1,0);
        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)
                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>::iterator tree<T, tree_node_allocator>::insert(sibling_iterator position, const T& x)
        {
        tree_node* tmp = alloc_.allocate(1,0);
        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();
                }
        else {
                tmp->parent=position.node->parent;
                tmp->prev_sibling=position.node->prev_sibling;
                position.node->prev_sibling=tmp;
                }

        if(tmp->prev_sibling==0)
                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>::iterator tree<T, tree_node_allocator>::insert_after(iterator position, const T& x)
        {
        tree_node* tmp = alloc_.allocate(1,0);
        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) {
                tmp->parent->last_child=tmp;
                }
        else {
                tmp->next_sibling->prev_sibling=tmp;
                }
        return tmp;
        }

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

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::replace(iterator position, const T& x)
        {
        destructor(&position.node->data);
        constructor(&position.node->data, x);
        return position;
        }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::replace(iterator position, iterator from)
        {
        assert(position.node!=head);

        tree_node *current_from=from.node;
        tree_node *start_from=from.node;
        tree_node *last=from.node->next_sibling;
        tree_node *current_to  =position.node;

        // replace the node at position with head of the replacement tree at from
        erase_children(position);       
        tree_node* tmp = alloc_.allocate(1,0);
        constructor(&tmp->data, (*from));
        tmp->first_child=0;
        tmp->last_child=0;
        if(current_to->prev_sibling==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) {
                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;
        destructor(&current_to->data);
        alloc_.deallocate(current_to,1);
        current_to=tmp;

        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>::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;
        iterator ret;
        while(1==1) {
                iterator tt=insert(iterator(orig_first), 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(orig_first);
                if(last) 
                        break;
                orig_first=next;
                }
        return ret;
        }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::flatten(iterator 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>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::reparent(iterator position, sibling_iterator begin, 
                                                                                                                                  sibling_iterator end)
        {
        tree_node *first=begin.node;
        tree_node *last=first;
        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;
        while(1==1) {
                pos->parent=position.node;
                if(pos==last) break;
                pos=pos->next_sibling;
                }

        return first;
        }

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

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::merge(iterator position, iterator other, bool duplicate_leaves)
        {
        sibling_iterator fnd;
        sibling_iterator oit=other;
        while(oit.is_valid()) {
                if((fnd=find(position.begin(), position.end(), (*other)))!=position.end()) {
                        if(duplicate_leaves && other.begin()==other.end()) { // it's a leave
                                append_child(position, (*other));
                                }
                        else {
                                if(other.begin()!=other.end())
                                        merge(fnd, other.begin(), duplicate_leaves);
                                }
                        }
                else {
                        insert(position.end(), oit);
                        }
                ++oit;
                }
        }

template <class T, class tree_node_allocator>
template <class StrictWeakOrdering> 
bool tree<T, tree_node_allocator>::compare_nodes<StrictWeakOrdering>::operator()(const tree_node *a, 
                                                                                                                                                                                                                        const tree_node *b)
        {
        static StrictWeakOrdering comp;

        return comp(a->data, b->data);
        }

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;
        sibling_iterator it=from, it2=to;
        while(it != to) {
                nodes.insert(it.node);
                ++it;
                }
        // reassemble
        --it2;
        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) {
                (*nit)->parent->first_child=(*nit);
                }
        --eit;
        while(nit!=eit) {
                (*nit)->prev_sibling=prev;
                if(prev)
                        prev->next_sibling=(*nit);
                prev=(*nit);
                ++nit;
                }
        if(prev)
                prev->next_sibling=(*eit);
        (*eit)->next_sibling=next;
        if(next==0) {
                (*eit)->parent->last_child=next;
                }

        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 <class BinaryPredicate>
bool tree<T, tree_node_allocator>::equal(iterator one, iterator two, iterator three, BinaryPredicate fun) const
        {
        while(one!=two && three.is_valid()) {
                if(one.number_of_children()!=three.number_of_children()) 
                        return false;
                if(!fun(*one,*three))
                        return false;
                ++one;
                ++three;
                }
        return true;
        }

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>
int tree<T, tree_node_allocator>::size() const
        {
        int i=0;
        iterator it=begin(), eit=end();
        while(it!=eit) {
                ++i;
                ++it;
                }
        return i;
        }

template <class T, class tree_node_allocator>
int tree<T, tree_node_allocator>::depth(iterator it) const
        {
        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>
unsigned int tree<T, tree_node_allocator>::number_of_children(iterator it) const
        {
        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;
                }
        return ret;
        }

template <class T, class tree_node_allocator>
unsigned int tree<T, tree_node_allocator>::number_of_siblings(iterator it) const
        {
        tree_node *pos=it.node;
        unsigned int ret=1;
        while(pos->next_sibling && pos->next_sibling!=head) {
                ++ret;
                pos=pos->next_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>
bool tree<T, tree_node_allocator>::is_in_subtree(iterator it, iterator begin, iterator end) const
        {
        // FIXME: this should be optimised.
        iterator tmp=begin;
        while(tmp!=end) {
                if(tmp==it) return true;
                ++tmp;
                }
        return false;
        }


template <class T, class tree_node_allocator>
T& tree<T, tree_node_allocator>::child(iterator it, unsigned int num) const
        {
        tree_node *tmp=it.node->first_child;
        while(num--) {
                assert(tmp!=0);
                tmp=tmp->next_sibling;
                }
        return tmp->data;
        }

// Iterator

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

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

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::iterator::iterator(const sibling_iterator& other)
        : node(other.node), skip_current_children_(false)
        {
        if(node==0) {
                if(other.range_last()!=0)
                        node=other.range_last();
                else 
                        node=other.parent_;
                skip_children();
                increment_();
                }
        }

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

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator tree<T, tree_node_allocator>::iterator::operator+(int num) const
        {
        iterator ret(*this);
        while(num>0) {
                ++ret;
                --num;
                }
        return ret;
        }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator& tree<T, tree_node_allocator>::iterator::operator++(void)
        {
        if(!increment_()) {
                node=0;
                }
        return *this;
        }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator& tree<T, tree_node_allocator>::iterator::operator--(void)
        {
        if(!decrement_()) {
                node=0;
                }
        return *this;
        }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::iterator& tree<T, tree_node_allocator>::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>::iterator& tree<T, tree_node_allocator>::iterator::operator-=(unsigned int num)
        {
        while(num>0) {
                --(*this);
                --num;
                }
        return (*this);
        }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::iterator::operator==(const iterator& other) const
        {
        if(other.node==node) return true;
        else return false;
        }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::iterator::operator!=(const iterator& other) const
        {
        if(other.node!=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::begin() const
        {
        sibling_iterator ret(node->first_child);
        ret.parent_=node;
        return ret;
        }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator tree<T, tree_node_allocator>::iterator::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::skip_children()
        {
        skip_current_children_=true;
        }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::iterator::is_valid() const
        {
        if(node==0) return false;
        else return true;
        }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::iterator::increment_()
        {
        assert(node!=0);
        if(!skip_current_children_ && node->first_child != 0) {
                node=node->first_child;
                return true;
                }
        else {
                skip_current_children_=false;
                while(node->next_sibling==0) {
                        node=node->parent;
                        if(node==0)
                                return false;
                        }
                node=node->next_sibling;
                return true;
                }
        }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::iterator::decrement_()
        {
        assert(node!=0);
        if(node->parent==0) {
                if(node->last_child==0)
                        node=node->prev_sibling;
                while(node->last_child)
                        node=node->last_child;
                if(!node) return false;
                }
        else {
                if(node->prev_sibling) {
                        if(node->prev_sibling->last_child) {
                                node=node->prev_sibling->last_child;
                                }
                        else {
                                node=node->prev_sibling;
                                }
                        }
                else {
                        node=node->parent;
                        if(node==0)
                                return false;
                        }
                }
        return true;
        }

template <class T, class tree_node_allocator>
unsigned int tree<T, tree_node_allocator>::iterator::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;
        }


// Sibling iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::sibling_iterator::sibling_iterator() 
        : node(0), parent_(0)
        {
        }

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

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

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

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::sibling_iterator::set_parent_()
        {
        parent_=0;
        if(node==0) return;
        if(node->parent!=0)
                parent_=node->parent;
        }

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

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

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::sibling_iterator& tree<T, tree_node_allocator>::sibling_iterator::operator++(void)
        {
        if(node)
                node=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--(void)
        {
        if(node) node=node->prev_sibling;
        else {
                assert(parent_);
                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+=(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>
bool tree<T, tree_node_allocator>::sibling_iterator::operator==(const sibling_iterator& other) const
        {
        // We do not compare the parent node pointer, because end iterator may not always
        // have that information (for instance, when creating a sibling_iterator from a normal
        // iterator which is equal to the end() of the tree). This is not a problem, because 
        // the result of comparing two sibling_iterators which are not iterating over siblings of
        // the same node is undefined.
        if(other.node==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!=node) return true;
        else return false;
        }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::sibling_iterator::is_valid() const
        {
        if(node==0) return false;
        else return true;
        }

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;
        }

#endif

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

---