#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <string>
using namespace std;

class Node
{
private:
	int key;
	int balance;
	Node* left;
	Node* right;
	string sign;
	int height;

public:
	Node(const int key) : key(key), balance(0), height(0)
	{
		left = nullptr;
		right = nullptr;
		sign = to_string(key);
	}

	~Node()
	{
		if (left) delete left;
		if (right) delete right;
	}

	const int getKey() { return key; }
	Node* getLeft() { return left; }
	Node* getRight() { return this->right; }
	string getSign() { return this->sign; }
	int getBalance() { return balance; }
	int getHeight() { return height; }

	void setLeft(Node* node) {
		this->left = node;
	}

	void setRight(Node* node) {
		this->right = node;
	}

	void setBalance(int newBalance) {
		this->balance = newBalance;
	}

	void setHeight(int newHeight) {
		this->height = newHeight;
	}

};

class Tree
{
private:
	Node* root;

	int getHeight(Node* node) {
		int lsize = 0;
		int rsize = 0;

		if (node == nullptr) {
			return 0;
		}
		if (node->getLeft() != nullptr) {
			lsize = getHeight(node->getLeft()) + 1;
		}
		if (node->getRight() != nullptr) {
			rsize = getHeight(node->getRight()) + 1;
		}

		return (lsize >= rsize ? lsize : rsize);
	}

	bool isNodeLeaf(Node* node) {
		if (node->getLeft() == nullptr && node->getRight() == nullptr) return true;
		else return false;
	}

	bool isChildSmaller(Node* nodeChild, Node* nodeParent) {
		if (nodeChild->getKey() > nodeParent->getKey())
		{
			return false;
		}
		return true;
	}

	void balanceCalulate(Node* node = nullptr) {
		static int i = 0;
		if (node == nullptr) {
			balanceCalulate(this->root);
		}
		else {
			int leftHeight = 0;
			int rightHeight = 0;

			if (node->getLeft() != nullptr) {
				leftHeight = getHeight(node->getLeft()) + 1;
				balanceCalulate(node->getLeft());
			}

			if (node->getRight() != nullptr) {
				rightHeight = getHeight(node->getRight()) + 1;
				balanceCalulate(node->getRight());
			}

			int newBalance = rightHeight - leftHeight;
			if (newBalance < -1)
			{
				leftRotation(node->getLeft());
				rightRotation(node);
				balanceCalulate(node);
			}
			else if (newBalance > 1)
			{
				rightRotation(node->getRight());
				leftRotation(node);
				balanceCalulate(node);
			}
			else
			{
				node->setBalance(newBalance);
			}
		}
	}

	void leftRotation(Node* nodeToRotate) {
		Node* child = nodeToRotate->getRight();

		if (child != nullptr) {
			nodeToRotate->setRight(child->getLeft());
			child->setLeft(nodeToRotate);

			vector<Node*> nodeToRotateFamilly = searchNodeList(nodeToRotate->getKey());

			if (nodeToRotateFamilly.size() >= 2) {

				Node* nodeToRotateParent = nodeToRotateFamilly.at(nodeToRotateFamilly.size() - 2);
				if (isChildSmaller(nodeToRotate, nodeToRotateParent)) {
					nodeToRotateParent->setLeft(child);
				}

				else {
					nodeToRotateParent->setRight(child);
				}
			}

			if (nodeToRotate == root)
			{
				root = child;
			}
		}
	}
	void rightRotation(Node * nodeToRotate) {
		Node* child = nodeToRotate->getLeft();
		if (child != nullptr) {
			nodeToRotate->setLeft(child->getRight());
			child->setRight(nodeToRotate);

			vector<Node*> nodeToRotateFamilly = searchNodeList(nodeToRotate->getKey());
			if (nodeToRotateFamilly.size() >= 2)
			{
				Node* nodeToRotateParent = nodeToRotateFamilly.at(nodeToRotateFamilly.size() - 2);
				if (isChildSmaller(nodeToRotate, nodeToRotateParent))
				{
					nodeToRotateParent->setLeft(child);
				}
				else
				{
					nodeToRotateParent->setRight(child);
				}
			}

			if (nodeToRotate == root)
			{
				this->root = child;
			}
		}
	}

public:
	Tree(Node* root = 0)
	{
		this->root = root;
		srand(time(0));
	}

