#include <iostream>
#include <chrono>
#include <thread>
#include <random>
#include <algorithm>
using namespace std;
long int rozmiar_zbior = 12000000;
int rozmiar_mieszajaca = 1048576;
double licznik = 0;
double counter = 0;

bool wstaw(int *tablica, int rozmiar, int x) {

		int k;
		for (int i = 0; i<rozmiar; i++) {

			if(i == 0) k = x % rozmiar;
			else k = (x % rozmiar + i) % rozmiar;
            licznik++;
			//k = ( ((x % rozmiar) + i*((((x/rozmiar) % (rozmiar/2)) * 2) + 1)) % rozmiar);

			if(tablica[k] == -1) {
				tablica[k] = x;
				return true;
			}
		}
		return false;
	}

	bool szukaj(int *tablica, int rozmiar, int liczba) {
		int k;
		for(int i=0; i<rozmiar; i++) {

			if(i == 0) k = liczba % rozmiar;
			else k = (liczba % rozmiar + i) % rozmiar;

			if(tablica[k] == liczba) return true;
			if(tablica[k] == -1) return false;
		}
		return false;
	}

int main() {

// Testowy zbiór liczb do wstawiania do tablicy mieszajacej

	int *tab_zbior = new int [rozmiar_zbior];
	int *tab_miesz = new int [rozmiar_mieszajaca];

	for(int i=0; i<rozmiar_zbior; i++) {
		tab_zbior[i] = i;
	}

	std::random_shuffle(tab_zbior, tab_zbior+rozmiar_zbior);




	cout << "Wstawianie\n";

	for (int n = 0; n < 10; n++) {

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

		for (int i = 0; i < n * (rozmiar_mieszajaca/10); i++)
		{
			wstaw(tab_miesz, rozmiar_mieszajaca, tab_zbior[i]);
		}
		licznik = 0;
		auto start = std::chrono::high_resolution_clock::now();
		for (int i = 0; i < 10000; i++)
		{
			wstaw(tab_miesz, rozmiar_mieszajaca, tab_zbior[n*(rozmiar_mieszajaca/10)+i]);
		}

		auto end = std::chrono::high_resolution_clock::now();
		std::chrono::duration<double, std::micro> duration = end - start;
		std::cerr << n << "0% -> Czas wstawianie: " << duration.count() / 10000 << "us\n";
		std::cout << n << "ilosc wywolan : " << licznik / 10000 << "\n";
	}
//	for(int i=0; i<rozmiar_mieszajaca; i++) {
//	 	wstaw(mieszajaca, rozmiar_mieszajaca, tablica[i]);
//	 	cout << tablica[i] << endl;
//	 }
//	 mieszajaca[23] = 5;
//	 bool t = szukaj(mieszajaca, rozmiar_mieszajaca, 5);
//	 cout << t;




	return 0;

}