#include "pch.h"
#include "stdafx.h"
#include <random>
#include <iomanip>
#include <algorithm>
#include <map>
#include <vector>
#include <time.h>
#include "tree.h"

using namespace std;

struct Matavimas {
	float laikasTree;
	float laikasMap;
};

Matavimas TestTrees(int N, int sortType);
void shuffle(int *A, int N);
void shuffle_weakly_sorted(int *A, int N);

int main()
{
	srand(time(NULL));
	Matavimas dvejM;
	int N = 30;

	for (int i = 0; i < 4; i++)
	{
		cout << "---------------------------------------\nDuomenu skaicius: " << N << endl;

		dvejM = TestTrees(N, 1);
		cout << " Sumaisyta atsitiktine tvarka seka: " << endl;
		cout << setprecision(3) << "  Paieskos laikas dvejetainiame : " << dvejM.laikasTree << endl;
		cout << setprecision(3) << "  Paieskos laikas subalansuotame: " << dvejM.laikasMap << endl;
		cout << endl;

		dvejM = TestTrees(N, 2);
		cout << " Silpnai rusiuota seka: " << endl;
		cout << setprecision(3) << "  Paieskos laikas dvejetainiame : " << dvejM.laikasTree << endl;
		cout << setprecision(3) << "  Paieskos laikas subalansuotame: " << dvejM.laikasMap << endl;

		N = N * 2;
	}

	return 0;
}

Matavimas TestTrees(int N, int sortType)
{
	int *Ids = new int[N];
	for (int i = 0; i < N; i++)
		Ids[i] = i + 1;

	//dvejetainis paieskos medis
	Tree t2;
	//subalansuotas dvejetainis paieskos medis
	map<int, T> t3;

	if (sortType == 1)
		shuffle(Ids, N);
	else if (sortType == 2)
		shuffle_weakly_sorted(Ids, N);

	//i dvejetaini medi
	for (int i = 0; i < N; i++) {
		T data;
		data.id = Ids[i];
		t2.insert(data);
	}
	//i subalansuota stl medi
	for (int i = 0; i < N; i++) {
		T data;
		data.id = Ids[i];
		t3[data.id] = data;
	}

	Matavimas mat;
	int kart;
	kart = 1000;

	//DVEJETAINIS MEDIS
	clock_t time = clock();
	for (int i = 0; i < kart; i++) {

		for (int j = 1; j <= N; j++) {
			if (t2.find(j) == NULL)
				cout << " klaida: nerado dvejetainiame medyje " << j << endl;
		}
	}
	time = clock() - time;
	float sec1 = (float)time / ((float)kart*(float)N*(float)CLOCKS_PER_SEC);

	mat.laikasTree = sec1;

	//SUBALANSUOTAS MEDIS
	time = clock();
	for (int i = 0; i < kart; i++) {

		for (int j = 1; j <= N; j++) {
			if (t3[j].id != j)
				cout << " klaida: nerado subalansuotame medyje" << j << endl;
		}
	}
	time = clock() - time;
	sec1 = (float)time / ((float)kart*(float)N*(float)CLOCKS_PER_SEC);

	mat.laikasMap = sec1;

	delete[] Ids;

	return mat;
}

void shuffle(int *A, int N) {
	for (int i = 0; i < N - 1; i++) {
		//j = i ... N-1
		int j = i + (rand() % (N - i));
		swap(A[i], A[j]);
	}
}

void shuffle_weakly_sorted(int *A, int N)
{
	vector<int> V(N);

	for (int i = 0; i < N; i++)
		V[i] = A[i];
	std::sort(V.begin(), V.end());
	for (int i = 0; i < N; i++)
		A[i] = V[i];

	int N2 = N - (int)pow((float)N, 0.9);

	for (int i = 0; i < N2; i++) {
		int i1 = rand() % N;
		int i2 = rand() % N;
		swap(A[i1], A[i2]);
	}
}