#include <stdio.h>
#include <ctype.h>
#include <conio.h>
#include <dos.h>
#include <string.h>
#include <stdlib.h>


struct PhoneBook{
	char Name[30];
	char Number[30];
	struct PhoneBook *Left, *Right;
};

typedef struct PhoneBook PHONEBOOK, NODE;

PHONEBOOK Book;

void Add(char *name, char *number){
	NODE *B, **ptr;
	if(!strcmp(name,""))return;
	if(!strcmp(Book.Name,"")){B=&Book;}
	else{
		B=&Book;
		while(B){
			if(strcmp(B->Name,name)>0){
				ptr=&B->Left;
				B=B->Left;
			}
			else{
				ptr=&B->Right;
				B=B->Right;
			}
		}
		*ptr=malloc(sizeof(PHONEBOOK));
		B=*ptr;
		B->Left=NULL;
		B->Right=NULL;
	}
	strcpy(B->Name,name);
	strcpy(B->Number,number);
	B->Left=NULL;
	B->Right=NULL;
}

NODE *FindName(char *name, PHONEBOOK *B){
	NODE *Qry;
	Qry=B;
	if(B){
		if(!strcmp(B->Name,name))Qry=B;
		else if(strcmp(B->Name,name)>0){
			if((Qry=FindName(name,B->Left))!=NULL)return Qry;
		}
		else if(strcmp(B->Name,name)<0){
			if((Qry=FindName(name,B->Right))!=NULL)return Qry;
		}
	}
	return Qry;
}

NODE *FindNumber(char *number, PHONEBOOK *B){
	NODE *Qry;
	Qry=B;
	if(B){
		if(!strcmp(B->Number,number))Qry=B;
		else{
			if((Qry=FindNumber(number,B->Left))!=NULL)return Qry;
			if((Qry=FindNumber(number,B->Right))!=NULL)return Qry;
		}
	}
	return Qry;
}

void ParentFind(char *name, PHONEBOOK *B, NODE **loc, NODE **parent){
	NODE *l, *par;
	par=*parent;
	if(B){
		if(!strcmp(B->Name,name)){*loc=B;return;}
		else if(strcmp(B->Name,name)>0){
			par=B;
			ParentFind(name,B->Left, &l, &par);
			if(l!=NULL){*loc=l;*parent=par;return;}
			else{*parent=NULL;*loc=NULL;return;}
		}

		else if(strcmp(B->Name,name)<0){
			par=B;
			ParentFind(name,B->Right, &l, &par);
			if(l!=NULL){*loc=l;*parent=par;return;}
			else{*parent=NULL;*loc=NULL;return;}
		}
	}
	*loc=NULL;*parent=NULL;
}

void Display(PHONEBOOK *B){
	if(B){
		Display(B->Left); /*traverse all left*/
		if(B!=&Book) /*check if root.. if so, don't print*/
			printf("Name: %s  #: %s\n",B->Name,B->Number);
		Display(B->Right); /*traverse all right*/
	}
}

void Delete(char *name){
	NODE *Parent=NULL, *Loc=NULL, *Left, *Right, *N;
	ParentFind(name,&Book,&Loc,&Parent);
	if(Loc==&Book)return; /* return if root */
	Left=Loc->Left; Right=Loc->Right;
	if(Parent){
		if(strcmp(Parent->Name,Loc->Name)>=0){
			Parent->Left=Left;
		}
		else Parent->Right=Left;
		N=Left;
		while(N){
			if(N->Right==NULL){
				N->Right=Right;
				break;
			}
			N=N->Right;
		}
		if(N==NULL){
			Parent->Right=Right;
		}
		free(Loc);
	}
}

int menu(){
	static int selection=0;
	int i, len;
	char ch;
	char options[][15]={
		" ADD          ",
		" DELETE       ",
		" SEARCH       ",
		" EDIT         ",
		" DISPLAY      ",
		" SAVE         ",
		" EXIT         ",
	};

	len=sizeof(options)/15;
	clrscr();
	for(;;){
		for(i=0;i<len;i++){
			if(i==selection){textcolor(0);textbackground(2);}
			else{textcolor(15);textbackground(0);}
			gotoxy(33,7+i);cprintf(options[i]);
		}
		textcolor(15);textbackground(0);
		gotoxy(38,5);cprintf("MENU");gotoxy(34,7+selection);
		ch=getch();
		switch(ch){
			case 27:return 7;
			case 72:
				if(selection==0)selection=len-1;
				else selection--;
				break;
			case 80:
				if(selection==len-1)selection=0;
				else selection++;
				break;
			case 13:
				return selection+1;
		}
	}
}

void add2rec(){
	char name[80], number[80];
	char ch;
	NODE *loc;
	clrscr();
	printf("Enter name: ");gets(name);
	printf("Enter number: ");gets(number);
	strlwr(name);
	loc=FindName(name,&Book);
	if(loc){
		printf("Name already exist!!!\n Replace?[y/n]");
		do{
			ch=tolower(getch());
		}while(ch!='n' && ch!='y');
		if(ch=='y'){
			strcpy(loc->Name,name);
			strcpy(loc->Number,number);
		}
	}else{
		Add(name,number);
	}
}

void deleterec(){
	NODE *loc;
	char name[80];
	char ch;
	clrscr();
	printf("Enter name: ");gets(name);
	strlwr(name);
	loc=FindName(name,&Book);
	if(loc){
		Delete(name);
		printf(" Entry deleted!");
		getch();
	}else{
		printf(" Entry not found!!!");
		getch();
	}
}

void search(){
	char ch;
	char search[80];
	NODE *loc;
	clrscr();
	printf("Search for [1]: Name, [2]: Number...\nEnter choice: ");
	do{
		ch=tolower(getch());
		if(ch==27)return;
	}while(ch!='1' && ch!='2');
	clrscr();

	if(ch=='1'){
		printf("Enter name: ");gets(search);strlwr(search);
		loc=FindName(search,&Book);
	}
	else{
		printf("Enter number: ");gets(search);
		loc=FindNumber(search,&Book);
	}

	if(!strcmp(search,""))loc=NULL;
	if(loc)printf("Name: %s  Number: %s",loc->Name,loc->Number);
	else printf("Entry not found...");
	getch();
}

void edit(){
	NODE *loc;
	char name[80], number[80];
	char ch;
	clrscr();
	printf("Enter name: ");gets(name);strlwr(name);
	loc=FindName(name,&Book);
	if(loc){
		printf("Enter new number: ");gets(number);
		strlwr(number);
		strcpy(loc->Number,number);
	}else{
		printf("Entry not found!!!");
		getch();
	}
}

void display(){
	char ch;
	clrscr();
	Display(&Book);
	getch();
}

void save(){
	clrscr();
	printf("Saved.");
	getch();
}

void load(){
}


void main(){
	textcolor(15);textbackground(0);
	clrscr();
	Add("Root",""); /* Root is not displayed nor can be deleted.*/
	load();
	for(;;){
		switch(menu()){
			case 1:
				add2rec();break;
			case 2:
				deleterec();break;
			case 3:
				search();break;
			case 4:
				edit();break;
			case 5:
				display();break;
			case 6:
				save();break;
			case 7:
				exit(0);
		}
	}
}