/*----------------------------------------------------------------*\
	   CS130 Assignment #2

	   OOP23.CPP - Implementation of 2-3-TREE

|
|    An Object Oriented Approach to Implementation Of 2-3-TREE
|
\*----------------------------------------------------------------*/


/*----------------------------------------------------------------*\
|			         	  CLASSES USED
|                      ------------------
|	 Instance Classes :
						Data   (For storing relevant info about each entry)
						Node
						Tree_23

	 Static function Classes :
						Interface ( Interface handling functions )

\*----------------------------------------------------------------*/

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum {LEFT,MIDDLE,RIGHT};
enum {ADDING,SPLITTING};
enum {SEARCH,DISPLAY};

const int MAXTREES=20;
const int MAXWORDLENGTH=80;

//___________Interface class to handle the interface____________
class Interface
{
public:
	static void Clear();
	static void DisplayCenter(char *s);
	static void DisplayLine(char *s);
	static void PressEnter();
	static void Leavespace(int i);
	static int GetInt(char* message,int ll);
	static long GetLong(char* message,long ll);
	static void GetString(char* buffer,char* message);

	static void Error(char* s)
	{
		cout << endl << "Error : " << s << endl;
	}

};

void Interface::Clear()
{
	for(int i=0;i<25;i++) cout << endl;
}

void Interface::DisplayCenter(char *s)
{
	int i=strlen(s);
	Leavespace((80-i)/2);
	cout << s;
}

void Interface::DisplayLine(char *s)
{
	for (int i=0;i<(80/strlen(s));i++) cout << s;
}


void Interface::PressEnter()
{
	cout << endl << endl << "Press Enter to continue....";
	getchar();

}

void Interface::Leavespace(int i)
{
	for(int j=0;j<i;j++) cout << " ";
}

int Interface::GetInt(char* message,int ll)
	{
		char buffer[11];
		int i=ll-1;
		while(i<ll)
		{
			cout << message;
			cin.getline(buffer,11);
			i=atoi(buffer);
			if(i<ll) Error("Please enter a valid number.");
		}
		return i;
	}


long Interface::GetLong(char* message,long ll)
	{
		char buffer[11];
		long i=ll-1;
		while(i<ll)
		{
			cout << message;
			cin.getline(buffer,11);
			i=atol(buffer);
			if(i<ll) Error("Please enter a valid number.");
		}
		return i;
	}

void Interface::GetString(char* buffer,char* message)
{
	buffer[0]=0;
	while(strlen(buffer)==0)
	{
		cout << message;
		cin.getline(buffer,MAXWORDLENGTH);
		if(strlen(buffer)==0)
			Error("Please enter a valid string argument.");
	}

}


//-------------------------------------
//       CLASS    DATA
//_____________________________________
class Data
{
private:
	char* name;

public:
	Data()
	{
		name=NULL;
	}

	~Data()
	{

		delete [] name;
		name=NULL;
	}

	void GetData()
	{
		char buffer[ MAXWORDLENGTH + 1 ];
		Interface::GetString(buffer,"\nPlease Enter the name :");
		name=new char[strlen(buffer)+1];
		strcpy(name,buffer);
	}

	void Display()
	{
		cout << "\nThe name is :" << name;
	}

	void operator = (Data& d)
	{
		if(&d==this) return;

		//_________copy the name into me________
		if(d.name!=NULL)
		{
			delete [] name;
			name = new char[strlen(d.name)+1];
			strcpy(name,d.name);
		}
		else
		{
			delete [] name;
			name=NULL;
		}
	}


};

//-------------------------------------------------------
//           C L A S S      N O D E
//_______________________________________________________

//__________Make a template for ( parameter of key may be any type )____

template <class T>
class Node
{
private:
	T leftkey,rightkey;
	Data* data;
	//___________3 children pointers____________
	Node* children[3];
	Node* parent;
	T lowest;

public:

	//____________Constructor____________
	Node(T lk,T rk,Data* d,Node* lc,Node* mc,Node* rc,Node* p,T l)
	{
		leftkey=lk;
		rightkey=rk;

		if(d==NULL)
			data=d;
		else
		{
			data=new Data;
			*data=*d; // Call Assignment operator
		}

		children[LEFT]=lc;
		children[MIDDLE]=mc;
		children[RIGHT]=rc;

		parent=p;

		lowest=l;
	}

