tree.hh

tree code, write by c

   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;
   // count forward
   while(pos->next_sibling && 
         pos->next_sibling!=head &&
         pos->next_sibling!=feet) {
      ++ret;
      pos=pos->next_sibling;
      }
   // count backward
   pos=it.node;
   while(pos->prev_sibling && 
         pos->prev_sibling!=head &&
         pos->prev_sibling!=feet) {
      ++ret;
      pos=pos->prev_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 T, class tree_node_allocator>
void tree<T, tree_node_allocator>::swap(iterator one, iterator two)
   {
   // if one and two are adjacent siblings, use the sibling swap
   if(one.node->next_sibling==two.node) swap(one);
   else if(two.node->next_sibling==one.node) swap(two);
   else {
      tree_node *nxt1=one.node->next_sibling;
      tree_node *nxt2=two.node->next_sibling;
      tree_node *pre1=one.node->prev_sibling;
      tree_node *pre2=two.node->prev_sibling;
      tree_node *par1=one.node->parent;
      tree_node *par2=two.node->parent;

      // reconnect
      one.node->parent=par2;
      one.node->next_sibling=nxt2;
      if(nxt2) nxt2->prev_sibling=one.node;
      else     par2->last_child=one.node;
      one.node->prev_sibling=pre2;
      if(pre2) pre2->next_sibling=one.node;
      else     par2->first_child=one.node;    

      two.node->parent=par1;
      two.node->next_sibling=nxt1;
      if(nxt1) nxt1->prev_sibling=two.node;
      else     par1->last_child=two.node;
      two.node->prev_sibling=pre1;
      if(pre1) pre1->next_sibling=two.node;
      else     par1->first_child=two.node;
      }
   }

// 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 || it.node==head) 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>
bool tree<T, tree_node_allocator>::leaf_iterator::operator!=(const leaf_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>::leaf_iterator::operator==(const leaf_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