/*hashing by first letter of name order by alphabet*/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define SIZE 26

struct Data{
	char name[50];
	char phone[15];
	struct Data *next;		//for chaining if there is collision
};

typedef struct Data Dt;		//struct Data alias Dt
Dt *head[SIZE];				//26 head (hashing table with size 26)

int getMenu(){
	int menu;
	printf("Phone Book\n");
	printf("----------\n");
	printf("1. Add\n");
	printf("2. Search\n");
	printf("3. Display\n");
	printf("4. Delete\n");
	printf("5. Exit\n");
	printf("Choose menu: ");
	scanf("%d", &menu); getchar();
	return menu;
}

int getHashKey(char name[]){
	char firstLetter = name[0];
	if( 'A' <= firstLetter && firstLetter <= 'Z') return firstLetter - 'A';
	if( 'a' <= firstLetter && firstLetter <= 'z') return firstLetter - 'a';
	return -1;	//if first letter of name is not an alphabet, it's not valid
}

void add(Dt in, int key){
	Dt *node;
	node = (Dt*) malloc(sizeof(Dt));
	*node = in;		//copy values of one struct
	node->next = NULL;
	if(head[key] == NULL){
		head[key] = node;
	}
	else{			//collision
		Dt *curr;				//find tail using curr
		curr = head[key];
		while( curr->next != NULL ){
			curr = curr->next;
		}
		curr->next = node;		//put node after tail
	}
}

void display(){
	Dt *curr;
	for(int i=0; i<SIZE; i++){
		printf("[%2d] ", i);
		curr = head[i];
		while(curr != NULL){
			printf("%s %s -> ", curr->name, curr->phone);
			curr = curr->next;
		}
		printf("\n");
	}
	printf("\n");
}

void search(int key, char src[]){
	Dt *curr=head[key];
	if(head[key]==NULL){
		printf("Name Not Found!\n\n");
	}
	else if(head[key]!=NULL && strcmp(head[key]->name, src)==0){
		printf("%s %s\n",curr->name,curr->phone);
	}
	else{
		while(curr!=NULL){
		 if(strcmp(curr->name,src)==0){
		 	printf("%s %s\n",curr->name,curr->phone);
		 	return;
		 	break;
		 }
		 curr=curr->next;
		}
		printf("Name Not Found!\n\n");
	}


}

void del(int key, char src[]){
	int flag=0;
	int cnt=-1;
	Dt *curr=head[key];
	if(head[key]==NULL){
		printf("No Name to be deleted!\n\n");
	}
	else if(head[key]!=NULL && strcmp(head[key]->name,src)==0){
		head[key]=head[key]->next;
		free(curr);
		printf("%s's contact sucessfully deleted!\n",src);
	}
	else{
		Dt *temp;
		while(curr->next!=NULL){
			if(strcmp(curr->next->name,src)==0){
				temp=curr->next;
				free(temp);
				flag=1;
				printf("%s's contact sucessfully deleted!\n",src);
			}
			cnt++;
			curr=curr->next;
		}
		if(head[key]!=NULL && strcmp(curr->name,src)==0){
			temp=head[cnt];
			temp->next=NULL;
			free(curr);
			printf("%s's contact sucessfully deleted!\n",src);
			flag=1;
		}
		if(flag==0){
		printf("No name to be deleted!\n\n");
		}
	}

}

void removeAll(){
	Dt *curr;
	Dt *temp;
	while(curr!=NULL){
		temp=curr;
		curr=curr->next;
		free(temp);
	}
}


int main(){
	int menu;

	do{
		menu = getMenu();
		if(menu == 1){		//add
			Dt in;
			printf("Name : ");
			scanf("%[^\n]", in.name); getchar();
			printf("Phone: ");
			scanf("%[^\n]", in.phone); getchar();

			int key = getHashKey(in.name);
			if(key == -1){
				printf("Name is invalid\n\n");
			}
			else{
				add(in, key);
				printf("Success adding new contact\n\n");
			}
		}
		else if(menu == 2){	//search
			char src[50];
			printf("Name to Search: ");
			int key=getHashKey(src);
			scanf("%[^\n]",&src);getchar();
			search(key,src);

		}
		else if(menu == 3){	//display
			display();
		}
		else if(menu == 4){	//delete
		char src[50];
		int key=getHashKey(src);
			printf("Name to delete: ");
			scanf("%[^\n]",&src);
			del(key,src);
		}
		else if(menu == 5){	//exit
		removeAll();
		}
	}while(menu != 5);	//repeat menu while menu is not exit

	return 0;
}