// Permutations.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include "pch.h"
#include <iostream>
#include <fstream>
#include <ctime>
#include <time.h>
#include <chrono>
std::fstream out;
std::fstream in;

#define N 9
#define MAX 70000 // Wielkosc stosu
struct stack {
	int first[MAX];
	int second[MAX];
	int top;
};
typedef struct stack STACK;
STACK s;
void push(int x, int y) {
	if (s.top == MAX - 1) {
		std::cout << "Stack is FULL" << std::endl;
		return;
	}
	else {
		s.top += 1;
		s.first[s.top] = x;
		s.second[s.top] = y;
	}
	return;
}
void pop(int* x, int* y) {
	if (s.top == -1) {
		std::cout << "Stack is EMPTY" << std::endl;
		return;
	}
	else {
		*x = s.first[s.top];
		*y = s.second[s.top];
		s.top -= 1;
	}
	return;
}
bool isEmpty() {
	if (s.top == -1) {
		return true;
	}
	else {
		return false;
	}
}
int top() {
	return s.first[s.top];
}

void swap(int* arr, int i, int j) {
	int k = arr[i];
	arr[i] = arr[j];
	arr[j] = k;
}
void Print(int* arr, int l) {

	for (int i = 0; i < l; i++) {
		out << arr[i] << " ";
	}
	out << std::endl;
}
void Permutations(int* array, int* rezult, int length) {
	Print(array, length);
	int* brr = new int[length];
	for (int i = 0; i < length; i++) {
		brr[i] = 0;
	}
	int i = 1;
	while (i < length) {
		if (brr[i] < i) {
			int j = ((i % 2) == 0) ? 0 : brr[i];
			swap(array, i, j);
			Print(array, length);
			brr[i]++;
			i = 1;
		}
		else {
			brr[i] = 0;
			i++;
		}
	}





}

// Funkcje sortujace
int partition(int* increase, int arr[], int low, int high) {
	int pivot = arr[high];    // pivot
	int i = (low - 1);  // Index of smaller element
	*increase = *increase + 2;
	for (int j = low; j <= high - 1; j++)
	{

		*increase = *increase + 1;
		if (arr[j] <= pivot)
		{
			i++;
			int k = arr[i];
			arr[i] = arr[j];
			arr[j] = k;
			*increase = *increase + 4;
		}
	}
	int k = arr[i + 1];
	arr[i + 1] = arr[high];
	arr[high] = k;
	*increase = *increase + 3;
	return (i + 1);
}
unsigned long int QuickSortIteretive(int arr[], int low, int high) {
	int increase = 0;
	while (true) {
		while (low < high) {
			int q = partition(&increase, arr, low, high);
			push((q + 1), high);
			high = q - 1;
			increase += 3;
		}
		if (isEmpty()) {
			break;
		}
		pop(&low, &high);
		increase++;
	}
	return increase;
}
unsigned long int BubleSort(int arr[]) {
	int i, j;
	int increase = 0;
	for (i = 0; i < N - 1; i++) {
		for (j = 0; j < N - i - 1; j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr, j, (j + 1));
				increase++;
			}
		}
	}
	return increase;
}
unsigned long int InsertionSort(int arr[]) {
	int i, key, j;
	int increase = 0;
	for (i = 1; i < N; i++)
	{
		key = arr[i];
		j = i - 1;
		increase += 2;
		while (j >= 0 && arr[j] > key)
		{
			arr[j + 1] = arr[j];
			j = j - 1;
			increase += 2;
		}
		arr[j + 1] = key;
		increase++;
	}
	return increase;
}
//===========================

void Testing_3_functions() {
	std::fstream outQuick;
	outQuick.open("Quicksort_Permutations.csv", std::ios::app);

	std::fstream outBuble;
	outBuble.open("Bublesort_Permutations.csv", std::ios::app);

	std::fstream outInsert;
	outInsert.open("Insertsort_Permutations.csv", std::ios::app);

	int end = 1;
	for (int i = 1; i <= N; i++) {
		end *= i;
	}
	for (int i = 0; i < end; i++) {
		//Tablicy dla kazdego z sortowan
		int* quick = new int[N];
		int* buble = new int[N];
		int* insert = new int[N];
		int* rezult = new int[N];  // Tablica dla N losowych liczb
		int count = 0; // inkrement dla naszej tablicy rezult
		for (int i = 0; i < N; i++) {
			rezult[i] = -1;;
		}
		for (int j = 0; j < N; j++) {
			in >> rezult[j];
			//std::cout << rezult[j] << " ";
		}

		in << std::endl;
		for (int j = 0; j < N; j++) {
			quick[j] = rezult[j];
			buble[j] = rezult[j];
			insert[j] = rezult[j];
		}
		//Nanosekundy
		//QUICK
		auto start_Q = std::chrono::high_resolution_clock::now();
		QuickSortIteretive(quick, 0, (N - 1));
		auto finish_Q = std::chrono::high_resolution_clock::now();
		int time_Q =  std::chrono::duration_cast<std::chrono::nanoseconds>(finish_Q - start_Q).count() ;
		//BUBLE
		auto start_B = std::chrono::high_resolution_clock::now();
		BubleSort(buble);
		auto finish_B = std::chrono::high_resolution_clock::now();
		int time_B = std::chrono::duration_cast<std::chrono::nanoseconds>(finish_B - start_B).count();

		//INSERT
		auto start_I = std::chrono::high_resolution_clock::now();
		InsertionSort(insert);
		auto finish_I = std::chrono::high_resolution_clock::now();
		int time_I = std::chrono::duration_cast<std::chrono::nanoseconds>(finish_I - start_I).count();

		//Milisekundy
		//Testujemy w zaleznosci od casu, liczymy czas
		// Testing Quick Sort
/*		unsigned long q = clock();
		//quickSort(quick, 0, (N - 1));
		QuickSortIteretive(quick, 0, (N - 1));
		int time_Q = clock() - q;
		//Testing Buble Sort
		unsigned long bub = clock();
		BubleSort(buble);
		int time_B = clock() - bub;
		// Testing Insert Sort
		unsigned long ins = clock();
		InsertionSort(insert);
		int time_I = clock() - ins;
		*/
	/*	std::cout  <<
			"\t Quick : " << time_Q <<
			"\t Buble : " << time_B <<
			"\t Insert : " << time_I <<
			std::endl;
*/

		//--------------------------------------------------
		outQuick << time_Q << std::endl;
		//Buble
		outBuble << time_B << std::endl;
		//Insert
		outInsert << time_I << std::endl;
		//---------------------------------------------------
		delete[] quick;
		delete[] buble;
		delete[] insert;
		delete[] rezult;
	}
	outQuick.close();
	outBuble.close();
	outInsert.close();
}


