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

using namespace std;
double wywolan = 0;
double wywolan1 = 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 has_al_wstaw(int x, int* tablica, int N)
{
	int k = 0;
	for (int i = 0; N-1; i++)
	{
		wywolan++;
		//k = ((x%N) + i) % N;
		int h1 = x%N;
		int h2 =( ((x / N) % (N / 2)) * 2) + 1;
		k = (h1 + i*h2) % N;
		if (tablica[k] == -1)
		{
			tablica[k] = x;
			return true;
		}
	}
	return false;
}
bool hash_al_szukaj(int x,int *tablica, int m)
{
	//int k = 0;
	for (int i = 0; i <= m - 1;i++)
	{
		wywolan1++;
	//k= ((x%m) + i) % m;
		int h1 = x%m;
		int h2 = (((x / m) % (m / 2)) * 2) + 1;
		int k = (h1 + i*h2) % m;
		if (tablica[k] == x)
			return true;
		if (tablica[k] == -1)
			return false;
	}
	return false;
}


int main()
{
	std::default_random_engine gen(std::random_device{}());
	const int N = 1000000;
	int *tablica = new  int[N];
	for (int i = 0; i < N; i++)
	{
		tablica[i] = -1;
	}

	const int M = 100000;
	int* tab = new  int[M]; // tablica losowych liczb
	for (int i = 0; i < M; i++)
	{
		tab[i] = losowa_liczba();
	}

	/*for (int x = 0; x <= 9; x++)
	{
		auto start = std::chrono::high_resolution_clock::now();
		for (int i = (M/10)*x; i <(M/10)*x+n; i++)
		{
			has_al_wstaw(tab[i], tablica, N);
		}
		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double, std::micro> duration = end - start;
		cerr << "Uplynelo: " << duration.count() / 10000 << "us" << "		" << 10 * x << "%" <<"		"<<wywolan/n<< endl;

		for (int i = (N / 10)*x + n; i < (N / 10)*x; i++)
		{
			has_al_wstaw(losowa_liczba(), tablica, N);
		}
	}*/

	for (int y = 0;y < 10;y++)
	{
		wywolan = 0;
		auto start = std::chrono::high_resolution_clock::now();
		for (int i = (M / 10)*y; i <(M / 10)*y + n; i++)
		{
			has_al_wstaw(tab[i], tablica, N);
		}
		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double, std::micro> duration = end - start;
		cout << "Wstawianie" << endl;
		cerr << "Uplynelo: " << duration.count() / 10000 << "us" << "		" << 10 * y << "%" << "		" << "Srednia liczba wywolan: " << wywolan / n << endl;



		if (y > 1)
		{
			shuffle(tab, tab + (y + 1) * 10000, gen);
		}
		wywolan1 = 0;
		start = std::chrono::high_resolution_clock::now();
		for (int i = 0;i < 10000;i++)
		{
			hash_al_szukaj(tab[i], tablica, N);
		}
		end = std::chrono::high_resolution_clock::now();
		duration = end - start;
		cout << "Szukanie" << endl;
		cerr << "Uplynelo: " << duration.count() / 10000 << "us" << "		" << 10 * y << "%" << "		" <<"Srednia liczba wywolan: "<< wywolan1 / n << endl;
		cout << endl;
		if (y < 9)
		{
			for (int i = (N / 10)*y + n; i < (N / 10)*(y + 1); i++)
			{
				has_al_wstaw(losowa_liczba(), tablica, N);
			}
		}
	}


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