#include <iostream>
#include <new>
#include "bstree.h"


template <typename SomeType>
// start of Delete(...)
// Recursive function that traverses the tree starting at treePtr to locate the data value to be removed
// Once located, DeleteNode is invoked to remove the value from the tree
// If tree is not empty and item is NOT present, throw NotFoundBSTree
void BSTree<SomeType>::Delete(BSTreeNode<SomeType>*& treePtr, SomeType& item)
{
    if(item < treePtr->data)
        Delete(treePtr->leftPtr, item);   // Look in left subtree
    else if(item > treePtr->data)
        Delete(treePtr->rightPtr, item); // Look in right subtree
    else if (treePtr == item) 
        DeleteNode(treePtr); // Node found; call DeleteNode
    else
        NotFoundBSTree();
}


template <typename SomeType>
void BSTree<SomeType>::DeleteNode(BSTreeNode<SomeType>*& treePtr)
// start of DeleteNode()
// Removes the node pointed to by treePtr from the tree
// Hint:  calls GetPredecessor and Delete
{
    SomeType data;
    BSTreeNode<SomeType>* tempPtr;

    if (treePtr->leftPtr==NULL)
    {
        treePtr=treePtr->rightPtr;
        delete tempPtr;
    }
    else if (treePtr->rightPtr==NULL)
    {
        treePtr = treePtr->leftPtr;
        delete tempPtr;
    }
    else
    {
        GetPredecessor(treePtr->leftPtr, data);
        treePtr->data = data;
        Delete(treePtr->leftPtr, data);
    }    
} // end of DeleteNode(...)

template <typename SomeType>
void BSTree<SomeType>::Insert(BSTreeNode<SomeType>*& ptr, SomeType item)
// Start of Insert(...)
// Recursive function that finds the correct position of item and adds it to the tree
// Throws FoundInBSTree if item is already in the tree
{
    if (ptr == item) FoundInBSTree();
    if (ptr==NULL)
    {
        ptr = new BSTreeNode<SomeType>;
        ptr->rightPtr = NULL;
        ptr->leftPtr = NULL;
        ptr->data = item;
    }
    else if (item < ptr->data)
        Insert(ptr->leftPtr, item);
    else
        Insert(item->rightptr, item);
    if (ptr ==item) FoundInBSTree();
}

template <typename SomeType>
void BSTree<SomeType>::Destroy(BSTreeNode<SomeType>*& ptr)
// Destroy()
// Recursively deallocates every node in the tree pointed to by ptr
{
    if (ptr==NULL)
    {
        Destroy(ptr->leftPtr);
        Destroy(ptr->rightPtr);
        delete ptr;
    }   
} // end of Destroy()

template <typename SomeType>
void BSTree<SomeType>::CopyTree(BSTreeNode<SomeType>*& copy, const BSTreeNode<SomeType>* originalTree)
// CopyTree()
// Recursively copies all data from original tree into copy
{
    if (originalTree == NULL)
        copy = NULL;
    else
    {
        copy = new BSTreeNode<typename SomeType>;
        copy->data = originalTree->data;
        CopyTree(copy->leftPtr, originalTree->leftPtr);
        CopyTree(copy->rightPtr, originalTree->rightPtr);
    }
}

template <typename SomeType>
SomeType BSTree<SomeType>::GetPredecessor(BSTreeNode<SomeType>* treePtr) const
// GetPredecessor()
// Finds the largest data value in the tree pointed to by treePtr and returns that data value
// as the functions return value
{
    while (treePtr->rightPtr != NULL)
        treePtr = treePtr->rightPtr;
    data = treePtr->data;
}

template <typename SomeType>
int BSTree<SomeType>::CountNodes(BSTreeNode<SomeType>* treePtr) const
// CountNodes()
// Recursive function that counts every node in the tree pointed to by treePtr and returns the
// count as the function return value
{
    if (treePtr == NULL)
        return 0;
    else
        return CountNodes(treePtr->leftPtr) + CountNodes(treePtr->rightPtr) + 1;
}

template <typename SomeType>
int BSTree<SomeType>::LevelCount(BSTreeNode<SomeType>* treePtr) const
// LevelCount()
// Recursive function that traverses the entire tree to determine the total number of levels in the tree
{
    if(treePtr->leftPtr == NULL && treePtr->rightPtr == NULL)
        return 0;

    int left = 0;
    if (treePtr->leftPtr != NULL)
        left = LevelCount(treePtr->leftPtr);

    int right = 0;
    if (treePtr->rightPtr != NULL)
        right = LevelCount(treePtr->rightPtr);
    
    return (max(left, right) + 1);
}

