tree.hh

tree code, write by c

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

   tree_node *tmp=alloc_.allocate(1,0);
   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);

   tree_node *tmp=alloc_.allocate(1,0);
   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);

   tree_node* tmp = alloc_.allocate(1,0);
   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);

   tree_node* tmp = alloc_.allocate(1,0);
   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);

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

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

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

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