tree.h

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

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

template <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;
   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;
   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!=this->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==this->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_base::begin() const
   {
   sibling_iterator ret(node->first_child);
   ret.parent_=this->node;
   return ret;
   }

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

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



// Pre-order iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator() 
   : iterator_base(0)
   {
   }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(tree_node *tn)
   : iterator_base(tn)
   {
   }

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

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::pre_order_iterator::pre_order_iterator(const sibling_iterator& other)
   : iterator_base(other.node)
   {
   if(this->node==0) {
      if(other.range_last()!=0)
         this->node=other.range_last();
      else 
         this->node=other.parent_;
      this->skip_children();
      ++(*this);
      }
   }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator++()
   {
   assert(this->node!=0);
   if(!this->skip_current_children_ && this->node->first_child != 0) {
      this->node=this->node->first_child;
      }
   else {
      this->skip_current_children_=false;
      while(this->node->next_sibling==0) {
         this->node=this->node->parent;
         if(this->node==0)
            return *this;
         }
      this->node=this->node->next_sibling;
      }
   return *this;
   }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator& tree<T, tree_node_allocator>::pre_order_iterator::operator--()
   {
   assert(this->node!=0);
   if(this->node->prev_sibling) {
      this->node=this->node->prev_sibling;
      while(this->node->last_child)
         this->node=this->node->last_child;
      }
   else {
      this->node=this->node->parent;
      if(this->node==0)
         return *this;
      }
   return *this;
}

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator++(int n)
   {
   pre_order_iterator copy = *this;
   ++(*this);
   return copy;
   }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::pre_order_iterator tree<T, tree_node_allocator>::pre_order_iterator::operator--(int n)
{
  pre_order_iterator copy = *this;
  --(*this);
  return copy;
}

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



// Post-order iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::post_order_iterator::post_order_iterator()