	//_____________Deconstructor________________
	~Node()
	{
		if(data!=NULL)
		{
			delete data;
			data=NULL;
		}
	}
	//_________________INTERFACE FUNCTIONS__________________

	//_______Returns the new root after addition___NULL if no change_____

	Node* AddElement(T lk,T rk,Data* d,Node* lc,Node* mc,Node* rc,Node* p,T l,int mode=ADDING);
	Node* DeleteElement(T lk);

	int SearchElement(T k,int mode=SEARCH);
	void Display();


//_____________IMPLEMENTATION FUNCTIONS__________________

	void Info()
	{
		cout << endl <<leftkey << "  " << rightkey << "  " << lowest <<  " p : " << parent << " me : " << this;
	}


	//_________Set all my children's parent field to myself__________
	void Set_mychildren()
	{
		if(children[LEFT]!=NULL) children[LEFT]->Set_parent(this);
		if(children[MIDDLE]!=NULL) children[MIDDLE]->Set_parent(this);
		if(children[RIGHT]!=NULL) children[RIGHT]->Set_parent(this);
	}

	//_______Adjust leftkey , rightkey , lowest params_____
	//_______according to children_____
	void Set_myparameters()
	{
		leftkey=children[MIDDLE]->lowest;

		if(children[RIGHT]!=NULL)
			rightkey=children[RIGHT]->lowest;
		else
			rightkey=0;

		lowest=children[LEFT]->lowest;
	}

	//_______Rearranges children in ascending order_____
	//______ir-respective of placement of children_____
	//_____( including intervening NULLS)_______
	void Rearrange()
	{
		Node<T>* temp[3];
		int j=0,i;
		for(i=0;i<=2;i++)
		{
			if(children[i]!=NULL)
			{
				temp[j]=children[i];
				j++;
			}
		}
		SortLeafs(temp,j);
		for(i=0;i<j;i++) children[i]=temp[i];
		for(i=j;i<=2;i++) children[i]=NULL;
	}



	void Set_parent(Node* p)
	{
		parent=p;
	}


	T Return_lowest()
	{
		return lowest;
	}

	Data* Return_data()
	{
		return data;
	}


	//________Return no of children i have_______
	int Return_childrenno()
	{
		for(int i=0;i<=2;i++)
		{
			if(children[i]==NULL) return i;
		}
		return 3;
	}

	//__________Tells if i am leaf or not_________________
	int IsLeaf()
	{
		if (children[LEFT]==NULL && parent!=NULL) return 1; else return 0;
	}

private:
	void SortLeafs(Node** nodearray,int n);
	void SwapPointers(Node* &p1,Node* &p2);
};

//-------------------------------------------------------
//           Node Class  Functions
//_______________________________________________________

