#ifndef TREE_H
#define TREE_H

#include <string>
using namespace std;


class Node
	{
		public:
   			Node *leftPtr;   // pointer to left subtree
  			Node *rightPtr;   // pointer to right subtree
			long idno;
			char name[15];
			char surname[15];
			char payment[5];
			int days;
			char roomType[10];
			int roomNo;
			char purpose[10];
   			Node(){leftPtr = NULL; rightPtr= NULL;}
			Node(long, char[], char[], char[],int, char[], int, char[]);
			long getID() const { return idno; }
  	  		void setData(long, char[], char[], char[],int, char[], int, char[]);
	};
void Node::setData(long id,	char fname[], char lname[],	char pay[],	int day, 
					    char rmType[],	int rmNo, char reason[])
	{
		idno = id;
		strcpy(name, fname);
		strcpy(surname, lname);
		strcpy(payment, pay);
		days = day;
		strcpy(roomType, rmType);
		roomNo = rmNo;
		strcpy(purpose, reason);
	}

Node::Node(long id,	char fname[], char lname[],	char pay[],	int day, char rmType[],int rmNo, char reason[])
	{
		idno = id;
		strcpy(name, fname);
		strcpy(surname, lname);
		strcpy(payment, pay);
		days = day;
		strcpy(roomType, rmType);
		roomNo = rmNo;
		strcpy(purpose, reason);
		leftPtr = NULL;
  		rightPtr = NULL;

	}


class Tree
	{
		private:
			Node *rootPtr;

			// utility functions  - These helper functions take the root address
			//                      of the tree (or sub tree)as their parameter
			void insertNodeHelper( Node **, long, char[], char[], char[],int, char[], int, char[]);
			string preOrderHelper( Node * ) const;
			string inOrderHelper( Node * ) const;
			string postOrderHelper( Node * ) const;
			string deleteNodeHelper(Node *&, long);

		public:
			Tree(){ rootPtr = NULL; };
			void insertNode( long, char[], char[], char[],int, char[], int, char[]);
			string preOrderTraversal() const;
			string inOrderTraversal() const;
			string postOrderTraversal() const;
			void removeMin();
			string deleteNode(long);
			Node* deleteMin(Node *&);
	};


void Tree::insertNode( long id,	char fname[], char lname[],	char pay[],	int day, char rmType[],
					   int rmNo, char reason[] )
   {
   		insertNodeHelper( &rootPtr, id, fname, lname, pay, day, rmType, rmNo, reason);
   }


// This function receives a POINTER to a pointer so the POINTER can be modified.
void Tree::insertNodeHelper( Node **ptr, long id,	char fname[], char lname[],	char pay[],	int day, 
					    char rmType[], int rmNo, char reason[] )
	{
   		if ( *ptr == NULL )                    // tree is empty
   			{
	      		*ptr = new Node( id, fname, lname, pay, day, rmType, rmNo, reason );
   			}
		else                              // tree is not empty
			if ( id < (( *ptr )->idno ))
      			insertNodeHelper( &( (*ptr)->leftPtr ), id, fname, lname, pay, day, rmType, rmNo, reason );
			else
   				if ( id > (( *ptr )->idno ))
      				insertNodeHelper( &( ( *ptr )->rightPtr ), id, fname, lname, pay, day, rmType, rmNo, reason );
	}

string Tree::preOrderTraversal() const
   {
   	string str = preOrderHelper( rootPtr );
	return str;

   }


string Tree::preOrderHelper(Node *ptr ) const
	{
		string str;

   		if ( ptr != NULL )
      		{
				char id[10], dayStr[10], room[10];
				
				itoa(ptr->idno, id, 10);
				itoa(ptr->days, dayStr, 10);
				itoa(ptr->roomNo, room, 10);
				
    			str.append(id);
				str.append("  ");
				str.append(ptr->name);
				if (strlen(ptr->name) < 7)
					str.append("        \t");
				else str.append("  \t");
				str.append(ptr->surname);
				if (strlen(ptr->surname) < 9)
					str.append("       \t");
				else
				str.append("\t");
				str.append(ptr->payment);
				str.append("\t");
				str.append(dayStr);
				str.append("\t");
				str.append(ptr->roomType);
				str.append("\t");
				str.append(room);
				str.append("\t\t");
				str.append(ptr->purpose);
				str.append("\n");

  				str.append(preOrderHelper( ptr->leftPtr ));
      			str.append(preOrderHelper( ptr->rightPtr ));
		   }
		return str;
	}

string Tree::inOrderTraversal() const
   {
   	string str = inOrderHelper( rootPtr );
	return str;
   }

