#pragma once
#include <iostream>
#include <time.h>
#include <exception>
#include <random>
#include <string>
template <typename T>
struct node {
	node() {};
	node(T value) : data(value) {}
	T data;
};
template <typename T>
struct kopiec {
	long int size = 0;
	long int capacity = 1;
	node<T>* table = new node<T>[capacity];
	kopiec() {

	}
	kopiec(T* tablica, int rozmiar) {

		for (int i = 0; i <= rozmiar; i++) {
			node<T> zmienna = tablica[i];
			//nowa[i] = tablica[i];
		}
		size = rozmiar;
		table = tablica;

		/*int c = 0;
		std::cout << "Aby posortowac wg top-down podaj 1" << std::endl;
		std::cout << "Aby posortowac wg bottom-up podaj 2" << std::endl;
		std::cin >> c;
		while ((c != 1) && (c != 2)) {
			std::cout << "Podaj 1 lub 2!";
			std::cin >> c;
		}
		if (c == 1) {
			top_Down();
		}
		else if (c == 2) {
			buttom_Up();
		}*/
	}
	~kopiec() {
		delete[] table;
	}
	int leftChild(int indeks) {
		int left = 2 * indeks;
		if (left <= size && left >= 0) {
			return left;
		}
		else {
			return -1;
		}
	}
	int rightChild(int indeks) {
		int right = 2 * indeks + 1;
		if (right <= size && right >= 0) {
			return right;
		}
		else {
			return -1;
		}
	}
	int parent(int indeks) {
		if (indeks > 0) {
			int rodzic = (indeks - 1) / 2;
			if (rodzic <= size && rodzic >= 0) {
				return rodzic;
			}
			else {
				return -1;
			}
		}
		else {
			return -1;
		}
	}
	T getAndDeleteMax() {
		T chwilowy = table[0].data;
		size--;
		table[0] = table[size];
		//przesunięcie tablicy o 1 w lewo
		/*for (int i = 0; i < size; i++) {
			table[i].data = table[i + 1].data;
		}

		if (table[0].data < table[1].data) {
			T chwilowyII = table[0].data;
			table[0].data = table[1].data;
			table[1] = chwilowyII;
		}
		if (table[0].data < table[2].data) {
			T chwilowyII = table[0].data;
			table[0].data = table[2].data;
			table[2] = chwilowyII;
		}*/
		przekopcowanieRekWDol(0);

		return chwilowy;
	}
	void addNewNode(node<T> newData) {
		if (size < capacity) {
			table[size] = node<T>{ newData };
			size++;
		}
		else {
			capacity = capacity * 2;
			node<T>* biggerTable = new node<T>[capacity];
			for (int i = 0; i < size; i++) {
				biggerTable[i] = table[i];
			}
			delete[] table;
			table = biggerTable;
			table[size] = node<T>{ newData };
			size++;
		}
		if (size > 1) {
			przekopcowanieRekWGore(size - 1);
		}
	}
	void deleteAll() {
		delete[] table;
	}
	void showAll() {
		for (int i = 0; i < size; i++) {
			std::cout << table[i];
		}
	}
	void przekopcowanieRekWGore(int indeks) {
		auto rodzic = parent(indeks);
		if (rodzic >= 0) {
			T chwilowy = table[rodzic].data;
			if (indeks > 0 && chwilowy < table[indeks].data)
			{
				table[rodzic].data = table[indeks].data;
				table[indeks].data = chwilowy;
				przekopcowanieRekWGore(rodzic);
			}
		}
		else {
			//std::cout << "przekopcowaniewgore nie tak" << std::endl;
		}
	}
	void przekopcowanieRekWDol(int indeks) {
		int largest = indeks;
		int left = leftChild(indeks);
		int right = rightChild(indeks);

		if (left > 0 && table[left].data > table[largest].data) {
			largest = left;
		}
		if (right > 0 && table[right].data > table[largest].data) {
			largest = right;
		}
		if (largest != indeks) {
			node<T> chwilowy;
			chwilowy.data = table[indeks].data;
			table[indeks].data = table[largest].data;
			table[largest] = chwilowy;
			//std::cout << indeks << std::endl;
			przekopcowanieRekWDol(largest);
		}
	}
	void sort() {
		for (int i = 0; i <= size; i++) {
			T chwilowy = table[0].data;
			table[0] = table[size];
			przekopcowanieRekWDol(0);
			table[size] = chwilowy;
		}
	}
	void top_Down() {
		//od indeks 1 do ostatniego
		for (int i = 1; i <= size; i++)
		{
			//rodzic elementu < elementu
			while (table[parent(i)].data < table[i].data)
			{
				przekopcowanieRekWGore(i);
			}
		}
	}
	void buttom_Up() {
		//od ostatniego nie liścia
		for (int i = size; i <= 0; i--)
		{
			//potomek elementu > elementu
			while (table[leftChild(i)].data < table[i].data || table[rightChild(i)].data < table[i].data)
			{
				przekopcowanieRekWDol(i);
			}
		}
	}
};

template <typename T>
std::ostream& operator<<(std::ostream& out, const node<T>& val) {
	out << val.data << std::endl;
	return out;
}
int main() {
	int table[10];
	for (int i = 0; i < 10; i++) {
		table[i] = 10-i;
		std::cout << table[i] << " ";
	}
	std::cout << std::endl;
	kopiec <int> example(table, 10);
	//BucketSort(table, 10);
	for (int i = 0; i < 10; i++) {
		std::cout << table[i] << " ";
	}
	getchar();