// HeapSort.cpp : This file contains the 'main' function. Program execution begins and ends there.
//This program encrypt every step of algoritm. And after that decrypt our first permutation
#include <iostream>
#include <string>
#define N 1000000
using namespace std;

struct  per{
	char l;
	char r;
};
struct mov {
	per* P = new per[N];
	int top;
};
void push(mov *M, char l, char r) {
	M->top++;
	if (M->top >= N) {
		cout << "Sturcture is FULL" << endl;
		return ;
	}
	M->P[M->top].l = l;
	M->P[M->top].r = r;

}
void pop(mov *M , char* l, char* r) {
	if (M->top < 0) {
		cout << "End of structure" << endl;
	}
	else {

		*l = M->P[M->top].l;
		*r = M->P[M->top].r;
		M->top--;
	}

}
bool full(mov* M) {
	if (M->top < 0) {
		return false;
	}
	return true;
}
void display(mov *M, char* l, char* r) {
	*l = M->P[M->top].l;
	*r = M->P[M->top].r;
}
//----------------------------------------------------------
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
		cout << arr[i] << " ";
	cout << "\n";
}

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void buildMaxHeap(mov * M,int arr[], int n)
{
	for (int i = 1; i < n; i++)
	{    // d > T
		if (arr[i] > arr[(i - 1) / 2])
		{
			int j = i;
			while (arr[j] > arr[(j - 1) / 2])
			{
				printArray(arr, n);
				if (j % 2 == 1) {
					push(M, '0', '0');
				}
				else {
					push(M, '0', '1');
				}
				swap(arr[j], arr[(j - 1) / 2]);
				j = (j - 1) / 2;
			}
		}
		push(M, '1', '0');
	}
}

void heapSort(mov * M, int arr[], int n)
{
	bool log = false;
	buildMaxHeap(M, arr, n);
	for (int i = n - 1; i > 0; i--)
	{
		swap(arr[0], arr[i]);
		printArray(arr, n);
		int root = 0, child;
		do{
			log = false;
			child = (2 * root + 1);
			if (arr[child] < arr[child + 1] && child < (i - 1))
				child++;

			if (arr[root] < arr[child] && child < i) {
				if (child % 2 == 1) {//lewe dziecko
					push(M, '0',  '0');
				}
				else {
					push(M, '0',  '1');
				}
				swap(arr[root], arr[child]);
			}
			if((arr[root] < arr[child])  ) {
					push(M, '1',  '0'); // Bit STOP
					log = true;
			}
			root = child;
		} while (child < i );
		if (log == false) {
			push(M, '1',  '0'); // Bit STOP
		}
	}
}
void unheapSort(mov * M, int arr[], int n) {
	char  l, r,k;
	//Czesc dla HeapSort for
	mov* H = new mov;
	H->top = -1;
	pop(M, &l, &r);
	for (int i = 1; i < n; i++) {
		int root = 0, child;
		pop(M,  &l, &r);
		//Idziemy po sciezce do napotkania bitu stop
		while (l == '0' &&  full(M)) {
			push(H,  l, r);
			pop(M, &l, &r);
		}//While

		while (full(H)) {
			pop(H,  &l, &r);
			if (l == '0' && r == '0') {
				root = 2 * root + 1;
			}
			if (l == '0' && r == '1') {
				root = 2 * root + 2;
			}
		}
		//Robimy MIN dla elementu root;
		child = root;
		while (root > 0) {
			root = (child - 1) / 2;
			swap(arr[root], arr[child]);
			child = root;
		}
		swap(arr[0], arr[i]);

	}//For

	cout << "Befor MAX ";
	printArray(arr, n);

	//czesc dla MaxHeap
	mov * K = new mov;
	K->top = -1;
	mov* R = new mov;
	R->top = -1;
	for (int i = n -1; i >= 0; i--) {
		int root = i, child;
		pop(M,  &l, &r);
		while (l == '0'  &&  full(M)) {
			push(K, l, r);
			pop(M,  &l, &r);
		}//While
		while (full(K)) {
			pop(K, &l, &r);
			push(R, l, r);
			root = (root - 1) / 2;
		}
		while (root < i) {
			pop(R, &l, &r);
			if (l == '0' && r == '0') {
				swap(arr[root], arr[root * 2 + 1]);
				root = 2 * root + 1;
			}
			if (l == '0'&& r == '1') {
				swap(arr[root], arr[root * 2 + 2]);
				root = root * 2 + 2;
			}
		}
		//Robimy szos dla elementu root;
		printArray(arr, n);
	}
}

// Driver program
int main()
{
	char s, l, r;
	mov * A = new mov;
	A->top = -1;
	push(A, '1', '0');

//	int arr[] = { 12, 11, 13, 5, 6, 7,2,9,14,8,4 };
//	int arr[] = { 12, 11, 13, 5, 6, 7,2,9,14,8,4,78 };
	int arr[] = { 43,26,45,17,19,31,1,4,143,61,37,1 };

	int n = sizeof(arr) / sizeof(arr[0]);

	heapSort(A,arr, n);

	cout << "Sorted array is \n";
	printArray(arr, n);
	cout << endl;
	unheapSort(A, arr, n);
	cout << endl << "Our permutation is : " <<endl;
	printArray(arr, n);

}