#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Windows.h>

#define Name_Length 30
#define Phone_Num_Length 20

double PCFreq = 0.0;
__int64 CounterStart = 0;

typedef struct Binary_T
{
	char name[Name_Length];
	char phone_Num[Phone_Num_Length];
	struct Binary_T *Left_Child;
	struct Binary_T *Right_Child;
} BiT_Node;
BiT_Node *Make_Tree(char name_data[], char ph_num_data[])
{
	BiT_Node *Root = (BiT_Node *)malloc(sizeof(BiT_Node));
	strcpy(Root->name, name_data);
	strcpy(Root->phone_Num, ph_num_data);
	Root->Left_Child = NULL;
	Root->Right_Child = NULL;
	return Root;
}
BiT_Node *Add_BiT_Node_Recursion(BiT_Node *Root, char name_data[], char ph_num_data[])
{
	if (Root == NULL)
		Root = Make_Tree(name_data, ph_num_data);
	else if (strcmp(name_data, Root->name) <= 0)
		Root->Left_Child = Add_BiT_Node_Recursion(Root->Left_Child, name_data, ph_num_data);
	else
		Root->Right_Child = Add_BiT_Node_Recursion(Root->Right_Child, name_data, ph_num_data);
	return Root;
}
BiT_Node *Search_No_Recursion(BiT_Node *Root, BiT_Node *SearchData)
{
	if (Root->name == NULL)
	{
		printf("No found for empty database\n");
		return NULL;
	}
	else
	{
		BiT_Node * prev = NULL;
		BiT_Node * current = Root;
		while (current != NULL)
		{
			prev = current;
			if (strcmp(SearchData->name, current->name) > 0)
				current = current->Right_Child;
			else if (strcmp(SearchData->name, current->name) < 0)
				current = current->Left_Child;
			else
				return current;
		}
		printf("Data No found\n");
		return NULL;
	}
}

void StartCounter()
{
	LARGE_INTEGER li;
	if (!QueryPerformanceFrequency(&li))
		printf("QueryPerformanceFrequency failed!\n");
	PCFreq = double(li.QuadPart) / 1000.0;
	QueryPerformanceCounter(&li);
	CounterStart = li.QuadPart;
}
double GetCounter()
{
	LARGE_INTEGER li;
	QueryPerformanceCounter(&li);
	return double(li.QuadPart - CounterStart) / PCFreq;
}
int main()
{

	BiT_Node *Expo = NULL;
	printf("Input name of  file:");
	FILE *file; char file_name[256]; scanf("%s", file_name);

	char name_data[Name_Length]; char ph_num_data[Phone_Num_Length];
	file = fopen(file_name, "r");
	if (file == NULL)
		printf("Can not open this file\nPlease check your filename\n");
	while ((fscanf(file, "%s%s", name_data, ph_num_data) != EOF))
	{
		Expo = Add_BiT_Node_Recursion(Expo, name_data, ph_num_data);
	}
	fclose(file);
	printf("INPUT YOUR DATA for searching:\n");
	char R_Search_Name[Name_Length];
	char R_Search_PhNum[Phone_Num_Length];
	*R_Search_PhNum = NULL;
	printf("Name:"); scanf("%s", R_Search_Name);

	StartCounter();
	BiT_Node *R_SearchData = NULL;
	R_SearchData = Make_Tree(R_Search_Name, R_Search_PhNum);
	BiT_Node * Result = Search_No_Recursion(Expo, R_SearchData);

	printf("Running time is: %lfms\n", GetCounter()*1000);
	if (Result != NULL)
		printf("Data Found\n");
	return 0;
}