#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;
    vector<int> keys;
    int count_keys = 0;
};

class FixedSet
{
    vector<struct Node> nodes; //вектор ячеек первой хэш табл
    vector<vector<int>> second_tables;
    int count_numbers;
    int table_size;
    // 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 m1 = c * count_numbers; //Размер 1 уровня
    int hash, key;
    bool flag = false; //Тру если простроили корректно

    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 (S <= this->table_size)
        {
            flag = true;
        }

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

    //Вышли из вайл - значит успешно построили первый уровень, теперь второй:
    int b_i;
    for (int i = 0; i < this->table_size; ++i)
    {

        flag = false;

        while (!flag) //Повторяю попытки пока не получится без коллизий (добавить проврку на пустоту)
        {
            b_i = nodes[i].count_keys;
            second_table_size = b_i * b_i * c;

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

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

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

            //Теперь проверяю на коллизции
            int z = 0;
            for (int k = 0; k < second_table_size; ++k)
            {
                //тут надо как то понять что уже такое встречалось
                if ()
                    z++;
                break;
            }

            if (z == 0)
                flag = true;
        }
    }
}

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