#include <iostream>
#include <string>
#include <ctime>
#include <chrono>

#define HASH_SIZE 10000

using namespace std;

struct node { //структура записи
        int index;
        string name;
        node* next;
    };

class HashTable {
public:
    node* table;
    int size=HASH_SIZE;


    HashTable() {
        table = new node[size]; //выделяем память под массив списков
    }

    int hash_function(int key) {
        return key % HASH_SIZE;  //идеальная хеш функция, если городов меньше HASH_SIZE и каждый имеет уникальный ID, иначе коллизии
    }

    void add(int key, string name) {


        int index = hash_function(key);
        node *new_node = new node;
        new_node->index = key;
        new_node->name = name;
        new_node->next = table[index].next;
        table[index].next = new_node;

    }

    node get(int key,string name) {
        int index = hash_function(key);
        node* temp = table[index].next; //получаем элемент хеш таблицы за постоянное время, далее проверяем все колизии (стоит учесть что это пустой элемент, а не коллизия)
        while(temp != NULL) {
            if(temp->name == name) { //если коллизий нет, то цикл пройдет 1 итерацию, если есть, то идем пока не найдем нужное имя
                return *temp;
            }
            temp = temp->next;
        }
        node nn = {-1, "NOT FOUND", NULL}; //если не нашли ниче, вернем ошибку
        return nn;
    }

    void print_collision(int key){
        int index = hash_function(key);
        node* temp = table[index].next;
        while(temp != NULL) {
            cout << temp->name << endl;
            temp = temp->next;
        }
    }

    void print_ht() {
        for(int i = 0; i < size; i++) {
            print_collision(i);
        }
    }

    ~HashTable() {
        delete[] table;
    }
};

void print_node(node n) {
    cout << n.index << " " << n.name << endl; //просто вывод структуры на экран
}



int main()
{
    srand(time(NULL));
    setlocale(LC_ALL, "Russian");
    system("chcp 1251 > null");
    HashTable ht;
    ht.add(1, "John"); //забиваем
    ht.add(1, "Jane");
    ht.add(1, "Jack");
    ht.add(4, "Jill");
    print_node(ht.get(1, "John"));//ищем

    cout<< "Выберите способ: \n1-Ручной ввод \n2-Автоматический \n";
    int n;
    cin >> n;
    if(n==1){
        cout<<"Введите количество городов: ";
        int k;
        cin >> k;
        for(int i=0;i<k;i++){
            cout<<"Введите номер города: ";
            int key;
            cin >> key;
            cout<<"Введите название города: ";
            string name;
            cin >> name;
            ht.add(key, name);
        }
    }else{
        int k;
        cout<<"Введите количество городов: ";
        cin >> k;
        for(int i=0;i<k;i++){
            int key = rand() % k;
            string name;
            name = "City" +to_string(key);
            ht.add(key, name);
        }
        int srch = rand() % k;

        cout<<"Ищем город с номером "<<srch<<endl;
        auto start = chrono::steady_clock::now();
        node nd = ht.get(srch, "City" +to_string(srch));
        auto end = chrono::steady_clock::now();
        auto diff = end - start;
        print_node(nd);
        cout<<"Время поиска: "<<chrono::duration <double, nano> (diff).count()<<" нс"<<endl;

    }

    return 0;
}