template <class T>
Node<T>* Node<T>::AddElement(T lk,T rk,Data* d,Node<T>* lc,Node<T>* mc,Node<T>* rc,Node<T>* p,T l,int mode)
{

	//__________Check special Cases if I am root________

	if (parent==NULL && mode==ADDING) // _____Unique property of root
	{
		if(children[LEFT]==NULL) //___Left child is NULL___0 children yet
		{
			children[LEFT]=new Node<T>(lk,0,d,NULL,NULL,NULL,this,lk);

			leftkey=children[LEFT]->Return_lowest()+1;
			lowest=children[LEFT]->Return_lowest();

			return NULL;
		}
		else if(children[MIDDLE]==NULL)
		{
			Node<T>* temp=new Node<T>(lk,0,d,NULL,NULL,NULL,this,lk);
			Node<T>* array[2]={children[LEFT],temp};
			SortLeafs(array,2);

			//____Redistribute___
			children[LEFT]=array[0];
			children[MIDDLE]=array[1];

			leftkey=children[MIDDLE]->Return_lowest();
			rightkey=0;
			lowest=children[LEFT]->Return_lowest();

			return NULL;

		}
	}

	//___________REGULAR ADDITION STATS HERE____________
	//_________See if in ADDING mode and not SPLITTING_____________
	if(children[LEFT]->IsLeaf()==0 && mode==ADDING) // If lower node is not a leaf
	{                                  // then simply call other objects
		if(lk<leftkey)
		{
			return children[LEFT]->AddElement(lk,0,d,NULL,NULL,NULL,this,lk);
		}
		else if( (rightkey==0 && lk>=leftkey) || (lk<rightkey && lk>=leftkey) )
		{
			return children[MIDDLE]->AddElement(lk,0,d,NULL,NULL,NULL,this,lk);
		}
		else if( lk>=rightkey)
		{
			return children[RIGHT]->AddElement(lk,0,d,NULL,NULL,NULL,this,lk);
		}
	}

	//__________Lower Child is a leaf____Actual adding part has come !_____
	else
	{
		Node<T>* temp;
		temp=new Node<T>(lk,rk,d,lc,mc,rc,p,l);
		temp->Set_mychildren();

		if(children[RIGHT]==NULL) //_______Only two leafs , insertion easy !_____
		{
			children[RIGHT]=temp;
			SortLeafs(children,3);

		//__________Redistribute keys and lowest fields____________

			leftkey=children[MIDDLE]->Return_lowest();
			rightkey=children[RIGHT]->Return_lowest();
			lowest=children[LEFT]->Return_lowest();
			Set_mychildren();

			return NULL;

		}
		// _________3 Children__Tough part , split upper parent into two_________
		else
		{
			Node<T>* array[4]={children[LEFT],children[MIDDLE],
											children[RIGHT],temp};
			Node<T>* temp1;
			Node<T>* temp2;
			SortLeafs(array,4);

			children[LEFT]=array[0];
			children[MIDDLE]=array[1];
			children[RIGHT]=NULL;

			temp1=array[2];
			temp2=array[3];

			//__________Redistribute keys and lowest fields____________
			leftkey=children[MIDDLE]->Return_lowest();
			rightkey=0;
			lowest=children[LEFT]->Return_lowest();

			Set_mychildren();

			if(parent!=NULL) //_____ if i am not root
			{
				return	parent->AddElement(temp2->Return_lowest(),
								0,NULL,temp1,temp2,NULL,parent,temp1->Return_lowest(),SPLITTING);
			}
			// _______I am the root___splitting myself and creating a new root_____
			else
			{
				Node<T>* temp3;
				Node<T>* root;
				//________My sibling under the new root_____
				temp3=new Node<T>(temp2->Return_lowest(),0,NULL,temp1,temp2,NULL,
									NULL,temp1->Return_lowest());

				//____________The new root___________
				root=new Node<T>(temp3->Return_lowest(),0,NULL,this,temp3,NULL,NULL,
										lowest);

				//_______New Root is made so set new parents____
				temp3->Set_mychildren();
				root->Set_mychildren();
				return root;

			}
		}
	}

	return NULL; // ____Appease c++
}

template <class T>
void Node<T>::SortLeafs(Node<T>** nodearray,int n)
{
int i,j;

//__________Simple Bubble sort Procedure for sorting leafs________
for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
		if(nodearray[i]->Return_lowest() > nodearray[j]->Return_lowest())
			SwapPointers(nodearray[i],nodearray[j]);

}

template <class T>
void Node<T>::SwapPointers(Node<T>* &p1,Node<T>* &p2)
{
	Node<T>* temp;
	temp=p1;
	p1=p2;
	p2=temp;
}

