#include <iostream>
#include <time.h>
#include <exception>
#include <random>
enum class kolor
{
	czarny, czerwony
};
template  <typename T>
struct wezel {
	T dane;
	wezel<T>* wskaznikNaRodzica = nullptr;
	wezel<T>* wskaznikNaPrawegoPotomka = nullptr;
	wezel<T>* wskaznikNaLewegoPotomka = nullptr;
	unsigned int indeks = 0;

	kolor color = kolor::czerwony;
};
template< typename T>
struct drzewo {
	wezel<T>* korzen = nullptr;
	int rozmiar = 0;
	void dodajNowyWezel(T datas) {
		wezel<T>* dziecko = new wezel<T>;
		if (rozmiar == 0) {
			dziecko->wskaznikNaRodzica = nullptr;
			dziecko->wskaznikNaPrawegoPotomka = nullptr;
			dziecko->wskaznikNaLewegoPotomka = nullptr;
			dziecko->indeks = 0;
			korzen = dziecko;
			korzen->color = kolor::czarny;
		}
		else {
			wezel<T>* tymczasowy;
			tymczasowy = korzen;
			while (tymczasowy != nullptr) {
				if (tymczasowy->wskaznikNaPrawegoPotomka == nullptr) {
					if (tymczasowy->dane <= datas) {
						tymczasowy->wskaznikNaPrawegoPotomka = dziecko;
						dziecko->wskaznikNaRodzica = tymczasowy;
						tymczasowy = dziecko;
						break;
					}
					tymczasowy = tymczasowy->wskaznikNaPrawegoPotomka;
				}
				else {
					if (tymczasowy->wskaznikNaLewegoPotomka == nullptr) {
						tymczasowy->wskaznikNaLewegoPotomka = dziecko;
						dziecko->wskaznikNaRodzica = tymczasowy;
						tymczasowy = dziecko;
						break;
					}
					tymczasowy = tymczasowy->wskaznikNaLewegoPotomka;
				}

			}
			tymczasowy = dziecko;
			sprawdzKolory(tymczasowy);
		}

		dziecko->indeks = rozmiar;
		dziecko->dane = datas;
		rozmiar++;

	}
	void sprawdzKolory(wezel<T>* ostatni) {
		wezel<T>* chwilowy = ostatni;
		if (chwilowy == korzen) {
			chwilowy->color = kolor::czarny;
			return;
		}
		while (chwilowy->wskaznikNaRodzica != nullptr && chwilowy->wskaznikNaRodzica->color != kolor::czarny) {
			if (chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka == chwilowy->wskaznikNaRodzica) {
				if (chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka != nullptr && chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka->color == kolor::czerwony) {

					chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka->color = kolor::czarny;
					chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
					chwilowy->wskaznikNaRodzica->color = kolor::czarny;
					chwilowy = chwilowy->wskaznikNaRodzica->wskaznikNaRodzica;

				}
				else {
					if (chwilowy->wskaznikNaRodzica->wskaznikNaPrawegoPotomka == chwilowy) {
						chwilowy = chwilowy->wskaznikNaRodzica;
						RotacjaLewa(chwilowy, chwilowy->wskaznikNaPrawegoPotomka);
					}
					chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
					chwilowy->wskaznikNaRodzica->color = kolor::czarny;
					RotacjaPrawa(chwilowy->wskaznikNaRodzica->wskaznikNaRodzica, chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka);
				}
			}
			else {
				if (chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka != nullptr && chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka->color != kolor::czarny) {
					chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaLewegoPotomka->color = kolor::czarny;
					chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
					chwilowy->wskaznikNaRodzica->color = kolor::czarny;
					chwilowy = chwilowy->wskaznikNaRodzica->wskaznikNaRodzica;
				}
				else {
					if (chwilowy->wskaznikNaRodzica->wskaznikNaLewegoPotomka == chwilowy) {
						chwilowy = chwilowy->wskaznikNaRodzica;
						RotacjaPrawa(chwilowy, chwilowy->wskaznikNaLewegoPotomka);
					}
					chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->color = kolor::czerwony;
					chwilowy->wskaznikNaRodzica->color = kolor::czarny;
					RotacjaLewa(chwilowy->wskaznikNaRodzica->wskaznikNaRodzica, chwilowy->wskaznikNaRodzica->wskaznikNaRodzica->wskaznikNaPrawegoPotomka);
				}
			}
			korzen->color = kolor::czarny;
		}
	}
	void RotacjaPrawa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
		//Rodzicem elementu naRodzica staje się element naDziecko,
		naRodzica->wskaznikNaRodzica = naDziecko;

		//lewy syn elementu naDziecko staje się prawym synem elementu naRodzica.
		naRodzica->wskaznikNaPrawegoPotomka = naDziecko->wskaznikNaLewegoPotomka;

