//ALGO2 IS1 220b LAB04
//Sebastian Ratanczuk
//sebastian-ratanczuk@zut.edu.pl
#include <iostream>
#include <string>
#include <time.h>
#include <algorithm>

template <typename T>
class Heap;

template <typename T>
class Array {
	friend class Heap<T>;
private:
	void increase()
	{
		this->MAX_CAP *= this->multip;
		T* new_array = new T[MAX_CAP];

		for (unsigned int i = 0; i < this->counter; i++)
			new_array[i] = this->array[i];

		delete[] this->array;
		array = new_array;
	}

	void set(unsigned int number, T data)
	{
		if (number < this->MAX_CAP)
			this->array[number] = data;
	}

public:
	T* array;
	unsigned int counter;
	unsigned int MAX_CAP;
	const int multip = 2;

	Array()
	{
		this->MAX_CAP = 1;
		this->counter = 0;
		this->array = new T[MAX_CAP];
	}

	Array(Array* data)
	{
		this->MAX_CAP = data->MAX_CAP;
		this->counter = data->counter;
		this->array = new T[this->MAX_CAP];
		for (int i = 0; i < this->counter; i++)
			this->array[i] = data->array[i];
	}

	virtual ~Array()
	{
		//for (unsigned int i = 0; i < this->counter; i++)
			//delete array[i];
		delete[] array;
	}

	void add_(T data)
	{
		if (this->counter < this->MAX_CAP)
		{
			this->array[this->counter] = data;
			counter++;
		}
		else
		{
			this->increase();
			this->array[this->counter] = data;
			counter++;
		}
	}

	T return_(unsigned int number)
	{
		if (number < this->counter)
			return this->array[number];
		else
			return NULL;
	}

	std::string to_string(int a)
	{
		std::string str;
		for (unsigned int i = 0; i < a; i++)
			str = str + std::to_string(array[i]) + " ";
		return str;
	}

	void reset_()
	{
		this->MAX_CAP = 1;
		this->counter = 0;

		T* new_array = new T[MAX_CAP];

		delete[] this->array;
		this->array = new_array;
	}
};

template <typename T>
class Heap : private Array<T>
{
public:

	Heap() {}

	Heap(Array<T>* a)
	{
		this->array = a->array;
		this->counter = a->counter;
		this->MAX_CAP = a->MAX_CAP;
	}

	void reset()
	{
		this->reset_();
	}

	void heapUp()
	{
		for (int x = 0; x < this->counter; x++)
		{
			for (int i = (this->counter - 1); i >= x; i--)
			{
				int parent = (i - 1) / 2;
				int a = this->array[i];
				int b = this->array[parent];
				if (this->array[i] > this->array[parent])
				{
					T tmp = this->array[i];
					this->array[i] = this->array[parent];
					this->array[parent] = tmp;
				}
			}
		}
	}

	void heapDown(int value)
	{
		unsigned int current = value;
		unsigned int left = value * 2 + 1;
		unsigned int right = value * 2 + 2;

		if (left <= this->counter && right >= this->counter)
		{
			if (this->array[current] < this->array[left])
			{
				T tmp = this->array[current];
				this->array[current] = this->array[left];
				this->array[left] = tmp;
				current = left;
			}
			return;
		}

		if (left >= this->counter && right >= this->counter)
			return;

		while ((this->array[current] < this->array[left]) || (this->array[current] < this->array[right]))
		{
			if ((this->array[left] - this->array[current]) > (this->array[right] - this->array[current]))
			{
				T tmp = this->array[current];
				this->array[current] = this->array[left];
				this->array[left] = tmp;
				current = left;
			}
			else
			{
				T tmp = this->array[current];
				this->array[current] = this->array[right];
				this->array[right] = tmp;
				current = right;
			}

			left = current * 2 + 1;
			right = current * 2 + 2;

			if (left <= this->counter && right >= this->counter)
			{
				if (this->array[current] < this->array[left])
				{
					T tmp = this->array[current];
					this->array[current] = this->array[left];
					this->array[left] = tmp;
					current = left;
				}
				break;
			}

			if (left >= this->counter && right >= this->counter)
				break;
		}
	}

	void add(T data)
	{
		if (this->counter == 0)
			this->add_(data);
		else
		{
			unsigned int current = this->counter;
			this->add_(data);
			unsigned int parrent = (current - 1) / 2;
			while (this->array[parrent] < this->array[current])
			{
				T tmp = this->array[current];
				this->array[current] = this->array[parrent];
				this->array[parrent] = tmp;
				current = parrent;
				parrent = (current - 1) / 2;
				if (current == 0)
					break;
			}
		}
	}

