tree_msvc.hh

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

/* 

   $Id: tree_msvc.hh,v 1.8 2003/03/25 11:09:08 t16 Exp $

   STL-like templated tree class.
   Copyright (C) 2001  Kasper Peeters <[e-mail]>

   Microsoft VC 6 version of tree.hh (1.80) by Tony Cook, see 

      http://www.damtp.cam.ac.uk/user/kp229/tree/

   for the original and for more information and documentation. 
   See the Changelog file for other credits.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
   
*/

#ifndef tree_hh_
#define tree_hh_

#include <cassert>
#include <memory>
#include <stdexcept>
#include <iterator>
#include <set>

// HP-style construct/destroy have gone from the standard,
// so here is a copy.

template <class T1, class T2>
inline void constructor(T1* p, T2& val) 
   {
   new ((void *) p) T1(val);
   }

template <class T1>
inline void constructor(T1* p) 
   {
   new ((void *) p) T1;
   }

template <class T1>
inline void destructor(T1* p)
   {
   p->~T1();
   }


template<class T>
struct tree_node_ {
      tree_node_<T> *parent;
      tree_node_<T> *first_child, *last_child;
      tree_node_<T> *prev_sibling, *next_sibling;
      T data;
};

template <class T, class tree_node_allocator = std::allocator<tree_node_<T> > >
class tree {
   protected:
      typedef tree_node_<T> tree_node;
   public:
      typedef T value_type;

      class iterator_base;
      class pre_order_iterator;
      class post_order_iterator;
      class sibling_iterator;

      tree() 
         {
         head_initialise_();
         }

      tree(const T& x) 
         {
         head_initialise_();
         set_head(x);
         }

      tree(const iterator_base& other)
         {
         head_initialise_();
         set_head((*other));
         replace(begin(), other);
         }

      tree(const tree<T, tree_node_allocator>& other)
         {
         head_initialise_();
         copy_(other);
         }

      ~tree()
         {
         clear();
         alloc_.deallocate(head,1);
         }

      void operator=(const tree<T, tree_node_allocator>& other)
         {
         copy_(other);
         }

      class iterator_base {
         public:
            typedef T                               value_type;
            typedef T*                              pointer;
            typedef T&                              reference;
            typedef size_t                          size_type;
            typedef ptrdiff_t                       difference_type;
            typedef std::bidirectional_iterator_tag iterator_category;

            iterator_base()
               : node(0), skip_current_children_(false)
               {
               }

            iterator_base(tree_node *tn)
               : node(tn), skip_current_children_(false)
               {
               }

            virtual iterator_base&  operator++()=0;
            virtual iterator_base&  operator--()=0;
            virtual iterator_base&  operator+=(unsigned int)=0;
            virtual iterator_base&  operator-=(unsigned int)=0;

            T&             operator*() const
               {
               return node->data;
               }

            T*             operator->() const
               {
               return &(node->data);
               }

            // do not iterate over children of this node
            void         skip_children()
               {
               skip_current_children_=true;
               }

            unsigned int 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;
               }

            sibling_iterator begin() const
               {
               sibling_iterator ret(node->first_child);
               ret.parent_=node;
               return ret;
               }

            sibling_iterator end() const
               {
               sibling_iterator ret(0);
               ret.parent_=node;
               return ret;
               }

            tree_node *node;