	~Tree()
	{
	}

	Node* getRoot() { return root; }

	void addNode(Node* node) {
		if (root == nullptr) {
			this->root = node;
		}
		else
		{
			addAsChild(node, root);
		}

		balanceCalulate();
	}

	void addAsChild(Node* nodeChild, Node* nodeParent) {
		bool stopCon = false;
		while (!stopCon) {
			if (nodeParent->getKey() == nodeChild->getKey()) {
				cout << "Wezel o takim kluczu już istnieje." << endl;
				stopCon = true;
			}
			else if (isChildSmaller(nodeChild, nodeParent))
			{
				if (nodeParent->getLeft() == nullptr) {
					nodeParent->setLeft(nodeChild);
					stopCon = true;
				}
				else nodeParent = nodeParent->getLeft();
			}
			else {
				if (nodeParent->getRight() == nullptr) {
					nodeParent->setRight(nodeChild);
					stopCon = true;
				}
				else nodeParent = nodeParent->getRight();

			}
		}
	}

	void putNode(Node* node) {
		addNode(node);
	}

	void putRandoms(int howMuch = 1000) {
		for (int i = 0; i < howMuch; i++)
		{
			const int key = (rand() % 20001) - 10000;
			Node* node = new Node(key);

			addNode(node);
		}
	}

	void delNode(const int key, Node* node = nullptr) {
		Node* nodeRoot = getRoot();
		vector<Node*> nodes = searchNodeList(key, nodeRoot);
		if (nodes.empty()) {
			cout << "Nie znaleziono wezla o kluczu: " << key << endl;
			return;
		}

		Node* nodeToDelete = nodes.back();
		Node* nodeToDelParent = nullptr;
		if (nodes.size() >= 2)
		{
			nodeToDelParent = nodes.at(nodes.size() - 2);
		}

		if (isNodeLeaf(nodeToDelete))
		{
			if (nodeToDelParent != nullptr)
			{
				//	Jeżeli ma rodzica sprawdzam czy jest po jego lewej czy prawej stronie
				//	i usuwam wskaźnik na usuwany element
				if (isChildSmaller(nodeRoot, nodeToDelParent))
				{
					nodeToDelParent->setLeft(nullptr);
				}
				else {
					nodeToDelParent->setRight(nullptr);
				}
			}
		}
		else
		{
			// Jest to węzeł poprzednik lub następnik
			Node* nodeToReplace = nullptr;
			vector<Node *> nodeToReplaceTrace;

			if (nodeToDelete->getLeft() != nullptr)
			{
				nodeToReplace = getMaxNode(nodeToDelete->getLeft());
				nodeToReplaceTrace = searchNodeList(nodeToReplace->getKey());

				Node* nodeToReplaceParent = nodeToReplaceTrace.at(nodeToReplaceTrace.size() - 2);
				if (nodeToReplaceParent != nodeToDelete)
				{
					nodeToReplaceParent->setRight(nodeToReplace->getLeft());
					nodeToReplace->setLeft(nodeToDelete->getLeft());
				}
				nodeToReplace->setRight(nodeToDelete->getRight());
			}
			else if (nodeToDelete->getRight() != nullptr)
			{
				nodeToReplace = getMinNode(nodeToDelete->getRight());
				nodeToReplaceTrace = searchNodeList(nodeToReplace->getKey());

				Node* nodeToReplaceParent = nodeToReplaceTrace.at(nodeToReplaceTrace.size() - 2);
				if (nodeToReplaceParent != nodeToDelete)
				{
					nodeToReplaceParent->setLeft(nodeToReplace->getRight());
					nodeToReplace->setRight(nodeToDelete->getRight());
				}
				nodeToReplace->setLeft(nodeToDelete->getLeft());
			}

			// Na koniec trzeba rodzicowi zmienić wskaźnik z usuniętego potomka na nowy
			if (nodeToDelParent != nullptr)
			{
				if (isChildSmaller(nodeToDelete, nodeToDelParent))
				{
					nodeToDelParent->setLeft(nodeToReplace);
				}
				else
				{
					nodeToDelParent->setRight(nodeToReplace);
				}
			}
			// Trzeba sprawdzić również czy nodeToDel to korzeń
			if (nodeToDelete == root)
			{
				this->root = nodeToReplace;
			}

		}

		// Na koniec usuwamy węzeł
		nodeToDelete->setLeft(0);
		nodeToDelete->setRight(0);
		delete nodeToDelete;

		// i liczymi współczynniki wyważenia
		balanceCalulate();
	}