	T pop()
	{
		if (this->counter == 0)
		{
			const T to_ret = this->array[0];
			this->reset_();
			return to_ret;
		}
		else if (this->counter > 0)
		{
			const T to_ret = this->array[0];

			this->array[0] = this->array[--this->counter];
			this->array[this->counter] = 0;
			unsigned int current = 0;
			unsigned int left = 1;
			unsigned int right = 2;

			if (left >= this->counter && right >= this->counter)
				return to_ret;

			if (left <= this->counter && right > this->counter)
			{
				if (this->array[current] > this->array[left])
				{
					T tmp = this->array[current];
					this->array[current] = this->array[left];
					this->array[left] = tmp;
					current = left;
				}
				return to_ret;
			}

			while ((this->array[current] < this->array[left]) || (this->array[current] < this->array[right]))
			{
				if ((this->array[left] - this->array[current]) > (this->array[right] - this->array[current]))
				{
					T tmp = this->array[current];
					this->array[current] = this->array[left];
					this->array[left] = tmp;
					current = left;
				}
				else
				{
					T tmp = this->array[current];
					this->array[current] = this->array[right];
					this->array[right] = tmp;
					current = right;
				}
				left = current * 2 + 1;
				right = current * 2 + 2;
				if (right > this->counter || left > this->counter)
					break;
			}
			return to_ret;
		}
		else
			std::cout << "tablica pusta";
	}

	std::string to_string()
	{
		std::string str;

		for (int i = 0; i < 10; i++)
			str = str + std::to_string(this->array[i]) + " ";
		return str;
	}

	void createHeap()
	{
		for (int x = this->counter; x >= 0; x--)
		{
			this->heapDown(x);
		}
	}

	void sortHeap()
	{
		this->createHeap();
		//std::cout << this->to_string() << std::endl;
		const unsigned int length = this->counter;
		for (int i = 0; i < length; i++)
		{
			unsigned int index = this->counter-1;
			T tmp = this->pop();
			this->set(index, tmp);
			//std::cout << this->to_string() <<", "<<this->counter <<", "<<tmp<<std::endl;
		}
		this->counter = length;
	}
};

template <typename T>
void sortCount(Array<T>* a)
{
	//std::cout << a->to_string() << std::endl;
	int mine = min(a);
	//std::cout << mine << std::endl;


	for (int i = 0; i < a->counter; i++)
		a->array[i] = a->array[i] - mine;

	//std::cout << a->to_string() << std::endl;

	int maxe = max(a);
	//std::cout << maxe << std::endl;

	int size = a->counter-1;
	T* tablicaelementow = new T[(maxe+2)];

	for (int i = 0; i < maxe+1; i++)
		++tablicaelementow[i]=0;

	for (int i = 0; i <= size; i++)
		++tablicaelementow[a->array[i]];

	for (int i = maxe; i >= 0; i--)
		for (int j = tablicaelementow[i];j>0;j--)
			a->array[size--] = i;

	for (int i = 0; i < a->counter; i++)
		a->array[i] = a->array[i] + mine;

	delete[] tablicaelementow;
}

template <typename T>
void sortBucket(Array<T>* a, const int n)
{
	using namespace std;
	T mine = min(a);
	T maxe = max(a);
	int ilosc = maxe - mine;

	Array<T>** buckets = new Array<T>*[(ilosc+1)];
	for (int i = 0; i < ilosc + 1; i++)
	{
		buckets[i] = new Array<T>;
	}

	for (int i = 0; i < a->counter; i++)
	{
		//cout << a->array[i] - mine << endl;
		buckets[a->array[i] - mine]->add_(a->array[i]);
	}

	for (int i = 0; i < ilosc+1; i++)
	{
		sortHeap(buckets[i]);
	}

	int id = 0;
	for (int i = 0; i < ilosc + 1; i++)
	{
		for (int j = 0; j < buckets[i]->counter; j++)
			a->array[id++] = buckets[i]->array[j];
	}

	for (int i = 0; i < ilosc + 1; i++)
	{
		delete buckets[i];
	}
	delete[] buckets;
}

template<typename T>
bool isSorted(Array<T>* a){

	for (int i = 0; i < a->counter-1; i++)
	{
		if (a->array[i] > a->array[i + 1])
			return false;
	}
	return true;
}

template<typename T>
T min(Array<T>* a)
{
	T min = a->array[0];

	for (int i = 0; i < a->counter; i++)
		if (min > a->array[i])
			min = a->array[i];
	return min;
}

template<typename T>
T max(Array<T>* a)
{
	T max = a->array[0];

	for (int i = 0; i < a->counter; i++)
		if (max < a->array[i])
			max = a->array[i];

	return max;
}

