tree.h

著名的标准C＋＋的html解析器

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

   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>
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();
   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)
   {
   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_.deallocate(prev,1);
      }
   it.node->first_child=0;
   it.node->last_child=0;
   }

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_.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>::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
   {
   tree_node *tmp=pos.node;
   unsigned int curdepth=0;
   while(curdepth<dp) { // go down one level
      while(tmp->first_child==0) {
         tmp=tmp->next_sibling;
         if(tmp==0)
            throw std::range_error("tree: begin_fixed out of range");
         }
      tmp=tmp->first_child;
      ++curdepth;
      }
   return tmp;
   }

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
   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
   {
   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>
template <typename iter>
iter tree<T, tree_node_allocator>::parent(iter position) const
   {
   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
   {
   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);

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

   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>::append_child(iter position, iter other)
   {
   assert(position.node!=head);

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