+ View the NASA Portal

Search JPL

Search CLARAty

- Algorithms- Infrastructure - Doxygen (public)- Doxygen (private)- Tutorials

- Repository- Nightly Build- Nightly Regression- Feature/Bug Tracking- Build Targets- Procedure- Conventions- Tools

tree.h

Go to the documentation of this file.

// -*-c++-*-
//---------------------------< /-/ CLARAty /-/ >------------------------------
/**
 * @file  tree.h
 *
 * Standard Template Library (STL)-like tree class.
 *
 * <br>@b Designer(s):    Hari Das Nayar
 * <br>@b Author(s):      Hari Das Nayar
 * <br>@b Date:           October 2, 2004 
 *
 * <b>Software License:</b><br>
 * <code> http://claraty.jpl.nasa.gov/license/open_src/  or 
 *        file: license/open_src.txt </code>
 *
 * &copy; 2006, Jet Propulsion Laboratory, California Institute of Technology<br><br>
 *
 * $Revision: 1.8 $
 */
//-----------------------------------------------------------------------------

#ifndef  TREE_H
#define  TREE_H

#include "claraty/share.h"
#include <algorithm>

/************************************************************************** 
  For the following tree below, an example of the pre-order iteration
    sequence for pre_order_iterator is as follows:

                                   --------1------
                                 /         |       \
                                /          |         \
                               2           7          13
                              / \        / | \
                             /   \     /   |   \
                            3     6   8    9    10
                           / \                 /  \
                          /    \              11   12
                         4      5

    Algorithm:
        pre-order(v)
        {
            visit(v)
            for    each child w of v
                pre-order(w)
        }


For the following tree below, an example of the post-order iteration
    sequence for post_order_iterator is as follows:

                                   --------13------
                                 /         |       \
                                /          |         \
                               5          11          12
                              / \        / | \
                             /   \     /   |   \
                            3     4   6    7    10
                           / \                 /  \
                          /    \              8    9
                         1      2

    Algorithm:
        post-order(v)
        {
            for    each child w of v
                post-order(w)
            visit(v)
        }

For the following tree below, an example of the sibling iteration
    sequence for sibling_iterator is as follows:

                                  ---------x------
                                 /         |       \
                                /          |         \
                               x           x          x
                              / \        / | \
                             /   \     /   |   \
                            x     x   1    2    3
                           / \                 /  \
                          /    \              x    x
                         x      x




For the following tree below, an example of the chain iteration
    sequence (where a begin (node #1) and an end (node #6) are previously
    defined to specify the chain) for a chain_iterator is as follows:

                                  ---------3------
                                 /         |       \
                                /          |         \
                               2           4          x
                              / \        / | \
                             /   \     /   |   \
                            x     1   x    x    5
                           / \                 /  \
                          /    \              6    x
                         x      x



*/
//-------------------------------------------------------------------------
//-------------------------<< Tree Class >>---------------------------
//-------------------------------------------------------------------------
//
// NOTE: Tree_Node and Iterator classes are defined within the
//            Tree class definition.
//

template < class T >
class Tree {
public:
  typedef T value_type;
  typedef ptrdiff_t difference_type;
  typedef T* pointer;
  typedef T& reference;

  //------------------------------------------------------------------
  //    Define the Tree_Node class here
  //------------------------------------------------------------------
  class Tree_Node {    
  public:
    Tree_Node *p_parent;
    Tree_Node *p_previous_sibling, *p_next_sibling;
    Tree_Node *p_first_child, *p_last_child;
    T *data;

    /**
     * Constructor: Add a new child to parent node specified in arg. This also
     * serves as a copy constructor when the parent arg. is not included.
     * @param[in] new_child  Reference to tree node data type.
     * @param[in] parent     Pointer to the parent node.
     */
    Tree_Node(T * new_child, Tree_Node* parent = 0);

    /**
     * Default constructor
     */
    Tree_Node();


    /**
     * Destructor: Note that as in std::vector, the elements are allocated
     * outside tree but destroyed within it when the tree is cleared.
     */
    ~Tree_Node();

    /**
     * Equals operator: sets the data of a Tree_Node to the
     * data of another Tree_Node.
     * @param[in] x  Reference to Tree_Node.
     * @return Reference to Tree_Node.
     */
    Tree_Node &  operator=(const Tree_Node & x);
  
  };

  //------------------------------------------------------------------
        // This is a special node that is used to bracket a set of elements in
  // the tree. It is used as a ficticous node to indicate that an iterator
  // is pointing beyond the end of the tree or before the beginning. By
  // convention, the end() iterator point to a location beyond the last
  // element and begin() points to the first zero-indexed element.
  //------------------------------------------------------------------
  class Tree_Terminal_Node {    
  public:

    /**
     * Default constructor
     */
    Tree_Terminal_Node():p_previous(0), p_next(0){}

    /**
     * Copy constructor
     * @param[in] a  Reference to Tree_Terminal_Node.
     */
    Tree_Terminal_Node(const Tree_Terminal_Node & a) : p_previous(a.p_previous), p_next(a.p_next)
    {}

    /**
     * Public members of Tree_Terminal_Node to point to the adjacent
     * elements of the tree.
     */
    Tree_Node *p_previous, *p_next;
        };




private:

  Tree_Node *_root_node; // Pointer to the root node always exists.
                                // However the root node must be allocated
                                // when the first node is added to the tree

        Tree_Node *_start_node; // Pointer to indicate the node before the first
                                                        // node of the tree.

        Tree_Node *_end_node;   // Pointer to indicate the node after the last
                                                        // node of the tree.

  size_t _number_of_nodes;    // The number of nodes in the tree

public:

    //------------------------------------------------------------------
    //    Begin define the iterator class here
    //    This is the base iterator class. Other iterators are derived
    //    from this.
    //------------------------------------------------------------------
  class Iterator {
  public:
    Tree_Node * current; // pointer to current node
    typedef std::bidirectional_iterator_tag iterator_category;

    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    Tree_Terminal_Node start;   // The node before the begin() iterator
    Tree_Terminal_Node end;     // The node at the end() iterator
    bool at_start, at_end;      // Flags to indicate if the iterator is at the
                                // start or end nodes respectively.

   /**
    * Default constructor
    * @param[in] init  Pointer to node.
    */
    Iterator(Tree_Node* init = 0);

   /**
    * Copy constructor
    * @param[in] a  Reference to the base iterator.
    */
    Iterator(const Iterator& a);

   /**
    * Template type constructor
    * @param[in] a  Reference to the template type.
    */
    Iterator(T & a);
     /**
    * Destructor
    */
    virtual ~Iterator() {};

   /**
    * Dereferencing data: allows access to data with the *iterator statement
    * @return Reference to node data type
    */
    T& operator*() const;

   /**
    * Returns the address of data: Allows calling public member functions of
    * data with the iterator->data_public_function() call
    * @return Pointer to node data type
    */
    T*  operator->() const;

   /**
    * Equals operator: sets the current position of an iterator to the
    * current position of another iterator.
    * @param[in] x  Reference to base iterator.
    * @return Reference to base iterator class.
    */
    template <typename Iterator_Type>
      Iterator& operator=(const Iterator_Type & x);

   /**
    * Set_Current function: sets the current position of this iterator to
    * the position new_current. This always returns true. This prototype is
    * used because it is overridden for the chain iterator where a check that
    * new_current is on the chain (see below) is performed.
    * @param[in] new_current  Pointer to node.
    * @return Always returns true.
    */
    bool set_current(Tree_Node * new_current);

   /**
    * == operator: Tests for equality between two iterators
                * NOTE: This only checks if the current nodes match to allow
                * comparison between different types of iterators.
    * @param[in] x  Reference to base iterator.
    * @return Result of test
    */
    bool operator==(const Iterator& x) const;

   /**
    * != operator: Tests for inequality between two iterators
                * NOTE: This only checks if the current nodes do not match to allow
                * comparison between different types of iterators.
    * @param[in] x  Reference to base iterator type.
    * @return       Result of test.
    */
    bool operator!=(const Iterator& x) const;

   /**
    * < operator: Tests for this less than rhs
    * @param[in] x  Unsigned int to specify the decrement.
    * @return       True if less than, false otherwise.
    */
    template <typename Iterator_Type>
      bool operator<(const Iterator_Type& x) const;

   /**
    * > operator: Tests for this greater than rhs
    * @param[in] x  Unsigned int to specify the decrement.
    * @return       True if greater than, false otherwise.
    */
    template <typename Iterator_Type>
      bool operator>(const Iterator_Type& x) const;
   /**
    * <= operator: Tests for this less than or equal to rhs
    * @param[in] x  Unsigned int to specify the decrement
    * @return       True if less than or equal to, false otherwise
    */
    template <typename Iterator_Type>
      bool operator<=(const Iterator_Type& x) const;

   /**
    * >= operator: Tests for this greater than or equal to rhs
    * @param[in] x   Unsigned int to specify the decrement
    * @return        True if greater than or equal to, false otherwise
    */
    template <typename Iterator_Type>
      bool operator>=(const Iterator_Type& x) const;

   /**
    * Determines the number of children the node at the current position has.
    * @return unsigned int number of children
    */
    unsigned int get_number_of_children() const;      
    /**
     * Return the iterator that points to the first child of this iterator's
     * node
     * @return Base or derived iterator 
     */
    Iterator get_first_child() const;
    
    /**
    * Tests if the node pointed to by the arg. iterator is a child
    * of this iterator.
    * @param[in] a  Reference to base iterator.
    * @return       Result of test.
    */
    bool is_child(const Iterator& a) const;

   /**
    * Tests if the node pointed to by the arg. iterator is a parent
    * of this iterator.
    * @param[in] a  Reference to base iterator.
    * @result       Result of test.
    */
    bool is_parent(const Iterator& a) const;

   /**
    * Tests if the node pointed to by the arg. iterator is a sibling
    * of this iterator. If the same node, return false.
    * @param[in] a  Reference to base iterator.
    * @result       Result of test.
    */
    bool is_sibling(const Iterator& a) const;

   /**
    * Tests if the node pointed to by the arg. iterator is a descendent
    * of this iterator.
    * @param[in] a  Reference to base iterator.
    * @result       Result of test
    */
    bool is_descendent(const Iterator& a) const;

   /**
    * Tests if the node pointed to by the arg. iterator is an ancestor
    * of this iterator.
    * @result bool result of test
    */
    bool is_ancestor(const Iterator& a) const;

    virtual int get_index_position() const {return 0;}

  private:
    virtual void _initialize() {};

  };

  //------------------------------------------------------------------
  //  Begin define the Sibling_Iterator class here
  //  This is derived from the base iterator class.
  //------------------------------------------------------------------
  class Sibling_Iterator : public Iterator {
  public:
   /**
    * Default constructor
    * @param[in] init  Pointer to node.
    */
    Sibling_Iterator(Tree_Node * init = 0);


