#pragma once

#include <iostream>
#include <random>

using namespace std;

/*template <typename T>
class CTablice
{
public:
	T *tab;
	CTablice()
	{
		tab = new int[n] {};
	}
	int shake_sort();
	void quick_sort_H();

};*/

class CSort {
public:

	int nElements;

	int* randomTable(int size) {
		int *T = nullptr;
		try {
			T = new int[size];
		}
		catch (std::bad_alloc) {
			getchar();
			std::cin.ignore();
			exit(0);
		}
		random_device rd;
		mt19937 mt(rd());
		uniform_int_distribution<int>dist(-1000, 2147483647);
		for (int i = 0; i < size; ++i) {
			T[i] = dist(mt);
		}
		return T;
	}

	int* growingTable(int size) {
		int *T = nullptr;
		try {
			T = new int[size];
		}
		catch (std::bad_alloc) {
			getchar();
			std::cin.ignore();
			exit(0);
		}
		for (int i = 0; i < size; i++) {
			T[i] = i;
		}
		return T;
	}

	int* decreasingTable(int size) {
		int *T = nullptr;
		try {
			T = new int[size];
		}
		catch (std::bad_alloc) {
			getchar();
			std::cin.ignore();
			exit(0);
		}
		for (int i = 0; i < size; i++) {
			T[i] = size - i;
		}
		return T;
	}

	int* smallPartShakedTable(int size) {
		int *T = nullptr;
		try {
			T = new int[size];
		}
		catch (std::bad_alloc) {
			getchar();
			std::cin.ignore();
			exit(0);
		}
		for (int i = 0; i < size; i++) {
			if (i % 10 == 0) {
				T[i] = size - i;
			}
			else T[i] = i;
		}
		return T;
	}
};

class CTablica:CSort
{
public:
	int *tab{ nullptr };
	int l_porownan, l_inwersji;
	CTablica(int number, int n)
	{
		switch (number)
		{
			case 1:
			{
				tab = randomTable(n);
				break;
			}
			case 2:
			{
				tab = growingTable(n);
				break;
			}
			case 3:
			{
				tab = decreasingTable(n);
				break;
			}
			case 4 :
			{
				tab = smallPartShakedTable(n);
				break;
			}
		}
	}

	void swap(int i, int j)
	{
		int temp = tab[i];
		tab[i] = tab[j];
		tab[j] = temp;
	}

	void show(int n)
	{
		for (int i = 0; i < n; i++)
		{
			cout << tab[i] << " ";
		}
		cout << "\nLiczba inwersji: " << l_inwersji << endl;
		cout << "Liczba porownan: " << l_porownan << endl;
	}
};

class ShakeSort:public CTablica
{
public:
	ShakeSort(int number, int n) :CTablica(number,n) {};
	void shake_sort(ShakeSort *T, int n);

};

class CoctailSort :public CTablica
{
public:
	CoctailSort(int number, int n) :CTablica(number, n) {};
	void cocktailSort(CoctailSort *T, const int lowestIndex, const int highestIndex);
};

class Loumoto:public CTablica
{
public:
	Loumoto(int number, int n) :CTablica(number, n) {};
	void quickSort_L(Loumoto *T, int lowestIndex, int highestIndex);
};

class Hoare :public CTablica
{
public:
	Hoare(int number, int n) :CTablica(number, n) {};
	void quick_sort_H(Hoare *T, int low, int high);
};

class Tree :public CTablica
{
public:
	Tree(int number, int n) :CTablica(number, n) {};
	void sortHeap(Tree *T, const int lowestIndex, const int highestIndex);
};

//Coctail sort
void CoctailSort::cocktailSort(CoctailSort *T, const int lowestIndex, const int highestIndex)
{
	int len = highestIndex - lowestIndex + 1;
	bool swapped = true;
	while (swapped) {
		for (int i = 0; i < len - 1; i++) {
			T->l_porownan++;
			if (T->tab[i] > T->tab[i+1]) {
				T->swap(i, i+1);
				T->l_inwersji++;
				swapped = true;
			}
		}
		if (swapped = false) {
			break;
		}
		swapped = false;
		for (int i = len - 1; i > 0; i--) {
			T->l_porownan++;
			if (T->tab[i-1] > T->tab[i]) {
				T->l_inwersji++;
				T->swap(i, i-1);
				swapped = true;
			}
		}
	}
}


