/*----------------------------------------------------------------*\
	   CS130 Assignment #1

	   OOPTRIE.CPP - Implementation of Trie

|
|    An Object Oriented Approach to Implementation Of TRIE
|
\*----------------------------------------------------------------*/


/*----------------------------------------------------------------*\
|			         	  CLASSES USED
|                      ------------------
|	 Instance Classes :
						Data
						Node
						Edge
						Trie

	 Static function Classes :
						String  ( String Manipulation Functions )
						Interface ( Interface handling functions )

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


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

enum { SEARCH,DISPLAY };
const int MAXWORDLENGTH=80;
//______Maximum number of allowed tries____________
const int MAXTRIES=20;



class String;
class Data;
class Node;
class Edge;
class Trie;
class Interface;

//___________String Manipulation Functions_______________
class String
{

public:

	static void Left(char *s,int l,char* a);
	static void Right(char *s,int l,char* a);
	static int Match(char *s1,char *s2);
	static void Concat(char *s1,char *s2,char *dest)
	{
		dest[0]=0;
		strcat(dest,s1);
		strcat(dest,s2);
	}

};

	//___________Extracts left portion of a string_________
	void String::Left(char *s,int l,char* a)
	{
		for(int i=0;i<l;i++) a[i]=s[i];
		a[l]=0;
	}

	//___________Extracts right portion of a string_________
	void String::Right(char *s,int l,char* a)
	{
		int length=strlen(s);
		if (l>length) return;
		for(int i=length-l;i<length;i++) a[i-(length-l)]=s[i];
		a[l]=0;
	}

	//_________Counts number of beginning characters till s2 matches s1_____
	int String::Match(char *s1,char *s2)
	{

		int l,i;

		if (s1 == NULL || s2==NULL) return 0;
		//__________l=Minimum (length of both strings) __________
		if(strlen(s1)<strlen(s2))
			l=strlen(s1);
		else
			l=strlen(s2);

		for(i=0;i<l;i++) if (s1[i]!=s2[i]) break;
		return i;
}


//___________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();
	static long GetLong();
	static void GetString(char* s,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....";
	cout.flush();
	getchar();

}

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


int Interface::GetInt()
	{
		char buffer[10];
		cin.getline(buffer,10);
		return atoi(buffer);
	}


long Interface::GetLong()
	{
		char buffer[10];
		cin.getline(buffer,10);
		return atol(buffer);
	}

void Interface::GetString(char* s,char* message)
	{
		s[0]=0;
		while(strlen(s)==0)
		{
			cout << message;
			cout.flush();

			cin.getline(s,MAXWORDLENGTH);
			if(strlen(s)==0)
				Error("Please Enter a valid string argument.");

		}
	}
//----------------------------------------------
//          DATA CLASS
//______________________________________________


class Data
{
private:
	long entryno;
//	char hostelname[25];



public:
	Data()
	{
		entryno=0;
//		hostelname[0]=0;

	}

	~Data()
	{
	}

	Data(long en)
	{
		entryno=en;
	}

	long Return_entryno()
	{
		return entryno;
	}
//	char* Return_hostelname()
//	{
//		return hostelname;
//	}

	void Set_entryno(long a)
	{
		entryno=a;
	}

	void GetData()
	{
		entryno=0;
		while(entryno<=0)
		{
			cout << "Please enter the Entry Number : ";
			cout.flush();
			entryno=Interface::GetLong();
			if(entryno<=0)
				Interface::Error("Please Enter a valid Entry Number.");
		}
//		cout << "Please enter the hostel name :";
//		cin >> hostelname;

	}

	void DisplayData()
	{
		cout << endl << "The entry no. is : " << entryno;
//		cout << endl << "The hostel is : " << hostelname;

	}

	void operator = ( Data& d)

	{
		if  (&d == this ) return;
		entryno=d.Return_entryno();
//		strcpy(hostelname,d.Return_hostelname());

	}


};

//_______________________________________________________________
//                         Node Class
//---------------------------------------------------------------
class Node
{

friend Edge;

private:
	int children;
	Edge* edgePointer;


public:
	//_______Constructors , Destructors________

	Node()
	{
		children=0;
		edgePointer=NULL;
	}
	Node(int ch,Edge* ed)
	{
		children=ch;
		edgePointer=ed;
	}

	~Node()
	{
	}

	//__________Functions_____________________
	void AddElement(char* key,Data& d);
	int SearchElement(char* key,int dflag) const;
	void DeleteElement(char* key);
	void DisplayStructure(int spacing);
	void DisplayAllKeys(char* buffer,int position) const;
	void Node::PartialSearch(char *buffer,int position,char* tomatch) const;
	void Node::DisplaytoFile (char* buffer,int position,char *filename) const;


	void Set_children(int c) { children=c; }
	int Return_children() { return children; }
	Edge* Return_edgePointer() { return edgePointer; }

private:
	//___________Destruction Functions___________
	//______Only for inner implementation_________
	void DestroyEdge();


};

//-----------------------------------------------------------
//                Edge Class
//-----------------------------------------------------------

class Edge
{

friend Node;
private:
	char* key;
	Data* data;
	char wordend;
	Node* down;
	Edge* next;
//___________________Interface____________________

public:
	//________Constructors and Destuctors_____________
	Edge(char *k,Data& d,char we,Edge* n,Node* dn)
	{
		key=new char[strlen(k)+1];
		strcpy(key,k);
		data=new Data;
		(*data)=d;
		down=dn;
		next=n;
		wordend=we;
	}
	~Edge()
	{
		delete key;
		delete data;

	}

	void AddElement(char* k,Data& d,Node& n);
	int SearchElement(char *k,int dflag) const;
	void DisplayStructure(int spacing) const;
	void Edge::DisplayAllKeys(char* buffer,int position) const;
	void Edge::PartialSearch(char* buffer,int position,char *tomatch) const;
	void Edge::DisplaytoFile(char* buffer,int position,char* filename) const;
	Edge* DeleteElement(char* k,Node& n);

private:
	//______________Implementation Functions______________

	void Set_key(char* a)
	{

		key=new char[strlen(a)+1];
		strcpy(key,a);
	}
	void Set_wordend(char we)
	{
		wordend=we;
	}

	Node* Return_down() const
	{
		return down;
	}
	Edge* Return_next() const
	{
		return next;
	}

	Data* Return_data() const
	{
		return data;
	}

	char* Return_key() const
	{
		return key;
	}

	char Return_wordend() const
	{
		return wordend;
	}

	//________________Destruction Functions_____________
	void DestroySpace()
	{
		delete key;
		delete data;
	}


};

/*---------------------------------------------------------------*\
|			 		E D G E  CLASS FUNCTIONS                      |
\*---------------------------------------------------------------*/