         /**
    * Copy constructor
    * @param[in] a  Reference to base or derived iterator classes.
    */
    template <typename Iterator_Type>
      Sibling_Iterator(const Iterator_Type& a);

   /**
    * Template type constructor
    * @param[in] a  Reference to the template type.
    */
    Sibling_Iterator(T & a);

   /**
    * pre-fix increment operator
    * @return Reference to sibling iterator
    */
    Sibling_Iterator& operator++();

   /**
    * pre-fix decrement operator
    * @return Reference to sibling iterator
    */
    Sibling_Iterator& operator--();

   /**
    * post-fix increment operator
    * @return Sibling iterator
    */
    Sibling_Iterator operator++(int);
    
   /**
    * post-fix decrement operator
    * @return Sibling iterator
    */
    Sibling_Iterator operator--(int);

   /**
    * increment by specified value operator
    * @param[in] a   Unsigned int to specify the increment
    * @return Reference to sibling iterator
    */
    Sibling_Iterator& operator+=(unsigned int a);

   /**
    * decrement by specified value operator
    * @param[in] a   Unsigned int to specify the decrement
    * @return Reference to sibling iterator
    */
    Sibling_Iterator& operator-=(unsigned int a);

   /**
    * Zero-referenced index from begin.
    */
    int get_index_position() const;

  private:
    /**
     * Initialize sibling iterator parameters
     */
    void _initialize();
    
  };


  //------------------------------------------------------------------
  //  Begin define the Pre_Order_Iterator class here
  //  This is derived from the base iterator class.
  //------------------------------------------------------------------
  class Pre_Order_Iterator : public Iterator {
  public:
   /**
    * Default constructor
    */
    Pre_Order_Iterator(Tree_Node * init = 0);

   /**
    * Copy constructor
    * @param[in] a  Reference to base or derived iterator classes.
    */
    template <typename Iterator_Type>
      Pre_Order_Iterator(const Iterator_Type& a);

   /**
    * Template type constructor
    * @param[in] a  Reference to the template type.
    */
    Pre_Order_Iterator(T & a);

   /**
    * pre-fix increment operator
    * @return Reference to pre-order iterator
    */
    Pre_Order_Iterator& operator++();
    
   /**
    * pre-fix decrement operator
    * @return Reference to pre-order iterator
    */
    Pre_Order_Iterator& operator--();

   /**
    * post-fix increment operator
    * @return Pre-order iterator
    */
    Pre_Order_Iterator operator++(int);
    
   /**
    * post-fix decrement operator
    * @return Pre-order iterator
    */
    Pre_Order_Iterator operator--(int);

   /**
    * increment by specified value operator
    * @param[in] a   Unsigned int to specify the increment
    * @return Reference to pre-order iterator
    */
    Pre_Order_Iterator& operator+=(unsigned int a);

   /**
    * decrement by specified value operator
    * @param[in] a   Unsigned into to specify the decrement
    * @return Reference to pre-order iterator
    */
    Pre_Order_Iterator& operator-=(unsigned int a);

    int get_index_position() const;

    void _initialize() {}               // No need to do anything here.
  };

  //------------------------------------------------------------------
  //  Begin define the Post_Order_Iterator class here
  //  This is derived from the base iterator class.
  //------------------------------------------------------------------
  class Post_Order_Iterator : public Iterator {
  public:
   /**
    * Default constructor
    * @param[in] init  Pointer to tree node.
    */
    Post_Order_Iterator(Tree_Node * init = 0);

   /**
    * Copy constructor
    * @param[in] a  Reference to base or derived iterator classes.
    */
    template <typename Iterator_Type>
      Post_Order_Iterator(const Iterator_Type& a);

   /**
    * Template type constructor
    * @param[in] a  Reference to the template type.
    */
    Post_Order_Iterator(T & a);

   /**
    * pre-fix increment operator
    * @return Reference to post-order iterator
    */
    Post_Order_Iterator& operator++();
   /**
    * pre-fix decrement operator
    * @return Reference to post-order iterator
    */
    Post_Order_Iterator& operator--();

   /**
    * post-fix increment operator
    * @return Post-order iterator
    */
    Post_Order_Iterator operator++(int);
    
   /**
    * post-fix decrement operator
    * @return Post-order iterator
    */
    Post_Order_Iterator operator--(int);

   /**
    * increment by specified value operator
    * @param[in] a   Unsigned int to specify the increment
    * @return Reference to post-order iterator
    */
    Post_Order_Iterator& operator+=(unsigned int a);

   /**
    * decrement by specified value operator
    * @param[in] a   Unsigned int to specify the decrement
    * @return Reference to post-order iterator
    */
    Post_Order_Iterator& operator-=(unsigned int a);


   /**
    * Zero-referenced index from begin.
    */
    int get_index_position() const;
  };

  //------------------------------------------------------------------
  //  Begin define the Chain_Iterator class here
  //  This is derived from the base iterator class.
  //------------------------------------------------------------------
  class Chain_Iterator : public Iterator {
  public:
   /**
    * Constructor
    * @param[in] begin_chain  Pointer to node that specifies the beginning of
    *                         the chain
    * @param[in] end_chain    Pointer to node that specifies the end of the
    *                         chain
    */
    Chain_Iterator( Tree_Node* begin_chain, Tree_Node* end_chain);

   /**
    * Constructor
    * @param[in] begin_chain  Pointer to node that specifies the beginning of
    *                         the chain
    * @param[in] end_chain    Pointer to node that specifies the end of the
    *                         chain
    */
    Chain_Iterator( Iterator begin_chain, Iterator end_chain);

   /**
    * Copy constructor
    */
    Chain_Iterator(const Chain_Iterator & a);

   /**
    * Destructor
    */
    ~Chain_Iterator();

   /**
    * Equals operator: sets the current position of a non-chain iterator to the
    * current position of this iterator if the arg. iterator's current node is
    * on the chain
    * @param[in] x  Reference to base iterator.
    * @return       Reference to base iterator class
    */
    template <typename Iterator_Type>
      Chain_Iterator &  operator=(const Iterator_Type & x);


   /**
    * Equals operator: sets the variables of the arg chain iterator to the
    * this chain iterator. The built-in equals operator does the same thing.
    * This is provided in case the class is extended in the future
    * to have allocated variables.
    * @param[in] x  Reference to base iterator.
    * @return       Reference to base iterator class
    */
    Chain_Iterator &  operator=(const Chain_Iterator & x);

   /**
    * Return beginning node of chain
    * @return Pointer to node
    */
    Tree_Node * get_first_node();

   /**
    * Return the ending node of the chain
    * @return Pointer to node
    */
    Tree_Node * get_last_node();

   /**
    * Set Chain_Iterator to begin node of chain
    */
    void set_begin();

   /**
    * Set Chain_Iterator to past end node of chain
    */
    void set_end();
   /**
    * pre-fix increment operator
    * @return Reference to chain iterator
    */
    Chain_Iterator& operator++();

   /**
    * pre-fix decrement operator
    * @return Reference to chain iterator
    */
    Chain_Iterator& operator--();

   /**
    * post-fix increment operator
    * @return Chain iterator
    */
    Chain_Iterator operator++(int);
    
   /**
    * post-fix decrement operator
    * @return Chain iterator
    */
    Chain_Iterator operator--(int);


   /**
    * increment by specified value operator
    * @param[in] a   Unsigned int to specify the increment
    * @return Reference to chain iterator
    */
    Chain_Iterator& operator+=(unsigned int a);

    /**
    * decrement by specified value operator
    * @param[in] a   Unsigned int to specify the decrement
    * @return Reference to chain iterator
    */
    Chain_Iterator& operator-=(unsigned int a);

   /**
    * Set current node, Check that the new current node is in the chain
    * @param[in] new_current  Pointer to specify the new node to point to.
    * @return                 Tree if successful, false if failed
    */
    bool set_current(Tree_Node * new_current);


   /**
    * Check if a node is on the chain of this chain iterator
    * @param[in] a  Pointer to node to test for.
    * @return       True if on chain, false if not on chain
    */
    bool on_chain(const Tree_Node * a) const;

    int get_index_position() const;

    void _initialize() {}

  };

  //------------------------------------------------------------------
  //  Define Tree functions here.
  //------------------------------------------------------------------

 /**
  * Default constructor
  */
  Tree();

 /**
  * Copy constructor
  * @param[in] a  Reference to another tree.
  */
  Tree(const Tree<T>& a);

 /**
  * Destructor
  */
  ~Tree();

 /**
  * initialize the start_node and end_node
        */
        void _initialize_tree();

 /**
  * get the number of the nodes on the tree
  * @return unsigned int number of nodes
  */
  unsigned int size();

 /**
  * Determine if tree is empty
  * @return bool true if tree is empty
  */
  bool empty();

 /**
  * Check if the current node of an iterator is on the tree
  * @param[in] d_iterator  Reference to base or derived iterator classes.
  * @return                True if on tree, false if not on tree
  */
  template <typename Iterator_Type> 
    bool on_tree(const Iterator_Type & d_iterator);


 /**
  * Clear the tree of nodes
  */
  void clear_tree();

 /**
  * Delete the node and all its descendents pointed to by the iterator
  * @param[in] a  Reference to base or derived iterator class.
  */
  template <typename Iterator_Type> 
    void delete_descendents(const Iterator_Type& a);

 /**
  * Delete this iterator's node only if it is valid, has no children and
  * is on this tree
  * @param[in] d_iter  Reference to base or derived iterator classes.
  */
  template <typename Iterator_Type> 
    void delete_node(const Iterator_Type d_iter);

 /**
  * Copy a specified tree into this tree
  * @param[in] a  Reference to a tree.
  */
  bool copy(const Tree<T>& a);

 /**
  * Copy the node and its descendents onto this tree at the specified node
  * @param[in] dest_itr  Reference to base or derived iterator classes to
  *                       copy to
  * @param[in] src_itr   Reference to base or derived iterator classes to
  *                      copy from
  */
  template <typename Iterator_Type1, typename Iterator_Type2> 
    bool copy_descendents(
    Iterator_Type1 dest_itr, Iterator_Type2 src_itr);

 /**
  * tree equal operator
  * @param[in] a  Reference to the tree to copy from.
  */
  Tree<T> &  operator=(const Tree<T> & a);

  template <typename Iterator_Type> 
  bool has_parent(const Iterator_Type& child) const;

