tree.h

著名的标准C＋＋的html解析器

/* 

   $Id: tree.h,v 1.3 2005/02/22 04:47:04 davi Exp $

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

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

   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
   
   TODO: - 'Move' members are long overdue; will hopefully be incorporated in the
           next release.
         - Fixed depth iterators do not iterate over the entire range if there
           are 'holes' in the tree.
         - If a range uses const iter_base& as end iterator, things will
           inevitably go wrong, because upcast from iter_base to a non-sibling_iter
           is incorrect. This upcast should be removed (and then all illegal uses
           as previously in 'equal' will be flagged by the compiler). This requires
           new copy constructors though.
         - There's a bug in replace(sibling_iterator, ...) when the ranges
           sit next to each other. Turned up in append_child(iter,iter)
           but has been avoided now.
         - "std::operator<" does not work correctly on our iterators, and for some
           reason a globally defined template operator< did not get picked up. 
           Using a comparison class now, but this should be investigated.
*/

#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.

namespace kp {

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

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

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

};

template<class T>
class tree_node_ { // size: 5*4=20 bytes (on 32 bit arch), can be reduced by 8.
   public:
      tree_node_<T> *parent;
      tree_node_<T> *first_child, *last_child;
      tree_node_<T> *prev_sibling, *next_sibling;
      T data;
}; 
//__attribute__((packed));

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();
      tree(const T&);
      tree(const iterator_base&);
      tree(const tree<T, tree_node_allocator>&);
      ~tree();
      void operator=(const tree<T, tree_node_allocator>&);

#ifdef __SGI_STL_PORT
      class iterator_base : public stlport::bidirectional_iterator<T, ptrdiff_t> {
#else
      class iterator_base {
#endif
         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();
            iterator_base(tree_node *);

            T&             operator*() const;
            T*             operator->() const;

            void         skip_children(); // do not iterate over children of this node
            unsigned int number_of_children() const;

            sibling_iterator begin() const;
            sibling_iterator end() const;

            tree_node *node;
         protected:
            bool skip_current_children_;
      };

      class pre_order_iterator : public iterator_base { 
         public:
            pre_order_iterator();
            pre_order_iterator(tree_node *);
            pre_order_iterator(const iterator_base&);
            pre_order_iterator(const sibling_iterator&);

            bool    operator==(const pre_order_iterator&) const;
            bool    operator!=(const pre_order_iterator&) const;
            pre_order_iterator&  operator++();
            pre_order_iterator&  operator--();
            pre_order_iterator   operator++(int);
            pre_order_iterator   operator--(int);
            pre_order_iterator&  operator+=(unsigned int);
            pre_order_iterator&  operator-=(unsigned int);
      };

      class post_order_iterator : public iterator_base {
         public:
            post_order_iterator();
            post_order_iterator(tree_node *);
            post_order_iterator(const iterator_base&);
            post_order_iterator(const sibling_iterator&);

            bool    operator==(const post_order_iterator&) const;
            bool    operator!=(const post_order_iterator&) const;
            post_order_iterator&  operator++();
            post_order_iterator&  operator--();
            post_order_iterator   operator++(int);
            post_order_iterator   operator--(int);
            post_order_iterator&  operator+=(unsigned int);
            post_order_iterator&  operator-=(unsigned int);

            void descend_all();
      };

      typedef pre_order_iterator iterator;

      class fixed_depth_iterator : public iterator_base {
         public:
            fixed_depth_iterator();
            fixed_depth_iterator(tree_node *);
            fixed_depth_iterator(const iterator_base&);
            fixed_depth_iterator(const sibling_iterator&);
            fixed_depth_iterator(const fixed_depth_iterator&);

            bool    operator==(const fixed_depth_iterator&) const;
            bool    operator!=(const fixed_depth_iterator&) const;
            fixed_depth_iterator&  operator++();
            fixed_depth_iterator&  operator--();
            fixed_depth_iterator   operator++(int);
            fixed_depth_iterator   operator--(int);
            fixed_depth_iterator&  operator+=(unsigned int);
            fixed_depth_iterator&  operator-=(unsigned int);

            tree_node *first_parent_;
         private:
            void set_first_parent_();
            void find_leftmost_parent_();
      };

      class sibling_iterator : public iterator_base {
         public:
            sibling_iterator();
            sibling_iterator(tree_node *);
            sibling_iterator(const sibling_iterator&);
            sibling_iterator(const iterator_base&);

            bool    operator==(const sibling_iterator&) const;
            bool    operator!=(const sibling_iterator&) const;
            sibling_iterator&  operator++();
            sibling_iterator&  operator--();
            sibling_iterator   operator++(int);
            sibling_iterator   operator--(int);
            sibling_iterator&  operator+=(unsigned int);
            sibling_iterator&  operator-=(unsigned int);

            tree_node *range_first() const;
            tree_node *range_last() const;
            tree_node *parent_;
         private:
            void set_parent_();
      };

      // begin/end of tree
      inline pre_order_iterator   begin() const;
      inline pre_order_iterator   end() const;
      post_order_iterator  begin_post() const;
      post_order_iterator  end_post() const;
      fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
      fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
      // begin/end of children of node
      sibling_iterator     begin(const iterator_base&) const;
      sibling_iterator     end(const iterator_base&) const;

      template<typename iter> iter parent(iter) const;
      template<typename iter> iter previous_sibling(iter) const;
      template<typename iter> iter next_sibling(iter) const;
      template<typename iter> iter next_at_same_depth(iter) const;

      void     clear();
      // erase element at position pointed to by iterator, increment iterator
      template<typename iter> iter erase(iter);
      // erase all children of the node pointed to by iterator
      void     erase_children(const iterator_base&);

      // insert node as last child of node pointed to by position (first one inserts empty node)
      template<typename iter> iter append_child(iter position); 
      template<typename iter> iter append_child(iter position, const T& x);
      // the following two append nodes plus their children
      template<typename iter> iter append_child(iter position, iter other_position);
      template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);

      // short-hand to insert topmost node in otherwise empty tree
      pre_order_iterator set_head(const T& x);
      // insert node as previous sibling of node pointed to by position
      template<typename iter> iter insert(iter position, const T& x);
      // specialisation: insert node as previous sibling of node pointed to by position
      //pre_order_iterator insert(sibling_iterator position, const T& x);
      sibling_iterator insert(sibling_iterator position, const T& x);
      // insert node (with children) pointed to by subtree as previous sibling of node pointed to by position
      template<typename iter> iter insert_subtree(iter position, const iterator_base& subtree);
      // insert node as next sibling of node pointed to by position
      template<typename iter> iter insert_after(iter position, const T& x);

      // replace node at 'position' with other node (keeping same children); 'position' becomes invalid.
      template<typename iter> iter replace(iter position, const T& x);
      // replace node at 'position' with subtree starting at 'from' (do not erase subtree at 'from'); see above.
      template<typename iter> iter replace(iter position, const iterator_base& from);
      // replace string of siblings (plus their children) with copy of a new string (with children); see above
      sibling_iterator replace(sibling_iterator orig_begin, sibling_iterator orig_end, 
                               sibling_iterator new_begin,  sibling_iterator new_end); 

      // move all children of node at 'position' to be siblings, returns position
      template<typename iter> iter flatten(iter position);
      // move nodes in range to be children of 'position'
      template<typename iter> iter reparent(iter position, sibling_iterator begin, sibling_iterator end);
      // ditto, the range being all children of the 'from' node
      template<typename iter> iter reparent(iter position, iter from);

      // new style move members, moving nodes plus children to a different location 
      template<typename iter> iter move_after(iter target, iter source);
      template<typename iter> iter move_before(iter target, iter source);
      template<typename iter> iter move_ontop(iter target, iter source);

      // merge with other tree, creating new branches and leaves only if they are not already present
      void     merge(sibling_iterator, sibling_iterator, sibling_iterator, sibling_iterator, 
                     bool duplicate_leaves=false);
      // sort (std::sort only moves values of nodes, this one moves children as well)
      void     sort(sibling_iterator from, sibling_iterator to, bool deep=false);
      template<class StrictWeakOrdering>
      void     sort(sibling_iterator from, sibling_iterator to, StrictWeakOrdering comp, bool deep=false);
      // compare two ranges of nodes (compares nodes as well as tree structure)
      template<typename iter>
      bool     equal(const iter& one, const iter& two, const iter& three) const;
      template<typename iter, class BinaryPredicate>
      bool     equal(const iter& one, const iter& two, const iter& three, BinaryPredicate) const;
      template<typename iter>
      bool     equal_subtree(const iter& one, const iter& two) const;
      template<typename iter, class BinaryPredicate>
      bool     equal_subtree(const iter& one, const iter& two, BinaryPredicate) const;
      // extract a new tree formed by the range of siblings plus all their children
      tree     subtree(sibling_iterator from, sibling_iterator to) const;
      void     subtree(tree&, sibling_iterator from, sibling_iterator to) const;
      // exchange the node (plus subtree) with its sibling node (do nothing if no sibling present)
      void     swap(sibling_iterator it);
      // find a subtree
