// *****************************************************
// *                                                   *
// *   bstree.C (MP6)                                  *   
// *                                                   *
// *   Implementation for a BST class                  *
// *                                                   *
// *   Written by Mark Allen Weiss                     *
// *     Altered by Jason Zych                         *
// *                                                   *
// *   Modified:  March 28 1999                        *
// *     Author:  Zaczek, Mariusz                      *
// *                                                   *
// *       - added to BSTree: operator<<, operator>>,  *
// *         counters: TotalCompares & RecentCompares. *
// *       - modified the Find, Insert and Remove fns. *
// *                                                   *
// *****************************************************

#include "bstree.h"


// BSTree
//    - default constructor
//    - initializes tree to be empty
template <class Etype>
BSTree<Etype>::BSTree() : root(NULL), lastFound(NULL), size(0),
			  TotalCompares(0), RecentCompares(0)
{
   // 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;
   size = origVal.size;
}



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



// 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;
      size = origVal.size;
    }
    return *this;
}



// Last
//    - return value : object of the generic type
//    - returns copy of element in the last node looked up;
//         if no node to return, return default object
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
   }
}



// Copy
//    - parameters : TN - a treenode pointer
//    - return value : a treenode pointer
//    - makes a new TreeNode which is a copy of the
//        parameter node, and returns it
template <class Etype>
TreeNode<Etype>* BSTree<Etype>::Copy(const TreeNode<Etype>* TN) 
{
   if (TN != NULL)
      return new TreeNode<Etype>
           (TN->element, Copy(TN->left), Copy(TN->right));
   else
      return NULL;
}



// Make_Empty
//    - parameters : TN - reference to a tree node pointer
//    - recursively clears the tree
template <class Etype>
void BSTree<Etype>::Make_Empty(TreeNode<Etype>*& TN) 
{
   if (TN != NULL) 
   {
      Make_Empty(TN->left);
      Make_Empty(TN->right);
      delete TN;
      TN = NULL;
   }
}



// PreOrder
//    - parameters : TN - reference to a tree node pointer
//    - recursively prints tree in preorder format; assumes Etype has
//       has operator<< defined
template <class Etype>
void BSTree<Etype>::PreOrder(const TreeNode<Etype>* TN) const 
{
   if (TN == NULL)
      return;
   else 
   {
      cout << TN->element << endl; 
      PreOrder(TN->left);
      PreOrder(TN->right);
   }
}



// InOrder
//    - parameters : TN - reference to a tree node pointer
//    - recursively prints tree in inorder format; assumes Etype has
//       has operator<< defined
template <class Etype>
void BSTree<Etype>::InOrder(const TreeNode<Etype>* TN) const 
{
   if (TN == NULL)
      return;
   else 
   {
      InOrder(TN->left);
      cout << TN->element << endl;
      InOrder(TN->right);
   }
}



// PostOrder
//    - parameters : TN - reference to a tree node pointer
//    - recursively prints tree in postorder format; assumes Etype has
//       has operator<< defined
template <class Etype>
void BSTree<Etype>::PostOrder(const TreeNode<Etype>* TN) const 
{
   if (TN == NULL)
      return;
   else 
   {
      PostOrder(TN->left);
      PostOrder(TN->right);
      cout << TN->element << endl;
   }
}
 


// Find
//    - parameters : searchElem - element to be found
//                 : TN - a treenode pointer
//    - return value : TreeNode pointer
//    - returns 1 if searchElem is found in tree, 0 else
//        also, if found, returns pointer to that node
template <class Etype>
TreeNode<Etype>* BSTree<Etype>::Find(const Etype& searchElem, 
					TreeNode<Etype>* TN)
{
   if (TN == NULL)
      return NULL;
   else if (searchElem < TN->element)
   {
      RecentCompares++;
      TotalCompares++;

      return Find(searchElem, TN->left);
   }
   else if (searchElem > TN->element)
   {
      RecentCompares++; 
      TotalCompares++;

      return Find(searchElem, TN->right);
   }
   else
      return TN;
}