 /**
  * Return the iterator that points to the parent of this iterator's node
  * @param[in] child  Reference to base or derived iterator classes.
  * @return           Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type
    get_parent(const Iterator_Type& child) const;
   
 /**
  * Return the iterator that points to the first child of this iterator's node
  * @param[in] child  Reference to base or derived iterator classes.
  * @return           Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type
    get_first_child(const Iterator_Type& child) const;

 /**
  * Return the iterator that points to the last child of this iterator's node
  * @param[in] child  Reference to base or derived iterator classes.
  * @return           Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type
    get_last_child(const Iterator_Type& child) const;
  
 /**
  * Return the iterator that points to the previous sibling of this
  * iterator's node
  * @param[in] child  Reference to base or derived iterator classes.
  * @return           Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type
    get_previous_sibling(const Iterator_Type& child) const;
  
 /**
  * Return the iterator that points to the next sibling of this iterator's node
  * @param[in] child  Reference to base or derived iterator classes.
  * @return           Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type
    get_next_sibling(const Iterator_Type& child) const;


 /**
  * Append the data as a new child of the parent node. Note that a new
  * copy of the node data type is made
  * @param[in] parent      Reference to base or derived iterator classes.
  * @param[in] child_data  Reference to node data type to be appended
  * @return                Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type append_child(
    Iterator_Type parent, T * child_data);

 /**
  * Insert the new node data at the specified location and displace the
  * specified location to be the next sibling. Note that a new
  * copy of the node data type is made.
  * @param[in] location      Reference to base or derived iterator classes
  * @param[in] element_data  Reference to node data type to be inserted
  * @return                  Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type insert(
    Iterator_Type location, T * element_data);


 /**
  * Insert the new node data after the specified location and displace the
  * specified location to be the previous sibling. Note that a new
  * copy of the node data type is made.
  * @param[in] location      Reference to base or derived iterator classes
  * @param[in] element_data  Reference to node data type to be inserted
  * @return                  Base or derived iterator 
  */
  template <typename Iterator_Type> Iterator_Type insert_after(
    Iterator_Type location, T * element_data);


 /**
  * Returns the depth of the node in the tree
  * @param[in] a  Reference to base or derived iterator classes.
  * @return       Depth; -1 if error; root node depth = 0
  */
  template <typename Iterator_Type> 
    int get_depth(const Iterator_Type& a);

 /**
  * Tests if the iterator is pointing at the root node
  * @param[in] a  Reference to base or derived iterator classes.
  * @return       True if is the root, false if not the root
  */
  template <typename Iterator_Type> bool is_root(const Iterator_Type& a) const;
 
 /**
  * Return a sibling iterator that points to the beginning of the siblings
  * @param[in] a  Reference to base or derived iterator classes.
  * @return       Sibling iterator
  */
  template <typename Iterator_Type> Sibling_Iterator
    begin_sibling(const Iterator_Type & a);
  
 /**
  * Return a pre-order iterator that points to the beginning of the pre-ordered
  * tree
  * @return Pre-order iterator
  */
  Pre_Order_Iterator begin_pre_order() const;

 /**
  * Return a post-order iterator that points to the beginning of the
  * post-ordered tree
  * @return Post-order iterator
  */
  Post_Order_Iterator begin_post_order() const;

 /**
  * Return a new chain iterator that points to the beginning of the chain
  * @param[in] a  Reference to a chain iterator.
  * @return       Chain iterator
  */
  Chain_Iterator begin_chain(Chain_Iterator & a) const;
  
 /**
  * Return a sibling iterator that points to the end (1 beyond the last)
  * sibling
  * @param[in] a  Reference to base or derived iterator classes.
  * @return       Sibling iterator
  */
  template <typename Iterator_Type>  Sibling_Iterator
    end_sibling(const Iterator_Type & a);
  
 /**
  * Return a pre-order iterator that points to the end of the pre-ordered tree
  * @return Pre-order iterator
  */
  Pre_Order_Iterator end_pre_order() const;
  
 /**
  * Return a post_order_iterator that points to the end of the post-ordered
  * tree
  * @return Post-order iterator
  */
  Post_Order_Iterator end_post_order() const;
   
 /**
  * Return a chain iterator that points to the end of this chain
  * @return Chain iterator
  */
  Chain_Iterator end_chain(Chain_Iterator & a) const;

};


/**************************************************************************/
/**************************************************************************/
/*                           TREE_NODE functions                          */
/**************************************************************************/
/**************************************************************************/
//------------------------------------------------------------------------
/**
 * Constructor: Add a new child to parent node specified in arg. This also
 * serves as a copy constructor when the parent arg. is not included.
 * @param[in] new_child  Reference to tree node data type.
 * @param[in] parent     Pointer to the parent node.
 */
template <class T>
inline Tree<T>::Tree_Node::Tree_Node(T * new_child, Tree_Node* parent)
    : data(0)
{
  if (new_child)                        // if new_child is valid, assign data to it
  {                                             // if new_child is not valid, data remains NULL
    data = new_child;

  }

  if (parent) // if parent is valid
  {
    p_parent = parent;    // set parent pointer to parent
    if (p_parent->p_last_child) // if parent already has a child, 
    {                            // add a new last sibling

      p_previous_sibling = p_parent->p_last_child;
      p_previous_sibling->p_next_sibling = this;
      p_parent->p_last_child = this;
    }
    else // otherwise add a new first/last child
    {
      p_parent->p_first_child = this;
      p_previous_sibling = 0;
      p_next_sibling = 0;
      p_parent->p_last_child = this;
    }
    p_parent->p_last_child = this;
  }
  else    // if parent is not valid, this is the first node so give it
          // root node properties
  {
    p_parent = 0;    // the root node does not have a parent nor siblings
    p_previous_sibling = 0;
  }

  // The new node doesn't have any children
  p_first_child = 0;
  p_last_child = 0;

  // The new node doesn't have a next sibling
  p_next_sibling = 0;
}

//------------------------------------------------------------------------
/**
 * Default constructor
 */
template <class T>
inline Tree<T>::Tree_Node::Tree_Node() : data(0)                // Data is NULL
{
  p_parent = 0;                // no parent specified so create a node
  p_previous_sibling = 0;        // that does't have any attachment to other
  p_next_sibling = 0;            // nodes
  p_first_child = 0;
  p_last_child = 0;
}

//------------------------------------------------------------------------
/**
 * Destructor: Note that as in std::vector, the elements are allocated
 * outside tree but destroyed within it when the tree is cleared.
 */
template <class T>
inline Tree<T>::Tree_Node::~Tree_Node()
{
  if (data != 0)
  {
    delete data;    // Clear the allocated memory

  }
}

//------------------------------------------------------------------------
/**
 * Equals operator: sets the data of a Tree_Node to the
 * data of another Tree_Node.
 * @param[in] x  Reference to Tree_Node.
 * @return       Reference to Tree_Node
 */
template <class T>
inline typename Tree<T>::Tree_Node & Tree<T>::Tree_Node::operator=(const Tree_Node & x)
{
  if (data)
    delete data;

  data = new T(x.data);

  return *this;
}

/**************************************************************************/
/**************************************************************************/
/*                           Iterator functions                           */
/*                                                                        */
/* This is the base iterator class. Other iterators are derived from this.*/
/**************************************************************************/
/**************************************************************************/
//------------------------------------------------------------------------
/**
 * Default constructor
 * @param[in] init  Pointer to node.
 */
template <class T>
inline Tree<T>::Iterator::Iterator(Tree_Node* init)
{
  current = init;
  end.p_previous = 0;
  start.p_next = 0;
  at_start = false;
  at_end = false;
}

//------------------------------------------------------------------------
/**
 * Copy constructor
 * @param[in] a  Reference to the base iterator.
 */
template <class T>
inline Tree<T>::Iterator::Iterator(const Iterator& a)
  : current(a.current), 
    start (a.start), 
    end   (a.end),
    at_start (a.at_start), 
    at_end   (a.at_end)
{
}

//------------------------------------------------------------------------
/**
 * Template type constructor
 * @param[in] a  Reference to the template type.
 */
template <class T>
inline Tree<T>::Iterator::Iterator(T & a)
{
  current->data = &a;
  end.p_previous = 0;
  start.p_next = 0;
  at_start = false;
  at_end = false;
}

//------------------------------------------------------------------------
/**
 * Destructor
 */
//template <class T>
//virtual inline Tree<T>::Iterator::~Iterator()
//{
//}

//------------------------------------------------------------------------
/**
 * Dereferencing data: allows access to data with the *iterator statement
 * @return Reference to node data type
 */
template <class T>
inline T&  Tree<T>::Iterator::operator*() const
{
  return *(current->data);  // Possible problem here if current is not valid
}

//------------------------------------------------------------------------
/**
 * Returns the address of data: Allows calling public member functions of
 * data with the iterator->data_public_function() call
 * @return Pointer to node data type
 */
template <class T>
inline T*  Tree<T>::Iterator::operator->() const
{
  return current->data;  // Possible problem here if current is not valid
}

//------------------------------------------------------------------------
/**
 * Equals operator: sets the current position of an iterator to the
 * current position of another iterator.
 * @param[in] x  Reference to base iterator.
 * @return       Reference to base iterator class.
 */
template <class T>
template <typename Iterator_Type>
inline typename Tree<T>::Iterator&  Tree<T>::Iterator::operator=(const Iterator_Type & x)
{
  current = x.current;
  end.p_previous = x.end.p_previous;
  start.p_next = x.start.p_next;
  at_start = x.at_start;
  at_end = x.at_end;
  return *this;
}

//------------------------------------------------------------------------
/**
 * Set_Current function: sets the current position of this iterator to
 * the position new_current. This always returns true. This prototype is
 * used because it is overridden for the chain iterator where a check that
 * new_current is on the chain (see below) is performed.
 * @param[in] new_current  Pointer to node.
 * @return                 Always true.
 */
template <class T>
inline bool  Tree<T>::Iterator::set_current(Tree_Node * new_current)
{
  current = new_current;
  at_end = false;
  at_start = false;
  
  return true;
}

//------------------------------------------------------------------------
/**
 * == operator: Tests for equality between two iterators
 * NOTE: This only checks if the current nodes match to allow
 * comparison between different types of iterators.
 * @param[in] x  Reference to base iterator.
 * @return       Result of test 
 */
template <class T>
inline bool  Tree<T>::Iterator::operator==(const Iterator& x) const
{
  return (current == x.current);
}

//------------------------------------------------------------------------
/**
 * != operator: Tests for inequality between two iterators
 * NOTE: This only checks if the current nodes do not match to allow
 * comparison between different types of iterators.
 * @param[in] x  Reference to base iterator type.
 * @reture       Result of test
 */
template <class T>
inline bool  Tree<T>::Iterator::operator!=(const Iterator& x) const
{
  return (current != x.current);
}

//------------------------------------------------------------------------
/**
 * < operator: Tests for this less than rhs
 * @param[in] x   Unsigned int to specify the decrement
 * @return        True if less than, false otherwise
 */