		//lewym dzieckiem elementu naDziecko staje się element naRodzica.
		naDziecko->wskaznikNaLewegoPotomka = naRodzica;
	}
	void RotacjaLewa(wezel<T>* naRodzica, wezel<T>* naDziecko) {
		naRodzica->wskaznikNaRodzica = naDziecko;
		naRodzica->wskaznikNaLewegoPotomka = naDziecko->wskaznikNaPrawegoPotomka;
		naDziecko->wskaznikNaPrawegoPotomka = naRodzica;
	}
	wezel<T>* znajdzDane(T datas) {
		wezel<T>* cos = korzen;
		while (cos) {
			if (cos->dane == datas) {
				return cos;
			}
			if (datas > cos->dane) {
				cos = cos->wskaznikNaPrawegoPotomka;
			}
			else {
				cos = cos->wskaznikNaLewegoPotomka;
			}
			return nullptr;
		}
	}
	void wyczyscDrzewo() {
		wezel<T>* kasownik = korzen;
		wyczyscDrzewoRek(kasownik);
	}
	void wyczyscDrzewoRek(wezel<T>* kasownik) {
		if (kasownik == nullptr) {
			return;
		}
		else {
			wyczyscDrzewoRek(kasownik->wskaznikNaLewegoPotomka);
			wyczyscDrzewoRek(kasownik->wskaznikNaPrawegoPotomka);
			delete kasownik;
		}
	}
	void wysokosc() {
		int wysokosc = wysokoscRek(korzen);
		std::cout << "wysokosc drzewa: " << wysokosc << std::endl;
	}
	int wysokoscRek(wezel<T> * cos) {
		int prawa;
		int lewa;
		// sprawdzamy prawa odnoge
		if (cos->wskaznikNaPrawegoPotomka != nullptr) {
			prawa = wysokoscRek(cos->wskaznikNaPrawegoPotomka);
		}
		else {
			prawa = 0;
		}
		//sprawdzamy lewa odnoge
		if (cos->wskaznikNaLewegoPotomka != nullptr) {
			lewa = wysokoscRek(cos->wskaznikNaLewegoPotomka);
		}
		else {
			lewa = 0;
		}
		//zwracamy wieksza
		if (lewa < prawa) {
			return prawa;
		}
		else
		{
			return lewa;
		}
	}
	//przechodzenie przez wezły
	void InOrder(wezel<T>* drzewo) {
		InOrder(drzewo->wskaznikNaLewegoPotomka);
		std::cout << drzewo->dane << ' ';
		InOrder(drzewo->wskaznikNaPrawegoPotomka);
	}
	//PreOrder służy do kopiowania drzewa
	void PreOrder(wezel<T>* drzewo) {
		std::cout << drzewo->dane << ' ';
		PreOrder(drzewo->wskaznikNaLewegoPotomka);
		PreOrder(drzewo->wskaznikNaPrawegoPotomka);
	}
	void wyswietlDrzewo() {
		wyswietlRek(korzen);
	}
	void wyswietlRek(wezel<T>* korzen) {
		if (korzen != nullptr) {
			std::cout << " dane " << korzen->dane << " indeks " << korzen->indeks;
		}
		if (korzen->color == kolor::czerwony)
		{
			std::cout << " czerwony ";
		}
		else {
			std::cout << " czarny ";
		}
		if (korzen->wskaznikNaLewegoPotomka == nullptr) {
			std::cout << " LP: brak ";
		}
		if (korzen->wskaznikNaLewegoPotomka != nullptr) {
			std::cout << " LP: " << korzen->wskaznikNaLewegoPotomka->indeks;
		}
		if (korzen->wskaznikNaPrawegoPotomka == nullptr) {
			std::cout << " PP: brak " << std::endl;
		}
		if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
			std::cout << " PP: " << korzen->wskaznikNaPrawegoPotomka->indeks << std::endl;
		}
		if (korzen->wskaznikNaLewegoPotomka != nullptr) {
			wyswietlRek(korzen->wskaznikNaLewegoPotomka);
		}
		if (korzen->wskaznikNaPrawegoPotomka != nullptr) {
			wyswietlRek(korzen->wskaznikNaPrawegoPotomka);
		}

	}
};
int main() {
	std::random_device rd;
	std::mt19937 gen(rd());
	std::uniform_int_distribution<> losowa(1, 10000);
	drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
	CzerwonoCzarne->dodajNowyWezel(1);
	CzerwonoCzarne->dodajNowyWezel(2);
	CzerwonoCzarne->dodajNowyWezel(3);
	CzerwonoCzarne->dodajNowyWezel(4);
	CzerwonoCzarne->dodajNowyWezel(5);
	CzerwonoCzarne->dodajNowyWezel(6);
	CzerwonoCzarne->dodajNowyWezel(8);
	CzerwonoCzarne->dodajNowyWezel(7);
	CzerwonoCzarne->dodajNowyWezel(9);
	CzerwonoCzarne->dodajNowyWezel(10);
	//const int MAX_ORDER = 7; // maksymalny rzad wielkosci dodawanych danych
	//drzewo <int>* CzerwonoCzarne = new drzewo <int>(); // stworzenie drzewa
	//for (int o = 1; o <= MAX_ORDER; o++)
	//{
	//	const int n = pow(10, o); // rozmiar danych
	//	// dodawanie do drzewa
	//	clock_t t1 = clock();
	//	for (int i = 0; i < n; i++)
	//	{
	//		int liczba = losowa(gen);
	//		CzerwonoCzarne->dodajNowyWezel(liczba);
	//	}
	//	clock_t t2 = clock();
	//	double time = (t2 - t1) / (double)CLOCKS_PER_SEC;
	//	std::cout << "Czas dodawania " << n << " elemenow: " << time << std::endl;
	CzerwonoCzarne->wyswietlDrzewo();
	CzerwonoCzarne->wysokosc();

	delete CzerwonoCzarne;
}