/*    $Id: tree.hh,v 1.125 2006/01/31 17:44:43 kp229 Exp $   STL-like templated tree class.   Copyright (C) 2001-2006  Kasper Peeters <kasper.peeters@aei.mpg.de>.*//** \mainpage tree.hh    \author   Kasper Peeters    \version  2.03    \date     01-Mar-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.   - 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;      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_();      };      /// 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 iterator to the parent of a node.      template<typename iter> iter parent(iter) const;      /// 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 child of node pointed to by position.      template<typename iter> iter append_child(iter position);       /// Insert node as last child of node pointed to by position.      template<typename iter> iter append_child(iter position, const T& x);      /// Append the node (plus its children) at other_position as a child of position.      template<typename iter> iter append_child(iter position, iter other_position);      /// Append the nodes in the from-to range (plus their children) as children of 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 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);      /// 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);            /// 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.      static unsigned int number_of_children(const iterator_base&);      /// 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;            /// Comparator class for iterators (compares pointer values; why doesn't this work automatically?)      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);      /// Comparator class for two nodes of a tree (used for sorting and searching).