template <class T>
template <typename Iterator_Type>
inline bool  Tree<T>::Iterator::operator<(const Iterator_Type& x) const
{
  return (this->get_index_position() < x.get_index_position());
}

//------------------------------------------------------------------------
/**
 * > operator: Tests for this greater than rhs
 * @param[in] x   Unsigned int to specify the decrement
 * @return        True if greater than, false otherwise
 */
template <class T>
template <typename Iterator_Type>
inline bool  Tree<T>::Iterator::operator>(const Iterator_Type& x) const
{
  return (this->get_index_position() > x.get_index_position());
}

//------------------------------------------------------------------------
/**
 * <= operator: Tests for this less than or equal to rhs
 * @param[in] x   Unsigned int to specify the decrement
 * @return        True if less than or equal to, false otherwise
 */
template <class T>
template <typename Iterator_Type>
inline bool  Tree<T>::Iterator::operator<=(const Iterator_Type& x) const
{
  return (this->get_index_position() <= x.get_index_position());
}

//------------------------------------------------------------------------
/**
 * >= operator: Tests for this greater than or equal to rhs
 * @param[in] x   Unsigned int to specify the decrement
 * @return        True if greater than or equal to, false otherwise
 */
template <class T>
template <typename Iterator_Type>
inline bool  Tree<T>::Iterator::operator>=(const Iterator_Type& x) const
{
  return (this->get_index_position() >= x.get_index_position());
}

//------------------------------------------------------------------------
/**
 * Determines the number of children the node at the current position has.
 * @return unsigned int number of children
 */
template <class T>
inline unsigned int  Tree<T>::Iterator::get_number_of_children() const      // return the number of children of current 
{
  Tree_Node *first = current->p_first_child;
  
  if (first == 0)
  {
    return 0;
  }
  
  unsigned int ret=1;
  
  while ((first = first->p_next_sibling))  // p_next_sibling = 0 for last sibling
    ++ret;  
  
  return ret;
}

//------------------------------------------------------------------------
/**
 * Return the iterator that points to the first child of this iterator's node
 * @return Base or derived iterator 
 */
template <class T>
inline typename Tree<T>::Iterator Tree<T>::Iterator::get_first_child() const
{
  // NOTE: Potential problem here if current points to an invalid node
  return Iterator(current->p_first_child);
}

//------------------------------------------------------------------------
/**
 * Tests if the node pointed to by the arg. iterator is a child
 * of this iterator.
 * @param[in] a  Reference to base iterator.
 * @return       Result of test.
 */
template <class T>
inline bool Tree<T>::Iterator::is_child(const Iterator& a) const
{
  if (!current)
  {
    return false;
  }
  return (current->p_parent == a.current);
}

//------------------------------------------------------------------------
/**
 * Tests if the node pointed to by the arg. iterator is a parent
 * of this iterator.
 * @param[in] a  Reference to base iterator.
 * @result       Result of test
 */
template <class T>
inline bool Tree<T>::Iterator::is_parent(const Iterator& a) const
{
  if (!a.current)
  {
    return false;
  }
  return (a.current->p_parent == current);
}

//------------------------------------------------------------------------
/**
 * Tests if the node pointed to by the arg. iterator is a sibling
 * of this iterator. If the same node, return false.
 * @param[in] a  Reference to base iterator.
 * @result       Result of test
 */
template <class T>
inline bool Tree<T>::Iterator::is_sibling(const Iterator& a) const
{
  if (!current)
  {
    return false;
  }
  if (current->p_parent == 0)  // The root node does not have siblings
  {
    return false;
  }
  if (*this == a)
  {
    return false;  // A node cannot be its own sibling
    // Using operator== overloaded function 
  }
  
  Tree_Node *first = current->p_parent->p_first_child;
  
  do
  {
    if (first == a.current)
    {
      return true;
    }
    first = first->p_next_sibling;
  } while (first);
  
  return false;
}

//------------------------------------------------------------------------
/**
 * Tests if the node pointed to by the arg. iterator is a descendent
 * of this iterator.
 * @param[in] a  Reference to base iterator.
 * @result       Result of test
 */
template <class T>
inline bool Tree<T>::Iterator::is_descendent(const Iterator& a) const
{
  if (!current)
  {
    return false;
  }
  Iterator tmp(current);
  while (tmp.current)
  {
    tmp.current = tmp.current->p_parent;
    if (tmp == a)    // Using operator== overloaded function 
    {
      return true;
    }
    
  }
  return false;
}

//------------------------------------------------------------------------
/**
 * Tests if the node pointed to by the arg. iterator is an ancestor
 * of this iterator.
 * @result bool result of test
 */
template <class T>
inline bool Tree<T>::Iterator::is_ancestor(const Iterator& a) const
{
  if (!current)
  {
    return false;
  }
  return a.is_descendent(*this);
}



/**************************************************************************/
/**************************************************************************/
/*                           Sibling Iterator functions                   */
/**************************************************************************/
/**************************************************************************/
//------------------------------------------------------------------------
/**
 * Default constructor
 * @param[in] init  Pointer to node.
 */
template <class T>
inline Tree<T>::Sibling_Iterator::Sibling_Iterator(Tree_Node * init)
  : Iterator(init)
{
  _initialize();
}


//------------------------------------------------------------------------
/**
 * Copy constructor
 * @param[in] a  Reference to base or derived iterator classes.
 */
template <class T>
template <typename Iterator_Type>
inline Tree<T>::Sibling_Iterator::Sibling_Iterator(const Iterator_Type& a)  
: Iterator(a)
{
  _initialize();
}

//------------------------------------------------------------------------
/**
 * Template type constructor
 */
template <class T>
inline Tree<T>::Sibling_Iterator::Sibling_Iterator(T & a) : Iterator(a)
{
  _initialize();
}

//------------------------------------------------------------------------
/**
 * pre-fix increment operator
 * @return Reference to sibling iterator
 */
template <class T>
inline typename Tree<T>::Sibling_Iterator& Tree<T>::Sibling_Iterator::operator++()
{
  if (this->current == 0)  // do nothing if this is not a valid node
  {
    return *this;
  }
  if (this->at_start)
  {
    this->current = this->start.p_next;
    this->at_start = false;
  }
  else
  {
    if (this->current->p_next_sibling != 0)
                {
      this->current = this->current->p_next_sibling;
                }
                else
      this->at_end = true;
  }
  
  return *this;  // return the next sibling
}

//------------------------------------------------------------------------
/**
 * pre-fix decrement operator
 * @return Reference to sibling iterator
 */
template <class T>
inline typename Tree<T>::Sibling_Iterator& Tree<T>::Sibling_Iterator::operator--()
{
  if (this->current == 0)  // do nothing if this is not a valid node
  {
    return * this;
  }
  if (this->at_end)
  {
    this->current = this->end.p_previous;
    this->at_end = false;
  }
  else
  {
    if (this->current->p_previous_sibling != 0)
                {
      this->current = this->current->p_previous_sibling;
                }
                else
      this->at_start = true;
  }
  
  return *this;  // return the previous sibling
}

//------------------------------------------------------------------------
/**
 * post-fix increment operator
 * @param[in] Dummy int parameter to provide a unique prototype for the
 *            function
 * @return    Sibling iterator
 */
template <class T>      // post-fix increment
inline typename Tree<T>::Sibling_Iterator Tree<T>::Sibling_Iterator::operator++(int)  
{
  Sibling_Iterator temp = *this;
  ++(*this);
  return temp;
}

//------------------------------------------------------------------------
/**
 * post-fix decrement operator
 * @param[in] Dummy int param to provide a unique prototype for the function
 * @return    Sibling iterator
 */
template <class T>  // post-fix decrement
inline typename Tree<T>::Sibling_Iterator Tree<T>::Sibling_Iterator::operator--(int)  
{
  Sibling_Iterator temp = *this;
  --(*this);
  return temp;
}

//------------------------------------------------------------------------
/**
 * increment by specified value operator
 * @param[in] x   Unsigned int to specify the increment
 * @return Reference to sibling iterator
 */
template <class T>
inline typename Tree<T>::Sibling_Iterator& Tree<T>::Sibling_Iterator::operator+=(unsigned int a)
{
  while (a > 0)
  {
    ++(*this);
    if (this->current == 0)
    {
      break;
    }
    --a;
  }
  return *this;
}

//------------------------------------------------------------------------
/**
 * decrement by specified value operator
 * @param[in] x   Unsigned int to specify the decrement
 * @return Reference to sibling iterator
 */
template <class T>
inline typename Tree<T>::Sibling_Iterator& Tree<T>::Sibling_Iterator::operator-=(unsigned int a)
{
  while (a > 0)
  {
    --(*this);
    if (this->current == 0)
    {
      break;
    }
    --a;
  }
  return *this;
}

//------------------------------------------------------------------------
/**
 * Zero-referenced index from begin.
 */
template <class T>
inline int Tree<T>::Sibling_Iterator::get_index_position() const
{
  int index = -1;
  Sibling_Iterator temp_itr(*this);
  if (this->at_start)
    return index;
  
  while (!temp_itr.at_start)
  {
    --temp_itr;
    ++index;
  }
  return index;
}

//------------------------------------------------------------------------
/**
 * Initialize sibling iterator parameters
 */
template <class T>
inline void Tree<T>::Sibling_Iterator::_initialize()
{
  if (this->current != 0)
  {
    Tree_Node * start_current = this->current;
    
    // Move to start of sibling chain
    while (this->current->p_previous_sibling != 0)
    {
      this->current = this->current->p_previous_sibling;
    }
    this->start.p_next = this->current; // Set the start.p_next ptr to pointer
    // to the first element in the chain
    
    // Reset and move to end of sibling chain
    this->current = start_current;
    while (this->current->p_next_sibling != 0)
    {
      this->current = this->current->p_next_sibling;
    }
    
    this->end.p_previous = this->current; // Set the end.p_previous ptr to pointe
    // to the last element in the chain
    
    this->current = start_current;      // Reset the current pointer
    // to its original location
  }
}

/**************************************************************************/
/**************************************************************************/
/*                         Pre-Order Iterator functions                   */
/**************************************************************************/
/**************************************************************************/
//------------------------------------------------------------------------
/**
 * Default constructor
 */
template <class T>
inline Tree<T>::Pre_Order_Iterator::Pre_Order_Iterator(Tree_Node * init)
: Iterator(init)
{
}

//------------------------------------------------------------------------
/**
 * Copy constructor
 * @param[in] a  Reference to base or derived iterator classes.
 */
template <class T>
template <typename Iterator_Type>
inline Tree<T>::Pre_Order_Iterator::Pre_Order_Iterator(const Iterator_Type& a) : Iterator(a)
{
}

