#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H


#include <string>
#include <iostream>
//#include "BinaryNode.h"

using namespace std;


template <typename Object>
class BinarySearchTree
{
	//TODO make virtual
	class BinaryNode
	{
		public:

	
		Object		data;
		BinaryNode* 	left;
		BinaryNode* 	right;
	
		//public:

		BinaryNode(Object dat = Object(), BinaryNode* ln = NULL, BinaryNode* rn = NULL) 
		: data(dat), left(ln), right(rn) {}

		~BinaryNode();
	
		int 		getHeight();
		int 		getSize();
	
		BinaryNode* duplicate();
	

	
		template <class Comparitor>
		Object* 	search (const Comparitor&) const;
	
		ostream& 	printInorder (bool tabbed, bool reverse) const;
		void 		printInorder (ostream& out, int depth, bool tabbed, bool reverse) const;
	
		void 		printSideways (int, bool) const;
		void 		printIndented (int, bool) const;

	
		//typedef BinaryNode<Object> Node;
		//typedef BinaryNode Node;
	
	

	};
	
	//typedef BinaryNode<Object> Node;
	typedef BinaryNode Node;
public:
	
	BinarySearchTree() : root(NULL) {};
	BinarySearchTree(const BinarySearchTree<Object> & rhs) : root(rhs.root->duplicate()) {};
	
	BinarySearchTree(const Object& rt) : root(new Node(rt)) {};
	virtual ~BinarySearchTree();
	
	virtual bool empty () const {return root == NULL;};
	virtual const BinarySearchTree<Object>& operator=(const BinarySearchTree<Object> &);
	
	virtual void makeEmpty();
	
	template <typename Comparitor>
	void remove (const Comparitor&);
	
	template <typename Comparitor>
	Object* search (const Comparitor&) const; // cant make virtual - no dynamic binding!!
	
	virtual Node* findMin (Node *) const;
	virtual Node* findMax (Node *) const;
	
	virtual int getSize() const;
	
	virtual bool insert (const Object&);

	virtual void printSideways (bool) const; // reverseinorder
	virtual void printIndented (bool) const; // preorder
	
	
protected:
	
	// Removal functions
	virtual void makeEmpty(Node *&);
	
	template <typename Comparitor> 
	void remove (const Comparitor&, Node *&);
	virtual void finaliseRemove (Node * & node); // used because remove can't be declared virtual
	
	virtual bool insert (const Object&, Node*&);
	
	virtual bool removeMin(Node *&);
	virtual bool removeMax(Node *&);



	Node *root;

};

#endif