	void showInOrder(Node* node = 0) {
		static int i = 0;
		if (node == NULL) {
			showInOrder(this->root);
		}
		else {
			if (node->getLeft() != nullptr)
			{
				showInOrder(node->getLeft());
			}

			cout << "Klucz: " << node->getKey() << "	Tablica: " << node->getSign()
				<< " Wsp. wywazenia: " << node->getBalance() << endl;

			if (node->getRight() != nullptr) {
				showInOrder(node->getRight());
			}
		}
	}
	void showPreOrder(Node * node = 0) {
		static int i = 0;
		if (node == NULL) {
			showPreOrder(this->root);
		}
		else {
			cout << "Klucz: " << node->getKey() << "	Tablica: " << node->getSign() << endl;

			if (node->getLeft() != nullptr)
			{
				showPreOrder(node->getLeft());
			}

			if (node->getRight() != nullptr) {
				showPreOrder(node->getRight());
			}
		}
	}

	Node* getMinNode(Node * node) {
		while (node->getLeft() != nullptr)
		{
			node = node->getLeft();
		}
		return node;
	}

	Node* getMaxNode(Node * node) {
		while (node->getRight() != nullptr)
		{
			node = node->getRight();
		}
		return node;
	}

	Node* searchNode(const int key, Node* node = nullptr) {
		if (node == NULL) {
			searchNode(key, this->root);
		}
		else {
			while (true) {
				if (node == nullptr) {
					cout << "Cannot find " << key << endl;
					break;
				}
				else if (node->getKey() == key) {
					break;
				}
				else if (node->getKey() > key) {
					node = node->getLeft();
				}
				else if (node->getKey() < key) {
					node = node->getRight();
				}
			}
			return node;
		}
	}

	vector<Node*> searchNodeList(const int key, Node* node = nullptr) {
		vector<Node*> nodes;
		if (this->root == nullptr)
		{
			cout << "Drzewo puste, nie ma nawet korzenia";
			return nodes;
		}

		if (node == nullptr) {
			nodes = searchNodeList(key, this->root);
		}
		else {
			while (true) {
				if (node == nullptr) {
					cout << "Cannot find " << key << endl;
					nodes.clear();
					break;
				}
				else if (node->getKey() == key) {
					nodes.push_back(node);
					break;
				}
				else if (node->getKey() > key) {
					nodes.push_back(node);
					node = node->getLeft();
				}
				else if (node->getKey() < key) {
					nodes.push_back(node);
					node = node->getRight();
				}
			}
		}
		return nodes;
	}
};

int main() {
	int X, k1, k2, k3, k4;

	fstream plik;
	plik.open("inlab04.txt");

	if (plik.good() == false) {
		cout << "Nie mozna otworzyc pliku!\n";
	}
	else
	{
		plik >> X;
		plik >> k1;
		plik >> k2;
		plik >> k3;
		plik >> k4;


		cout << X << " " << k1 << " " << k2 << " " << k3 << " " << k4 << endl;
	}


	plik.close();

	srand(time(NULL));

	clock_t begin, end;
	double time_spent;
	begin = clock();

	Tree avl;

	avl.delNode(k1);
	/*avl.addNode(k1);*/
	avl.putRandoms(X);
	avl.showInOrder(avl.getRoot());
	avl.showPreOrder(avl.getRoot());
	/*avl.addNode(k2);*/
	avl.showInOrder(avl.getRoot());
	/*avl.addNode(k3);
	avl.addNode(k4);*/
	avl.delNode(k1);
	avl.showPreOrder(avl.getRoot());
	avl.searchNode(k1);
	avl.showInOrder(avl.getRoot());
	avl.delNode(k3);
	avl.delNode(k4);

	end = clock();
	time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
	cout << endl << time_spent << endl;

	system("pause");
	return 0;
}