/******************************************************************
 * Memorial University of Newfoundland
 * Engineering 4892 Data Structures
 *
 * $RCSfile: BinTree.h,v $   $Revision: 1.2 $
 * $Date: 2001-07-11 11:46:57-02:30 $
 * $State: Exp $ 
 *
 * Binary Tree class template.
 *
 ******************************************************************/

/******************************************************************
 *                     REVISION HISTORY
 *
 * $Log: BinTree.h,v $
 * Revision 1.2  2001-07-11 11:46:57-02:30  dpeters
 * Added DuplicateElement to Status, checked with M$ Visual C++
 *
 * Revision 1.1  2001-07-10 17:00:58-02:30  dpeters
 * Initial revision
 *
 *
 ******************************************************************/

#ifndef BINTREE_DEF
#define BINTREE_DEF

#include <string>
#include <strstream>
#include <vector>
#include <algorithm>

template <class T>
class BinaryNode // The node of the binary tree
{
  public:
    T key;
    BinaryNode* left;
    BinaryNode* right;
    BinaryNode(BinaryNode *l = 0, BinaryNode* r = 0) 
      : left(l), right(r) { }
    BinaryNode(const T& k, BinaryNode *l = 0, BinaryNode* r = 0) 
      : key(k), left(l), right(r) { }
};

template <class T>
class BinaryTree 
{
  public:

  // Local types
    enum Status { Ok, NewFail, NoSuchElement, DuplicateElement };

  // Constructors 
    BinaryTree();
    // Post: empty tree constructed

    BinaryTree(const BinaryTree<T>& r);
    // Post: tree is a copy of r

  // Destructor
    virtual ~BinaryTree();

  // Accessors
    bool empty() const;
    // Post: Result = (tree is empty)

    int height() const;
    // Post: Result = length of longest path from root to a leaf

    Status getStatus() const { return err; }
    // Post: Result = status of last access

    std::vector<T> preorderList() const;
    std::vector<T> inorderList() const;
    std::vector<T> postorderList() const;

    std::string toString() const;

  // Mutators
    Status insert(const T& x);
    // Post: x is inserted in the tree keeping it optimally balanced

    BinaryTree<T>& operator=(const BinaryTree<T>& r);
    // Assignment operator
    // Post: this is a copy of r



  protected: 

    BinaryNode<T>* root;

    mutable Status err;   // Status of the last call.

  private:
    // Private methods
    BinaryNode<T>* rCopyTree(const BinaryNode<T>* r);
    void rDeleteTree(BinaryNode<T>* r);
    int rTreeHeight(BinaryNode<T>* r) const;
    virtual Status rInsert(BinaryNode<T>*& r, const T& x);
    void rPreorderList(BinaryNode<T>* r, std::vector<T>& l) const;
    void rInorderList(BinaryNode<T>* r, std::vector<T>& l) const;
    void rPostorderList(BinaryNode<T>* r, std::vector<T>& l) const;
    void rToString(BinaryNode<T>* r, std::ostrstream& l, int depth) const;
};

#include <cassert>
#include <new>


/******************************************************************
 * BinaryTree -- constructor
 *
 * Post: err = Ok /\ root = 0
 *******************************************************************/
template <class T>
BinaryTree<T>::BinaryTree<T>()
{
  root = 0;
  err = Ok;
}

/******************************************************************
 * BinaryTree<T> -- copy constructor
 * 
 * Post: err = Ok -> root points to a tree that is a copy of r
 *       err = NewFail -> memory allocation failure
 *******************************************************************/
template <class T>
BinaryTree<T>::BinaryTree<T>(const BinaryTree<T>& r)
{
  root = rCopyTree(r.root);
}

/******************************************************************
 * ~BinaryTree<T> -- destructor
 * 
 *******************************************************************/
template <class T>
BinaryTree<T>::~BinaryTree()
{
  rDeleteTree(root);
  err = Ok;
}

/******************************************************************
 * empty -- return true if the tree is empty, false otherwise
 * 
 * Post: Result = root == 0
 *******************************************************************/
template <class T>
bool 
BinaryTree<T>::empty() const
{
  return (root == 0);
}

/******************************************************************
 * height -- return the height of the tree 
 * 
 * Post: Result = height of the tree
 *******************************************************************/
template <class T>
int 
BinaryTree<T>::height() const
{
  return rTreeHeight(root);
}

/******************************************************************
 * operator= -- assignment operator
 * 
 * Post: err = Ok -> (this is a copy of r)
 *       err = NewFail -> root = 0 (memory allocation failure)
 *******************************************************************/
template <class T>
BinaryTree<T>& 
BinaryTree<T>::operator=(const BinaryTree<T>& r)
{
  if (&r != this) {
    rDeleteTree(root);
    err = Ok;
    root = rCopyTree(r.root);
  }
  return *this;
}