//------------------------------------------------------------------------
/**
 * Template type constructor
 * @param[in] a  Reference to the template type.
 */
template <class T>
inline Tree<T>::Pre_Order_Iterator::Pre_Order_Iterator(T & a) : Iterator(a)
{
}

//------------------------------------------------------------------------
/**
  * pre-fix increment operator
 * @return Reference to pre-order iterator
 */
template <class T>
inline typename    //pre-fix increment
Tree<T>::Pre_Order_Iterator& Tree<T>::Pre_Order_Iterator::operator++()  
{
  if (this->current == 0)  // do nothing if this is not a valid node
  {
    return *this;  
  }
  Tree_Node * tmp_current = this->current;
  if (this->current->p_first_child != 0)  // if this node has a child, point to it
  {
    this->current = this->current->p_first_child;
  }
  
  else              // if this node doesn't have a child,
  {    // while the node doesn't have siblings 
    while (this->current->p_next_sibling == 0)  
    {
      if (this->current->p_parent != 0)
      {
        this->current = this->current->p_parent;// point to the parent
      }
    }
    // the node has a sibling so point to it
    this->current = this->current->p_next_sibling;  
  }
  if (this->current->p_parent == 0)     // We're at the root node or its siblings
  {
                if (this->current->p_next_sibling == 0) // At end so set end condition pointer
    {                                                                   // and flag
      this->end.p_previous = tmp_current;
      this->at_end = true;
    }
  }
  if (this->at_start)                   // Was at start so reset flag 
                this->at_start = false; // to indicate that no longer at start
  
  return *this;       // return the new node that's pointed to.
}
    
//------------------------------------------------------------------------
/**
  * pre-fix decrement operator
 * @return Reference to pre-order iterator
 */
template <class T>
inline typename    // pre-fix decrement
Tree<T>::Pre_Order_Iterator& Tree<T>::Pre_Order_Iterator::operator--()  
{
  if (this->current == 0)  // do nothing if this is not a valid node
  {
    return *this;
  }
  
  Tree_Node * tmp_current = this->current;
  if (this->current->p_previous_sibling != 0)  // if this node has a previous sibling
  {  // go down the sibling chain to find the last child
    this->current = this->current->p_previous_sibling;  
    while (this->current->p_last_child != 0)  // 
    {
      this->current = this->current->p_last_child;
    }
  }
  else             // this node doesn't have a previous sibling
  {
    if (this->current->p_parent != 0)
      this->current = this->current->p_parent;  // point to its parent
  }
  if (this->current->p_parent == 0)     // We're at the root node or its siblings
  {
                if (this->current->p_previous_sibling == 0)     // At start so set start condition
    {                                                                           // pointer and flag
      this->start.p_next = tmp_current;
      this->at_start = true;
    }
  }
  if (this->at_end)                             // Was at end to reset flag
          this->at_end = false;         // to indicate that no longer at end
  
  return *this;       // return the new node that's pointed to.
}

//------------------------------------------------------------------------
/**
  * post-fix increment operator
 * @param[in] Dummy int parameter to provide a unique prototype for the
 *            function
 * @return    Pre-order iterator
 */
template <class T>
inline typename    // post-fix increment
Tree<T>::Pre_Order_Iterator Tree<T>::Pre_Order_Iterator::operator++(int)  
{
  Pre_Order_Iterator temp = *this;
  ++(*this);
  return temp;
}
    
//------------------------------------------------------------------------
/**
  * post-fix decrement operator
 * @param[in] Dummy int parameter to provide a unique prototype for the
 *            function
 * @return     Pre-order iterator
 */
template <class T>
inline typename    // post-fix decrement
Tree<T>::Pre_Order_Iterator Tree<T>::Pre_Order_Iterator::operator--(int)  
{
  Pre_Order_Iterator temp = *this;
  --(*this);
  return temp;
}

//------------------------------------------------------------------------
/**
  * increment by specified value operator
 * @param[in] x   Unsigned int to specify the increment
 * @return Reference to pre-order iterator
 */
template <class T>
inline typename Tree<T>::Pre_Order_Iterator&
Tree<T>::Pre_Order_Iterator::operator+=(unsigned int a)
{
  while (a > 0)
  {
    ++(*this);
    if (this->current == 0)
    {
      break;
    }
    --a;
  }
  return *this;
}

//------------------------------------------------------------------------
/**
 * decrement by specified value operator
 * @param[in] x   Unsigned into to specify the decrement
 * @return Reference to pre-order iterator
 */
template <class T>
inline typename Tree<T>::Pre_Order_Iterator&
Tree<T>::Pre_Order_Iterator::operator-=(unsigned int a)
{
  while (a > 0)
  {
    --(*this);
    if (this->current == 0)
    {
      break;
    }
    --a;
  }
  return *this;
}

template <class T>
inline int Tree<T>::Pre_Order_Iterator::get_index_position() const
{
  if ((this->current == 0) && (!this->at_end) && (!this->at_start))     // If current is invalid
    return 0;           // and not at start or end, the only possibility is that
  // we're at an un-allocated root node i.e. empty tree
  
  int index = -1;
  Pre_Order_Iterator temp_itr = *this;

  // Point a pre-order iterator at the current location
  while (!temp_itr.at_start)    
  {                                                             // decrenment the iterator and increment the index
    --temp_itr;                         // to determine the current index position.
    ++index;
  }
  return index;
}



/**************************************************************************/
/**************************************************************************/
/*                        Post-Order Iterator functions                   */
/**************************************************************************/
/**************************************************************************/
//------------------------------------------------------------------------
/**
 * Default constructor
 * @param[in] init  Pointer to tree node.
 */
template <class T>
inline Tree<T>::Post_Order_Iterator::Post_Order_Iterator(Tree_Node * init)
: Iterator(init)
{
}

//------------------------------------------------------------------------
/**
 * Copy constructor
 * @param[in] a  Reference to base or derived iterator classes.
 */
template <class T>
template <typename Iterator_Type>
inline Tree<T>::Post_Order_Iterator::Post_Order_Iterator(const Iterator_Type& a)
: Iterator(a)
{
}

//------------------------------------------------------------------------
/**
 * Template type constructor
 * @param[in] a  Reference to the template type.
 */
template <class T>
inline Tree<T>::Post_Order_Iterator::Post_Order_Iterator(T & a)
: Iterator(a)
{
}

//------------------------------------------------------------------------
/**
  * pre-fix increment operator
 * @return Reference to post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator&
Tree<T>::Post_Order_Iterator::operator++()  // pre-fix increment
{
  if (this->current == 0)  // do nothing if this is not a valid node
  {
    return *this;
  }
  
  Tree_Node * tmp_current = this->current;
  if (this->current->p_next_sibling != 0)
  {
    this->current = this->current->p_next_sibling;
    while (this->current->p_first_child != 0)
    {
      this->current = this->current->p_first_child;
    }
  }
  else
  {
    if (this->current->p_parent != 0)
      this->current = this->current->p_parent;
  }
  if (this->current->p_parent == 0)     // We're at the root node or its siblings
  {
    if (this->current->p_next_sibling == 0)
    {
      this->end.p_previous = tmp_current;// At end so set end condition pointer
      this->at_end = true;                                      // and set flag
    }
  }
  if (this->at_start)                   // Was at start to reset flag to indicate no longer
    this->at_start = false;     // at start
  return *this;
}

//------------------------------------------------------------------------
/**
  * pre-fix decrement operator
 * @return Reference to post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator&
Tree<T>::Post_Order_Iterator::operator--()  // pre-fix decrement
{
  if (this->current == 0)  // do nothing if this is not a valid node
  {
    return *this;
  }
  
  Tree_Node * tmp_current = this->current;
  if (this->current->p_last_child != 0)
  {
    this->current = this->current->p_last_child;
  }
  else
  {
    while (this->current->p_previous_sibling == 0)
    {
      this->current = this->current->p_parent;
      if (this->current == 0)
      {
        return *this;
      }
    }
    this->current = this->current->p_previous_sibling;
  }
  if (this->current->p_parent == 0)     // We're at the root node or its siblings
  {
                                if (this->current->p_previous_sibling == 0)
        {
          this->start.p_next = tmp_current;// At start so set start condition pointer
          this->at_start = true;                        // and flag
        }
  }
  if (this->at_end)
                                this->at_end = false;// Was at end to reset flag to indicate no longer at end
  
  return *this;
}

//------------------------------------------------------------------------
/**
  * post-fix increment operator
 * @param[in] Dummy int parameter to provide a unique prototype for the
 *            function
 * @return    Post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator
Tree<T>::Post_Order_Iterator::operator++(int)  // pree-fix increment
{
  Post_Order_Iterator temp = *this;
  ++(*this);
  return temp;
}
    
//------------------------------------------------------------------------
/**
  * post-fix decrement operator
 * @param[in] Dummy int parameter to provide a unique prototype for the
 *            function
 * @return    Post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator
Tree<T>::Post_Order_Iterator::operator--(int)  // pree-fix decrement
{
  Post_Order_Iterator temp = *this;
  --(*this);
  return temp;
}

//------------------------------------------------------------------------
/**
  * increment by specified value operator
 * @param[in] x   Unsigned int to specify the increment
 * @return Reference to post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator&
Tree<T>::Post_Order_Iterator::operator+=(unsigned int a)
{
  while (a > 0)
  {
    ++(*this);
    if (this->current == 0)
    {
      break;
    }
    --a;
  }
  return *this;
}

//------------------------------------------------------------------------
/**
  * decrement by specified value operator
 * @param[in] x   Unsigned int to specify the decrement
 * @return Reference to post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator&
Tree<T>::Post_Order_Iterator::operator-=(unsigned int a)
{
  while (a > 0)
  {
    --(*this);
    if (this->current == 0)
    {
      break;
    }
    --a;
  }
  return *this;
}


//------------------------------------------------------------------------
/**
 * Zero-referenced index from begin.
 * @param[in] x   Unsigned int to specify the decrement
 * @return        True if less than, false otherwise
 */
template <class T>
inline int Tree<T>::Post_Order_Iterator::get_index_position() const
{
  if ((this->current == 0) && (!this->at_end) && (!this->at_start))
    return 0;
  
  int index = -1;
  Post_Order_Iterator temp_itr = *this; // Point a post-order iterator
  // at the current location
  while (temp_itr.current->p_parent != 0
    || temp_itr.current->p_previous_sibling != 0)
  {
    --temp_itr;         // decrenment the iterator and increment the index
    ++index;                    // to determine the current index position.
  }
  return index;
}


/**************************************************************************/
/**************************************************************************/
/*                           Chain Iterator functions                     */
/**************************************************************************/
/**************************************************************************/
//------------------------------------------------------------------------
/**
 * Constructor
 * @param[in] begin_chain Pointer to node that specifies the beginning of the
 *                        chain
 * @param[in] end_chaing   Pointer to node that specifies the end of the chain
 */