int main()
{

	int* arr = new int[N];
	int* brr = new int[N]; // tablica na kolejne permutacje
	//Tworzymy tablice od 0 do n
	for (int i = 0; i < N; i++) {
		arr[i] = i;
		brr[i] = -1;
	}
	out.open("Permutations_10.csv", std::ios::app);
	Permutations(arr, brr,  N);
	std::cout << "Generator wszystkich permutacj o dlugosci " << N << " zakonczyl dzialanie " << std::endl;
	out.close();
	in.open("Permutations_10.csv", std::ios::in | std::ios::out);
	Testing_3_functions();
	in.close();

	std::fstream outQuick;
	outQuick.open("Quicksort_Permutations.csv", std::ios::in | std::ios::out);


	std::fstream outBuble;
	outBuble.open("Bublesort_Permutations.csv", std::ios::in | std::ios::out);


	std::fstream outInsert;
	outInsert.open("Insertsort_Permutations.csv", std::ios::in | std::ios::out);

	int end = 1;
	for (int i = 1; i <= N; i++) {
		end *= i;
	}
	long unsigned int max_Q = 0;
	int min_Q = 10000000;
	long unsigned int suma_Q = 0;
	long unsigned int max_B = 0;
	int min_B = 10000000;
	long unsigned int suma_B = 0;
	long unsigned int max_I = 0;
	int min_I = 10000000;
	long unsigned int suma_I = 0;
	int min_id_Q = 0;
	int max_id_Q = 0;
	int min_id_B = 0;
	int max_id_B = 0;
	int min_id_I = 0;
	int max_id_I = 0;

	for (int i = 0; i < end; i++) {
		int quick;
		outQuick >> quick;
		outQuick << std::endl;
		if (max_Q < quick) {
			max_Q = quick;
			max_id_Q = i;
		}
		if (min_Q > quick) {
			min_Q = quick;
			min_id_Q = i;
		}
		suma_Q += quick;
		int buble;
		outBuble >> buble;
		outBuble << std::endl;
		if (max_B < buble) {
			max_B = buble;
			max_id_B = i;
		}
		if (min_B > buble) {
			min_B = buble;
			min_id_B = i;
		}
		suma_B += buble;
		int insert;
		outInsert >> insert;
		outInsert << std::endl;
		if (max_I < insert) {
			max_I = insert;
			max_id_I = i;
		}
		if (min_I > insert) {
			min_I = insert;
			min_id_I = i;
		}
		suma_I += insert;
	//	std::cout << quick << "\t" << buble << "\t" << insert << std::endl;
		if (outQuick.eof() || outBuble.eof() || outInsert.eof() ){
			end = i;
			break;
		}
	}
	std::fstream rezult;
	rezult.open("Rezult.txt", std::ios::app);

	rezult << "QuickSort" << std::endl;
	rezult << "Czas pesymistyczny : " << max_Q << ".Ta tablica pod numerem : " <<max_id_Q + 1 << std::endl;
	rezult << "Czas optymistyczny : " << min_Q << ".Ta tablica pod numerem : " << min_id_Q + 1 << std::endl;
	rezult << "Czas sredni : " << (suma_Q / end) << std::endl;

	rezult << "BubleSort" << std::endl;
	rezult << "Czas pesymistyczny : " << max_B << ".Ta tablica pod numerem : " << max_id_B + 1 << std::endl;
	rezult << "Czas optymistyczny : " << min_B << ".Ta tablica pod numerem : " << min_id_B + 1 << std::endl;
	rezult << "Czas sredni : " << (suma_B / end) << std::endl;

	rezult << "InsertSort" << std::endl;
	rezult << "Czas pesymistyczny : " << max_I << ".Ta tablica pod numerem : " << max_id_I + 1 << std::endl;
	rezult << "Czas optymistyczny : " << min_I << ".Ta tablica pod numerem : " << min_id_I + 1 << std::endl;
	rezult << "Czas sredni : " << (suma_I / end) << std::endl;

	rezult.close();

	outQuick.close();
	outBuble.close();
	outInsert.close();


}