// *****************************************************
// *                                                   *
// *   bstree.C (MP5)                                  *   
// *                                                   *
// *   Implementation for a BST class                  *
// *                                                   *
// *   Written by Mark Allen Weiss                     *
// *     Altered by Jason Zych                         *
// *                                                   *
// *****************************************************

#include <stdlib.h>
#include "bstree.h"


// BSTree
//    - default constructor
//    - initializes tree to be empty
template <class Etype>
BSTree<Etype>::BSTree() : root(NULL), lastFound(NULL) 
{
   // no additional code needed
}



// BSTree
//    - copy constructor
//    - parameters : origVal - previously allocated BSTree object
//    - initializes object to be a copy of origVal
template <class Etype>
BSTree<Etype>::BSTree(const BSTree<Etype>& origVal)
{
   root = Copy(origVal.root); 
   lastFound = root;
}



// ~BSTree
//    - destructor
//    - deletes dynamically allocated memory
template <class Etype>
BSTree<Etype>::~BSTree()
{ 
   Make_Empty(root); 
   root = lastFound = NULL; 
}



// operator=
//    - parameters : origVal - previously allocated BSTree object
//    - return value - const reference to this object  
//    - sets object to be a copy of origVal
template <class Etype>
const BSTree<Etype>& BSTree<Etype>::operator=(const BSTree<Etype>& origVal)
{
   if(this != &origVal) 
   {
      Make_Empty(root);
      root = Copy(origVal.root);
      lastFound = root;
    }
    return *this;
}




 
// Last
//    - returns element in the last node looked up 
template <class Etype>
Etype BSTree<Etype>::Last() const
{     
   if (lastFound != NULL)
      return lastFound->element;
   else
   {
      Etype x;
      return x;   // return default Etype; user needs to be able
                  //   to tell the difference
   }
}




template <class Etype>
TreeNode<Etype> *
BSTree<Etype>::Copy( const TreeNode<Etype> *T ) {
    if( T != NULL )
        return new TreeNode<Etype>
            ( T->element, Copy( T->left ), Copy( T->right ) );
    else
        return NULL;
}

template <class Etype>
void 
BSTree<Etype>::Make_Empty( TreeNode<Etype> * & T ) {
    if( T != NULL ) {
        Make_Empty( T->left );
        Make_Empty( T->right );
        delete T;
        T = NULL;
    }
}




template <class Etype>
void
BSTree<Etype>::PreOrder( const TreeNode<Etype> *T) const {
   if (T == NULL)
     return;
   else {
     cout << T->element << endl; 
     PreOrder(T->left);
     PreOrder(T->right);
   }
}
 
template <class Etype>
void
BSTree<Etype>::InOrder( const TreeNode<Etype> *T) const {
   if (T == NULL)
     return;
   else {
     InOrder(T->left);
     cout << T->element << endl;
     InOrder(T->right);
   }
}


template <class Etype>
void
BSTree<Etype>::PostOrder( const TreeNode<Etype> *T) const {
   if (T == NULL)
     return;
   else {
     PostOrder(T->left);
     PostOrder(T->right);
     cout << T->element << endl;
   }
}
 


template <class Etype>
TreeNode<Etype>*
BSTree<Etype>::Find( const Etype & X, TreeNode<Etype> * T ) const {
    if( T == NULL )
        return NULL;
    else
    if( X < T->element )
        return Find( X, T->left );
    else
    if( X > T->element )
        return Find( X, T->right );
    else
        return T;
}


// This is a recursive version
template <class Etype>
TreeNode<Etype>*
BSTree<Etype>::Find_Min( TreeNode<Etype> *T ) const {
    if( T == NULL )
        return NULL;
    else
    if( T->left == NULL )
        return T;
    else
        return Find_Min( T->left );
}

// This is the similar non-recursive version
template <class Etype>
TreeNode<Etype>*
BSTree<Etype>::Find_Max( TreeNode<Etype> *T ) const {
    if( T != NULL )
        while( T->right != NULL )
            T = T->right;
    return T;
}

template <class Etype>
void
BSTree<Etype>::Insert( const Etype & X, TreeNode<Etype> * & T ) {
    if( T == NULL )
    {
        T = new TreeNode<Etype>( X );
        if( T == NULL )
            BST_Error( "Out of space" );
    }
    else
    if( X < T->element )
        Insert( X, T->left );
    else
    if( X > T->element )
        Insert( X, T->right );
    // Else X is in the tree already.  We'll do nothing.
}


template <class Etype>
void
BSTree<Etype>:: Remove( const Etype & X, TreeNode<Etype> * & T ) {
    TreeNode<Etype> *Tmp_Cell;

    if( T == NULL )
        BST_Error( "element not found" );
    else
    if( X < T->element )	// Go left.
        Remove( X, T->left );
    else
    if( X > T->element )	// Go right.
        Remove( X, T->right );
    else			// Found element to be removed.
    if( T->left != NULL && T->right != NULL )	// Two children.
    {	// Replace with smallest in right subtree.
        Tmp_Cell = Find_Min( T->right );
        T->element = Tmp_Cell->element;
        Remove( T->element, T->right );
    }
    else		// One or zero child.
    {
        Tmp_Cell = T;
        if( T->left == NULL )	// Only a right child.
            T = T->right;
        else
        if( T->right == NULL )	// Only a left child.
            T = T->left;
        delete Tmp_Cell;
    }
}



template <class Etype>
void BSTree<Etype>::BST_Error(const char *msg){
   cerr << "Fatal Binary Search Tree error: " << msg << endl;
   cout << "Fatal Binary Search Tree error: " << msg << endl;
   // abort();
}