template <class T>
inline  Tree<T>::Chain_Iterator::Chain_Iterator(
            Tree_Node* begin_chain, Tree_Node* end_chain) :
Iterator(begin_chain)
{
  this->start.p_next = begin_chain;
  this->end.p_previous = end_chain;
}

//------------------------------------------------------------------------
/**
 * Constructor
 * @param[in] begin_chain Pointer to node that specifies the beginning of the
 *                        chain
 * @param[in] end_chain   Pointer to node that specifies the end of the chain
 */
template <class T>
inline  Tree<T>::Chain_Iterator::Chain_Iterator(
            Iterator begin_chain, Iterator end_chain) :
Iterator(begin_chain)
{
  this->start.p_next = begin_chain.current;
  this->end.p_previous = end_chain.current;
}

//------------------------------------------------------------------------
/**
 * Copy constructor
 */
template <class T>
inline  Tree<T>::Chain_Iterator::Chain_Iterator(const Chain_Iterator & a)
: Iterator(a)
{
}

//------------------------------------------------------------------------
/**
 * Destructor
 */
template <class T>
inline  Tree<T>::Chain_Iterator::~Chain_Iterator()
{
}

//------------------------------------------------------------------------
/**
 * Equals operator: sets the current position of a non-chain iterator to the
 * current position of this iterator if the arg. iterator's current node is on
 * the chain
 * @param[in] x  Reference to base iterator
 * @return       Reference to base iterator class
 */
template <class T>
template <typename Iterator_Type>
inline typename Tree<T>::Chain_Iterator&
Tree<T>::Chain_Iterator::operator=(const Iterator_Type & x)
{
  if (on_chain(x.current))      // before setting, check that the
  {                    // x node is on the chain
    this->current = x.current;
  }
  return *this;
}


//------------------------------------------------------------------------
/**
 * Equals operator: sets the variables of the arg chain iterator to the
 * this chain iterator. The built-in equals operator does the same thing.
 * This is provided in case the class is extended in the future
 * to have allocated variables.
 * @param[in] x  Reference to base iterator.
 * @return       Reference to base iterator class
 */
template <class T>
inline typename Tree<T>::Chain_Iterator & 
Tree<T>::Chain_Iterator::operator=(const Chain_Iterator & x)
{
  this->current = x.current;
  this->start.p_next = x.start.p_next;
  this->end.p_previous = x.end.p_previous;
  this->at_start = x.at_start;
  this->at_end = x.at_end;
  
  return *this;
}

//------------------------------------------------------------------------
/**
 * Return beginning node of chain
 * @return Pointer to node
 */
template <class T>
inline typename Tree<T>::Tree_Node* Tree<T>::Chain_Iterator::get_first_node()
{
  return this->start.p_next;
}

//------------------------------------------------------------------------
/**
 * Return the ending node of the chain
 * @return Pointer to node
 */
template <class T>
inline typename Tree<T>::Tree_Node* Tree<T>::Chain_Iterator::get_last_node()
{
  return this->end.p_previous;
}

//------------------------------------------------------------------------
/**
 * Set Chain_Iterator to begin node of chain
 */
template <class T>
inline void Tree<T>::Chain_Iterator::set_begin()
{
  this->current =  this->start.p_next;
  this->at_start = false;
  this->at_end = false;
}

//------------------------------------------------------------------------
/**
 * Set Chain_Iterator to past end node of chain
 */
template <class T>
inline void Tree<T>::Chain_Iterator::set_end()
{
  this->current =  this->end.p_previous;
  this->at_start = false;
  this->at_end = true;
}

//------------------------------------------------------------------------
/**
 * pre-fix increment operator
 * @return Reference to chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator&
Tree<T>::Chain_Iterator::operator++()
{
  if (this->current == 0)
  {
    return *this;
  }
  if (this->at_start)
  {
        this->current = this->start.p_next;
        this->at_start = false;
        return *this;
  }
  
  if (this->current == this->end.p_previous)
  {
                                this->at_end = true;
        return *this;
  }
  
  if (is_ancestor(Iterator(this->end.p_previous))) // Move down the tree towards _end
  {                            
    this->current = this->current->p_first_child;  // determine which child 
    // is ancestor 
    while (!is_ancestor(Iterator(this->end.p_previous))) // iterate through siblings
    {                              
      if (this->current == this->end.p_previous)  // At end of chain 
      {
        return *this;            // so return this
      }
      this->current = this->current->p_next_sibling;
    }
  }
  else  // Move up the tree towards _end or an ancestor of _end
  {
    this->current = this->current->p_parent;
  }
  
  return *this;
}

//------------------------------------------------------------------------
/**
 * pre-fix decrement operator
 * @return Reference to chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator&
Tree<T>::Chain_Iterator::operator--()
{
  if (this->current == 0)
  {
    return *this;
  }
  
  if (this->at_end)
  {
    this->current = this->end.p_previous;
        this->at_end = false;
        return *this;
  }
  
  if (this->current == this->start.p_next)
  {
                                this->at_start = true;
        return *this;
  }
  
  
  if (is_ancestor(Iterator(this->start.p_next))) // Move down the tree towards _begin
  {   // determine which child is ancestor of _begin
    this->current = this->current->p_first_child;
    while (!is_ancestor(Iterator(this->start.p_next))) 
    {
      if (this->current == this->start.p_next)  // At _begin of chain
      {
        return *this;            // so return this
      }
      this->current = this->current->p_next_sibling;
      
    }
  }
  else  // Move up the tree towards _begin or an ancestor of _begin
  {
    this->current = this->current->p_parent;
  }
  return *this;
}

//------------------------------------------------------------------------
/**
 * post-fix increment operator
 * @param[in] Dummy int parameter to provide a unique prototype for the
 *            function
 * @return    Chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator
Tree<T>::Chain_Iterator::operator++(int)  // post-fix increment
{
  Chain_Iterator temp = *this;
  ++(*this);
  return temp;
}
    
//------------------------------------------------------------------------
/**
 * post-fix decrement operator
 * @param[in] Dummy int parameter to provide a unique prototype for the
 *            function
 * @return    Chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator
Tree<T>::Chain_Iterator::operator--(int)  // post-fix decrement
{
  Chain_Iterator temp = *this;
  --(*this);
  return temp;
}


//------------------------------------------------------------------------
/**
 * increment by specified value operator
 * @param[in] x   Unsigned int to specify the increment
 * @return Reference to chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator&
Tree<T>::Chain_Iterator::operator+=(unsigned int a)
{
  while (a > 0)
  {
    ++(*this);
    if (this->current == 0)
    {
      break;
    }
    a--;
  }
  return *this;
}

//------------------------------------------------------------------------
/**
 * decrement by specified value operator
 * @param[in] x   Unsigned int to specify the decrement
 * @return Reference to chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator&
Tree<T>::Chain_Iterator::operator-=(unsigned int a)
{
  while (a > 0)
  {
    --(*this);
    if (this->current == 0)
    {
      break;
    }
    a--;
  }
  return *this;
}

//------------------------------------------------------------------------
/**
 * Set current node, Check that the new current node is in the chain
 * @param[in] new_current  Pointer to specify the new node to point to.
 * @return                 True if successful, false if failed
 */
template <class T>    // Override the base class function
inline bool Tree<T>::Chain_Iterator::set_current(Tree_Node * new_current)  
{
  if (on_chain(new_current))      // before setting, check that the
  {
    this->current = new_current;          // new_current is on the chain
                                this->at_end = false;
        this->at_start = false;
        return true;
  }
  return false;
}


//------------------------------------------------------------------------
/**
 * Check if a node is on the chain of this chain iterator
 * @param[in] a  Pointer to node to test for.
 * @return       True if on chain, false if not on chain
 */
template <class T>
inline bool Tree<T>::Chain_Iterator::on_chain(const Tree_Node * a) const
{
  Chain_Iterator local_iterator(*this);
  
  local_iterator.set_begin();
  
  while (!local_iterator.at_end)
  {
    if (a == local_iterator.current)
    {
      return true;
    }
    ++local_iterator;
  }
  return false;
}


//------------------------------------------------------------------------
/**
 * Zero-referenced index from begin.
 * @return        Index
 */
template <class T>
inline int Tree<T>::Chain_Iterator::get_index_position() const
{
  int index = -1;
  Chain_Iterator temp_itr(*this);
  if (temp_itr.at_start)
    return index;
  
  while (!temp_itr.at_start)
  {
    --temp_itr;
    ++index;
  }
  return index;
  
}

/**************************************************************************/
/**************************************************************************/
/*                             TREE functions                             */
/**************************************************************************/
/**************************************************************************/
//------------------------------------------------------------------------
/**
 * Default constructor
 */
template <class T>
inline Tree<T>::Tree()
: _root_node(0), _start_node(0), _end_node(0), _number_of_nodes(0)
{
                _initialize_tree();
};

//------------------------------------------------------------------------
/**
 * Copy constructor
 * @param[in] a  Reference to another tree.
 */
template <class T>
inline Tree<T>::Tree(const Tree<T>& a)
: _root_node(0), _start_node(0), _end_node(0), _number_of_nodes(0)
{
  _root_node = 0;
  _number_of_nodes = 0;
                _initialize_tree();
    copy(a);
}

//------------------------------------------------------------------------
/**
 * Destructor
 */
template <class T>
inline Tree<T>::~Tree()
{
  clear_tree();    // Clear the tree of nodes
  delete _end_node;
  delete _start_node;
}

//------------------------------------------------------------------------
/**
 * initialize the start_node and end_node
 */
template <class T>
inline void Tree<T>::_initialize_tree()
{
  _start_node = new Tree_Node();
  _start_node->p_next_sibling = _root_node;
  _end_node = new Tree_Node();
  _end_node->p_previous_sibling = _root_node;
  
}

//------------------------------------------------------------------------
/*
 * get the number of the nodes on the tree
 * @return unsigned int number of nodes
 */
template <class T>
inline unsigned int Tree<T>::size()
{
  return _number_of_nodes;
}

//------------------------------------------------------------------------
/**
 * Determine if tree is empty
 * @return bool true if tree is empty
 */
template <class T>
inline bool Tree<T>::empty()
{
  return (_number_of_nodes == 0);
}

//------------------------------------------------------------------------
/**
 * Check if the current node of an iterator is on the tree
 * @param[in] d_iterator  Reference to base or derived iterator classes.
 * @return                True if on tree, false if not on tree
 */
