//ALGO2 IS1 221A LAB04
//Marcin Bogacz
//mbogacz06@wp.pl

#include "pch.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string.h>
#include <cstring>
using namespace std;

struct Wezel {
	char tab[10];
	int klucz;
	Wezel* mniejsze;
	Wezel* wieksze;
	Wezel() { wieksze = nullptr, mniejsze = nullptr; }
};

struct Drzewo {
	Wezel* root;
	Drzewo() { root = nullptr; }
	bool wstawianie(int);
	Wezel* szukanie(int);
	//Wezel* balance(int[], int, int);
	void rotate_right(Wezel*, Wezel*, Wezel*);
	void rotate_left(Wezel*, Wezel*, Wezel*);
	void make_backbone(Wezel*);
	void make_perfect_tree(int);
	void deleteTree(Wezel*);
	bool usuwanie(int);
	int preorder(Wezel*, int);
	int inorder(Wezel*, int);
	int postorder(Wezel*, int);

};

Wezel* Drzewo::szukanie(int klucz)
{
	Wezel* p = root;
	while (p)
	{
		if (klucz < p->klucz)
		{
			p = p->mniejsze;
		}
		else if (klucz > p->klucz)
		{
			p = p->wieksze;
		}
		else if (klucz == p->klucz)
		{
			return p;
		}
	}
	return nullptr;
}

bool Drzewo::wstawianie(int klucz)
{
	Wezel* previous = nullptr;
	Wezel* p = root;
	while (p != nullptr)
	{
		if (p->klucz == klucz)
		{
			return false;
		}
		previous = p;
		if (p->klucz < klucz)
		{
			p = p->wieksze;
		}
		else
		{
			p = p->mniejsze;
		}
	}
	Wezel* new_node = new Wezel;
	new_node->klucz = klucz;
	char tab[10];
	_itoa_s(klucz, tab, 10);
	for (int i = 0; i < 10; i++)
	{
		new_node->tab[i] = tab[i];
	}
	if (previous == nullptr)
	{
		root = new_node;
		return true;
	}
	if (previous->klucz < klucz)
	{
		previous->wieksze = new_node;
	}
	else
	{
		previous->mniejsze = new_node;
	}
	return true;
}

/*
Wezel* Drzewo:: balance(int data[],int first,int last)
{
	int middle = (first + last) / 2;
	if (first <= last)
	{
		Wezel* new_node = new Wezel;
		new_node->klucz = data[middle];
		char tab[10];
		_itoa_s(data[middle], tab, 10);
		for (int i = 0; i < 10; i++)
		{
			new_node->tab[i] = tab[i];
		}
		new_node->mniejsze = balance(data, first, middle - 1);
		new_node->wieksze = balance(data, middle + 1, last);

	}
	return(node);
}
*/

void Drzewo::rotate_right(Wezel* grandfather, Wezel* parent, Wezel* child)
{
	Wezel* tmp = new Wezel;
	if (grandfather != nullptr)
	{
		if (grandfather->wieksze == parent)
		{
			grandfather->wieksze = child;
		}
		else
		{
			grandfather->mniejsze = child;
		}
	}
	else
	{
		root = child;
	}
	tmp = child->wieksze;
	child->wieksze = parent;
	parent->mniejsze = tmp;
	return;
}

void Drzewo::rotate_left(Wezel* grandfather, Wezel* parent, Wezel* child)
{
	Wezel* tmp = new Wezel;
	if (grandfather != nullptr)
	{
		if (grandfather->mniejsze == parent)
		{
			grandfather->mniejsze = child;
		}
		else
		{
			grandfather->wieksze = child;
		}
	}
	else
	{
		root = child;
	}
	tmp = child->mniejsze;
	child->mniejsze = parent;
	parent->wieksze = tmp;
	return;
}

void Drzewo::make_backbone(Wezel* root)
{
	Wezel* grandfather = nullptr;
	Wezel* tmp = root;
	while (tmp != nullptr)
	{
		if (tmp->mniejsze != nullptr)
		{
			Wezel* tmp2 = tmp->mniejsze;
			rotate_right(grandfather, tmp, tmp->mniejsze);
			tmp = tmp2;
		}
		else
		{
			grandfather = tmp;
			tmp = tmp->wieksze;
		}
	}
}

