#ifndef _BINARY_SEARCH_TREE_H_
#define _BINARY_SEARCH_TREE_H_



// -- INCLUDES ----------------------------------------------------------------
#include <iostream>
using namespace std;



// -- FUNCTORS ----------------------------------------------------------------



///////////////////////////////////////////////////////////////////////////////
// This is our abstract functor to act as a base class for any functors 
// someone wishes to create.
///////////////////////////////////////////////////////////////////////////JMMH
template <typename T>
class TraversalFunctor
{
public:
    virtual void handleNode(const T & data) = 0;
};



///////////////////////////////////////////////////////////////////////////////
// This is our generic output functor which can be used to print to an output
// stream.  The default output stream is cout
///////////////////////////////////////////////////////////////////////////JMMH
template <typename T>
class OutputTraversalFunctor : public TraversalFunctor<T>
{
    ostream & out;      // reference to the output stream of our choice

public:
    // set the ostream reference (cout by default)
    OutputTraversalFunctor(ostream & o=cout) : out(o)
    {
    }

    // for the handle method, we will just print the data + newline
    virtual void handleNode(const T & data)
    {
        out << data << endl;
    }
};



// BinarySearchTree class
template <typename T>
class BinarySearchTree
{
	// a node in the tree.  Public nested structure
	struct Node
	{
		T element;
		Node *left;
		Node *right;

		// constructor for the node
		Node(const T & theElement, Node *lt=0, Node *rt=0)
		  : element( theElement ), left( lt ), right( rt ) { }
	};

	// the root of the tree
    Node *root;

	// recursive inserts and removals
    void rInsert(const T & x, Node * & current);
    void rRemove(const T & x, Node * & current);

	// recursive find
    bool rFind(T & item, Node * current) const;

	// recursive clear
    void rClear(Node * current);

	// recursive traversal
    void rTraverse(Node *current, TraversalFunctor<T> & pHandler) const;

	// recursive copy
    Node * rCopy(Node * current);

	// function to find the smallest node down a subtree
	Node * rFindMin(Node * current) const;

  public:
	// default constructor
    BinarySearchTree(void);

	// copy constructor and assignment operator
    BinarySearchTree(const BinarySearchTree<T> & old);
    const BinarySearchTree & operator=(const BinarySearchTree<T> & old);

	// general copy function
	void copy(const BinarySearchTree<T> &old);
	
	// find function
    bool find(T & item) const;

	// true if tree empty
    bool empty() const;

	// traversals
    void traverse(TraversalFunctor<T> & pHandler=OutputTraversalFunctor<T>()) const;

	// nuke the tree
    void clear();

	// add and remove items into tree
    void insert(const T & newItem);
    void remove(const T & oldItem);

    virtual ~BinarySearchTree();
};



///////////////////////////////////////////////////////////////////////////////
// Construct the tree as empty.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
BinarySearchTree<T> :: BinarySearchTree()
     : root(0)
{
}



///////////////////////////////////////////////////////////////////////////////
// COnstruct the tree as a copy of another tree
///////////////////////////////////////////////////////////////////////////////
template <typename T>
BinarySearchTree<T> :: BinarySearchTree(const BinarySearchTree<T> & old)
     : root(0)
{ 
    copy(old);
}



///////////////////////////////////////////////////////////////////////////////
// Destructor for the tree.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
BinarySearchTree<T> :: ~BinarySearchTree()
{
    clear();
}



///////////////////////////////////////////////////////////////////////////////
// Insert x into the tree; duplicates are ignored.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: insert(const T & newItem)
{
	// call our recursive insert to add the item into the tree starting at
	// the root of our tree.
    rInsert(newItem, root);
}



///////////////////////////////////////////////////////////////////////////////
// Remove x from the tree. Nothing is done if x is not found.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: remove(const T & oldItem)
{
	// call our recursive remove to kill the item from the tree starting at
	// the root of our tree.
    rRemove(oldItem, root);
}



///////////////////////////////////////////////////////////////////////////////
// Find item x in the tree.
// Return the matching item or ITEM_NOT_FOUND if not found.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
bool BinarySearchTree<T> :: find(T & item) const
{
	// call the recursive find to start searching at the root.
    return rFind(item, root);
}



///////////////////////////////////////////////////////////////////////////////
// Make the tree empty.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: clear()
{
	// call recursive clear on the root
    rClear(root);
	root = 0;
}