// Find_Min
//    - parameters : TN - a treenode pointer
//    - return value : TreeNode pointer
//    - returns pointer to the minimum value in tree
//    - (recursive)
template <class Etype>
TreeNode<Etype>* BSTree<Etype>::Find_Min(TreeNode<Etype>* TN) const
{
   if (TN == NULL)
      return NULL;
   else if (TN->left == NULL)
      return TN;
   else
      return Find_Min(TN->left);
}



// Find_Max
//    - parameters : TN - a treenode pointer
//    - return value : TreeNode pointer
//    - returns pointer to the maximum value in tree
//    - (nonrecursive)
template <class Etype>
TreeNode<Etype>* BSTree<Etype>::Find_Max(TreeNode<Etype>* TN) const 
{
   if (TN != NULL)
      while(TN->right != NULL)
         TN = TN->right;
   return TN;
}



// Insert
//    - parameters : insElem - element to be inserted
//                 : TN - a treenode pointer
//    - recursively inserts insElem into tree (does nothing if
//         it is already there
template <class Etype>
void BSTree<Etype>::Insert(const Etype& insElem, TreeNode<Etype>*& TN) 
{
   if (TN == NULL)
   {
      TN = new TreeNode<Etype>(insElem);
      size++;
   }
   else if (insElem < TN->element)
   {
      RecentCompares++;

      Insert(insElem, TN->left);
   }
   else if (insElem > TN->element)
   {
      RecentCompares++;

      Insert(insElem, TN->right);
   }
   // Else insElem is in the tree already.  We'll do nothing.
}


// Remove
//    - parameters : remElem - element to be removed
//                 : TN - a treenode pointer
//    - recursively removes remElem from tree if it is in tree
template <class Etype>
void BSTree<Etype>::Remove(const Etype & X, TreeNode<Etype>*& TN) 
{
    TreeNode<Etype> *Tmp_Cell;

   if (TN == NULL)
      return;
   else if(X < TN->element )	// Go left.
   {
      RecentCompares++;

      Remove( X, TN->left );
   }
   else if(X > TN->element)	// Go right.
   {
      RecentCompares++;

      Remove( X, TN->right);
   }
   else			// Found element to be removed.
   {
    
      if((TN->left != NULL) && (TN->right != NULL))  // Two children.
      {	

	RecentCompares++;

         // Replace with smallest in right subtree.
        Tmp_Cell = Find_Min(TN->right);
        TN->element = Tmp_Cell->element;
        Remove(TN->element, TN->right);
      }
      else	// One child or zero children
      {
         Tmp_Cell = TN;
         if (TN->left == NULL )	// Only a right child or no children.
            TN = TN->right;
         else if (TN->right == NULL )	// Only a left child.
            TN = TN->left;
         delete Tmp_Cell;
         size--;
      }
   }
}



// operator<<
//    - parameters : Out - an ostream reference
//                 : outputBSTree - a BS tree to write to output
//    - return value : an ostream reference
//    - writes the given BS tree to the given output stream
template<class Etype>
ostream& operator<<(ostream& Out, const BSTree<Etype>& outputBSTree)
{
  BSTree<Etype> treeCopy=outputBSTree;  // Make a copy of the tree
  KeyPair<String, int> temp;

  // Remove KeyPairs from the BS tree copy until it is empty and
  //   output them into a file.
  while( !treeCopy.IsEmpty() )
  {
    treeCopy.Find_Min();
    temp = treeCopy.Last();
    Out << "1 " << temp << endl;    // Ouput a "1" to signify BS tree
    treeCopy.Remove(temp);
  }
 
  return Out;
}


// operator>>
//    - parameters : In - an istream reference
//                 : inputBSTree - a BS tree to read from input
//    - return value : an istream reference
//    - reads a BS tree from the given input stream
template<class Etype> 
istream& operator>>(istream& In, BSTree<Etype>& inputBSTree)
{
  KeyPair<String, int> temp;
  int type;

  // While there is still data in the input file and the data 
  //   corresponds to the BS tree (i.e. type flag == 1) then 
  //   continue to read in KeyPairs and insert them into the tree.
  while( (In >> type >> temp) && (type == 1) )
  {
    inputBSTree.Insert(temp);
  }

  // Clear the statistics
  inputBSTree.ClearStats();
  
  return In;
}