template <typename SomeType>
int BSTree<SomeType>::FindLevel(BSTreeNode<SomeType>* treePtr, SomeType item) const
// FindLevel()
// Recursive function that traverses the tree looking for item and returns the level where
// item was found
{
    int static level = 0;
    if (treePtr == NULL)
        return 0;

    int left = 0;
    if (treePtr->leftPtr != NULL && treePtr->data != item)
        left = LevelCount(treePtr->leftPtr);

    int right = 0;
    if (treePtr->rightPtr != NULL)
        right = LevelCount(treePtr->rightPtr);

    return (max(left, right));
}

template <typename SomeType>
BSTree<SomeType>::BSTree()
{
    rootPtr=NULL;
}


template <typename SomeType>
//start of BSTree(...)
BSTree<SomeType>::BSTree(const BSTree<SomeType>& someTree)
// BSTree()
// Copy constructor for BSTree
// Hint:  calls CopyTree
{
    CopyTree(someTree);
}

template <typename SomeType>
void BSTree<SomeType>::operator=(const BSTree<SomeType>& originalTree)
// operator=() 
// Overloaded assignment operator for BSTree.
// Hint:  calls CopyTree
{
    if (originalTree==this)
        return;

    Destroy(rootPtr);
    CopyTree(originalTree);
}

template <typename SomeType>
BSTree<SomeType>::~BSTree()						
  // ~BSTree()
  // Destructor deallocates all tree nodes
  // Hint:  calls the private helper function Destroy
{
    Destroy(rootPtr);
}

template <typename SomeType>
void BSTree<SomeType>::InsertItem(SomeType item)		
// InsertItem()
// Inserts item into BSTree;  if tree already full, throws FullBSTree exception
// If item is already in BSTree, throw FoundInBSTree exception
// Hint:  calls the private helper function Insert
{
    Insert(item);
}

template <typename SomeType>
SomeType BSTree<SomeType>::DeleteItem(SomeType item)	
// DeleteItem()
// Deletes item from BSTree if item is present AND returns object via function return value
// If tree is empty, throw the EmptyBSTree exception
// If tree is not empty and item is NOT present, throw NotFoundBSTree
// Hint:  calls the private helper function Delete
{
    if (rootPtr == NULL) EmptyBSTree();
    Delete(item);
}

template <typename SomeType>
void BSTree<SomeType>::MakeEmpty()
// MakeEmpty()
// Deallocates all BSTree nodes and sets root pointer to NULL
// Hint:  calls the private helper function Destroy
{
    Delete(rootPtr);
    rootPtr=NULL;
}

template <typename SomeType>
int BSTree<SomeType>::Size() const
// Size()
// Returns total number of data values stored in tree
{
    return CountNodes(rootPtr);
}

template <typename SomeType>
bool BSTree<SomeType>::IsFull() const
{
    BSTreeNode<SomeType>* location;
    try
    {
        location = new BSTreeNode<SomeType>;
        delete location;
        return false;
    }
    catch( bad_alloc )
    {
        return true;
    }
}

template <typename SomeType>
bool BSTree<SomeType>::IsEmpty() const
{
    if (rootPtr == NULL) return true;
    return false;
}

template <typename SomeType>
SomeType BSTree<SomeType>::Min() const
{
    if (rootPtr == NULL) EmptyBSTree();

    int res = rootPtr->data;
    BSTreeNode<SomeType>* current;
    while (current->leftPtr != NULL)
    {
        current = current->leftPtr;
    }
    return(current->leftPtr);   
}

template <typename SomeType>
SomeType BSTree<SomeType>::Max() const
{
    if (rootPtr == NULL) EmptyBSTree();

    BSTreeNode<SomeType>* current;
    while (current->rightPtr != NULL)
    {
        current = current->rightPtr;
    }
    return(current->rightPtr);
}

template <typename SomeType>
int BSTree<SomeType>::TotalLevels() const
// TotalLevels()
// Returns the maximum level value for current tree contents
// Levels are numbered 0, 1, ..., N-1.  This function returns N
// Throws EmptyBSTree if empty
// Hint:  calls the private helper function LevelCount
{
    if (rootPtr == NULL) EmptyBSTree();
    int level = LevelCount(rootPtr);
    return level+1;
}

template <typename SomeType>
int BSTree<SomeType>::Level(SomeType item) const
// Level()
// Returns the level within the BSTree at which the value item is found
// If tree is empty, throws EmptyBSTree
// If tree is not empty and item is not found, throws NotFoundBSTree
// Hint:  calls the private helper funtion FindLevel
{
    if (rootPtr == NULL) EmptyBSTree();
    return  FindLevel(rootPtr, item);
}