tree.hh

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

      template<class StrictWeakOrdering>
      class compare_nodes {
         public:
            compare_nodes(StrictWeakOrdering comp) : comp_(comp) {};
            
            bool operator()(const tree_node *a, const tree_node *b) 
               {
               static StrictWeakOrdering comp;
               return comp(a->data, b->data);
               }
         private:
            StrictWeakOrdering comp_;
      };
};

//template <class T, class tree_node_allocator>
//class iterator_base_less {
// public:
//    bool operator()(const typename tree<T, tree_node_allocator>::iterator_base& one,
//                  const typename tree<T, tree_node_allocator>::iterator_base& two) const
//       {
//       txtout << "operatorclass<" << one.node < two.node << std::endl;
//       return one.node < two.node;
//       }
//};

// template <class T, class tree_node_allocator>
// bool operator<(const typename tree<T, tree_node_allocator>::iterator& one,
//                const typename tree<T, tree_node_allocator>::iterator& two)
//    {
//    txtout << "operator< " << one.node < two.node << std::endl;
//    if(one.node < two.node) return true;
//    return false;
//    }
// 
// template <class T, class tree_node_allocator>
// bool operator==(const typename tree<T, tree_node_allocator>::iterator& one,
//                const typename tree<T, tree_node_allocator>::iterator& two)
//    {
//    txtout << "operator== " << one.node == two.node << std::endl;
//    if(one.node == two.node) return true;
//    return false;
//    }
// 
// template <class T, class tree_node_allocator>
// bool operator>(const typename tree<T, tree_node_allocator>::iterator_base& one,
//                const typename tree<T, tree_node_allocator>::iterator_base& two)
//    {
//    txtout << "operator> " << one.node < two.node << std::endl;
//    if(one.node > two.node) return true;
//    return false;
//    }



// Tree

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::tree() 
   {
   head_initialise_();
   }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::tree(const T& x) 
   {
   head_initialise_();
   set_head(x);
   }

template <class T, class tree_node_allocator>
tree<T, tree_node_allocator>::tree(const iterator_base& other)
   {
   head_initialise_();
   set_head((*other));
   replace(begin(), other);
   }

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>::breadth_first_queued_iterator tree<T, tree_node_allocator>::begin_breadth_first() const
   {
   return breadth_first_queued_iterator(head->next_sibling);
   }

template <class T, class tree_node_allocator>
typename tree<T, tree_node_allocator>::breadth_first_queued_iterator tree<T, tree_node_allocator>::end_breadth_first() const
   {
   return breadth_first_queued_iterator();
   }

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
   {
   assert(pos.node!=0);
   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);
   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 <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;