#include <iostream>
#include <algorithm>
#include <chrono>

int licznik = 0;
/*
int h(int x, int akt_i, int T)
{
    if (akt_i == 0) return x % T;

    return (h(x, 0, T) + akt_i) % T;
}
*/
int h1(int x, int T)
{
    return x%T;
}

int h2(int x, int T)
{
    return (((x / T) %(T / 2)) * 2) + 1;
}

int h(int x, int akt_i, int T)
{
    return (h1(x,T) + akt_i*h2(x,T)) % T;
}

bool hash_al_wstaw(int* tab, int x, int T)
{
    for (int i = 0; i < T; i++)
    {
        int k = h(x, i, T);
        licznik++;
        if (tab[k] == -1 || tab[k] == -2)
        {
            tab[k] = x;
            return true;
        }
    }
    return false;
}

bool hash_al_szukaj(int* tab, int x, int T)
{
    for (int i = 0; i < T; i++)
    {
        int k = h(x, i, T);
        licznik++;
        if (tab[k] == x) return true;
        if (tab[k] == -1) return false;
    }
    return false;
}

int main()
{
    int T = 1048576;
    int* tab = new int[T];
    for (int i = 0; i < T; i++)
    {
        tab[i] = -1;
    }
    //hash_al_wstaw(tab, 1048576, T);
    //std::cout << tab[0];

    int rozmiar = 12000000;
    int* tablica = new int[rozmiar];
    for (int i = 0; i < rozmiar; i++)
    {
        tablica[i] = i;
    }
    //std::cout << tablica[515];
    std::random_shuffle(tablica, tablica + rozmiar);
    //std::cout << tablica[515];

    std::cout << "Wstawianie: " << std::endl;
    std::cout << std::endl;

    std::cout << "0%: " << std::endl;
    auto start = std::chrono::high_resolution_clock::now();

    for (int i = 0; i < 10000; i++)
    {
        hash_al_wstaw(tab, tablica[i], T);
    }

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::micro> duration = end - start;
    std::cerr << "Uplynelo: " << duration.count() << "us\n";
    std::cout << "Wywolania: " << licznik << std::endl;
    licznik = 0;
    int pom = 1048576/10;
    //std::cout << pom << std::endl;


    for (int j = 1; j < 10; j++)
    {
        std::cout << j << "0%: " << std::endl;


        for (int i = 0; i < T; i++)
        {
            tab[i] = -1;
        }

        auto start = std::chrono::high_resolution_clock::now();

        for (int i = 0; i < pom*j; i++)
        {
            hash_al_wstaw(tab, tablica[i], T);
        }
        licznik = 0;
        for (int i = pom * j; i < pom * j + 10000; i++)
        {
            hash_al_wstaw(tab, tablica[i], T);
        }

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::micro> duration = end - start;
        std::cerr << "Uplynelo: " << duration.count() << "us\n";
        std::cout << "Wywolania: " << licznik << std::endl;
        licznik = 0;
    }

    std::cout << std::endl;
    std::cout << "Szukanie: " << std::endl;
    std::cout << std::endl;

    for (int j = 1; j < 10; j++)
    {
        std::cout << j << "0%: " << std::endl;

        for (int i = 0; i < T; i++)
        {
            tab[i] = -1;
        }


        for (int i = 0; i < pom*j; i++)
        {
            hash_al_wstaw(tab, tablica[i], T);
        }

        auto start = std::chrono::high_resolution_clock::now();
        licznik = 0;
        for (int i = 0; i < pom * j; i+=pom*j/10000)
        {
            hash_al_szukaj(tab, tablica[i], T);
        }

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double, std::micro> duration = end - start;
        std::cerr << "Uplynelo: " << duration.count() << "us\n";
        std::cout << "Wywolania: " << licznik << std::endl;
        licznik = 0;
    }

    delete[] tab;
    delete[] tablica;
    system("pause");
    return 0;
}