// 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;   // 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>int tree<T, tree_node_allocator>::size() const   {   int i=0;   pre_order_iterator it=begin(), eit=end();   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) 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(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;   while(pos->next_sibling &&          pos->next_sibling!=head &&         pos->next_sibling!=feet) {      ++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 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) return false;   else return true;   }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>::child(const iterator_base& it, unsigned int num) const   {   tree_node *tmp=it.node->first_child;   while(num--) {      assert(tmp!=0);      tmp=tmp->next_sibling;      }   return tmp;   }// Iterator basetemplate <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;