/*

	-Hash tables are used to efficiently store data.
	-hashing is a process that uses a hash function to get the key for the hash table and transform it into an index that will point to the place
	where the information is stored.
	-here we used 2 functions, hashInsert and hashSearch and a procedure that creates an empty hash table
	-the first one is for inserting data into the hash table, and the second one is for searching if a specific element is in the table or not

*/
#include <iostream>
#include "Profiler.h"
#define totPos 9973

Profiler profiler("hash");

double fillingFactor[] = { 0.8, 0.85, 0.9, 0.95, 0.99 };
int maxEffortFound[5], maxEffortNotFound[5];
float avgEffortFound[5], avgEffortNotFound[5];
int search_effort = 0;

using namespace std;

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

void createEmptyHash(Entry t[], int size)
{
	for (int i = 0; i < size; i++)
		t[i].id = NULL;
}

int hash_function(int val, int i, int size)
{
	int h = val + i * i;
	int f = h % size;
	return f;
}
int hashInsert(Entry t[], int key, int size)
{
	int i = 0;
	while (i < size)
	{
		int j = hash_function(key, i, size);
		if (t[j].id == NULL)
		{
			t[j].id = key;
			return j;
		}
		else
			i++;
	}
	cout << "hash table overflow" << "\n";
	return 0;
}
int hashSearch(Entry t[], int key, int size)
{
	int i = 0, j=0;
	do
	{
		j = hash_function(key, i, size);
		search_effort++;
		if (t[j].id == key)
		{
			return j;
		}
		i++;
	}while (i < size && t[j].id != NULL);
	return NULL;
}

void hashInsertDemo()
{
	cout << "Demo Insertion" << "\n";
	int a[6] = { 2,8,5,7,9,10 };
	Entry t[11];
	createEmptyHash(t, 11);
	cout << "We add in the table: ";
	for (int i = 0; i < 6; i++)
	{
		cout << a[i] << " ";
	}
	cout << "\n";
	for (int i = 0; i < 6; i++)
	{
		hashInsert(t, a[i], 11);
	}
	cout << "After performig insertion, we have: ";
	cout << "\n";
	for (int i = 0; i < 11; i++)
		cout << "On the position " << i << ": " << t[i].id << "\n";
	cout << "\n";
}
void hashSearchDemo()
{
	cout << "Demo Searching" << "\n";
	int a[6] = { 2,8,5,7,9,10 };
	int test[4] = { 2,1,6,10 };
	Entry t[11];
	createEmptyHash(t, 11);
	for (int i = 0; i < 6; i++)
	{
		hashInsert(t, a[i], 10);
	}
	cout << "We search for: ";
	for (int i = 0; i < 4; i++)
	{
		cout << test[i] << " ";
	}
	cout << "\n";
	cout << "The hash table is: ";
	for (int i = 0; i < 11; i++)
	{
		cout << t[i].id << " ";
	}
	cout << "\n";
	for (int i = 0; i < 6; i++)
	{
		int ok;
		ok = hashSearch(t, test[i], 11);
		if (ok == NULL) cout << "The el " << test[i] << " is not in the table\n";
		else if (ok!=NULL) cout << "The el " << test[i] << " is in the table\n";
	}
}
void demo95FillFactor()
{
	Entry t[totPos];
	createEmptyHash(t, totPos);
	int a[totPos], notFound[1500];
	FillRandomArray(notFound, 1500, 11000, 15000, true, 0);
	FillRandomArray(a, int(0.95 * totPos), 0, 10500, true, 0);
	for (int i = 0; i < int(0.95 * totPos); i++)
		hashInsert(t, a[i], totPos);
	for (int i = 0; i < 1500; i++)
	{
		search_effort = 0;
		int x = hashSearch(t, t[i].id, totPos);
		if (x != NULL)
		{
			if (search_effort > maxEffortFound[3])
				maxEffortFound[3] = search_effort;
			avgEffortFound[3] += search_effort;
		}
		search_effort = 0;
		 x = hashSearch(t, notFound[i], totPos);
		if (search_effort > maxEffortNotFound[3])
			maxEffortNotFound[3] = search_effort;
		avgEffortNotFound[3] += search_effort;
	}
	avgEffortFound[3] = avgEffortFound[3] / 1500;
	avgEffortNotFound[3] = avgEffortNotFound[3] / 1500;
	cout << "\nFor the fill factor .95, with non-uniform selection of elements, we have: \n";
	cout << "Avg effort found: " << avgEffortFound[3];
	cout << "\nMax effort found: " << maxEffortFound[3];
	cout << "\nAvg effort not found: " << avgEffortNotFound[3];
	cout << "\nMax Effort not found: " << maxEffortNotFound[3] << "\n\n\n";
}
/*void demo95FillFactor()
{
	Entry table[totPos];
	createEmptyHash(table, totPos);
	int insVector[totPos], nfVector[1505];
	FillRandomArray(nfVector, 1500, 11000, 15000, true, 0);
	FillRandomArray(insVector, int(0.95 * totPos), 0, 10500, true, 0);
	/* We choose .95 as the fill factor for this case
	for (int i = 0; i < int(0.95 * totPos); i++)
		hashInsert(table, insVector[i], totPos);
	for (int i = 0; i < 1500; i++) {
		search_effort = 0;
		int aux;
		aux = hashSearch(table, nfVector[i], totPos);
		if (aux != NULL) cout << "x";
		if (search_effort > maxEffortNotFound[3])
			maxEffortNotFound[3] = search_effort;
		avgEffortNotFound[3] += search_effort;

		search_effort = 0;
		aux = hashSearch(table, table[i].id, totPos);
		if (aux != NULL) {
			if (search_effort > maxEffortFound[3])
				maxEffortFound[3] = search_effort;
			avgEffortFound[3] += search_effort;
		}
	}
	avgEffortFound[3] = avgEffortFound[3] / 1500;
	avgEffortNotFound[3] = avgEffortNotFound[3] / 1500;
	cout << "\nFor the fill factor .95, with non-uniform selection of elements, we have: \n";
	cout << "Avg effort found: " << avgEffortFound[3];
	cout << "\nMax effort found: " << maxEffortFound[3];
	cout << "\nAvg effort not found: " << avgEffortNotFound[3];
	cout << "\nMax Effort not found: " << maxEffortNotFound[3] << "\n\n\n";
}*/
int main()
{
	hashInsertDemo();
	hashSearchDemo();
	demo95FillFactor();
	return 0;
}