#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int TABLE_SIZE = 8;

/*
 * HashNode Class Declaration
 */
class HashNode
{
    public:
    int key;
	int value;
	HashNode* next;

        HashNode(int key, int value)//конструктор
        {
        this->key = key;
	    this->value = value;
	    this->next = NULL;
        }
};

/*
 * HashMap Class Declaration
 */
class HashMap
{
    private:
        HashNode** htable;
    public:
        HashMap()//конструктор
        {
            htable = new HashNode*[TABLE_SIZE];
            for (int i = 0; i < TABLE_SIZE; i++)
                htable[i] = NULL;
        }
        ~HashMap()//диструктор(при удалении)
        {
            for (int i = 0; i < TABLE_SIZE; ++i)
	    {
                HashNode* entry = htable[i];
                while (entry != NULL)
	        {
                    HashNode* prev = entry;
                    entry = entry->next;
                    delete prev;
                }
            }
            delete[] htable;
        }
        /*
         * Hash Function
         */
        int HashFunc(int key)
        {
            return key % TABLE_SIZE;
        }

        /*
         * Add Element at a key
         */
        void Insert(int key, int value)
        {
            int hash_val = HashFunc(key);
            HashNode* prev = NULL;
            HashNode* entry = htable[hash_val];
            while (entry != NULL)
            {
                prev = entry;
                entry = entry->next;
            }
            if (entry == NULL)
            {
                entry = new HashNode(key, value);
                if (prev == NULL)
	        {
                    htable[hash_val] = entry;
                }
	        else
	        {
                    prev->next = entry;
                }
            }
            else
            {
                entry->value = value;
            }
        }
        /*
         * Delete Element at a key
         */
       void del(int value)
{
bool found = false;
for (int i = 0; i < TABLE_SIZE && !found; i++)
{
HashNode* temp = htable[i];
HashNode* prev = NULL;
while (temp)
{
if (temp->value == value)
{
if (!prev)
{
htable[i] = temp->next;
delete temp;
found = true;
break;
}
else
{
prev->next = temp->next;
delete temp;
found = true;
break;
}
}
prev = temp;
temp = temp->next;
}
}
if (!found)
cout << "Не найден" << endl;
else
cout << "Успешно удалено" << endl;
system("pause");
}
        /*
         * Search Element at a key
         */
        int Search(int key)
        {
            bool flag = false;
            int hash_val = HashFunc(key);
            HashNode* entry = htable[hash_val];
            while (entry != NULL)
	    {
                if (entry->key == key)
	        {
                    cout<<entry->value<<" ";
                    flag = true;
                }
                entry = entry->next;
            }
            if (!flag)
                return -1;
        }
		/*
         * Print
         */

	void print()
{
for (int i = 0;i<8; i++)
{
cout << "Ключ " << i <<": ";
HashNode* temp = htable[i];
while (temp)
{
cout << temp->value << " ";
temp = temp->next;
}
cout << endl;
}
}
	}
;
/*
 * Main
 */
int main()
{
	setlocale(LC_ALL, "russian");
    HashMap hash;
    int key, value;
    int choice;
    while (1)
    {
        cout<<"\n----------------------"<<endl;
        cout<<"Операции"<<endl;
        cout<<"\n----------------------"<<endl;
        cout<<"1.Добавить элемент в таблицу"<<endl;
        cout<<"2.Поиск по ключу"<<endl;
        cout<<"3.Удаление по ключу"<<endl;
        cout <<"4.Вывод таблицы"<<endl;
		cout<<"5.Выход"<<endl;
        cout<<"Ваш выбор: ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Введите элемент,который хотите добавить: ";
            cin>>value;
            cout<<"Введите ключ: ";
            cin>>key;
            hash.Insert(key, value);
            break;
        case 2:
            cout<<"Введите ключ элемента для поиска: ";
            cin>>key;
            cout<<"Элементы по ключу "<<key<<" : ";
            if (hash.Search(key) == -1)
            {
	        cout<<"Элементы по заданному ключу не найдены "<<key<<endl;
	        continue;
	    }
            break;
        case 3:
            cout<<"Введите ключ, по которому будет удален элемент: ";
            cin>>key;
            hash.del(key);
            break;
		case 4:
			cout<<"Хеш-таблица:\n";
			hash.print();
			break;

        case 5:
            exit(1);
		}
    }
    return 0;
}