tmp->next_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);   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>::append_children(iter position, sibling_iterator from, sibling_iterator to)   {   assert(position.node!=head);   assert(position.node);   iter ret=from;   while(from!=to) {      insert_subtree(position.end(), 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);   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);   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);   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(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);   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   erase_children(position);     tree_node* tmp = alloc_.allocate(1,0);   kp::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;   kp::destructor(&current_to->data);   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;   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>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>::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;   // 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;   // 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_iteratorstemplate <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;