// templated binary search tree class,
//
// Dave Reed		11/1/04
//
// CONSTRUCTION:  (1) with no initializer, or
//                (2) with BinarySearchTree (copy constructor)
//
//   note: Item to be stored must have a default constructor
//
// ******************** PUBLIC OPERATIONS ******************************
//   bool IsStored(const Item & desiredItem) -- returns true if desiredItem
//                                              is already stored
//   void Insert(const Item & desiredItem)   -- adds desiredItem to tree
//   void Remove(const Item & desiredItem)   -- removes desiredItem from tree
//                                              (assumes already stored)
//   void Display()                          -- displays contents of tree
//                                              in order
//
//   operator =                              -- assignment operator
//

#ifndef _BSTREE_H
#define _BSTREE_H

#include <iostream>
#include "BinaryNode.h"
using namespace std;

template <class Item>
class BinarySearchTree
{
  public:
    BinarySearchTree()
    // default constructor
    // postcondition: tree initialized to be empty
    {
        root = NULL;
    }

    BinarySearchTree(const BinarySearchTree<Item> & tree)
    // copy constructor
    // precondition : Item supports assignment
    // postcondition: makes a copy of tree
    {
        root = copyTree(tree.root);
    }

    ~BinarySearchTree()
    // destructor
    // postcondition: dynamically allocated storage freed
    {
        deleteTree(root);
    }

    bool isStored(const Item & desiredItem) const
    // precondition : Item supports relational operators (==, <, <=, ...)
    // postcondition: returns true if desiredItem stored in tree, else false
    {
        return searchTree(root, desiredItem);
    }

    void insert(const Item & desiredItem)
    // precondition : Item supports assignment, relational operators
    // postcondition: desiredItem is inserted into correct location
    {
        insertIntoTree(root, desiredItem);
    }

    void remove(const Item & desiredItem)
    // precondtion  : desired stored in tree, Item supports relational ops
    // postcondition: occurrence of desiredItem is removed from tree
    //                Note: if duplicates, only one occurrence is removed
    {
        removeFromTree(root, desiredItem);
    }

    void display(ostream & ostr = cout) const
    // precondition : Item supports "<<" operator
    // postcondition: displays contents of tree via inorder traversal
    {
        inOrder(root, ostr);
    }

    BinarySearchTree & operator=(const BinarySearchTree<Item> & tree)
    // overload assignment
    // precondition: Item supports assignment
    // postcondition: self is assigned tree
    {
        if (this != &tree)      // don't assign to self!
        {
            deleteTree(root);
            root = copyTree(tree.root);
        }
        return *this;
    }

  private:
    BinaryNode<Item> * root;

    BinaryNode<Item> * copyTree(BinaryNode<Item> * rootPtr) 
    // postcondition: returns pointer to copy of tree w/ rootPtr
    {
        if (rootPtr == NULL) {
            return NULL;
        }
        else {
            return new BinaryNode<Item>(rootPtr->GetData(), 
				                        copyTree(rootPtr->getLeft()), 
								        copyTree(rootPtr->getRight()));
        }
    }

    void deleteTree(BinaryNode<Item> * rootPtr) 
    // postcondition: deletes contents of tree w/ rootPtr
    {
        if (rootPtr != NULL) {
            deleteTree(rootPtr->getLeft());
            deleteTree(rootPtr->getRight());
            delete rootPtr;
        }
    }

    bool searchTree(BinaryNode<Item> * rootPtr, const Item & desired) const
    // postcondition: returns true if desired in tree w/ rootPtr
    {
        if (rootPtr == NULL) {
            return false;
        }
        else if (desired == rootPtr->getData()) {
            return true;
        }
        else if (desired < rootPtr->getData()) {
            return searchTree(rootPtr->getLeft(), desired);
        }
        else {
            return searchTree(rootPtr->getRight(), desired);
        }
    }

    void insertIntoTree(BinaryNode<Item> * & rootPtr, const Item & desired)
    // postcondition: inserts desired into tree w/ rootPtr
    {

        if (rootPtr == NULL) {
            rootPtr = new BinaryNode<Item>(desired, NULL, NULL);
        }
        else if (rootPtr->getData() >= desired) {
            insertIntoTree(rootPtr->getLeft(), desired);
        }
        else {
            insertIntoTree(rootPtr->getRight(), desired);
        }
    }

    static Item findLargest(BinaryNode<Item> * rootPtr) 
    // precondition : rootPtr != NULL
    // postcondition: retruns largest value in tree w/ rootPtr
    {
        while (rootPtr->getRight() != NULL) {
            rootPtr = rootPtr->getRight();
        }
        return rootPtr->getData();
    }

    void removeFromTree(BinaryNode<Item> * & rootPtr, const Item & desired)
    // postcondition: removes desired from tree w/ rootPtr
    {
        if (desired == rootPtr->getData()) {
            if (rootPtr->getLeft() == NULL) {
                BinaryNode<Item> * temp = rootPtr;
                rootPtr = rootPtr->getRight();
                delete temp;
            }
            else {
                rootPtr->setData(findLargest(rootPtr->getLeft()));
                removeFromTree(rootPtr->getLeft(), rootPtr->getData());
            }
        }
        else if (desired < rootPtr->getData()) {
            removeFromTree(rootPtr->getLeft(), desired);
        }
        else {
            removeFromTree(rootPtr->getRight(), desired);
        }
    }

    void inOrder(BinaryNode<Item> * rootPtr, ostream & ostr) const
    // postcondition: displays contents of tree w/ rootPtr
    {
        if (rootPtr != NULL) {
            inOrder(rootPtr->getLeft(), ostr);
            ostr << rootPtr->getData() << endl;
            inOrder(rootPtr->getRight(), ostr);
        }
    }

};

#endif