template <class T>
template <typename Iterator_Type> 
inline bool Tree<T>::on_tree(const Iterator_Type & d_iterator)
{
  if (!d_iterator.current)
  {
    return false;
  }
  
  // If no nodes; return false
  if (size() == 0)
    {
      return false;
    }

  // Start at the pre-ordered begin of the tree
  Pre_Order_Iterator  check_iterator(begin_pre_order()); 
  
  // Iterate through the tree; if the node is found, return true
  while (check_iterator < end_pre_order())
  {
    if (check_iterator == d_iterator)
    {
      return true;
    }
    ++check_iterator;
  }
  
  // Node was not found so return false
  return false;
}


//------------------------------------------------------------------------
/**
 * Clear the tree of nodes
 */
template <class T>
inline void Tree<T>::clear_tree()
{
  if (!_root_node)  // If the root node isn't valid, the tree already
  {
    return;      // doesn't have any nodes to return
  }
  
  // Begin clearing the tree of nodes at the first post-order node.
  Iterator p_tmp;
  Post_Order_Iterator  clr_iterator(begin_post_order());
  
  while (size() > 0)  // While there are still valid nodes
  {
    p_tmp = clr_iterator;  // Point to the current node
    
    ++clr_iterator;        // Increment to the next post-order node
    
    delete_node(p_tmp);      // Delete the previous node
    
  }
  _root_node = 0;  // Set the root node to 0
}

//------------------------------------------------------------------------
/**
 * Delete the node and all its descendents pointed to by the iterator
 * @param[in] a  Reference to base or derived iterator class.
 */
template <class T>
template <typename Iterator_Type> 
inline void Tree<T>::delete_descendents(const Iterator_Type& a)
{
  if (!a.current)  // If the node isn't valid, return
  {
    return;
  }
  
  Iterator p_tmp;
  Post_Order_Iterator stop_iterator(a);
  Post_Order_Iterator delete_iterator(a);
  
  // Stop deleting at the node after the node that's pointed to
  ++stop_iterator;  
  
  --delete_iterator;  // Find the start node to begin deleting
  while (delete_iterator.is_descendent(a))
  {
    --delete_iterator;
  }
  if (delete_iterator.current)
  {
    // Increment by 1 to point to the first node to be deleted
    ++delete_iterator;  
  }
  else
  {
    delete_iterator = begin_post_order(); // start at the beginning
  }
  
  while (delete_iterator != stop_iterator)  // delete in post_order until the
  {                      // stop node is reached
    p_tmp = delete_iterator;
    ++delete_iterator;
    delete_node(p_tmp);
  }
}

//------------------------------------------------------------------------
/**
 * Delete this iterator's node only if it is valid, has no children and
 * is on this tree
 * @param[in] d_iter  Reference to base or derived iterator classes.
 */
template <class T>
template <typename Iterator_Type> 
inline void Tree<T>::delete_node(Iterator_Type d_iter)
{
  if (!d_iter.current)  // should have a valid node
  {
    return;
  }
  
  if (d_iter.current->p_first_child)
  {
    return;  // this node should not have any children
  }
  
  if (!on_tree(d_iter))  // The node should be on the tree
  {
    return;
  }
  
  if (d_iter.current->p_parent)  // This is not the root node
  {
    // First reset pointers to isolate the node to be deleted
    
    // If it is the first child
    if (d_iter.current == d_iter.current->p_parent->p_first_child)  
    {
      if (!d_iter.current->p_next_sibling)      // if it is the only child
      {
        // detach its links to its parent
        d_iter.current->p_parent->p_first_child = 0;  
        d_iter.current->p_parent->p_last_child = 0;
      }
      else  // it has a next sibling, make the next sibling the first sibling
      {
        d_iter.current->p_parent->p_first_child
          = d_iter.current->p_next_sibling;
        d_iter.current->p_next_sibling->p_previous_sibling = 0;
      }
    }
    else  // it is not the first child
    {
      // If it is the last child
      if (d_iter.current == d_iter.current->p_parent->p_last_child)  
      {
        d_iter.current->p_parent->p_last_child
          = d_iter.current->p_previous_sibling; // detach it from its parent
        d_iter.current->p_previous_sibling->p_next_sibling = 0;
      }
      else  // this is a middle child
      {
        d_iter.current->p_previous_sibling->p_next_sibling
          = d_iter.current->p_next_sibling;
        d_iter.current->p_next_sibling->p_previous_sibling
          = d_iter.current->p_previous_sibling;
      }
    }
    
  }
  
  d_iter.current = 0;
  --_number_of_nodes;  // Reduce the number of nodes by 1
}

//------------------------------------------------------------------------
/**
 * Copy a specified tree into this tree
 * @param[in] a  Reference to a tree.
 */
template <class T>
inline bool Tree<T>::copy(const Tree<T>& a)
{
  if (this == &a)    // A tree cannot copy itself
  {
    return false;
  }
  
  if (!a._root_node)  // the tree to be copied must have nodes
  {
    return false;
  }
  
  clear_tree();  // Clear this tree
  
  //_root_node = new Tree_Node(*(a._root_node->data));  // copy a's root node
  
  Pre_Order_Iterator a_iterator(a.begin_pre_order());
  Pre_Order_Iterator local_iterator(begin_pre_order());
  
  copy_descendents(local_iterator, a_iterator);
  
  return true;
  
}

//------------------------------------------------------------------------
/**
 * Copy the node and its descendents onto this tree at the specified node
 * @param[in] dest_itr Reference to base or derived iterator classes to copy
 *                     to.
 * @param[in] src_itr  Reference to base or derived iterator classes to copy
 *                     from
 */
template <class T>
template <typename Iterator_Type1, typename Iterator_Type2> 
inline bool Tree<T>::copy_descendents(
                      Iterator_Type1 dest_itr, Iterator_Type2 src_itr)
{

  // Src node must be valid
  if (!src_itr.current)
  {
    return false;
  }
  
  // Dest node must either be on the tree or the
  // root node (when the tree is empty)
  if (!on_tree(dest_itr) && !is_root(dest_itr))
  {
    return false;
  }
  
  // Source and destination cannot be identical; 
  if (src_itr == dest_itr)
  {
    return false;
  }
  
  // Destination cannot be a descendent of the source
  if (dest_itr.is_descendent(src_itr))
  {
    return false;
  }
  
  
  typename Tree<T>::Iterator src_itr_local(src_itr);
  typename Tree<T>::Pre_Order_Iterator new_parent;


  // T should have a copy constructor
  T * new_data = new T(*(src_itr.current->data)); 
  
  // First append the current node
  new_parent = append_child(dest_itr, new_data);
  
  // Now copy the children of the current node
  // If the current node of a has children
  if (src_itr_local.current->p_first_child)  
  {
    // point to first child
    src_itr.current = src_itr_local.current->p_first_child;    
    src_itr_local.current = src_itr.current;
    
    // add the first child and its descendents
    copy_descendents(new_parent, src_itr);  
    
    // while there are additional siblings of the current node
    while (src_itr_local.current->p_next_sibling)  
    {
      src_itr.current = src_itr_local.current->p_next_sibling;
      
      // add the descendents of the new node
      copy_descendents(new_parent, src_itr);  
      src_itr_local.current = src_itr_local.current->p_next_sibling;
    }
  }
  return true;
}

//------------------------------------------------------------------------
/**
 * tree equal operator
 * @param[in] a  Reference to the tree to copy from.
 */
template <class T>
inline Tree<T> &  Tree<T>::operator=(const Tree<T> & a)
{
  copy(a);
  return *this;
}

//------------------------------------------------------------------------
/**
 * Return the iterator that points to the parent of this iterator's node
 * @paramp[in] a  Reference to base or derived iterator classes.
 * @return        Base or derived iterator .
 */
template <class T>
template <typename Iterator_Type> Iterator_Type
inline Tree<T>::get_parent(const Iterator_Type& child) const
{
  
  // NOTE: Potential problem here if current points to an invalid node
  return Iterator_Type(child.current->p_parent);
}

//------------------------------------------------------------------------
/**
 * Query if the node pointed to has a parent
 * @param[in] child  Reference to base or derived iterator classes.
 * @return           True if has a parent, false if not
 */
template <class T>
template <typename Iterator_Type> 
inline bool Tree<T>::has_parent(const Iterator_Type& child) const
{
  
  // NOTE: Potential problem here if current points to an invalid node
  return (child.current->p_parent==0)?false:true;
}

//------------------------------------------------------------------------
/**
 * Return the iterator that points to the first child of this iterator's node
 * @param[in] child  Reference to base or derived iterator classes.
 * @return           Base or derived iterator 
 */
template <class T>
template <typename Iterator_Type> Iterator_Type 
inline  Tree<T>::get_first_child(const Iterator_Type& child) const
{
  
  // NOTE: Potential problem here if current points to an invalid node
  return Iterator_Type(child.current->p_first_child);
}

//------------------------------------------------------------------------
/**
 * Return the iterator that points to the last child of this iterator's node
 * @param[in] child  Reference to base or derived iterator classes.
 * @return           Base or derived iterator 
 */
template <class T>
template <typename Iterator_Type> Iterator_Type 
inline  Tree<T>::get_last_child(const Iterator_Type& child) const
{
  
  // NOTE: Potential problem here if current points to an invalid node
  return Iterator_Type(child.current->p_last_child);
}

//------------------------------------------------------------------------
/**
 * Return the iterator that points to the previous sibling of
 * this iterator's node
 * @param[in] child  Reference to base or derived iterator classes.
 * @return           Base or derived iterator 
 */
template <class T>
template <typename Iterator_Type> Iterator_Type 
inline  Tree<T>::get_previous_sibling(const Iterator_Type& child) const
{
  
  // NOTE: Potential problem here if current points to an invalid node
  return Iterator_Type(child.current->p_previous_sibling);
}
  
//------------------------------------------------------------------------
/**
 * Return the iterator that points to the next sibling of this iterator's node
 * @param[in] child  Reference to base or derived iterator classes.
 * @return           Base or derived iterator 
 */
template <class T>
template <typename Iterator_Type> Iterator_Type 
inline  Tree<T>::get_next_sibling(const Iterator_Type& child) const
{
  
  // NOTE: Potential problem here if current points to an invalid node
  return Iterator_Type(child.current->p_next_sibling);
}


//------------------------------------------------------------------------
/**
 * Append the data as a new child of the parent node. Note that a new
 * copy of the node data type is made
 * @param[in] parent       Reference to base or derived iterator classes.
 * @param[in] child_data   Reference to node data type to be appended
 * @return                 Base or derived iterator 
 */
