#include <chrono>
#include <thread>
#include <random>
#include <iostream>
#include <algorithm>


int licznik1 = 0;
int licznik = 0;
int n = 10000;
int losowa_liczba(int min = 0, int max = std::numeric_limits<int>::max())
{
	static std::default_random_engine gen(std::random_device{}());
	static std::uniform_int_distribution<int> dist;
	return dist(gen, std::uniform_int_distribution<int>::param_type{ min, max });
}
bool hash_al_wstaw(int x, int* tab, int N)
{

	int k = 0;
	for (int i = 0; N - 1; i++)
	{
		licznik++;
		k = ((x%N) + i) % N;
		if (tab[k] == -1)
		{
			tab[k] = x;
			return true;
		}
	}
	return false;

}

int hash_al_szukaj(int x, int*tab,int N)
{
	int k = 0;
	for (int i = 0; N - 1; i++)
	{
		licznik1++;
		//int k = ((x%N) + i) % N;
		int k = (((x%N) + i*(((x / N) % (n / 2))) * 2) + 1) % N;
		if (tab[k] == x)
		{
			return true;
		}
		if (tab[k] == -1)
			return false;
	}
	return false;
}

int main()
{
	std::default_random_engine gen(std::random_device{}());

	const int N = 1000000;
	int* tab = new int[N];
	for (int i = 0; i < N; i++)
	{
		tab[i] = -1;
	}
	const int M = 100000;
	int* tab1 = new int[M];
	for (int i = 0; i < M; i++)
	{

		tab1[i] = losowa_liczba();
	}


	for (int l = 0; l <= 9; l++)
	{

		licznik = licznik1 = 0;
		auto start = std::chrono::high_resolution_clock::now();
		for (int i = (M / 10)*l; i < (M / 10)*l + n; i++)
		{

			hash_al_wstaw(tab1[i], tab, N);
		}





		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double, std::micro> duration = end - start;
		std::cerr << "Wstawianie : " << duration.count() / 10000 << "us dla " << 10 * l << "%    ";
		std::cout << licznik / 10000.0 << "\n";
		shuffle(tab1, tab1 + (1 + l)*n, gen);
		start = std::chrono::high_resolution_clock::now();
		for (int i = 0; i < n; i++)
		{

			if (!hash_al_szukaj(tab1[i], tab, N))
				std::cout << "error";
		}



		end = std::chrono::high_resolution_clock::now();
		duration = end - start;
		std::cerr << "Szukanie : " << duration.count() / 10000 << "us dla " << 10 * l << "%    ";
		std::cout << licznik1 / 10000.0 << "\n";



		for (int i = 0; i < M - n; i++)
		{
			hash_al_wstaw(losowa_liczba(), tab, N);
		}

		std::cerr << "\n";
	}


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


}