template <class T>
Node<T>* Node<T>::DeleteElement(T lk)
{

	//______Check for special Cases if one or two elements left_____

	int child_id;

	if(children[LEFT]->IsLeaf()==0)
	{
		//________assign child_id the appropriate child to call______
		if(lk<leftkey)
			child_id=LEFT;
		else if( (rightkey==0 && lk>=leftkey) || (lk<rightkey && lk>=leftkey) )
			child_id=MIDDLE;
		else if( lk>=rightkey)
			child_id=RIGHT;

		children[child_id]->DeleteElement(lk);

		//________Only One children left_____________
		if(children[child_id]->Return_childrenno()==1)
		{
			Node<T>* t=NULL;

			//______look for three children sibling in adjacent nodes______
			int left_status=0;
			//_____try left sibling_____
			int i=child_id-1;

				if(i>=0)  // if left sibling is valid;
				{
					//______A adjacent node with 3 children found !______
					if(children[i]->Return_childrenno()==3)
					{
						t=children[i]->children[RIGHT];
						children[i]->children[RIGHT]=NULL;
						children[i]->Set_myparameters();
						left_status=1; // ____Success on left adjacent node

					}
				}

			if(left_status==0)
			{
				//________try right sibling_________
				i=child_id+1;
				if(i<=2 && children[i]!=NULL)  // if right sibling is valid;
				{
					//______A adjacent right node with 3 children found !______
					if(children[i]->Return_childrenno()==3)
					{
						t=children[i]->children[LEFT];
						children[i]->children[LEFT]=NULL;
						children[i]->Rearrange();
						children[i]->Set_myparameters();
					}
				}
			}
			// ___________If extra child found______________
			if(t!=NULL)
			{
				children[child_id]->children[MIDDLE]=t;
				children[child_id]->Rearrange();
				children[child_id]->Set_mychildren();
				children[child_id]->Set_myparameters();
			}
			//____________Failure no, no extra child found___
			//________Transfer one child to sibling_____
			else
			{
				t=children[child_id]->children[LEFT];
				//________delete its parent________
				delete children[child_id];
				children[child_id]=NULL;


				i=child_id-1;
				if(i<0) i=child_id+1;

				//__________Insert it anywhere
						children[i]->children[RIGHT]=t;
						children[i]->Rearrange();
						children[i]->Set_mychildren();
						children[i]->Set_myparameters();
			}
		}


		Rearrange();
		Set_mychildren();
		if(Return_childrenno()!=1)
		{
			Set_myparameters();
		}

		//____________Check Special Case__________
		if(parent==NULL && Return_childrenno()==1)
		{
			children[LEFT]->Set_parent(NULL);
			return children[LEFT];
		}

	}
	//_____________Reached the leaf , finally delete the required element_______
	else
	{
		for(int i=0;i<=2;i++)
		{

			if(children[i]!=NULL && children[i]->leftkey==lk)
			{
				delete children[i];
				children[i]=NULL;
			}
		}
		Rearrange();
		if(Return_childrenno()>1)
			Set_myparameters();
	}


	return NULL;
}



template <class T>
void Node<T>::Display()
{

//cout << "\nPresent Node -> " << leftkey << "  " << rightkey << "  " << lowest << " p :  " << parent << " me : " << this;

if(IsLeaf()) //____2nd condition -> i am not root______
{
	cout << endl << leftkey ;
}
else
{

	if(children[LEFT]!=NULL) children[LEFT]->Display();
	if( children[MIDDLE]!=NULL) children[MIDDLE]->Display();
	if( children[RIGHT]!=NULL) children[RIGHT]->Display();
}

}

template <class T>
int Node<T>::SearchElement(T k,int mode)
{

if(IsLeaf()) //____2nd condition -> i am not root______
{
	if(k==leftkey)
	{
		if(mode==DISPLAY)
			if(data!=NULL)
				data->Display();
		return 1;
	}
	else
		return 0;
}
else
{

	int a=0;
	if(children[LEFT]!=NULL) a=a | children[LEFT]->SearchElement(k,mode);
	if( children[MIDDLE]!=NULL) a=a | children[MIDDLE]->SearchElement(k,mode);
	if( children[RIGHT]!=NULL) a= a | children[RIGHT]->SearchElement(k,mode);
	return a;
}

}


//------------------------------------------
//			T R E E _  2 3   C L A S S
//________________________________________

template <class T>
class Tree_23
{
private:
	Node<T>* root;   // ___Store the root pointer____
	int no_of_elements;

public:

	//_____Constructors , Destructors______
	Tree_23();
	~Tree_23()
	{
	// ________Add Memory De-allocation routines for complete Tree
		delete root;
		root=NULL;
	}

	void AddElement(T key,Data& d);
	int SearchElement(T key,int mode=SEARCH);
	void DeleteElement(T key);
	void Display();

	int Return_no_of_elements()
	{
		return no_of_elements;
	}


};


template <class T>
Tree_23<T>::Tree_23()
{
root=new Node<T>(0,0,NULL,NULL,NULL,NULL,NULL,0);
no_of_elements=0;

}

template <class T>
void Tree_23<T>::AddElement(T key,Data& d)
{

	Node<T>*  temp=root->AddElement(key,0,&d,NULL,NULL,NULL,NULL,key);
	if(temp!=NULL)
	{
		root=temp;
	}
	no_of_elements++;

}

