#ifndef BINARY_SEARCH_TREE_CLASS
#define BINARY_SEARCH_TREE_CLASS

#ifndef NULL
#include <cstddef>
#endif  // NULL

#include <iomanip>		// for setw()
#include <strstream>		// for format conversion
#include <string>			// node data formatted as a string
#include <queue>
#include <utility>		// pair class

#include "d_except.h"	// exception classes

using namespace std;

// declares a binary search tree node object
template <typename T>
class stnode
{
   public:
		// stnode is used to implement the binary search tree class
		// making the data public simplifies building the class functions

		T nodeValue;
			// node data
		stnode<T> *left, *right, *parent;
		// child pointers and pointer to the node's parent

      // constructor
		stnode (const T& item, stnode<T> *lptr = NULL, 
              stnode<T> *rptr = NULL, stnode<T> *pptr = NULL):
				nodeValue(item), left(lptr), right(rptr), parent(pptr)
		{}
};

// objects hold a formatted label string and the level,column
// coordinates for a shadow tree node
class tnodeShadow
{
	public:
		string nodeValueStr;	// formatted node value
		int level,column;
		tnodeShadow *left, *right;

		tnodeShadow ()
		{}
};

template <typename T>
class stree
{
	public:

// include the iterator nested classes
#include "d_stiter.h"

		stree();
			// constructor. initialize root to NULL and size to 0
		stree(T *first, T *last);
			// constructor. insert the elements from the pointer
			// range [first, last) into the tree
		stree(const stree<T>& tree);
			// copy constructor
		~stree();
			// destructor
		stree<T>& operator= (const stree<T>& rhs);
			// assignment operator

		iterator find(const T& item);
			// search for item. if found, return an iterator pointing
			// at it in the tree; otherwise, return end()
		const_iterator find(const T& item) const;
			// constant version

		int empty() const;
			// indicate whether the tree is empty
		int size() const;
			// return the number of data items in the tree

		pair<iterator, bool> insert(const T& item);
			// if item is not in the tree, insert it and
			// return a pair whose iterator component points
			// at item and whose bool component is true. if item
			// is in the tree, return a pair whose iterator
			// component points at the existing item and whose
			// bool component is false
			// Postcondition: the tree size increases by 1 if item
			// is not in the tree

		int erase(const T& item);
			// if item is in the tree, erase it and return 1;
			// otherwise, return 0
			// Postcondition: the tree size decreases by 1 if
			// item is in the tree

		void erase(iterator pos);
			// erase the item pointed to by pos.
			// Preconditions: the tree is not empty and pos points
			// to an item in the tree. if the tree is empty, the
			// function throws the underflowError exception. if the
			// iterator is invalid, the function throws the referenceError
			// exception.
			// Postcondition: the tree size decreases by 1

		void erase(iterator first, iterator last);
			// erase all items in the range [first, last).
			// Precondition: the tree is not empty. if the tree
			// is empty, the function throws the underflowError
			// exception.
			// Postcondition: the size of the tree decreases by
			// the number of elements in the range [first, last)

		iterator begin();
			// return an iterator pointing to the first item
			// inorder
		const_iterator begin() const;
			// constant version
		iterator end();
			// return an iterator pointing just past the end of
			// the tree data
		const_iterator end() const;
			// constant version

		void displayTree(int maxCharacters);
			// tree display function. maxCharacters is the
			// largest number of characters required to draw
			// the value of a node

	private:
		stnode<T> *root;
			// pointer to tree root
		int treeSize;
			// number of elements in the tree

		stnode<T> *getSTNode(const T& item,
									stnode<T> *lptr,stnode<T> *rptr, stnode<T> *pptr);
			// allocate a new tree node and return a pointer to it.
			// if memory allocation fails, the function throws the
			// memoryAllocationError exception

		stnode<T> *copyTree(stnode<T> *t);
			// recursive function used by copy constructor and assignment
			// operator to assign the current tree as a copy of another tree

		void deleteTree(stnode<T> *t);
			// recursive function used by destructor and assignment
			// operator to delete all the nodes in the tree

		stnode<T> *findNode(const T& item) const;
			// search for item in the tree. if it is in the tree,
			// return a pointer to its node; otherwise, return NULL.
			// used by find() and erase()

		tnodeShadow *buildShadowTree(stnode<T> *t, int level, int& column);
			// recursive function that builds a subtree of the shadow tree
			// corresponding to node t of the tree we are drawing. level is the
			// level-coordinate for the root of the subtree, and column is the
			// changing column-coordinate of the tree nodes

