tree.hh

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

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(dst_prev_sibling!=0) dst_prev_sibling->next_sibling=src;
   else                    target.parent_->first_child=src;
   src->prev_sibling=dst_prev_sibling;
   if(dst) {
      dst->prev_sibling=src;
      src->parent=dst->parent;
      }
   src->next_sibling=dst;
   return src;
   }

template <class T, class tree_node_allocator>
template <typename iter> iter tree<T, tree_node_allocator>::move_ontop(iter target, iter source)
   {
   tree_node *dst=target.node;
   tree_node *src=source.node;
   assert(dst);
   assert(src);

   if(dst==src) return source;

   // remember connection points
   tree_node *b_prev_sibling=dst->prev_sibling;
   tree_node *b_next_sibling=dst->next_sibling;
   tree_node *b_parent=dst->parent;

   // remove target
   erase(target);

   // take src out of the tree
   if(src->prev_sibling!=0) src->prev_sibling->next_sibling=src->next_sibling;
   else                     src->parent->first_child=src->next_sibling;
   if(src->next_sibling!=0) src->next_sibling->prev_sibling=src->prev_sibling;
   else                     src->parent->last_child=src->prev_sibling;

   // connect it to the new point
   if(b_prev_sibling!=0) b_prev_sibling->next_sibling=src;
   else                  b_parent->first_child=src;
   if(b_next_sibling!=0) b_next_sibling->prev_sibling=src;
   else                  b_parent->last_child=src;
   src->prev_sibling=b_prev_sibling;
   src->next_sibling=b_next_sibling;
   src->parent=b_parent;
   return src;
   }

template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::merge(sibling_iterator to1,   sibling_iterator to2,
                                          sibling_iterator from1, sibling_iterator from2,
                                          bool duplicate_leaves)
   {
   sibling_iterator fnd;
   while(from1!=from2) {
      if((fnd=std::find(to1, to2, (*from1))) != to2) { // element found
         if(from1.begin()==from1.end()) { // full depth reached
            if(duplicate_leaves)
               append_child(parent(to1), (*from1));
            }
         else { // descend further
            merge(fnd.begin(), fnd.end(), from1.begin(), from1.end(), duplicate_leaves);
            }
         }
      else { // element missing
         insert_subtree(to2, from1);
         }
      ++from1;
      }
   }


template <class T, class tree_node_allocator>
void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, bool deep)
   {
   std::less<T> comp;
   sort(from, to, comp, deep);
   }

template <class T, class tree_node_allocator>
template <class StrictWeakOrdering>
void tree<T, tree_node_allocator>::sort(sibling_iterator from, sibling_iterator to, 
                                        StrictWeakOrdering comp, bool deep)
   {
   if(from==to) return;
   // make list of sorted nodes
   // CHECK: if multiset stores equivalent nodes in the order in which they
   // are inserted, then this routine should be called 'stable_sort'.
   std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> > nodes(comp);
   sibling_iterator it=from, it2=to;
   while(it != to) {
      nodes.insert(it.node);
      ++it;
      }
   // reassemble
   --it2;

   // prev and next are the nodes before and after the sorted range
   tree_node *prev=from.node->prev_sibling;
   tree_node *next=it2.node->next_sibling;
   typename std::multiset<tree_node *, compare_nodes<StrictWeakOrdering> >::iterator nit=nodes.begin(), eit=nodes.end();
   if(prev==0) {
      if((*nit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
         (*nit)->parent->first_child=(*nit);
      }
   else prev->next_sibling=(*nit);

   --eit;
   while(nit!=eit) {
      (*nit)->prev_sibling=prev;
      if(prev)
         prev->next_sibling=(*nit);
      prev=(*nit);
      ++nit;
      }
   // prev now points to the last-but-one node in the sorted range
   if(prev)
      prev->next_sibling=(*eit);

   // eit points to the last node in the sorted range.
   (*eit)->next_sibling=next;
   (*eit)->prev_sibling=prev; // missed in the loop above
   if(next==0) {
      if((*eit)->parent!=0) // to catch "sorting the head" situations, when there is no parent
         (*eit)->parent->last_child=(*eit);
      }
   else next->prev_sibling=(*eit);

   if(deep) {  // sort the children of each node too
      sibling_iterator bcs(*nodes.begin());
      sibling_iterator ecs(*eit);
      ++ecs;
      while(bcs!=ecs) {
         sort(begin(bcs), end(bcs), comp, deep);
         ++bcs;
         }
      }
   }

template <class T, class tree_node_allocator>
template <typename iter>
bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_) const
   {
   std::equal_to<T> comp;
   return equal(one_, two, three_, comp);
   }

template <class T, class tree_node_allocator>
template <typename iter>
bool tree<T, tree_node_allocator>::equal_subtree(const iter& one_, const iter& two_) const
   {
   std::equal_to<T> comp;
   return equal_subtree(one_, two_, comp);
   }

template <class T, class tree_node_allocator>
template <typename iter, class BinaryPredicate>
bool tree<T, tree_node_allocator>::equal(const iter& one_, const iter& two, const iter& three_, BinaryPredicate fun) const
   {
   pre_order_iterator one(one_), three(three_);

// if(one==two && is_valid(three) && three.number_of_children()!=0)
//    return false;
   while(one!=two && is_valid(three)) {
      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) 
   {
   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;