void Edge::AddElement(char* k,Data& d,Node& n)
{
	int match_till;
	int keylength;

	match_till=String::Match(key,k);
	keylength=strlen(key);

	//_______________If something to do with the present edge________
	if(match_till>0)
	{

		//________________Breaking Procedures_______________
		if(match_till<keylength)
		{

			char* t1;
			char* t2;
			t1=new char[match_till+1];
			t2=new char[keylength-match_till+1];


			String::Left(key,match_till,t1);
			String::Right(key,keylength-match_till,t2);


			down=new Node(1,new Edge(t2,*data,wordend,NULL,down));

			DestroySpace();
			Set_wordend(0);
			Set_key(t1);
			data=NULL;

			delete t1; delete t2;

		}

		char* left;
		left=new char[strlen(k)-match_till+1];
		String::Right(k,strlen(k)-match_till,left);

		if(strlen(left)>0)
			down->AddElement(left,d);
		else
		{
			Set_wordend(1);
			data=new Data;
			(*data)=d;
		}

		delete left;

	}

	//___________If nothing to do with current Edge___________
	if(match_till==0)
	{
		if(strlen(k))
		{
			if(next!=NULL)
			{
				next->AddElement(k,d,n);
			}
			else
			{
				n.Set_children(n.Return_children()+1);
				next=new Edge(k,d,1,NULL,new Node(0,NULL));
			}
		}
	}

}

int Edge::SearchElement(char *k,int dflag) const
{

	int match_till;
	match_till=String::Match(key,k);

	if(match_till>0)
	{
	if(match_till<strlen(key))
	{
		return 0;
	}
	else
	{
			//_________Compute left-over string_____________
			char* left;
			left=new char[strlen(k)-match_till+1];
			String::Right(k,strlen(k)-match_till,left);

			if(strlen(left)==0)
			{
				if (Return_wordend()!=0)
				{
					delete left;
					// Display key data if requested
					if(dflag)
						data->DisplayData();

					return 1;
				}
				else
				{
					delete left;
					return 0;
				}
			}
			else
				{
					int temp=down->SearchElement(left,dflag);
					delete left;
					return temp;
				}

	}
	}

	if(match_till==0)
	{
		if(Return_next()!=NULL)
		{
			return next->SearchElement(k,dflag);
		}
		else
		{
			return 0;
		}
	}
	return 0;
}

