/******************************************************************
 * Memorial University of Newfoundland
 * Engineering 4892 Data Structures
 *
 * $RCSfile: assign5.h,v $   $Revision: 1.3 $
 * $Date: 2001-07-16 14:28:04-02:30 $
 * $State: Exp $ 
 *
 * Include file for Assignment 5.
 *
 ******************************************************************/

/******************************************************************
 *                     REVISION HISTORY
 *
 * $Log: assign5.h,v $
 * Revision 1.3  2001-07-16 14:28:04-02:30  dpeters
 * Fixed type for Status.
 *
 * Revision 1.2  2001-07-10 17:05:45-02:30  dpeters
 * Fixed log.
 *
 *
 ******************************************************************/

#ifndef ASSIGN5_DEF
#define ASSIGN5_DEF

#include <list>
#include "BinTree.h"

enum Branch { Left, Right };

typedef std::list<Branch> Path;

template <class T>
class A5Tree : public BinaryTree<T>
{
  public: 
    int size() const; 
    // Post: Result = number of nodes in the tree

    BinaryTree<T>::Status remove(Path p);
    // Post: Result = Ok -> tree has node at location p removed and all
    //       other nodes remain such that the inorder traversal produces
    //       the same list except for the missing node.
    //       Resut = NoSuchElement <-> p is not a valid path in the tree

  private:
    int rSize(BinaryNode<T>* r) const;
    BinaryTree<T>::Status rRemove(BinaryNode<T>*& r, Path& p);
};

/******************************************************************
 * size -- count the nodes in the tree
 * 
 * Post: Result = number of nodes in the tree
 *******************************************************************/

template <class T>
int
A5Tree<T>::size() const
{
  return rSize(root);
}

/******************************************************************
 * remove -- Remove the node at location p
 * 
 * p is used to find a location in the tree, starting at the front, each
 * Branch is used to choose between the left or right sub-trees of the
 * current node.
 *
 * Post: Result = Ok -> tree has node at location p removed and all
 *       other nodes remain such that the inorder traversal produces
 *       the same list except for the missing node. /\ 
 *       Resut = NoSuchElement <-> p is not a valid path in the tree
 *******************************************************************/
template <class T>
BinaryTree<T>::Status
A5Tree<T>::remove(Path p)
{
  return rRemove(root, p);
}

#endif