///////////////////////////////////////////////////////////////////////////////
// Clone the tree
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: copy(const BinarySearchTree<T> &old)
{
	// nuke ourselves first
    clear();

	// then copy starting at root
	root = rCopy(old.root);
}



///////////////////////////////////////////////////////////////////////////////
// Return true if the tree is empty.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
bool BinarySearchTree<T> :: empty() const
{
    return root == 0;
}



///////////////////////////////////////////////////////////////////////////////
// Visit the tree contents in sorted order.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: traverse(TraversalFunctor<T> & tFunc) const
{
	// start a recursive traverse on the tree starting at root
	rTraverse(root, tFunc);
}



///////////////////////////////////////////////////////////////////////////////
// Assignment operator, make a deep copy if not same as self.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
const BinarySearchTree<T> & BinarySearchTree<T> :: operator=(const BinarySearchTree<T> & old)
{
	// make sure we're not assigning to self.
    if(this != &old)
    {
        copy(old);
    }

	// return self to allow chaining
    return *this;
}



///////////////////////////////////////////////////////////////////////////////
// Internal recursive method to insert into a subtree.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: rInsert(const T & newItem, Node * & current)
{
    if(current == 0)
        current = new Node(newItem);

    else if(newItem < current->element)
        rInsert(newItem, current->left);

    else 
        rInsert(newItem, current->right);
}



///////////////////////////////////////////////////////////////////////////////
// Internal recursive method to remove from a subtree.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: rRemove(const T & oldItem, Node * & current)
{
	// if this node exists
    if(current != 0)
	{
		// if its smaller than current, go left
		if(oldItem < current->element)
			rRemove(oldItem, current->left);

		// if its bigger than current, go right
		else if(current->element < oldItem)
			rRemove(oldItem, current->right);

		// otherwise its equal.  If there are both left and right subtrees
		// we need to find the smallest node on the right and promote it
		else if(current->left && current->right)
		{
			current->element = rFindMin(current->right)->element;
			rRemove(current->element, current->right);
		}

		// otherwise, only one subtree.  promote that subtree
		else
		{
			Node *oldNode = current;
			current = (current->left != NULL ) ? current->left : current->right;
			delete oldNode;
		}
	}
}



///////////////////////////////////////////////////////////////////////////////
// Internal method to find the smallest item in a subtree t.
// Return node containing the smallest item.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
BinarySearchTree<T>::Node * BinarySearchTree<T> :: rFindMin(Node * current) const
{
	// if there is no node, we return null
    if(!current)
        return 0;

	// if theres no left child, we're the smallest
    if(!current->left)
        return current;

	// otherwise, keep looking to the left, since we know right is only >=
    return rFindMin(current->left);
}



///////////////////////////////////////////////////////////////////////////////
// Internal recursive method to find an item in a subtree.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
bool BinarySearchTree<T> :: rFind(T & item, Node *current) const
{
	// if out of tree, return false
    if(!current)
        return false;

	// if smaller, go left
    else if(item < current->element)
        return rFind(item, current->left);

	// if bigger, go right
    else if(current->element < item)
        return rFind(item, current->right);

	// if equal, set to out param to return and return true
    else
	{
		item = current->element;
        return true;    // Match
	}
}



///////////////////////////////////////////////////////////////////////////////
// Internal recursive method to make subtree empty.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: rClear(Node * current)
{
    if(current)
    {
        rClear(current->left);
        rClear(current->right);
        delete current;
    }
}



///////////////////////////////////////////////////////////////////////////////
// Internal recursive method to print a subtree rooted at current in order.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
void BinarySearchTree<T> :: rTraverse(Node * current, TraversalFunctor<T> & pFxn) const
{
    if(current)
    {
        rTraverse(current->left, pFxn);
        pFxn.handleNode(current->element);
        rTraverse(current->right, pFxn);
    }
}



///////////////////////////////////////////////////////////////////////////////
// Internal recursive method to copy subtree.
///////////////////////////////////////////////////////////////////////////////
template <typename T>
BinarySearchTree<T>::Node * BinarySearchTree<T> :: rCopy(Node * current)
{
    if(!current)
        return 0;
    else
        return new Node(current->element, rCopy(current->left), rCopy(current->right));
}


#endif