Edge* Edge::DeleteElement(char* k,Node& n)
{
	int match_till;
	match_till=String::Match(key,k);

	if(match_till>0)
	{
		//_______________Partial Matching______________
		if(match_till<strlen(k))
		{
			//_________Compute left-over string_____________
			char* left;
			left=new char[strlen(k)-match_till+1];
			String::Right(k,strlen(k)-match_till,left);

			down->DeleteElement(left);
			delete left;
		}
		//___________Full Matching_____Delete___________
		if(match_till==strlen(k))
		{
			if(down->Return_children()==0)
			{
				delete down;
				down=NULL;
				return next;
			}
			else
			{
				Set_wordend(0);
				delete data;
				data=NULL;

				//return this;
			}
		}
	}

	//____________If nothing to do with current edge____________
	if(match_till==0)
	{


		if(next!=NULL)
		{

			Edge* temp;
			temp=next->DeleteElement(k,n);
			if(temp!=next)
			{
				delete next;
				n.Set_children(n.Return_children()-1);
				next=temp;
			}
		}
	}

	//______Finally check if lower node has just one child____________
	//__________________&& currentwordend=0 --- Then Merge____________

	if (		down->Return_children()==1 &&
				Return_wordend()==0)
	{
//		cout << "Merging at : " << key << endl;
		//________Merge current key____________
		char* temp=(down->Return_edgePointer())->Return_key();
		char* temp1;

		temp1=new char[strlen(key)+strlen(temp)+1];
		String::Concat(key,temp,temp1);
		delete key;
		key=temp1;

		//___________Merge data_______________
		data=new Data;

		(*data)=*((down->Return_edgePointer())->Return_data());
		wordend=(down->Return_edgePointer())->Return_wordend();



		//________Delete down && down->edgePointer__________
		Node* temp2;
		temp2=(down->Return_edgePointer())->Return_down();
		down->DestroyEdge();
		delete down;
		down=temp2;

//		cout << endl << key;
//		data->DisplayData();
//		cout << endl <<down->Return_children() << endl;

	}
	return this;
}

void Edge::DisplayStructure(int spacing) const
{

int i;

for(i=0;i<spacing;i++) cout << "  ";
cout << key;
if(wordend) cout << "$";
cout << endl;

down->DisplayStructure(spacing+1);

if(next!=NULL)
	next->DisplayStructure(spacing);

}

void Edge::DisplayAllKeys(char* buffer,int position) const
{

strcat(buffer,key);
if(wordend) cout << buffer << endl;

position+=strlen(key);
down->DisplayAllKeys(buffer,position);
position-=strlen(key);

buffer[position]=0;


if(next!=NULL)
	next->DisplayAllKeys(buffer,position);

}

void Edge::PartialSearch(char* buffer,int position,char *tomatch) const
{

strcat(buffer,key);
if(wordend && String::Match(tomatch,buffer)==strlen(tomatch)) cout << buffer << endl;

position+=strlen(key);
down->PartialSearch(buffer,position,tomatch);
position-=strlen(key);

buffer[position]=0;


if(next!=NULL)
	next->PartialSearch(buffer,position,tomatch);

}

void Edge::DisplaytoFile(char* buffer,int position,char* filename) const
{
ofstream outfile;
outfile.open(filename,ios::app);


strcat(buffer,key);

if(wordend)
{
	outfile << buffer << endl;
	outfile << data->Return_entryno() << endl;
	outfile.flush();
}

position+=strlen(key);
down->DisplaytoFile(buffer,position,filename);
position-=strlen(key);

buffer[position]=0;

if(next!=NULL)
	next->DisplaytoFile(buffer,position,filename);
}

/*---------------------------------------------------------------*\
|			 		N O D E  CLASS FUNCTIONS                   |
\*---------------------------------------------------------------*/