template <typename T>
void sortHeap(Array<T>* a)
{
	Heap<T>* heap = new Heap<T>(a);
	heap->sortHeap();
}

int porownaj_int(const void* a, const void* b) {  // funkcja porównująca
	int* arg1 = (int*)a;
	int* arg2 = (int*)b;
	if (*arg1 < *arg2) return -1;
	else if (*arg1 == *arg2) return 0;
	else return 1;
}

template<typename T>
void sortQuick(Array<T>*a)
{
	std::qsort(a->array, a->counter, sizeof(int), porownaj_int);
}

int main()
{
	//srand(time(NULL));
	srand(0);
	const int MAX_ORDER = 8;
	for (int o = 1; o < MAX_ORDER; o++)
	{
		std::cout << "Przebieg " << o << std::endl;
		Array<int>* tablica1 = new Array<int>;
		const int MAXIMUM = pow(10,5);
		const int n = pow(10, o);

		for (int i = 0; i < n; i++)
			tablica1->add_(((rand() << 15) + rand()) % MAXIMUM);

		Array<int>* tablica2 = new Array<int>(tablica1);
		Array<int>* tablica3 = new Array<int>(tablica1);
		Array<int>* tablica4 = new Array<int>(tablica1);

		//heap sort
		Heap<int>* kopiec = new Heap<int>(tablica1);

		clock_t t1 = clock();
		kopiec->sortHeap();
		clock_t t2 = clock();

		double time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
		std::cout << "Heap sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. "  << "Is sorted? " << isSorted(tablica1) << std::endl;
		//std::cout << tablica1->to_string() << std::endl;

		//count sort
		t1 = clock();
		sortCount(tablica2);
		t2 = clock();
		time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
		std::cout << "Count sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica2) << std::endl;
		//std::cout << tablica2->to_string() << std::endl;

		//bucket sort
		t1 = clock();
		sortBucket(tablica3, 1);
		t2 = clock();
		time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
		std::cout << "Bucket sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica3) << std::endl;
		//std::cout << tablica3->to_string() << std::endl;

		//quick sort
		t1 = clock();
		sortQuick(tablica4);
		t2 = clock();
		time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
		std::cout << "Quick sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica4) << std::endl << std::endl;
		//std::cout << tablica3->to_string() << std::endl;

		delete tablica1;
		delete tablica2;
		delete tablica3;
		delete tablica4;
	}

	return 0;
}

class Osoba
{
public:
	int losowepole1;
	int losowepole2;

	Osoba()
	{
		losowepole1 = rand();
		losowepole2 = rand();
	}

	void operator = (int z)
	{
		this->losowepole1 = z;
	}

	bool operator < (Osoba x)
	{
		if (this->losowepole1 < x.losowepole1)
		{
			return true;
		}
		return false;
	}

	bool operator > (Osoba x)
	{
		if (this->losowepole1 > x.losowepole1)
		{
			return true;
		}
		return false;
	}

	int operator - (Osoba x)
	{
		return (this->losowepole1 - x.losowepole1);
	}
};

//int main()//obiekty
//{
//	srand(time(NULL));
//	srand(0);
//	const int MAX_ORDER = 8;
//	for (int o = 1; o < MAX_ORDER; o++)
//	{
//		std::cout << "Przebieg " << o << std::endl;
//		Array<Osoba>* tablica1 = new Array<Osoba>;
//		const int MAXIMUM = pow(10,5);
//		const int n = pow(10, o);
//
//		for (int i = 0; i < n; i++)
//		{
//			Osoba os;
//			tablica1->add_(os);
//		}
//
//		Array<Osoba>* tablica2 = new Array<Osoba>(tablica1);
//
//
//		//heap sort
//		Heap<Osoba>* kopiec = new Heap<Osoba>(tablica1);
//
//		clock_t t1 = clock();
//		kopiec->sortHeap();
//		clock_t t2 = clock();
//
//		double time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
//		std::cout << "Heap sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. "  << "Is sorted? " << isSorted(tablica1) << std::endl;
//		//std::cout << tablica1->to_string() << std::endl;
//
//
//
//		//bucket sort
//		t1 = clock();
//		sortBucket(tablica2, 1);
//		t2 = clock();
//		time1 = (t2 - t1) / (double)CLOCKS_PER_SEC;
//		std::cout << "Bucket sort: " << "Czas ogolny: " << time1 * 1000 << " milisekund. " << "Czas na element: " << (time1 / n) * 1000000 << " mikrosekund. " << "Is sorted? " << isSorted(tablica2) << std::endl;
//		//std::cout << tablica3->to_string() << std::endl;
//
//		delete tablica1;
//		delete tablica2;
//	}
//
//	return 0;
//}