         protected:
            bool skip_current_children_;
      };

      class pre_order_iterator : public iterator_base { 
         public:
            pre_order_iterator() 
               : iterator_base(0)
               {
               }

            pre_order_iterator(tree_node *tn)
               : iterator_base(tn)
               {
               }

            pre_order_iterator(const iterator_base &other)
               : iterator_base(other.node)
               {
               }

            pre_order_iterator(const sibling_iterator& other)
               : iterator_base(other.node)
               {
               if(node==0) {
                  if(other.range_last()!=0)
                     node=other.range_last();
                  else 
                     node=other.parent_;
                  skip_children();
                  ++(*this);
                  }
               }

            bool operator==(const pre_order_iterator& other) const
               {
               if(other.node==node) return true;
               else return false;
               }

            bool operator!=(const pre_order_iterator& other) const
               {
               if(other.node!=node) return true;
               else return false;
               }

            virtual iterator_base&  operator++()
               {
               assert(node!=0);
               if(!skip_current_children_ && node->first_child != 0) {
                  node=node->first_child;
                  }
               else {
                  skip_current_children_=false;
                  while(node->next_sibling==0) {
                     node=node->parent;
                     if(node==0)
                        return *this;
                     }
                  node=node->next_sibling;
                  }
               return *this;
               }

            virtual iterator_base&  operator--()
               {
               assert(node!=0);
               if(node->prev_sibling) {
                  node=node->prev_sibling;
                  while(node->last_child)
                     node=node->last_child;
                  }
               else {
                  node=node->parent;
                  if(node==0)
                     return *this;
                  }
               return *this;
               }

            virtual iterator_base&  operator+=(unsigned int num)
               {
               while(num>0) {
                  ++(*this);
                  --num;
                  }
               return (*this);
               }

            virtual iterator_base&  operator-=(unsigned int num)
               {
               while(num>0) {
                   --(*this);
                   --num;
                   }
               return (*this);
               }
      };

      class post_order_iterator : public iterator_base {
         public:
            post_order_iterator() 
               : iterator_base(0)
               {
               }

            post_order_iterator(tree_node *tn)
               : iterator_base(tn)
               {
               }

            post_order_iterator(const iterator_base &other)
               : iterator_base(other.node)
               {
               }

            post_order_iterator(const sibling_iterator& other)
               : iterator_base(other.node)
               {
               if(node==0) {
                  if(other.range_last()!=0)
                     node=other.range_last();
                  else 
                     node=other.parent_;
                  skip_children();
                  ++(*this);
                  }
               }

            bool operator==(const post_order_iterator& other) const
               {
               if(other.node==node) return true;
               else return false;
               }

            bool operator!=(const post_order_iterator& other) const
               {
               if(other.node!=node) return true;
               else return false;
               }

            virtual iterator_base&  operator++()
               {
               assert(node!=0);
               if(node->next_sibling==0) 
                  node=node->parent;
               else {
                  node=node->next_sibling;
                  if(skip_current_children_) {
                     skip_current_children_=false;
                     }
                  else {
                     while(node->first_child)
                        node=node->first_child;
                     }
                  }
               return *this;
               }

            virtual iterator_base&  operator--()
               {
               assert(node!=0);
               if(skip_current_children_ || node->last_child==0) {
                  skip_current_children_=false;
                  while(node->prev_sibling==0)
                     node=node->parent;
                  node=node->prev_sibling;
                  }
               else {
                  node=node->last_child;
                  }
               return *this;
               }

            virtual iterator_base&  operator+=(unsigned int num)
               {
               while(num>0) {
                  ++(*this);
                  --num;
                  }
               return (*this);
               }

            virtual iterator_base&  operator-=(unsigned int num)
               {
               while(num>0) {
                  --(*this);
                  --num;
                  }
               return (*this);
               }

            void descend_all()
               {
               assert(node!=0);
               while(node->first_child)
                  node=node->first_child;
               }

      };

      typedef pre_order_iterator iterator;

      class sibling_iterator : public iterator_base {
         public:
            sibling_iterator() 
               : iterator_base()
               {
               }

            sibling_iterator(tree_node *tn)
               : iterator_base(tn)
               {
               set_parent_();
               }

            sibling_iterator(const sibling_iterator& other)
               : iterator_base(other), parent_(other.parent_)
               {
               }

            sibling_iterator(const iterator_base& other)
               : iterator_base(other.node)
               {
               set_parent_();
               }

            bool operator==(const sibling_iterator& other) const
               {
               if(other.node==node) return true;
               else return false;
               }