//________________Node Class Functions____________
void Node::AddElement(char* key,Data& d)
{

if (edgePointer!=NULL)
	edgePointer->AddElement(key,d,*this);
else
	{
		children++;
		edgePointer=new Edge(key,d,1,NULL,new Node(0,NULL));
	}
}


int Node::SearchElement(char* key,int dflag) const
{
	if(edgePointer!=NULL)
		return edgePointer->SearchElement(key,dflag);
	else
		return 0;
}

void Node::DeleteElement(char* key)
{
	Edge *temp;

	if (edgePointer!=NULL)
	{
		temp=edgePointer->DeleteElement(key,*this);
		if (temp!=edgePointer)
		{
			children--;
			delete edgePointer;
			edgePointer=temp;
		}
	}
}

void Node::DisplayStructure(int spacing)
{

if (edgePointer!=NULL)
	edgePointer->DisplayStructure(spacing);


}

void Node::DisplayAllKeys(char *buffer,int position) const
{
	if(edgePointer!=NULL)
	{
		edgePointer->DisplayAllKeys(buffer,position);

	}
}

void Node::PartialSearch(char *buffer,int position,char* tomatch) const
{
	if(edgePointer!=NULL)
	{
		edgePointer->PartialSearch(buffer,position,tomatch);

	}
}

void Node::DisplaytoFile (char *buffer,int position,char *filename) const
{
	if(edgePointer!=NULL)
	{
		edgePointer->DisplaytoFile(buffer,position,filename);

	}
}


//__________Private Node Functions_________

//__________Destruction Functions________
void Node::DestroyEdge()
{
	if (Return_children()==1)
	{
		delete edgePointer;
	}
}

/*---------------------------------------------------------------*\
|			 		T R I E 	C L A S S                        |
|     "  I do none of the work but get all the credit "			 |
\*---------------------------------------------------------------*/

class Trie
{

private:
	Node *root;
	int no_of_elements;


public:
	//_____________Constructors , Destructors________________
	Trie()
	{
		root=new Node(0,NULL);
		no_of_elements=0;
	}
	~Trie()
	{
		delete root;
	}

	//________Interface___________
	void AddEntry(char* key,Data &d);
	int SearchEntry(char* key,int dflag);
	void DisplayTrie();
	void DeleteEntry(char* key);
	void DisplayAllKeys() const;
	void PartialSearch(char* tomatch) const;
	void DisplaytoFile(char* filename) const;



	int Return_no_of_elements()
	{
		return no_of_elements;
	}



};

void Trie::AddEntry(char* key,Data &d)
{
	no_of_elements++;
	root->AddElement(key,d);
}

int Trie::SearchEntry(char* key,int dflag)
{
	return root->SearchElement(key,dflag);
}

void Trie::DisplayTrie()
{

	root->DisplayStructure(0);
}

void Trie::DisplayAllKeys() const
{
	char* buffer;
	buffer = new char[MAXWORDLENGTH+1];
	buffer[0]=0;
	root->DisplayAllKeys(buffer,0);
	delete buffer;

}

void Trie::PartialSearch(char* tomatch) const
{
	char* buffer;
	buffer = new char[MAXWORDLENGTH+1];
	buffer[0]=0;
	root->PartialSearch(buffer,0,tomatch);
	delete buffer;

}

void Trie::DisplaytoFile(char* filename) const
{
	char* buffer;
	buffer = new char[MAXWORDLENGTH+1];
	buffer[0]=0;
	root->DisplaytoFile(buffer,0,filename);
	delete buffer;
}

void Trie::DeleteEntry(char* key)
{
	root->DeleteElement(key);
}


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


//__________________________Main user console starts____________________




