#include <iostream>
#include <vector>
#include <cstdlib> // для функций rand() и srand()
#include <list>
#include <iterator>
using namespace std;

const int c = 3; // O(n) ~ 3n
const int p = 2000000033;

int rand_int(int min, int max)
{
    static const double fraction = 1.0 / (static_cast<double>(RAND_MAX) + 1.0);
    return static_cast<int>(rand() * fraction * (max - min + 1) + min);
}

int uni_hash(int a, int b, int m, int key)
{
    return ((a * key + b) % p) % m;
}


struct Node
{
    int a;
    int b;
    vector<int>* second_table = NULL;
    int second_table_size = 0;
    vector<int> keys;
    int count_keys = 0;
};

class FixedSet
{
    vector<struct Node> nodes; //вектор ячеек первой хэш табл
    vector<vector<int>> second_tables; //вектор хэш таблиц второго уровня
    int count_numbers;
    int table_size;
    int main_a;
    int main_b;
    // vector<vector<int>> vec(2, vector<int>(10));
public:
    FixedSet();
    void Initialize(const vector<int>& numbers);
    bool Contains(int number) const;
    void print();
};

FixedSet::FixedSet()
{
    this->count_numbers = 0;
    this->nodes;
    this->table_size = 0;
}

void FixedSet::Initialize(const vector<int>& numbers)
{
    this->count_numbers = numbers.size();
    this->table_size = c * count_numbers;

    //Задаём размеры таблиц
    this->nodes.resize(table_size);
    this->second_tables.resize(table_size); //внутренние размера 0

    int hash, key;
    bool flag = false; //Тру если простроили корректно
    int a, b;
    while (!flag)

    {
        a = rand_int(1, p - 1);
        b = rand_int(0, p - 1); //Глобальная ХФ

        //Закинули все ключи в таблицу
        for (int i = 0; i < this->count_numbers; ++i)
        {
            key = numbers[i];
            hash = uni_hash(a, b, table_size, key);
            nodes[hash].keys.push_back(key);
            nodes[hash].count_keys += 1;
        }

        //Теперь считаю коллизии
        int S = 0;
        for (int i = 0; i < this->table_size; ++i)
        {
            S += (nodes[i].count_keys) * (nodes[i].count_keys);
        }

        if (this->table_size >= S) //Влезаем в линейный объем на 2 уровне
        {
            flag = true;
        }

        else //Чистка
        {
            this->nodes.clear();
            nodes.resize(this->table_size);
        }
    }

    //Запомнили значение полученной глобальной функции
    this->main_a = a;
    this->main_b = b;

    //Вышли из вайл - значит успешно построили первый уровень, теперь второй:

    int b_i; //Число элементов в ячейке i
    int second_table_size;
    for (int i = 0; i < this->table_size; ++i) //Для каждой ячейки не пустой строим ХФ без коллизий
    {
        b_i = nodes[i].count_keys;
        if (b_i > 0) //Если там есть хоть 1 ключ то строим иначе зачем?
        {
            flag = false;
            while (!flag) //Повторяю попытки пока не получится без коллизий (добавить проврку на
            //пустоту)
            {
                second_table_size = b_i * b_i * c;

                //создать таблицу второго уровня для данного ключ
                //Кладу по умолчанию p чтобы понять что лежит там мусор или ключ
                this->second_tables[i].resize(second_table_size, p);

                a = rand_int(1, p - 1);
                b = rand_int(0, p - 1); // i-ая ХФ для второго слоя

                //Для каждого ключа в ячейке генерю хэш и отправляю в соот табл
                bool there_is_collis = false;
                for (int j = 0; j < b_i; ++j)
                {
                    key = nodes[i].keys[j];
                    hash = uni_hash(a, b, second_table_size, key);

                    //Проверка что там изначально пусто (нет коллизии)
                    if (this->second_tables[i][hash] != p)
                    {
                        there_is_collis = true;
                        break;
                    }

                    this->second_tables[i][hash] = key;
                }

                if (!there_is_collis)
                {
                    flag = true;
                    this->nodes[i].a = a; //Запоминаю полученную ХФ beta_i
                    this->nodes[i].b = b;
                    this->nodes[i].second_table = &(this->second_tables[i]); //Мб не надо
                    this->nodes[i].second_table_size = second_table_size;
                }
            }
        }
    }
}

bool FixedSet::Contains(int number) const
{
    int hash_1, hash_2, a, b;
    int key;

    a = this->main_a;
    b = this->main_b;
    hash_1 = uni_hash(a, b, table_size, number);

    Node node;
    node = this->nodes[hash_1];

    int a_k, b_k;
    a_k = node.a;
    b_k = node.b;
    int second_table_size = node.second_table_size;

    hash_2 = uni_hash(a_k, b_k, second_table_size, number);
    // key = node.second_table[hash_2];
    key = second_tables[hash_1][hash_2];

    return (key == number);
}

void FixedSet::print()
{
    cout << "\n print: \n";
    for (int i = 0; i < this->nodes.size(); ++i)
    {
        cout << "i= " << i << " : ";
        for (int j = 0; j < this->nodes[i].keys.size(); ++j)
            cout << this->nodes[i].keys[j] << endl;
    }
    cout << endl;
}

int main()
{
    cout << "Hello World";
    FixedSet f;

    vector<int> numbers = { 1, 2, 3 };
    f.Initialize(numbers);
    // f.print();


    return 0;
}