		void deleteShadowTree(tnodeShadow *t);
			// remove the shadow tree from memory after displayTree()
			// displays the binary search tree
};

template <typename T>
stnode<T> *stree<T>::getSTNode(const T& item,
			stnode<T> *lptr,stnode<T> *rptr, stnode<T> *pptr)
{
	stnode<T> *newNode;

	// initialize the data and all pointers
	newNode = new stnode<T> (item, lptr, rptr, pptr);
	if (newNode == NULL)
		throw memoryAllocationError("stree: memory allocation failure");

	return newNode;
}

template <typename T>
stnode<T> *stree<T>::copyTree(stnode<T> *t)
{
	stnode<T> *newlptr, *newrptr, *newNode;

	// if tree branch NULL, return NULL
	if (t == NULL)
		return NULL;
  
	// copy the left branch of root t and assign its root to newlptr
	newlptr = copyTree(t->left);

	// copy the right branch of tree t and assign its root to newrptr
	newrptr = copyTree(t->right);

	// allocate storage for the current root node, assign
	// its value and pointers to its left and right subtrees.
	// the parent pointer of newNode is assigned when
	// newNode's parent is created. if newNode is root,
	// NULL is the correct value for its parent pointer
	newNode = getSTNode(t->nodeValue, newlptr, newrptr, NULL);

	// the current node is the parent of any subtree that
	// is not empty
	if (newlptr != NULL)
		newlptr->parent = newNode;
	if (newrptr != NULL)
		newrptr->parent = newNode;

	return newNode;
}

// delete the tree stored by the current object
template <typename T>
void stree<T>::deleteTree(stnode<T> *t)
{
	// if current root node is not NULL, delete its left subtree,
	// its right subtree and then the node itself
	if (t != NULL)
	{
		deleteTree(t->left);
		deleteTree(t->right);
		delete t;
	}
}

// search for data item in the tree. if found, return its node
// address; otherwise, return NULL
template <typename T>
stnode<T> *stree<T>::findNode(const T& item) const
{   
	// cycle t through the tree starting with root
	stnode<T> *t = root;

	// terminate on on empty subtree
	while(t != NULL && !(item == t->nodeValue))
		if (item < t->nodeValue)
			t = t->left;
		else 
			t = t->right;

	// return pointer to node; NULL if not found
	return t;
}

template <typename T>
stree<T>::stree(): root(NULL),treeSize(0)
{}

template <typename T>
stree<T>::stree(T *first, T *last): root(NULL),treeSize(0)
{
	T *p = first;

	// insert each item in [first, last) into the tree
	while (p != last)
	{
		insert(*p);
		p++;
	}
}

template <typename T>
stree<T>::stree(const stree<T>& tree): treeSize(tree.treeSize)
{
	// copy tree to the current object
	root = copyTree(tree.root);
}

template <typename T>
stree<T>::~stree()
{
	// erase the tree nodes from memory
	deleteTree(root);

	// tree is emtpy
	root = NULL;
	treeSize = 0;
}

template <typename T>
stree<T>& stree<T>::operator= (const stree<T>& rhs)
{
	// can't copy a tree to itself
	if (this == &rhs)
		return *this;

	// erase the existing tree nodes from memory
	deleteTree(root);

	// copy tree rhs into current object
	root = copyTree(rhs.root);

	// set the tree size
	treeSize = rhs.treeSize;

	// return reference to current object
	return *this;
}

template <typename T>
stree<T>::iterator stree<T>::find(const T& item)
{
	stnode<T> *curr;

	// search tree for item
	curr = findNode (item);

	// if item found, return const_iterator with value current;
	// otherwise, return end()
	if (curr != NULL)
		return iterator(curr, this);
	else
		return end();
}

template <typename T>
stree<T>::const_iterator stree<T>::find(const T& item) const
{
	stnode<T> *curr;

	// search tree for item
	curr = findNode (item);

	// if item found, return const_iterator with value current;
	// otherwise, return end()
	if (curr != NULL)
		return const_iterator(curr, this);
	else
		return end();
}

template <typename T>
int stree<T>::empty() const
{
	return root == NULL;
}

template <typename T>
int stree<T>::size() const
{
	return treeSize;
}

template <typename T>
pair<stree<T>::iterator, bool> stree<T>::insert(const T& item)
{