void main()
{
Trie trie[MAXTRIES];
int currenttrie=0;
int choice;
char *name;
name=new char[MAXWORDLENGTH+1];
Data data;

while(1)
{

Interface::Clear();

//________Display Main Menu_______
Interface::DisplayCenter("TRIE Manipulation Program");
cout << endl;
Interface::DisplayLine("-");
cout << endl << endl;


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


cout << endl << endl;
Interface::Leavespace(25);	cout << "1.	Add a name to TRIE";	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 TRIE structure";	cout << endl;
Interface::Leavespace(25);	cout << "5.	Display all words in TRIE";	cout << endl;
Interface::Leavespace(25);	cout << "6.	Change current TRIE";	cout << endl;
Interface::Leavespace(25);	cout << "7.	Partial Search for name";	cout << endl;
Interface::Leavespace(25);	cout << "8.	Output the data to a file";	cout << endl;
Interface::Leavespace(25);	cout << "9.	Exit the Program";	cout << endl;

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

cout << "Current TRIE number is : " << (currenttrie+1) << endl;
cout << "No. of words in current TRIE is  : " << trie[currenttrie].Return_no_of_elements() << endl;
cout << "Maximum number of TRIES : " << MAXTRIES << endl << endl;


cout << "Please Enter you choice :";
cout.flush();

choice=Interface::GetInt();


	switch (choice)
	{
		case 1:
			cout << endl;
			name[0]=0;
			cout << endl << "Help : When you want to stop ,  just enter \"$\" as the last name." << endl;
			while(strcmp(name,"$"))
			{
				Interface::GetString(name,"\nPlease Enter the name : ");

				if (trie[currenttrie].SearchEntry(name,SEARCH))
				{
					cout << endl;
					cout << name << " is already present in the TRIE";
				}
				else if(strcmp(name,"$"))
				{
					data.GetData();
					trie[currenttrie].AddEntry(name,data);
				}
			}
				break;

		case 2:
			Interface::GetString(name,"\nPlease Enter the name to search: ");
			if (trie[currenttrie].SearchEntry(name,SEARCH))
			{
				cout << endl;
				cout << name << " is present in the TRIE";
				trie[currenttrie].SearchEntry(name,DISPLAY);

			}
			else
			{
				cout << endl;
				cout << name << " is not present in the TRIE";
			}
			Interface::PressEnter();
			break;

		case 3:
			Interface::GetString(name,"\nPlease Enter the name to delete :");
			if (!trie[currenttrie].SearchEntry(name,SEARCH))
			{
				cout << endl;
				cout << name << " is not present in the TRIE";
				Interface::PressEnter();
				break;
			}
			trie[currenttrie].DeleteEntry(name);
			break;
		case 7:
			cout << endl;
			Interface::GetString(name,"\nPlease Enter the first few matching characters :");
			cout << endl << endl;
			Interface::DisplayCenter("Partial Search Results");
			cout << endl; Interface::DisplayLine("-"); cout << endl;
			if(trie[currenttrie].Return_no_of_elements()==0)
			{
				cout << "\n\nThere are no words currenly stored in the TRIE\n";
			}
			else
			{
				trie[currenttrie].PartialSearch(name);
			}
			Interface::PressEnter();
			break;

		case 4:
			cout << endl;
			Interface::DisplayCenter("The TRIE structure");
			cout << endl; Interface::DisplayLine("-"); cout << endl;
			if(trie[currenttrie].Return_no_of_elements()==0)
			{
				cout << "\n\nThere are no words currenly stored in the TRIE\n";
			}
			trie[currenttrie].DisplayTrie();
			Interface::PressEnter();
			break;
		case 5:
			cout << endl;
			Interface::DisplayCenter("Word List in TRIE");
			cout << endl; Interface::DisplayLine("-"); cout << endl;
			if(trie[currenttrie].Return_no_of_elements()==0)
			{
				cout << "\n\nThere are no words currenly stored in the TRIE\n";
			}
			trie[currenttrie].DisplayAllKeys();
			Interface::PressEnter();
			break;
		case 8:
			cout << endl;
			Interface::DisplayCenter("File Output");
			cout << endl; Interface::DisplayLine("-"); cout << endl;
			if(trie[currenttrie].Return_no_of_elements()==0)
			{
				cout << "\n\nThere are no words currenly stored in the TRIE\n";
				Interface::PressEnter();
				break;
			}
			else
			{
				Interface::GetString(name,"\nEnter the save filename ( APPEND mode ) :");
			}

			trie[currenttrie].DisplaytoFile(name);
			Interface::PressEnter();
			break;
		case 9:
			cout << endl << endl;
			Interface::DisplayCenter("Exiting the Program....");
			cout << endl;
			Interface::DisplayLine("-");
			cout << endl << endl;

			exit(0);
		case 6:
			int num;
			cout << endl;
			cout << "Maximum number allowed is : " << MAXTRIES << endl;
			cout << "Please Enter the new TRIE number  : ";
			num=Interface::GetInt();
			if ( num>=1 && num<=MAXTRIES)
			{
				currenttrie=num-1;
				break;
			}

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

		}
}
}