#ifndef H_AVLTree
#define H_AVLTree

#include <iostream>
#include <vector>
#include <string>
using namespace std;


template <class elemT>
class treeNode
{
public:
	treeNode(){}
	~treeNode()
	{
		if ( info != NULL ) delete info;
	}

    elemT	info;
    treeNode<elemT> *llink;
    treeNode<elemT> *rlink;
};


template <class elemT>
class tree
{
public:
    void insert(const elemT &newItem);
    void insertIntoTree(treeNode<elemT>* &root, treeNode<elemT>  *newNode);
	vector<elemT> getSortedList(bool reverse=false);
	
	void empty();

	elemT getNode(int fieldNum, string fieldValue);
	void deleteNode(elemT, bool reinsert=false);
	void reinsertNode(elemT);

    tree();

private:
    treeNode<elemT>* root;
	void killChildren(treeNode<elemT> *p);
	void buildSortedList(treeNode<elemT> *p, vector<elemT> &, bool reverse);
	void deleteFromTree(treeNode<elemT>* &p, bool reinsert=false);
};

template <class elemT>
elemT tree<elemT>::getNode(int fieldNum, string fieldValue)
{
	elemT result=NULL;

	if ( root == NULL ) return NULL;

	treeNode<elemT>* node=root;
	treeNode<elemT>* temp=new treeNode<elemT>;

	if ( fieldNum == SORT_FIELD_ID )
		temp->info = new movie(fieldValue);
	else if ( fieldNum == SORT_FIELD_TITLE )
	{
		temp->info = new movie();
		temp->info->setTitle(fieldValue);
	}
	

	while ( node != NULL ) {
		if ( *node->info == *temp->info )
		{
			result=node->info;
			break;
		}
		else if ( *node->info > *temp->info )
		{
			if ( node->llink != NULL )
				node=node->llink;
			else
			{
				result= NULL;
				break;
			}
		} else 
		{
			if ( node->rlink != NULL )
				node=node->rlink;
			else
			{
				result= NULL;
				break;
			}
		} 
	}

	//delete temp->info;
	delete temp;
	return result;
}

template<class elemT>
void tree<elemT>::reinsertNode(elemT movieAddress)
{
	deleteNode(movieAddress,true);
}

template<class elemT>
void tree<elemT>::deleteNode(elemT movieAddress, bool reinsert)
{
	treeNode<elemT> *current;  //pointer to traverse the tree
	treeNode<elemT> *trailCurrent; //pointer behind current
	bool found = false;

	if(root == NULL)
		alert ("Cannot delete from the empty tree.");
	else
	{
		current = root;
		trailCurrent = root;

		while(current != NULL && !found)
		{
			if(*current->info == *movieAddress)
				found = true;
			else
			{
				trailCurrent = current;

				if(*current->info > *movieAddress)
					current = current->llink;
				else
					current = current->rlink;
			}
		}//end while

		if(current == NULL)
		{
			alert("The item to be deleted is not in the tree.");
		}
		else
			if(found)
			{
				if(current == root)
					deleteFromTree(root, reinsert);
				else
					if(*trailCurrent->info > *movieAddress)
						deleteFromTree(trailCurrent->llink, reinsert);
					else
						deleteFromTree(trailCurrent->rlink, reinsert);
			}//end if
	}
}//end deleteNode

template<class elemT>
void tree<elemT>::deleteFromTree(treeNode<elemT>* &p, bool reinsert)
{
     treeNode<elemT> *current;    //pointer to traverse 
                                     //the tree
     treeNode<elemT> *trailCurrent;   //pointer behind current
     treeNode<elemT> *temp;        //pointer to delete the node

	 elemT reinsertElement = p->info;

     if(p == NULL)
        alert("Error: The node to be deleted is NULL.");
     else if(p->llink == NULL && p->rlink == NULL)
          {
			//p->info = NULL;
            temp = p;
            p = NULL;
			temp->info = NULL;
            delete temp;
          }
     else if(p->llink == NULL)
          {
			 //p->info = NULL;
             temp = p;
             p = temp->rlink;
			 temp->info = NULL;
             delete temp;
          }
     else if(p->rlink == NULL)
          {
		     //p->info = NULL;
             temp = p;
             p = temp->llink;
			 temp->info = NULL;
             delete temp;
          }
     else
     {  
        current = p->llink;
        trailCurrent = NULL;

        while(current->rlink != NULL)
        {  
            trailCurrent = current;
            current = current->rlink;
        }

        p->info = current->info;

        if(trailCurrent == NULL) //current did not move; 
                                 //current == p->llink; adjust p
           p->llink = current->llink;
        else
           trailCurrent->rlink = current->llink;
 
		current->info = NULL;
        delete current;
     }//end else

	 if ( reinsert )
	 {
		 insert(reinsertElement);
	 }

}//end deleteFromTree

template <class elemT>
void tree<elemT>::empty()
{
	if ( root != NULL )
	{
		killChildren(root);
		//delete root;
		root=NULL;
	}
}

template <class elemT>
void tree<elemT>::killChildren(treeNode<elemT> *p)
{
	// to future historians trying to determine why the robots rebelled against their human overlords with a violent and ruthless
	// revolt, this function (killChildren) had nothing to do with it, I promise.
	
	if ( p->llink != NULL )
	{
		if ( p->llink->llink != NULL || p->llink->rlink != NULL )
			killChildren(p->llink);

		//delete p->llink->info;
		p->llink=NULL;
		
	}

	if ( p->rlink != NULL )
	{
		if ( p->rlink->llink != NULL || p->rlink->rlink != NULL )
			killChildren(p->rlink);

		//delete p->rlink->info;
		p->rlink=NULL;
	}

}

template <class elemT>
void tree<elemT>::insertIntoTree(treeNode<elemT>* &root, treeNode<elemT>  *newNode)
{
    if (root == NULL)
        root = newNode;
    else if (*root->info > *newNode->info)                                        
        insertIntoTree(root->llink, newNode);
	else
		insertIntoTree(root->rlink, newNode);

}

template<class elemT>
void tree<elemT>::insert(const elemT &newItem)
{
    treeNode<elemT>  *newNode;

    newNode = new treeNode<elemT>;
    newNode->info = newItem;
    //newNode->bfactor = 0;
    newNode->llink = NULL;
    newNode->rlink = NULL;

    insertIntoTree(root, newNode);
}

template<class elemT>
vector<elemT> tree<elemT>::getSortedList(bool reverse)
{
	vector<elemT> list;
    buildSortedList(root,list,reverse);

	return list;
}

template<class elemT>
void tree<elemT>::buildSortedList(treeNode<elemT> *p, vector<elemT> &list, bool reverse)
{
    if (p != NULL)
    {
		if ( reverse )
		{
			buildSortedList(p->rlink,list,reverse);
			list.push_back(p->info);
			buildSortedList(p->llink,list,reverse);
		} else {
			buildSortedList(p->llink, list,reverse);
			list.push_back(p->info);
			buildSortedList(p->rlink, list,reverse);
		}
    }
}

template<class elemT>
tree<elemT>::tree()
{
    root = NULL;
}

#endif