#include <iostream>
#include "Profiler.h"
#define  totalPos 10007

using namespace std;

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

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


int hLinear(int val) {
	return val % totalPos;
}

int hQuadric(int val, int i, int totalPosi) {
	return (val + 7*i + i * i) % totalPosi;
}

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

int hashInsert(Entry table[], int value, int size) {
	int i = 0;
	do {
		int j = hQuadric(value, i, size);
		if (table[j].id == NULL) {
			table[j].id = value;
			return j;
		}
		else i++;
	} while (i < size);
	cout << "Error: Hash Table overflow\n";
	return 0;
}

int hashSearch(Entry table[], int value, int size) {
	int i = 0, j;
	do {
	    j = hQuadric(value, i, size);
		effort++;
		if (table[j].id == value) {
			//cout << table[j].name << " ";
			return j;
		}
		i++;
	} while (table[j].id != NULL && i < size);
	return NULL;
}

void singleFillFactor() {
	Entry table[totalPos];
	createEmptyHash(table, totalPos);
	int insVector[totalPos], nfVector[1505];
	FillRandomArray(nfVector, 1500, 11000, 15000, true, 0);
	FillRandomArray(insVector, int(0.95 * totalPos), 0, 10500, true, 0);
	/* We choose .95 as the fill factor for this case */
	for (int i = 0; i < int(0.95 * totalPos); i++)
		hashInsert(table, insVector[i], totalPos);
	for (int i = 0; i < 1500; i++) {
		effort = 0;
		int aux;
		aux = hashSearch(table, nfVector[i], totalPos);
		if (effort > maxEffortNotFound[3])
			maxEffortNotFound[3] = effort;
		avgEffortNotFound[3] += effort;

		effort = 0;
		aux = hashSearch(table, table[i].id, totalPos);
		if (aux != NULL) {
			if (effort > maxEffortFound[3])
				maxEffortFound[3] = effort;
			avgEffortFound[3] += 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 allFillFactors() {
	cout << "For all fill factors with uniform selection, we have:\n";
	cout << "Filling Factort\t\t" << "Avg Effort Found\t" << "Max Effort Found\t" << "Avg Effort Not Found\t" << "Max Effort Not Found\n";
	for (int factor = 0; factor < 5; factor++) {
		float x_factor = fillingFactor[factor];
		Entry table[totalPos];
		createEmptyHash(table, totalPos);
		int insVector[totalPos], nfVector[1505];
		FillRandomArray(nfVector, 1500, 11000, 15000, true, 0);
		FillRandomArray(insVector, int(x_factor * totalPos), 0, 10500, true, 0);
		for (int i = 0; i < int(x_factor * totalPos); i++)
			hashInsert(table, insVector[i], totalPos);
		for (int i = 0; i < 1500; i++) {
			effort = 0;
			int aux;
			aux = hashSearch(table, nfVector[i], totalPos);
			if (effort > maxEffortNotFound[factor])
				maxEffortNotFound[factor] = effort;
			avgEffortNotFound[factor] += effort;

			effort = 0;
			aux = hashSearch(table, table[i * 6].id, totalPos);
			if (aux != NULL) {
				if (effort > maxEffortFound[factor])
					maxEffortFound[factor] = effort;
				avgEffortFound[factor] += effort;
			}
		}
		avgEffortFound[factor] = avgEffortFound[factor] / 1500;
		avgEffortNotFound[factor] = avgEffortNotFound[factor] / 1500;
		cout << x_factor << "\t\t\t" << avgEffortFound[factor] << "\t\t\t" << maxEffortFound[factor] << "\t\t\t" << avgEffortNotFound[factor] << "\t\t\t" << maxEffortNotFound[factor] <<"\n";
	}
}

void insertDemo() {
	cout << "INSERTION DEMO\n\n";
	int v[] = { 1, 2, 3, 4, 55, 66, 77, 44, 33, 6, 9};
	Entry table[11];
	createEmptyHash(table, 11);
	cout << "The vector we add in the hash table: ";
	for (int i = 0; i < 11; i++)
		cout << v[i] << " ";
	cout << "\nThe initial Hash Table: ";
	for (int i = 0; i < 11; i++)
		cout << table[i].id << " ";
	for (int i = 0; i < 11; i++)
		hashInsert(table, v[i], 11);
	cout << "\nAfter the insertion, we have:\n";
	for (int i = 0; i < 11; i++)
		cout <<"On the position " <<i <<": " <<table[i].id <<"\n";
}

void searchDemo() {
	cout << "\n\nSEARCH DEMO\n\n";
	int v[] = { 1, 2, 3, 4, 5, 6};
	int tested[] = { 1, 3, 5, 7, 8, 9 };
	Entry table[10];
	createEmptyHash(table, 10);
	for (int i = 0; i < 6; i++)
		hashInsert(table, v[i], 10);
	cout << "The array we search for is: ";
	for (int i = 0; i < 6; i++)
		cout << tested[i] << " ";
	cout << "\nThe Hash Table is: ";
	for (int i = 0; i < 10; i++)
		cout << table[i].id << " ";
	cout << "\n";
	for (int i = 0; i < 6; i++) {
		int ok;
		ok = hashSearch(table, tested[i], 10);
		if (ok == NULL) cout << "The element " << tested[i] << " is not in the table\n";
		else cout << "The element " << tested[i] << " is in the table\n";
	}
}


int main()
{
	insertDemo();
	searchDemo();
	singleFillFactor();
	allFillFactors();

	/*for (int i = 0; i < 5; i++)
		cout << fillingFactor[i] << " "; */
	return 0;
}