template <class T>
void Tree_23<T>::DeleteElement(T key)
{
	Node<T>* t;
	t=root->DeleteElement(key);
	if(t!=NULL)
	{
		delete root;
		root=t;
	}
	no_of_elements--;
}


template <class T>
void Tree_23<T>::Display()
{
	root->Display();
}

template <class T>
int Tree_23<T>::SearchElement(T key,int mode)
{
	return root->SearchElement(key,mode);
}



/*--------------------------------------------------------*\
| 				M A I N    C O N S O L E                   |
\*--------------------------------------------------------*/


//__________________________Main user console starts____________________




void main()
{
Tree_23<long> tree[MAXTREES];

long key;

int currenttree=0;
int choice;
Data data;

while(1)
{

Interface::Clear();

//________Display Main Menu_______
Interface::DisplayCenter("2-3-TREE Demonstration Program");
cout << endl;
Interface::DisplayLine("-");
cout << endl << endl;


Interface::DisplayCenter("----->  MAIN MENU <------");


cout << endl << endl;
Interface::Leavespace(25);	cout << "1.	Add a name to TREE";	cout << endl;
Interface::Leavespace(25);	cout << "2.	Search for a name";	cout << endl;
Interface::Leavespace(25);	cout << "3.	Delete a name";	cout << endl;
Interface::Leavespace(25);	cout << "4.	Display all entries in TREE";	cout << endl;
Interface::Leavespace(25);	cout << "5.	Change current TREE";	cout << endl;
Interface::Leavespace(25);	cout << "6.	Exit the Program";	cout << endl;

cout << endl;
Interface::DisplayLine("_");
cout << endl;

cout << "Current TREE number is : " << (currenttree+1) << endl;
cout << "No. of entries in current TREE is  : " << tree[currenttree].Return_no_of_elements() << endl;
cout << "Maximum number of TREES allowed : " << MAXTREES << endl << endl;



choice=Interface::GetInt("Please Enter your choice :",1);


	switch (choice)
	{
		case 1:
			cout << endl;
			cout << endl << "Help : When you want to stop , just enter 0 as the last number" << endl;
			key=1;
			while(key!=0)
			{
				key=Interface::GetLong("\nPlease Enter the Entry No. :",0);

				if (tree[currenttree].SearchElement(key))
				{
					cout << endl;
					cout << key << " is already present in the TREE";
				}
				else if(key>0)
				{
					data.GetData();
					tree[currenttree].AddElement(key,data);
				}
			}
				break;

		case 2:
			key=Interface::GetLong("\nPlease Enter the number to search: ",1);
			if (tree[currenttree].SearchElement(key,SEARCH))
			{
				cout << endl;
				cout << key << " is present in the TREE";
				tree[currenttree].SearchElement(key,DISPLAY);

			}
			else
			{
				cout << endl;
				cout << key << " is not present in the TREE";
			}
			Interface::PressEnter();
			break;
		case 3:
			key=Interface::GetLong("\nPlease Enter the number to delete :",1);
			if (!tree[currenttree].SearchElement(key,SEARCH))
			{
				cout << endl;
				cout << key << " is not present in the TREE";
				Interface::PressEnter();
				break;
			}
			tree[currenttree].DeleteElement(key);
			break;

		case 4:
			cout << endl;
			Interface::DisplayCenter("THE TREE LIST");
			cout << endl; Interface::DisplayLine("-"); cout << endl;
			if(tree[currenttree].Return_no_of_elements()==0)
			{
				cout << "\n\nThere are no entries currenly stored in the TREE\n";
			}
			tree[currenttree].Display();
			Interface::PressEnter();
			break;
		case 6:
			cout << endl << endl;
			Interface::DisplayCenter("Exiting the Program....");
			cout << endl;
			Interface::DisplayLine("-");
			cout << endl << endl;

			exit(0);
		case 5:
			int num;
			cout << endl;
			cout << "Maximum number allowed is : " << MAXTREES << endl;
			num=Interface::GetInt("Please Enter the new TREE number :",1);
			if ( num>=1 && num<=MAXTREES)
			{
				currenttree=num-1;
			}
			else
			{
				Interface::Error("Number entered is not valid.");
				Interface::PressEnter();
			}
			break;

		default:
			Interface::Error("Wrong Choice !!");
			Interface::PressEnter();

		}
}
}