void Drzewo::make_perfect_tree(int N)
{
	Wezel* grandfather = nullptr;
	Wezel* tmp = root;
	int m = 1;
	while (m < N)
	{
		m = 2 * m + 1;
	}
	m = m / 2;
	for (int i = 0; i < (N - m); i++)
	{
		Wezel* tmp2 = tmp->wieksze;
		if (tmp2 != nullptr)
		{
			rotate_left(grandfather, tmp, tmp->wieksze);
			grandfather = tmp2;
			tmp = tmp2->wieksze;
		}
	}
	while (m > 1)
	{
		m = m / 2;
		grandfather = nullptr;
		tmp = root;
		for (int i = 0; i < m; i++)
		{
			Wezel* tmp2 = tmp->wieksze;
			rotate_left(grandfather, tmp, tmp->wieksze);
			grandfather = tmp2;
			tmp = tmp2->wieksze;
		}
	}
}

void Drzewo::deleteTree(Wezel* node)
{
	if (node == nullptr)
	{
		return;
	}
	deleteTree(node->mniejsze);
	deleteTree(node->wieksze);
	free(node);
}

bool Drzewo::usuwanie(int klucz)
{
	Wezel* previous = root;
	Wezel* p = root;
	while (p != nullptr)
	{
		if (p->klucz == klucz)
		{
			if (p->mniejsze == nullptr && p->wieksze == nullptr)
			{
				if (p->klucz > previous->klucz)
				{
					previous->wieksze = nullptr;
				}
				else
				{
					previous->mniejsze = nullptr;
				}
				delete p;
				return true;
			}
			else if (p->mniejsze == nullptr || p->wieksze == nullptr)
			{
				if (p->klucz < previous->klucz)
				{
					if (p->mniejsze == nullptr)
					{
						previous->mniejsze = p->wieksze;
						delete p;
						return true;
					}
					if (p->wieksze == nullptr)
					{
						previous->mniejsze = p->mniejsze;
					}
				}
				else if (p->klucz < previous->klucz)
				{
					if (p->mniejsze == nullptr)
					{
						previous->mniejsze = p->wieksze;
						delete p;
						return true;
					}
					if (p->wieksze == nullptr)
					{
						previous->mniejsze = p->mniejsze;
					}
				}
			}
			else
			{
				Wezel* minimum = p->wieksze;
				Wezel* minimumP = p;
				while (minimum->mniejsze != nullptr)
				{
					minimumP = minimum;
					minimum = minimum->mniejsze;
				}
				p->klucz = minimum->klucz;
				for (auto i = 0; i < 10; i++)
				{
					p->tab[i] = minimum->tab[i];
				}
				if (minimum == p->wieksze)
				{
					p->wieksze = minimum->wieksze;
					delete minimum;
					return true;
				}
				else if (minimum->wieksze != nullptr)
				{
					minimumP->mniejsze = minimum->wieksze;
					delete minimum;
					return true;
				}
			}
		}
		previous = p;
		if (p->klucz < klucz)
		{
			p = p->wieksze;
		}
		else
		{
			p = p->mniejsze;
		}
	}
	return false;
}

int Drzewo::preorder(Wezel* p, int licznik = 0)
{
	if (p) {
		std::cout << p->klucz << " ";
		preorder(p->mniejsze);
		preorder(p->wieksze);
	}
	return 0;
}

int Drzewo::inorder(Wezel* p, int licznik = 0)
{
	if (p) {
		preorder(p->mniejsze);
		std::cout << p->klucz << " ";
		preorder(p->wieksze);
	}
	return 0;
}

int Drzewo::postorder(Wezel* p, int licznik = 0)
{
	if (p) {
		preorder(p->mniejsze);
		preorder(p->wieksze);
		std::cout << p->klucz << " ";
	}
	return 0;
}

int losKlucz()
{
	int klucz;
	klucz = (rand() % 20001) - 10000;
	return klucz;
}


int main()
{
	//czas-start--------------------------
	srand(time(NULL));
	clock_t begin, end;
	double time_spent;
	begin = clock();
	//wczytwyanie-z-pliku------------------
	int iloscElementow2, iloscElementow1;
	ifstream dane("inlab05.txt");
	dane >> iloscElementow1;
	dane >> iloscElementow2;
	cout << "ilosc Elementow 1= " << iloscElementow1 << endl;
	cout << "ilosc Elementow 2= " << iloscElementow2 << endl;

	cout << endl;
	//--tworzenie--drzewa------------------
	Drzewo drzewo;

	for (int i = 0; i < iloscElementow1; i++)
	{
		int klucz;
		klucz = losKlucz();
		drzewo.wstawianie(klucz);
	}
	drzewo.make_perfect_tree(iloscElementow1);
	drzewo.deleteTree(drzewo.root);


	//czas-stop----------------------------
	end = clock();
	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
	cout << "Czas wykonania: " << time_spent << endl;
	system("PAUSE");
}