//    template<class BinaryPredicate>
//    iterator find_subtree(sibling_iterator, sibling_iterator, iterator from, iterator to, BinaryPredicate) const;
      
      // count the total number of nodes
      int      size() const;
      // check if tree is empty
      bool     empty() const;
      // compute the depth to the root
      int      depth(const iterator_base&) const;
      // count the number of children of node at position
      unsigned int number_of_children(const iterator_base&) const;
      // count the number of 'next' siblings of node at iterator
      unsigned int number_of_siblings(const iterator_base&) const;
      // determine whether node at position is in the subtrees with root in the range
      bool     is_in_subtree(const iterator_base& position, const iterator_base& begin, 
                             const iterator_base& end) const;
      // determine whether the iterator is an 'end' iterator and thus not actually
      // pointing to a node
      bool     is_valid(const iterator_base&) const;

      // determine the index of a node in the range of siblings to which it belongs.
      unsigned int index(sibling_iterator it) const;
      // inverse of 'index': return the n-th child of the node at position
      sibling_iterator  child(const iterator_base& position, unsigned int) const;
      
      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
               {
               return one.node < two.node;
               }
      };
      tree_node *head, *feet;    // head/feet are always dummy; if an iterator points to them it is invalid
   private:
      tree_node_allocator alloc_;
      void head_initialise_();
      void copy_(const tree<T, tree_node_allocator>& other);
      template<class StrictWeakOrdering>
      class compare_nodes {
         public:
            bool operator()(const tree_node *a, const tree_node *b) 
               {
               static StrictWeakOrdering comp;
               return comp(a->data, b->data);
               }
      };
};

//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_base& one,
               const typename tree<T, tree_node_allocator>::iterator_base& two)
   {
   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);
   }