#include <stdio.h>
#include <stdlib.h>
#include "Profiler.h"
#include <string.h>
#define n 10007
#define none 0

#ifdef _DEBUG
#define LOG(...) printf(__VA_ARGS__)
#define IS_DEBUG true
#else
#define LOG(...)
#define IS_DEBUG false
#endif

Profiler profiler("HashTable");

int searchEffort;
int percent[5] = { 80, 85, 90, 95, 99 };

typedef struct
{
	int id;
	char name[30];
} NodeT;

int hashFct(int k,int i,int size)
{
	return (k+5*i+11*i*i) % size;
}

int fillFactor(int percent,int size)
{
	int x = (percent * size) / 100;
	return x;
}

void hashReset(NodeT* T, int size)
{
	for (int i = 0; i < size; i++)
	{
		T[i].id = none;
		strcpy_s(T[i].name, "empty");
	}
}

int hashInsert(NodeT* T,int size,int key)
{
	int i = 0;
	do
	{
		int j = hashFct(key, i,size);
		if (T[j].id == none)
		{
			T[j].id = key;
			strcpy_s(T[j].name,"Element");
			if(IS_DEBUG) printf("The element %d is insered on position %d\n", key,j);
			return j;
		}
		else i++;

	} while (i != size);
	if (IS_DEBUG) printf("Error: full table");
}


int hashSearch(NodeT* T, int size, int key)
{
	int i = 0,j;
	searchEffort = 0;
	do
	{
		 j = hashFct(key, i,size);
		 searchEffort++;
		if (T[j].id == key)
		{

			if (IS_DEBUG) printf("The element %d was found on position %d\n", key, j);
			return j;

		}
			i++;

	} while (T[i].id != none && i != size);

	if (IS_DEBUG) printf("Error: element %d not found\n",key);
	return 0;


}

void printHash(NodeT* T, int size)
{
	for (int i = 0; i < size; i++)
	{
		printf("%d %s\n", T[i].id,T[i].name);
	}
}

void demoHash()
{
	printf("-------------operation verify--------------\n");
	printf("------------------insertion----------------\n");
	NodeT* T = (NodeT*)malloc(11 * sizeof(NodeT));
	hashReset(T, 11);
	hashInsert(T, 11, 23);
	hashInsert(T, 11, 2);
	hashInsert(T, 11, 55);
	hashInsert(T, 11, 6);
	hashInsert(T, 11, 21);
	hashInsert(T, 11, 15);
	hashInsert(T, 11, 5);
	hashInsert(T, 11, 11);
	hashInsert(T, 11, 12);
	hashInsert(T, 11, 18);
	printf("\nThe content of the table is:\n");
	printHash(T, 11);
	printf("\n----------------searching----------------\n");
	hashSearch(T, 11, 23);
	hashSearch(T, 11, 3);
	hashSearch(T, 11, 55);
	hashSearch(T, 11, 7);
	printf("\n");
}

void demoFill95()
{
	int maxEffortFound = 0, maxEffortNotFound = 0;
	int totalEffortFound = 0, totalEffortNotFound = 0;
	printf("-------------search evaluation for 0.95 fill factor--------------\n");
	NodeT* T = (NodeT*)malloc(n * sizeof(NodeT));
	hashReset(T, n);
	int* a = (int*)malloc(n * sizeof(int));
	FillRandomArray(a, n , 1, 20000 , false, 0);
	for (int i = 0; i < fillFactor(95, n); i++)
	{
		hashInsert(T, n, a[i]);
	}

	for (int i = 0; i < 1500; i++)
	{
		hashSearch(T, n, a[i]);
		if (searchEffort > maxEffortFound) maxEffortFound= searchEffort;
		totalEffortFound += searchEffort;
		printf("%d ", searchEffort);


	}
	int j = 20001;
	for (int i = 0; i < 1500; i++)
	{

		hashSearch(T, n, j);
		j ++;
		if (searchEffort > maxEffortNotFound) maxEffortNotFound = searchEffort;
		totalEffortNotFound += searchEffort;
	}
	printf("%d", totalEffortNotFound);
	double x = (double)totalEffortFound / 1500;
	double y = (double)totalEffortNotFound / 1500;
	printf("\nFillFactor	|	Avg. Effort(found)	|	Max Effort(found)	|	Avg. Effort(not found)	|	Max Effort(not found)	|\n");
	printf("-------------------------------------------------------------------------------------------------------------------------------------------------\n");
	printf("	95	|		%0.2lf		|		%d		|	%0.2lf		|	%d			|\n",x,maxEffortFound,y,maxEffortNotFound);


}

void table()
{
	printf("\n\n\nFillingFactor\t\tAvgEffortFound\t\tMaxEffortFound\t\tAvgEffortNotFound\t\tMaxEffortNotFound");
	printf("\n");
	int i, j;
	NodeT* T = (NodeT*)malloc(n * sizeof(NodeT));

	for (i = 0; i < 5; i++)
	{

		double avgFound = 0;
		double maxFound = 0;
		double avgNotFound = 0;
		double maxNotFound = 0;

		for (j = 0; j < 5; j++)
		{
			int a[n];
			int indexArray[1500];
			FillRandomArray(a, n, 1, 20000);
			FillRandomArray(indexArray,1500, 1, n);

			hashReset(T, n);

			int k;
			for (k = 0; k < fillFactor(i, n); k++)
			{
				hashInsert(T, n, a[k]);
			}

			int k1;
			int maxEffortFound = 0;
			double AvgSearchF = 0;

			for (k1 = 0; k1 < 1500; k1++)
			{
				searchEffort = 0;
				hashSearch(T,n,a[indexArray[k]]);
				if (searchEffort > maxEffortFound) maxEffortFound = searchEffort;
				AvgSearchF = AvgSearchF + searchEffort;
			}
			AvgSearchF /= 1500.0;


			avgFound += AvgSearchF;
			maxFound += (double)maxEffortFound;


			int k2;
			int elem = 20001;
			int maxEffortNotFound = 0;
			double AvgSearchNF = 0;
			for (k2 = 0; k2 < 1500; k2++)
			{
				searchEffort = 0;
				int found2 = hashSearch(T,n,elem);
				elem += 500;

				if (searchEffort > maxEffortNotFound) maxEffortNotFound = searchEffort;
				AvgSearchNF = AvgSearchNF + searchEffort;
			}
			AvgSearchNF /= 1500.0;

			avgNotFound += AvgSearchNF;
			maxNotFound += maxEffortNotFound;
		}


		printf("%d\t\t%0.3lf\t\t%0.3lf\t\t\t%0.3lf\t\t\t%0.3lf\n", percent[i], avgFound / 5, maxFound / 5, avgNotFound / 5, maxNotFound / 5);

	}
}



int main()
{
	if (IS_DEBUG)
	{
		demoHash();

	}
	else
	{
		//demoFill95();
		table();
	}
}