string Tree::inOrderHelper(Node *ptr ) const
	{
		string str;
   		if ( ptr != NULL )
      		{
    			char id[10], dayStr[10], room[10];
 				itoa(ptr->idno, id, 10);
				itoa(ptr->days, dayStr, 10);
				itoa(ptr->roomNo, room, 10);
 				
				str.append(inOrderHelper( ptr->leftPtr ));		
    			str.append(id);
				str.append("  ");
				str.append(ptr->name);
				if (strlen(ptr->name) < 7)
					str.append("        \t");
				else str.append("  \t");
				str.append(ptr->surname);
				if (strlen(ptr->surname) < 9)
					str.append("       \t");
				else
				str.append("\t");
				str.append(ptr->payment);
				str.append("\t");
				str.append(dayStr);
				str.append("\t");
				str.append(ptr->roomType);
				str.append("\t");
				str.append(room);
				str.append("\t\t");
				str.append(ptr->purpose);
				str.append("\n");

				str.append(inOrderHelper( ptr->rightPtr ));
		   }
		return str;
	}


string Tree::postOrderTraversal() const
   {
   		string str = postOrderHelper( rootPtr );
		return str;
   }


string Tree::postOrderHelper( Node *ptr ) const
	{
		string str;
   		if ( ptr != NULL )
      		{
				char id[10], dayStr[10], room[10];
				
				itoa(ptr->idno, id, 10);
				itoa(ptr->days, dayStr, 10);
				itoa(ptr->roomNo, room, 10);
				
				str.append(postOrderHelper( ptr->leftPtr ));		
				str.append(postOrderHelper( ptr->rightPtr ));		
    			str.append(id);
				str.append("  ");
				str.append(ptr->name);
				if (strlen(ptr->name) < 7)
					str.append("        \t");
				else str.append("  \t");
				str.append(ptr->surname);
				if (strlen(ptr->surname) < 9)
					str.append("       \t");
				else
				str.append("\t");
				str.append(ptr->payment);
				str.append("\t");
				str.append(dayStr);
				str.append("\t");
				str.append(ptr->roomType);
				str.append("\t");
				str.append(room);
				str.append("\t\t");
				str.append(ptr->purpose);
				str.append("\n");
		   }
		return str;

	}


//Delete the minimum value of a "sub-tree"
Node* Tree::deleteMin(Node * &rt)
	{
//		assert(rt != NULL);			  // There must be a node to delete

		if (rt->leftPtr != NULL)     // Continue left
		    return deleteMin(rt->leftPtr);
		else            				  // Found it
    		{
				Node* temp = rt;
				rt = rt->rightPtr;
				return temp;
			}

   }


//Find the absolute minimum value in the tree and delete it.
void Tree::removeMin()
	{
		deleteMin(rootPtr);	// There must be a node to delete
    }



string Tree::deleteNode(long val)
	{
    	string str = deleteNodeHelper( rootPtr, val );
		return str;
    }



string Tree::deleteNodeHelper(Node*& rt, long val)
	{
		string str;
		char id[10], dayStr[10], room[10];

		if (rt != NULL)
			{
				if (val < (rt->getID()))  					// Check left
					str.append(deleteNodeHelper(rt->leftPtr, val));
					else if (val > (rt->getID())) 			// Check right
							str.append(deleteNodeHelper(rt->rightPtr, val));
						else             							// Found it: remove it
				       		{
								Node* temp = rt;
								Node* tempData = rt;                //Hold the data to display in the textbox later
							    if (rt->leftPtr == NULL)			// Only a right child so point to right
								      rt = rt->rightPtr;   			      
							    else if (rt->rightPtr == NULL) 		// Only a left child so point to left
									      rt = rt->leftPtr;    		      
									   else
							   				{   // Both children are non-empty. Replace with min in right subtree
										      temp = deleteMin(rt->rightPtr);
										      rt->setData( temp->idno, temp->name, temp->surname, temp->payment, 
												           temp->days, temp->roomType, temp->roomNo, temp->purpose);
											}

	 							itoa(tempData->idno, id, 10);
								itoa(tempData->days, dayStr, 10);
								itoa(tempData->roomNo, room, 10);
	 				
    							str.append(id);
								str.append("  ");
								str.append(tempData->name);
								if (strlen(tempData->name) < 7)
									str.append("        \t");
								else str.append("  \t");
								str.append(tempData->surname);
								if (strlen(tempData->surname) < 9)
									str.append("       \t");
								else
									str.append("\t");
								str.append(tempData->payment);
								str.append("\t");
								str.append(dayStr);
								str.append("\t");
								str.append(tempData->roomType);
								str.append("\t");
								str.append(room);
								str.append("\t\t");
								str.append(tempData->purpose);
								str.append("\n");

							    delete temp;         // Return node to free store
						  }
			}
		return str;
	}


#endif