/******************************************************************
 * insert -- insert an element in the tree, keeping it balanced
 * 
 * Post: 
 *******************************************************************/
template <class T>
BinaryTree<T>::Status 
BinaryTree<T>::insert(const T& x)
{
  return rInsert(root, x);
}

/******************************************************************
 * preorderList -- construct a list in preorder form
 * 
 * Post: Result = list of elements from tree in pre-order
 *******************************************************************/
template <class T>
std::vector<T>
BinaryTree<T>::preorderList() const
{
  std::vector<T> l;
  rPreorderList(root, l);
  return l;
}

/******************************************************************
 * inorderList -- construct a list in inorder form
 * 
 * Post: Result = list of elements from tree in pre-order
 *******************************************************************/
template <class T>
std::vector<T>
BinaryTree<T>::inorderList() const
{
  std::vector<T> l;
  rInorderList(root, l);
  return l;
}

/******************************************************************
 * postorderList -- construct a list in postorder form
 * 
 * Post: Result = list of elements from tree in pre-order
 *******************************************************************/
template <class T>
std::vector<T>
BinaryTree<T>::postorderList() const
{
  std::vector<T> l;
  rPostorderList(root, l);
  return l;
}

/******************************************************************
 * toString -- produce a bracketed string representation of the tree
 * 
 * Post: Result = string containing the string representation
 *******************************************************************/
template <class T>
std::string
BinaryTree<T>::toString() const
{
  std::ostrstream l;
  rToString(root, l, 0);
  l << '\0';
  return l.str();
}

template <class T>
BinaryNode<T>*
BinaryTree<T>::rCopyTree(const BinaryNode<T>* src)
{
  BinaryNode<T>* result = 0;
  if (src != 0 && err == Ok) {
    result = new(std::nothrow) BinaryNode<T>(src->key);
    if (result != 0) {
      result->left = rCopyTree(src->left);
      result->right = rCopyTree(src->right);
    } else {
      err = NewFail;
    }
  }
  return result;
}

template <class T>
void
BinaryTree<T>::rDeleteTree(BinaryNode<T>* cur)
{
  if (cur != 0) {
    rDeleteTree(cur->left);
    rDeleteTree(cur->right);
    delete cur;
  }
}

template <class T>
int
BinaryTree<T>::rTreeHeight(BinaryNode<T>* r) const
{
  int result = 0;
  if (r != 0) {
    result = 1 + std::max(rTreeHeight(r->left), rTreeHeight(r->right));
    // You could also do this the 'old-fashioned' way:
    // int lh = rTreeHeight(r->left);
    // int rh = rTreeHeight(r->right);
    // if (lh > rh) {
    //   result = 1 + lh;
    // } else {
    //   result = 1 + rh;
    // }
    // (It appears that "max" is not defined in the STL implementation that
    // ships with M$ Visual C++, so you might need to do it the
    // old-fashioned way if you want to use that software.)
  }
  return result;
}

template <class T>
BinaryTree<T>::Status
BinaryTree<T>::rInsert(BinaryNode<T>*& r, const T& x)
{
  if (r == 0) {
    r = new(std::nothrow) BinaryNode<T>(x);
    if (r != 0) {
      err = Ok;
    } else {
      err = NewFail;
    }
  } else if (rTreeHeight(r->left) <= rTreeHeight(r->right)) {
    err = rInsert(r->left, x);
  } else {
    err = rInsert(r->right, x);
  }
  return err;
}

template <class T>
void 
BinaryTree<T>::rPreorderList(BinaryNode<T>* r, std::vector<T>& l) const
{
  if (r != 0) {
    l.push_back(r->key);
    rPreorderList(r->left, l);
    rPreorderList(r->right, l);
  }
}

template <class T>
void 
BinaryTree<T>::rInorderList(BinaryNode<T>* r, std::vector<T>& l) const
{
  if (r != 0) {
    rInorderList(r->left, l);
    l.push_back(r->key);
    rInorderList(r->right, l);
  }
}

template <class T>
void 
BinaryTree<T>::rPostorderList(BinaryNode<T>* r, std::vector<T>& l) const
{
  if (r != 0) {
    rPostorderList(r->left, l);
    rPostorderList(r->right, l);
    l.push_back(r->key);
  }
}

template <class T>
void 
BinaryTree<T>::rToString(BinaryNode<T>* r, std::ostrstream& l, int depth) const
{
  if (r != 0) {
    rToString(r->right, l, depth+1);
    for (int i = 0; i < depth; i++) l << "\t";
    l << r->key <<"\n";
    rToString(r->left, l, depth+1);
  }
}

#endif