#include "pch.h"
#include <iostream>
#include <random>
#include <string>
#include <functional>
using namespace std;

enum Color { Black, Red };
/*struct Data
{
public:
	int number;
	char key;
public:
	Data() {};
	Data(int n, char k)
	{
		this->number = n;
		this->key = k;
	}
};*/
template<typename T>
class RBTree;

template <typename T>
class Node
{
	friend class RBTree<T>;
	T data;
	Color color;
	Node* parent;
	Node* leftChild;
	Node* rightChild;
public:
	Node()
	{
		this->parent = nullptr;
		this->leftChild = nullptr;
		this->rightChild = nullptr;
		//color = Red;
	}
	void gibColor(Node<T>*x)
	{
		if (x->color == Black)
			cout << "czarny";
		else
			cout << "czerowny";
	}
};

template <typename T>
class RBTree
{
	Node<T>* root;
	int size;
public:
	RBTree()
	{
		root = nullptr;
		size = 1;
	}

	void leftRotate(Node<T>*child, Node<T>*parent)
	{
		child = parent->rightChild;
		parent->rightChild = child->leftChild;
		if (child->leftChild != nullptr)
		{
			child->leftChild->parent = parent;
		}

		child->parent = parent->parent;
		if (parent->parent == nullptr)
		{
			root = child;
		}
		else if (parent == parent->parent->leftChild)
		{
			parent->parent->leftChild = child;
		}
		else {
			parent->parent->rightChild = child;
		}

		child->leftChild = parent;
		parent->parent = child;
	}
	void rightRotate(Node<T>*child, Node<T>*parent)
	{
		child = parent->leftChild;
		parent->leftChild = child->rightChild;
		if (child->rightChild != nullptr)
		{
			child->rightChild->parent = parent;
		}
		child->parent = parent->parent;
		if (parent->parent == nullptr)
		{
			root = child;
		}
		else if (parent == parent->parent->rightChild)
		{
			parent->parent->rightChild = child;
		}
		else
		{
			parent->parent->leftChild = child;
		}

		child->rightChild = parent;
		parent->parent = child;
	}
	void fixViolation(Node<T>*n)
	{
		Node<T>*grandparent;
		Node<T>*parent;
		Node<T>*uncle;
		parent = n->parent;
		while (parent != nullptr&& parent->color == Red)
		{
			grandparent = n->parent->parent;
			if (grandparent->leftChild == parent)
			{
				uncle = grandparent->rightChild;
				if (uncle != nullptr&&uncle->color == Red)
				{
					parent->color = Black;
					uncle->color = Black;
					grandparent->color = Red;
					n = grandparent;
					parent = n->parent;
				}
				else
				{
					if (parent->rightChild == n)
					{
						n = parent;
						leftRotate(n->parent, n);
					}

					parent->color = Black;
					grandparent->color = Red;
					rightRotate(parent, grandparent);
				}
			}
			else
			{
				uncle = grandparent->leftChild;
				if (uncle != nullptr&&uncle->color == Red)
				{
					uncle->color = Black;
					parent->color = Black;
					grandparent->color = Red;
					n = grandparent;
					parent = n->parent;
				}
				else
				{
					if (parent->leftChild == n)
					{
						n = parent;
						rightRotate(n->parent, n);
					}

					parent->color = Black;
					grandparent->color = Red;
					leftRotate(parent, grandparent);
				}
			}
			//root->color = Black;
		}
		root->color = Black;
	}
	/*void InsertFixUp(Node<T>* node)
	{
		Node<T>*parent;
		parent = node->parent;
		while (node !=root  && parent->color == Red)
		{
			Node<T>*gparent = parent->parent;
			if (gparent->leftChild == parent)
			{
				Node<T>*uncle = gparent->rightChild;
				if (uncle != nullptr && uncle->color == Red)
				{
					parent->color = Black;
					uncle->color = Black;
					gparent->color = Red;
					node = gparent;
					parent = node->parent;
				}
				else
				{
					if (parent->rightChild == node)
					{
						leftRotate(root, parent);

					}
					rightRotate(root, gparent);
					gparent->color = Red;
					parent->color = Black;
					break;
				}
			}
			else
			{
				Node<T>*uncle = gparent->leftChild;
				if (uncle != nullptr && uncle->color == Red)
				{
					gparent->color = Red;
					parent->color = Black;
					uncle->color = Black;

					node = gparent;
					parent = node->parent;
				}
				else
				{
					if (parent->leftChild == node)
					{
						rightRotate(root, parent);

					}
					leftRotate(root, gparent);
					parent->color = Black;
					gparent->color = Red;
					break;
				}
			}
		}
		root->color = Black;
	}*/
	/*void fixViolation(Node<T> *t)
	{
		Node<T> *u=new Node<T>();
		Node<T> *g = new Node<T>();
		if (root == t)
		{
			t->color = Black;
			return;
		}
		while (t->parent != nullptr && t->parent->color == Red)
		{
			Node<T> *g = t->parent->parent;
			if (g->leftChild == t->parent)
			{
				if (g->rightChild != nullptr)
				{
					u = g->rightChild;
					if (u->color == Red)
					{
						t->parent->color = Black;
						u->color = Black;
						g->color = Red;
						t = g;
						t->parent = t->parent;
					}
				}
				else
				{
					if (t->parent->rightChild == t)
					{
						t = t->parent;
						leftRotate(t,t->parent->parent);
					}
					t->parent->color = Black;
					g->color = Red;
					rightRotate(t->parent,g);
				}
			}
			else
			{
				if (g->leftChild != nullptr)
				{
					u = g->leftChild;
					if (u->color == Red)
					{
						t->parent->color = Black;
						u->color = Black;
						g->color = Red;
						t = g;
						t->parent = t->parent;
					}
				}
				else
				{
					if (t->parent->leftChild == t)
					{
						t = t->parent;
						rightRotate(t,t->parent->parent);
					}
					t->parent->color = Black;
					g->color = Red;
					leftRotate(t->parent,g);
				}
			}
			root->color = Black;
		}
	}*/