template <class T>
template <typename Iterator_Type> Iterator_Type 
inline Tree<T>::append_child(
                Iterator_Type parent, T * child_data)
{
  Tree_Node * new_child = 0;
  
  if ((parent.current)&&(on_tree(parent))) // parent is valid and on tree
  {
    new_child = new Tree_Node(child_data, parent.current);
  }
  else 
  {  // if root node exists attach to root node
    if (_root_node)
    {
      Iterator_Type root_parent(_root_node);
      new_child = new Tree_Node(child_data, root_parent.current);
    }
    else  // if root node does not exist, make this the root node
    {
      // don't need to change root node pointers
      _root_node = new Tree_Node(child_data);  
      new_child = _root_node;
      //parent.current = _root_node;  // point parent to root node
      _start_node->p_next_sibling = _root_node;
      _end_node->p_previous_sibling = _root_node;
      _root_node->p_previous_sibling = _start_node;
      _root_node->p_next_sibling = _end_node;
    }
  }
  Iterator_Type tmp(new_child);
  ++_number_of_nodes;
  return tmp;
}

//------------------------------------------------------------------------
/**
 * Insert the new node data at the specified location and displace the
 * specified location to be the next sibling. Note that a new
 * copy of the node data type is made.
 * @param[in] location       Reference to base or derived iterator classes
 * @param[in] element_data   Reference to node data type to be inserted
 * @return                   Base or derived iterator 
 */
template <class T>
template <typename Iterator_Type> Iterator_Type 
inline Tree<T>::insert(
                  Iterator_Type location, T * element_data)
{
  Tree_Node * new_node;
  Iterator_Type new_location;
  
  // location is valid and on tree
  if ((location.current!= 0)&&(on_tree(location)) 
    ||(size() == 0))  
  {
    new_location = location;
  }
  else
  {
    
    // put the new node at the
    return insert_after(--end_pre_order(), element_data); 
    // end of the pre-ordered tree
  }
  new_node = new Tree_Node(element_data);
  
  if (new_location.current!=0)  // if this is not the root node
  {
    new_node->p_parent = new_location.current->p_parent;

    // new_location is a first child
    if (!new_location.current->p_previous_sibling)  
      new_location.current->p_parent->p_first_child = new_node;
    
    // new_location is a last child
    if (!new_location.current->p_next_sibling)  
      new_location.current->p_parent->p_last_child = new_node;
    
    if (new_location.current->p_previous_sibling)
      new_location.current->p_previous_sibling->p_next_sibling = new_node;
    
    new_node->p_previous_sibling = new_location.current->p_previous_sibling;
    new_node->p_next_sibling = new_location.current;
    new_location.current->p_previous_sibling = new_node;
    
    
  }
  else  // if this is the root node, it doesn't have a parent
  {
    new_node->p_parent = 0;
    new_node->p_previous_sibling = 0;
    new_node->p_next_sibling = 0;
    _root_node = new_node;
    _start_node->p_next_sibling = _root_node;
    _end_node->p_previous_sibling = _root_node;
    _root_node->p_previous_sibling = _start_node;
    _root_node->p_next_sibling = _end_node;
    
  }
  
  new_node->p_first_child = 0;
  new_node->p_last_child = 0;
  new_location.current = new_node;
  
  ++_number_of_nodes;
  
  return new_location;
}


//------------------------------------------------------------------------
/**
 * Insert the new node data after the specified location and displace the
 * specified location to be the previous sibling. Note that a new
 * copy of the node data type is made.
 * @param[in] location      Reference to base or derived iterator classes.
 * @param[in] element_data  Reference to node data type to be inserted.
 * @return                  Base or derived iterator 
 */
template <class T>
template <typename Iterator_Type> Iterator_Type 
inline Tree<T>::insert_after(
              Iterator_Type location, T * element_data)
{
  Tree_Node * new_node;
  Iterator_Type new_location;
  
  // location is valid and on tree
  if ((location.current!= 0)&&(on_tree(location)))  
  {
    new_location = location;
  }
  else if (size() != 0)
  {
    new_location = --end_pre_order(); // put the new node at the end
    // of the pre-ordered tree
  }
  new_node = new Tree_Node(element_data);
  
  if (new_location.current != 0)  // if this is not the root node
  {
    new_node->p_parent = new_location.current->p_parent;
    
    if (!new_location.current->p_next_sibling)  // new_location is a last child
    {
      new_location.current->p_parent->p_last_child = new_node;
    }
    
    if (new_location.current->p_next_sibling)
    {
      new_location.current->p_next_sibling->p_previous_sibling = new_node;
    }
    
    new_node->p_previous_sibling = new_location.current;
    new_node->p_next_sibling = new_location.current->p_next_sibling;
    new_location.current->p_next_sibling = new_node;
  }
  else  // if this is the root node, it doesn't have a parent
  {
    new_node->p_parent = 0;
    new_node->p_previous_sibling = 0;
    new_node->p_next_sibling = 0;
    _root_node = new_node;
    _start_node->p_next_sibling = _root_node;
    _end_node->p_previous_sibling = _root_node;
    _root_node->p_previous_sibling = _start_node;
    _root_node->p_next_sibling = _end_node;
  }
  
  new_node->p_first_child = 0;
  new_node->p_last_child = 0;
  new_location.current = new_node;
  
  //location.current = new_node;
  ++_number_of_nodes;
  
  
  return new_location;
}


//------------------------------------------------------------------------
/**
 * Returns the depth of the node in the tree
 * @param[in] a  Reference to base or derived iterator classes.
 * @return       Depth; -1 if error; root node depth = 0
 */
template <class T>
template <typename Iterator_Type> 
inline int Tree<T>::get_depth(const Iterator_Type& a)
{
  if (a.current == 0) // If iterator current position is invalid
  {
    return -1;    // return -1
  }
  if (!on_tree(a))  // If iterator does not point to a node on this tree
  {
    return -1;    // return -1
  }
  
  
  typename Tree<T>::Tree_Node * a_position = a.current;
  unsigned int return_value=0;
  
  while(a_position->p_parent != 0) // While not at the root node
  {
    a_position = a_position->p_parent;  // Iterate towards root
    ++return_value;            // and increment depth counter
  }
  return return_value;
}

//------------------------------------------------------------------------
/**
 * Tests if the iterator is pointing at the root node
 * @param[in] a  Reference to base or derived iterator classes.
 * @return       True if is the root, false if not the root.
 */
template <class T>
template <typename Iterator_Type>
inline bool Tree<T>::is_root(const Iterator_Type& a) const
{
  return (a.current == _root_node);
}

//------------------------------------------------------------------------
/**
 * Return a sibling iterator that points to the beginning of the siblings
 * @param[in] a  Reference to base or derived iterator classes.
 * @return       Sibling iterator
 */
template <class T>
template <typename Iterator_Type>
inline typename Tree<T>::Sibling_Iterator Tree<T>::begin_sibling(const Iterator_Type & a)
{
                Sibling_Iterator sib_itr(a.current);
    sib_itr.current = sib_itr.start.p_next;
    return sib_itr;
}
  
//------------------------------------------------------------------------
/**
 * Return a pre-order iterator that points to the beginning of the
 * pre-ordered tree
 * @return Pre-order iterator
 */
template <class T>
inline typename Tree<T>::Pre_Order_Iterator Tree<T>::begin_pre_order() const
{
  
  Pre_Order_Iterator begin_pre_itr(_root_node);
  begin_pre_itr.at_end = false;
  begin_pre_itr.at_start = false;
  
  return begin_pre_itr;
}
  
//------------------------------------------------------------------------
/**
 * Return a post-order iterator that points to the beginning of the
 * post-ordered tree
 * @return Post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator Tree<T>::begin_post_order() const
{
  Tree_Node * p_tmp = begin_pre_order().current;
  
  if (!p_tmp)
    return Post_Order_Iterator(p_tmp);
  
  while (p_tmp->p_first_child)
    p_tmp = p_tmp->p_first_child;
  
  Post_Order_Iterator begin_post_itr(p_tmp);
  begin_post_itr.at_end = false;
  begin_post_itr.at_start = false;
  
  return begin_post_itr;
}
  
//------------------------------------------------------------------------
/**
 * Return a new chain iterator that points to the beginning of the chain
 * @param[in] a  Reference to a chain iterator.
 * @return       Chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator
Tree<T>::begin_chain(Chain_Iterator & a) const
{
  Chain_Iterator chain_itr(a);
  chain_itr.set_current(a.get_first_node());
  chain_itr.at_start = false;
  chain_itr.at_end = false;
  
  return chain_itr;
}
  
//------------------------------------------------------------------------
/**
 * Return a sibling iterator that points to the end (1 beyond the last)
 * sibling
 * @param[in] a  Reference to base or derived iterator classes.
 * @return       Sibling iterator
 */
template <class T>
template <typename Iterator_Type> 
inline typename Tree<T>::Sibling_Iterator
Tree<T>::end_sibling(const Iterator_Type & a)
{
  Sibling_Iterator sib_itr(a.current);
  
  sib_itr.current = sib_itr.end.p_previous;
  sib_itr.at_end = true;                // end_sibling points to a fictious 
  sib_itr.at_start = false;     // node beyone the last sibling
  
  return sib_itr;
}
  
//------------------------------------------------------------------------
/**
 * Return a pre-order iterator that points to the end of the pre-ordered tree
 * @return Pre-order iterator
 */
template <class T>
inline typename Tree<T>::Pre_Order_Iterator Tree<T>::end_pre_order() const
{
  Pre_Order_Iterator end_pre_itr(_end_node);
  end_pre_itr.at_end = true;
  end_pre_itr.at_start = false;
  
  return Pre_Order_Iterator(end_pre_itr);
}
  
//------------------------------------------------------------------------
/**
 * Return a post_order_iterator that points to the end of the post-ordered tree
 * @return Post-order iterator
 */
template <class T>
inline typename Tree<T>::Post_Order_Iterator Tree<T>::end_post_order() const
{
  Post_Order_Iterator end_post_itr(_end_node);
  end_post_itr.end.p_previous = _end_node->p_previous_sibling;
  end_post_itr.at_end = true;
  end_post_itr.at_start = false;
  
  return Post_Order_Iterator(end_post_itr);
}
  
//------------------------------------------------------------------------
/**
 * Return a chain iterator that points to the end of this chain
 * @return Chain iterator
 */
template <class T>
inline typename Tree<T>::Chain_Iterator
Tree<T>::end_chain(Chain_Iterator & a) const
{
  Chain_Iterator chain_itr(a);
  chain_itr.set_current(a.get_last_node());
  chain_itr.at_start = false;
  chain_itr.at_end = true;
  
  return chain_itr;
  
}



#endif // __TREE_H

Last modified: June 05 2007 10:19:53

JPL PRIVACY STATEMENT GLOSSARY SITEMAP FEEDBACK CONTACT US

Site Manager: Issa A.D. Nesnas
Site Maintainer: Kelly Breed
Document Clearance #: CL 07-0635