#include <iostream>
#include <string>
#include <fstream>

using namespace std;

const int MAX_SIZE = 1501;

struct ITEM {
	string key;
	ITEM *next;
};

struct LIST {
	string key;
	ITEM *headItem;
};

LIST myList[MAX_SIZE];

ITEM *getItem(int index, int &count)
{
	ITEM *currentItem = myList[index].headItem;
	while (++count && currentItem->next != NULL)
		currentItem = currentItem->next;
	return currentItem;
}

void hashTableInitial()
{
	for (int i = 0; i<MAX_SIZE; i++)
	{
		myList[i].key.empty();
		myList[i].headItem = new ITEM;
		myList[i].headItem->next = NULL;
	}
}

int hashFunction(string key)
{
	unsigned sum = 0;
	for (const char * str = key.c_str(); *str; str++)
		sum = (sum * 1664525) + (unsigned char)(*str) + 1013904223;
	return sum%MAX_SIZE;
}

int addKey(string key)
{
	int count = 0;
	int hash = hashFunction(key);
	if (++count && myList[hash].key.empty())
		myList[hash].key = key;
	else
	{
		ITEM *currentItem = getItem(hash, count);
		ITEM *tmp = new ITEM;
		tmp->key = key;
		tmp->next = NULL;
		currentItem->next = tmp;
		currentItem = tmp;
	}
	return count;
}

int searchKey(string key, int &count)
{
	int flag = 0;
	int hash = hashFunction(key);
	if (++count && myList[hash].key == key)
		flag = 1;
	else
	{
		ITEM *tmp = myList[hash].headItem->next;
		while (++count && tmp != NULL)
		{
			if (tmp->key == key)
			{
				flag = 1;
				break;
			}
			tmp = tmp->next;
		}
	}
	if (flag)
		return 1;
	else
		return 0;
}

string keyRandom(string key)
{
	int firstRand, secondRand, thirdRand, fourdRand, fifthRand, sixthRand;
	char first, second, third, fourth, fifth, sixth;
	string keygen;
	keygen = "";
	firstRand = rand() % 9;
	first = (char)(firstRand + 48);
	secondRand = rand() % 26;
	second = (char)(secondRand + 65);
	thirdRand = rand() % 26;
	third = (char)(thirdRand + 65);
	fourdRand = rand() % 26;
	fourth = (char)(fourdRand + 65);
	fifthRand = rand() % 26;
	fifth = (char)(fifthRand + 65);
	sixthRand = rand() % 9;
	sixth = (char)(sixthRand + 48);
	keygen.push_back(first);
	keygen.push_back(second);
	keygen.push_back(third);
	keygen.push_back(fourth);
	keygen.push_back(fifth);
	keygen.push_back(sixth);
	return keygen;
}

void showList()
{
	cout << endl;
	for (int i = 0; i < MAX_SIZE; i++)
	{
		if (!myList[i].key.empty())
		{
			cout << "Table[" << i << "] = " << myList[i].key;
			ITEM *tmp = myList[i].headItem->next;
			while (tmp != NULL)
			{
				cout << " : " << tmp->key << " ";
				tmp = tmp->next;
			}
			cout << endl;
		}
	}
}

int deleteKey(string key)
{
	int flag = 0;
	int hash = hashFunction(key);
	if (myList[hash].key == key)
	{
		if (myList[hash].headItem->next == NULL)
		{
			flag = 1;
			myList[hash].key.empty();
		}
		else
		{
			myList[hash].key = myList[hash].headItem->next->key;
			ITEM *tmp = myList[hash].headItem->next;
			myList[hash].headItem->next = tmp->next;
			flag = 1;
			delete tmp;
		}
	}
	else
	{
		ITEM *prev = myList[hash].headItem;
		ITEM *tmp = myList[hash].headItem->next;
		while (tmp != NULL)
		{
			if (tmp->key == key)
			{
				prev->next = tmp->next;
				delete tmp;
				flag = 1;
				break;
			}
			else
			{
				prev = tmp;
				tmp = tmp->next;
			}
		}
	}
	return flag;
}

void outHashTable()
{
	int counter = 1;
	ofstream fout("outPut.txt");
	for (int i = 0; i < MAX_SIZE; i++)
	{
		if (!myList[i].key.empty())
		{
			counter = 1;
			fout << i << " ";
			ITEM *tmp = myList[i].headItem->next;
			while (tmp != NULL)
			{
				counter++;
				tmp = tmp->next;
			}
			fout << counter << endl;
		}
	}
}

int main()
{
	setlocale(LC_ALL, "Russian");
	string key;
	hashTableInitial();
	int count, n;
	char command;

	do
	{
		cout << "----------------------" << endl;
		cout << "1. Добавить ключ" << endl
			<< "2. Искать ключ" << endl
			<< "3. Показать таблицу" << endl
			<< "4. Удалить ключ" << endl
			<< "0. Выход из программы" << endl;
		cout << "----------------------" << endl;
		cout << "Введите номер команды: ";
		cin >> command;
		switch (command)
		{
		case '1':
			cout << endl << "Введите количество ключей: ";
			cin >> n;
			count = 0;
			for (int i = 0; i < n; i++)
			{
				key = keyRandom(key);
				if (searchKey(key, count) != 0)
				{
					cout << endl << "Ключ был использован, сравнений = " << count << endl;
				}
				else
				{
					count = addKey(key);
				}
			}
			cout << "Ключи успешно добавлены!" << endl;
			outHashTable();
			break;
		case '2':
			cout << endl << "Введите ключ = ";
			cin >> key;
			count = 0;
			if (searchKey(key, count) != 0)
				cout << endl << "Найдено, сравнений = " << count << endl;
			else
				cout << endl << "Не найдено" << endl;
			outHashTable();
			break;
		case '3':
			showList();
			break;
		case '4':
			cout << endl << "Введите ключ = ";
			cin >> key;
			if (deleteKey(key) == 1)
				cout << endl << "Удалено" << endl;
			else
				cout << endl << "Не найдено" << endl;
			outHashTable();
			break;
		case '0':
			outHashTable();
			break;
		default:
			cout << "Неверное значение! Повторите ввод!\n";
			break;
		}

	} while (command != '0');
	cin.get();

}