	void addElement(T el)
	{
		Node<T>*n = new Node<T>();
		n->data = el;
		n->leftChild = nullptr;
		n->rightChild = nullptr;
		n->color = Red;
		Node<T>*temp = this->root;
		Node<T>*y = nullptr;
		if (root == nullptr)
		{
			n->color = Black;
			root = n;
		}
		else
		{
			while (temp != nullptr)
			{
				y = temp;
				if (temp->data < n->data)
				{
					temp = temp->rightChild;
				}
				else
				{
					temp = temp->leftChild;
				}
			}
			n->parent = y;
			if (y->data == n->data)
			{
				cout << "Duplikaty won!" << endl;
				return;
			}
			if (y->data < n->data)
			{
				y->rightChild = n;
				size = size + 1;
			}
			else
			{
				y->leftChild = n;
				size = size + 1;
			}
			//InsertFixUp(n);
			fixViolation(n);
		}

	}
	void print(Node<T>*x)
	{

		//cout << "size: " << size << endl;
		if (x == nullptr)
		{
			return;
		}
		if (x->parent == nullptr)
		{
			cout << "(" << x->data << ")";
			cout << "[" << "kolor:";
			x->gibColor(x);
			cout << ", rodzic: NULL," << " l.dziecko: ";
			if (x->leftChild == nullptr)
			{
				cout << "NIL";
			}
			else
				cout << x->leftChild->data;
			cout << ", p. dziecko: ";
			if (x->rightChild == nullptr)
			{
				cout << "NIL";
			}
			else
				cout << x->rightChild->data;
			cout << "]";
			cout << "-korzen " << endl;
			//rodzic, l.dziecko, p.dziecko

		}
		else if (x->parent->leftChild == x)
		{
			//int c = x->gibColor(x);
			cout << "(" << x->data << ")";
			cout << "[" << "kolor:";
			x->gibColor(x);
			cout << ", rodzic: " << x->parent->data << ", l.dziecko: ";
			if (x->leftChild == nullptr)
			{
				cout << "NIL";
			}
			else
				cout << x->leftChild->data;
			cout << ", p. dziecko: ";
			if (x->rightChild == nullptr)
			{
				cout << "NIL" << "]" << endl;
			}
			else
				cout << x->rightChild->data << "]" << endl;
		}
		else
		{
			cout << "(" << x->data << ")";
			cout << "[" << "kolor:";
			x->gibColor(x);
			cout << ", rodzic: " << x->parent->data << ", l.dziecko: ";
			if (x->leftChild == nullptr)
			{
				cout << "NIL";
			}
			else
				cout << x->leftChild->data;
			cout << ", p. dziecko: ";
			if (x->rightChild == nullptr)
			{
				cout << "NIL" << "]" << endl;;
			}
			else
				cout << x->rightChild->data << "]" << endl;
		}
		print(x->leftChild);
		print(x->rightChild);

	}
	void printTree()
	{

		if (root == nullptr)
		{
			cout << "Puste drzewo!" << endl;

		}
		else
			print(root);
	}
	//wyszukiwanie elementu
	//przejście preorder
	//przejście inorder
	//czyszczenie drzewa
	//wyznaczenie wysokości
	//rotacje jako funkcje naprawcze dodawania
};
int randomInt()
{
	uniform_int_distribution<int> rozklad{ 0, 11000000 };
	default_random_engine generator{ 11 };
	function<int()> los{ bind(rozklad, generator) };
	int l = los();
	return l;
}

int main()
{
	RBTree<int>* d1 = new RBTree<int>();
	//d1->initialize(3);
	d1->addElement(35);
	d1->addElement(67);
	d1->addElement(69);
	d1->addElement(15);
	d1->addElement(30);
	d1->addElement(300);
	d1->addElement(123);
	/*d1->addElement(5);
	d1->addElement(10);
	d1->addElement(1);
	d1->addElement(8);
	d1->addElement(6);
	d1->addElement(7);
	d1->addElement(9);*/
	d1->printTree();

}