//Loumoto sort
/*
po wyznaczeniu skrajnego elementu tablicy (z prawej) jako pivota, musimy wyznaczyć jego właściwe położenie. Do tego indeksy: i oraz j.
Porównujemy kolejno wszystkie elementy od lewej z pivotem. Służy nam do tego zmienna j oznaczająca indeks tablicowy porównywanego aktualnie elementu
*/
int partitionLomuto(Loumoto *T, const int lowestIndex, const int highestIndex) {
	int pivot = T->tab[highestIndex];
	int swapIndex = lowestIndex - 1; //place for swaping
	for (int i = lowestIndex; i < highestIndex; i++)
	{
		T->l_porownan++;
		if (T->tab[i] <= pivot)
		{
			swapIndex++;
			T->swap(swapIndex, i);
			T->l_inwersji++;
		}
	}
	T->swap(swapIndex + 1, highestIndex);
	T->l_inwersji++;
	return swapIndex + 1;
}

void Loumoto::quickSort_L(Loumoto *T, int lowestIndex, int highestIndex) {
	if (lowestIndex < highestIndex) {

		int partitionIndex = partitionLomuto(T, lowestIndex, highestIndex);

		quickSort_L(T, lowestIndex, partitionIndex - 1);
		quickSort_L(T, partitionIndex + 1, highestIndex);

	}
}

//Tree sort
//poddrzewo zakorzenione w wezle
void subTree(Tree *T, const int first, const int last)
{
	int toSwap = last;
	int leftIndex = 2 * last + 1;
	int rightIndex = leftIndex + 1;

	//gdy lewe dziecko wieksze od korzenia(tego od czego wychodzi)
	T->l_porownan++;
	if (leftIndex<first && T->tab[leftIndex]>T->tab[toSwap])
	{
		toSwap = leftIndex;
	}

	//gdy prawe -//-
	T->l_porownan++;
	if (rightIndex<first && T->tab[rightIndex]>T->tab[toSwap])
	{
		toSwap = rightIndex;
	}

	if (toSwap != last) {
		T->swap(last, toSwap);
		T->l_inwersji++;
		subTree(T, first, toSwap);
	}
}

void Tree::sortHeap(Tree *T, const int lowestIndex, const int highestIndex)
{
	for (int i = (highestIndex / 2) - 1; i >= 0; i--) {
		subTree(T, i, highestIndex);
	}

	for (int i = highestIndex - 1; i >= 0; i--) {
		T->swap(0, i);
		subTree(T, i, 0);
	}
}



// Benio
//Shake sort
void ShakeSort::shake_sort(ShakeSort *T, int n)
{
	int l_inwersji{ 0 };
	for (int i = 0; i < n / 2; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (T->tab[j-1] > T->tab[j])
			{
				T->l_porownan++;
				T->swap(j, j - 1);
				T->l_inwersji++;
			}
		}
		for (int k = n - i - 1; k > 0; k--)
		{
			if (T->tab[k-1] > T->tab[k])
			{
				T->l_porownan++;
				T->swap(k, k - 1);
				T->l_inwersji++;
			}
		}
	}
}

//Hoare sort
int partition(Hoare *T, int low, int high)
{
	int pivot{ T->tab[low] };
	int i = low - 1, j = high + 1;
	while (true)
	{
		do {
			i++;
			T->l_porownan++;
		} while (T->tab[i] < pivot);

		do {
			j--;
			T->l_porownan++;
		} while (T->tab[j] > pivot);

		if (i >= j)
			return j;

		T->swap(i, j);
		T->l_inwersji++;
	}
}

void Hoare::quick_sort_H(Hoare *T, int low, int high)
{
	if (low < high)
	{
		int parti = partition(T, low, high);
		quick_sort_H(T, low, parti);
		quick_sort_H(T, parti + 1, high);
	}
}