tree.hh

tree code, write by c

/* 

   $Id: tree.hh,v 1.136 2006/10/25 10:08:23 peekas Exp $

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

*/

/** \mainpage tree.hh
    \author   Kasper Peeters
    \version  2.3
    \date     29-Nov-2006
    \see      http://www.aei.mpg.de/~peekas/tree/
    \see      http://www.aei.mpg.de/~peekas/tree/ChangeLog

   The tree.hh library for C++ provides an STL-like container class
   for n-ary trees, templated over the data stored at the
   nodes. Various types of iterators are provided (post-order,
   pre-order, and others). Where possible the access methods are
   compatible with the STL or alternative algorithms are
   available. 
*/


/*
   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 
   - New-style move members are not completely finished yet.
   - It would be good to have an iterator which can iterate over all
     nodes below a given node.
   - 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>
#include <queue>

// 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();
   }

};

/// A node in the tree, combining links to other nodes as well as the actual data.
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:
      /// Value of the data stored at a node.
      typedef T value_type;

      class iterator_base;
      class pre_order_iterator;
      class post_order_iterator;
      class sibling_iterator;
      class leaf_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>&);

      /// Base class for iterators, only pointers stored, no traversal logic.
#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;

            /// When called, the next increment/decrement skips children of this node.
            void         skip_children();
            /// Number of children of the node pointed to by the iterator.
            unsigned int number_of_children() const;

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

            tree_node *node;
         protected:
            bool skip_current_children_;
      };

      /// Depth-first iterator, first accessing the node, then its 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);
      };

      /// Depth-first iterator, first accessing the children, then the node itself.
      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);

            /// Set iterator to the first child as deep as possible down the tree.
            void descend_all();
      };

      /// Breadth-first iterator, using a queue
      class breadth_first_queued_iterator : public iterator_base {
         public:
            breadth_first_queued_iterator();
            breadth_first_queued_iterator(tree_node *);
            breadth_first_queued_iterator(const iterator_base&);

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

         private:
            std::queue<tree_node *> traversal_queue;
      };

      /// The default iterator types throughout the tree class.
      typedef pre_order_iterator            iterator;
      typedef breadth_first_queued_iterator breadth_first_iterator;

      /// Iterator which traverses only the nodes at a given depth from the root.
      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_();
      };

      /// Iterator which traverses only the nodes which are siblings of each other.
      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_();
      };

      /// Iterator which traverses only the leaves.
      class leaf_iterator : public iterator_base {
         public:
            leaf_iterator();
            leaf_iterator(tree_node *);
            leaf_iterator(const sibling_iterator&);
            leaf_iterator(const iterator_base&);

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

      /// Return iterator to the beginning of the tree.
      inline pre_order_iterator   begin() const;
      /// Return iterator to the end of the tree.
      inline pre_order_iterator   end() const;
      /// Return post-order iterator to the beginning of the tree.
      post_order_iterator  begin_post() const;
      /// Return post-order iterator to the end of the tree.
      post_order_iterator  end_post() const;
      /// Return fixed-depth iterator to the first node at a given depth.
      fixed_depth_iterator begin_fixed(const iterator_base&, unsigned int) const;
      /// Return fixed-depth iterator to end of the nodes at given depth.
      fixed_depth_iterator end_fixed(const iterator_base&, unsigned int) const;
      /// Return breadth-first iterator to the first node at a given depth.
      breadth_first_queued_iterator begin_breadth_first() const;
      /// Return breadth-first iterator to end of the nodes at given depth.
      breadth_first_queued_iterator end_breadth_first() const;
      /// Return sibling iterator to the first child of given node.
      sibling_iterator     begin(const iterator_base&) const;
      /// Return sibling iterator to the end of the children of a given node.
      sibling_iterator     end(const iterator_base&) const;
      /// Return leaf iterator to the first leaf of the tree.
      leaf_iterator   begin_leaf() const;
      /// Return leaf iterator to the last leaf of the tree.
      leaf_iterator   end_leaf() const;

      /// Return iterator to the parent of a node.
      template<typename iter> static iter parent(iter);
      /// Return iterator to the previous sibling of a node.
      template<typename iter> iter previous_sibling(iter) const;
      /// Return iterator to the next sibling of a node.
      template<typename iter> iter next_sibling(iter) const;
      /// Return iterator to the next node at a given depth.
      template<typename iter> iter next_at_same_depth(iter) const;

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

      /// Insert empty node as last/first child of node pointed to by position.
      template<typename iter> iter append_child(iter position); 
      template<typename iter> iter prepend_child(iter position); 
      /// Insert node as last/first child of node pointed to by position.
      template<typename iter> iter append_child(iter position, const T& x);
      template<typename iter> iter prepend_child(iter position, const T& x);
      /// Append the node (plus its children) at other_position as last/first child of position.
      template<typename iter> iter append_child(iter position, iter other_position);
      template<typename iter> iter prepend_child(iter position, iter other_position);
      /// Append the nodes in the from-to range (plus their children) as last/first children of position.
      template<typename iter> iter append_children(iter position, sibling_iterator from, sibling_iterator to);
      template<typename iter> iter prepend_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 of previous member.
      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);
      /// Move all child nodes of 'from' to be children of 'position'.
      template<typename iter> iter reparent(iter position, iter from);

      /// Replace node with a new node, making the old node a child of the new node.
      template<typename iter> iter wrap(iter position, const T& x);

      /// Move 'source' node (plus its children) to become the next sibling of 'target'.
      template<typename iter> iter move_after(iter target, iter source);
      /// Move 'source' node (plus its children) to become the previous sibling of 'target'.
      template<typename iter> iter move_before(iter target, iter source);
      sibling_iterator move_before(sibling_iterator target, sibling_iterator source);
      /// Move 'source' node (plus its children) to become the node at 'target' (erasing the node at 'target').
      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);
      /// Exchange two nodes (plus subtrees)
      void     swap(iterator, iterator);
      
      /// Count the total number of nodes.