tree.hh

一个德国人Kasper Peeters用C++ template写的tree的STL实现

   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() 
   : iterator_base(0)
   {
   }

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

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

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::post_order_iterator::post_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>::post_order_iterator& tree<T, tree_node_allocator>::post_order_iterator::operator++()
   {
   assert(this->node!=0);
   if(this->node->next_sibling==0) {
      this->node=this->node->parent;
      this->skip_current_children_=false;
      }
   else {
      this->node=this->node->next_sibling;
      if(this->skip_current_children_) {
         this->skip_current_children_=false;
         }
      else {
         while(this->node->first_child)
            this->node=this->node->first_child;
         }
      }
   return *this;
   }

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

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

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


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

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::post_order_iterator::descend_all()
   {
   assert(this->node!=0);
   while(this->node->first_child)
      this->node=this->node->first_child;
   }


// Breadth-first iterator

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

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(tree_node *tn)
   : iterator_base(tn)
   {
   traversal_queue.push(tn);
   }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::breadth_first_queued_iterator::breadth_first_queued_iterator(const iterator_base& other)
   : iterator_base(other.node)
   {
   traversal_queue.push(other.node);
   }

template <class T, class tree_node_allocator>
bool tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator!=(const breadth_first_queued_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>::breadth_first_queued_iterator::operator==(const breadth_first_queued_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>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator++()
   {
   assert(this->node!=0);

   // Add child nodes and pop current node
   sibling_iterator sib=this->begin();
   while(sib!=this->end()) {
      traversal_queue.push(sib.node);
      ++sib;
      }
   traversal_queue.pop();
   if(traversal_queue.size()>0)
      this->node=traversal_queue.front();
   else 
      this->node=0;
   return (*this);
   }

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

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator& tree<T, tree_node_allocator>::breadth_first_queued_iterator::operator+=(unsigned int num)
   {
   while(num>0) {
      ++(*this);
      --num;
      }
   return (*this);
   }



// Fixed depth iterator

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator()
   : iterator_base()
   {
   set_first_parent_();
   }

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

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

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::fixed_depth_iterator::fixed_depth_iterator(const sibling_iterator& other)
   : iterator_base(other.node), first_parent_(other.parent_)
   {
   find_leftmost_parent_();
   }

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

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::fixed_depth_iterator::set_first_parent_()
   {
   r