//ALGO2 N1 20B LAB04
//Maciej Baraniecki
//bm35988@zut.edu.pl


#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>
#include <stdio.h>

using namespace std;

struct BSTNode
{
	int klucz;
	struct BSTNode *left, *right;
	char tab[10];

};

/*BSTNode* newNode(int klucz)
{
        BSTNode* temp = new BSTNode;
        temp->klucz = klucz;
        temp->left=temp->right = NULL;
        return temp;
}*/


bool dodaj(BSTNode* root, int klucz)
{
        BSTNode* p = root;
        BSTNode* prev=nullptr;

        while(p!=nullptr)
        {
                prev=p;
                if(p->klucz<klucz)
                {
                        p=p->right;
                }
                else
                {
                        p=p->left;
                }

        }

        if(root->klucz==0)
        {
                //root=new BSTNode;
                root->klucz=klucz;
                root->left=nullptr;
                root->right=nullptr;
                cout<<"Dodano korzen"<<endl;
                return true;
        }
        else if(prev->klucz<klucz)
        {
                prev->right=new BSTNode;
                (prev->right)->klucz=klucz;
                (prev->right)->left=nullptr;
                (prev->right)->right=nullptr;
                cout<<"Dodano wezel prawy"<<endl;
                return true;
        }
        else if(prev->klucz>klucz)
        {
                prev->left=new BSTNode;
                (prev->left)->klucz=klucz;
                (prev->left)->left=nullptr;
                (prev->left)->right=nullptr;
                cout<<"Dodano wezel lewy"<<endl;
                return true;
        }
        else
        {
                return false;
        }


};

void wstawianie(BSTNode* root, int X)
{
        int klucz;
	for (int i = 0; i < X; i++)
	{
	        do
	        {
		        klucz = (rand() % 20000) - 1000;
	        }while(dodaj(root,klucz)!=true);
	}
}

BSTNode* search(BSTNode* root, int klucz)
{
	BSTNode* p = root;
	if(!p)
	{
	        cout<<"Drzewo puste!"<<endl;
	        return nullptr;
	}
	while((p==nullptr)&(klucz==p->klucz))
	{
	        if(p->klucz<klucz)
	        {
	                cout<<"NIE"<<endl;
	                p=p->right;
	        }
	        else
	        {
	                cout<<"TAK"<<endl;
	                p=p->left;
	        }
	}
	cout<<"ZNaleziono"<<endl;
	return(p);

}

BSTNode* minValueNode(BSTNode* node)
{
    BSTNode* current = node;

    /* loop down to find the leftmost leaf */
    while (current->left != nullptr)
        current = current->left;

    return current;
}


BSTNode* usun(BSTNode* root, int klucz)
{
        if(root == NULL)
        {
                return root;
        }

        if(klucz < root->klucz)
        {
                root->left = usun(root->left,klucz);
        }
        else if(klucz > root->klucz)
        {
                root->right = usun(root->right, klucz);
        }
        else
        {
                if(root->left == NULL)
                {
                        BSTNode* temp = root->right;
                        delete(root);
                        return temp;
                }
                else if(root->right == NULL)
                {
                        BSTNode* temp = root->left;
                        delete(root);
                        return temp;
                }

                BSTNode* temp=minValueNode(root->right);

                root->klucz = temp->klucz;

                root->right = usun(root->right, temp->klucz);

        }
        return root;



}

BSTNode* usuwaj(BSTNode* root){ //pierwszy argument to head
	if (root->left)
		usuwaj(root->left);
	if (root->right)
		usuwaj(root->right);
	delete(root);
	if (root)
		root = NULL;


	return NULL;
}




void preorder(BSTNode* root)
{
	int liczba = 0;
	{
		if (root == NULL)
			return;
		cout << "PREORDER--------------------------   ";
		cout << root->klucz << " "<<endl;
		liczba++;

		preorder(root->left);
		preorder(root->right);
	}

}


void inorder(BSTNode * root)
{
	if (root)
	{
			inorder(root->left);
			cout << "INORDER------------------------   ";
			cout << root->klucz << endl;  // tutaj przetwarzamy bieżący węzeł
			inorder(root->right);
	}
}


void postorder(BSTNode* root)
{
	if (root == NULL)
		return;
	postorder(root->left);
	postorder(root->right);
	cout << root->klucz << " ";
}


BSTNode* rotate_right(BSTNode* root, BSTNode* grandfather, BSTNode* parent, BSTNode* child)
{
	BSTNode* tmp;
	if (grandfather){
		if (grandfather->right == parent){
			grandfather->right = child;
		}
		else{
			grandfather->left = child;
		}
	}
	else
		root = child;

	if (parent->left == child){
		tmp = child->right;
		child->right = parent;
		parent->left = tmp;
	}
	else{
		tmp = child->right;
		child->left = parent;
		parent->right = tmp;
	}

	return root;


}

BSTNode* rotate_left(BSTNode* root, BSTNode* grandfather, BSTNode* parent, BSTNode* child)
{
        BSTNode* tmp;
	if (grandfather){
		if (grandfather->right == parent){
			grandfather->right = child;
		}
		else{
			grandfather->left = child;
		}
	}
	else
		root = child;

	if (parent->right == child){
		tmp = child->left;
		child->left = parent;
		parent->right = tmp;
	}
	else{
		tmp = child->left;
		child->right = parent;
		parent->left = tmp;
	}

	return root;
}

BSTNode* make_backbone(BSTNode* root)
{
        BSTNode* grandfather=NULL;
        BSTNode* tmp=root;
        while(tmp!=NULL)
        {
                if((tmp->left)!=NULL)
                {
                        BSTNode* tmp2 = tmp->left;
                        root=rotate_right(root,grandfather,tmp,tmp->left);
                        tmp=tmp2;
                }
                else
                {
                        grandfather=tmp;
                        tmp=tmp->right;
                }
        }
        return root;
}

BSTNode* make_perfect_tree(BSTNode* root,int N)
{
        BSTNode* grandfather=NULL;
        BSTNode* tmp=root;
        BSTNode* tmp2;
        int m=1;
        while(m<=N)
        {
                m=2*m+1;
        }
        m=m/2;
        for(int i=0;i<(N-m);i++)
        {
                tmp2=tmp->right;
                if(tmp2!=NULL)
                {
                        root=rotate_left(root, grandfather,tmp,tmp->right);
                        grandfather=tmp2;
                        tmp=tmp2->right;
                }
        }
        while(m>1)
        {
                m=m/2;
                grandfather=NULL;
                tmp=root;
                for(int j=0;j<m;j++)
                {
                        tmp2=tmp->right;
                        root=rotate_left(root, grandfather,tmp,tmp->right);
                        grandfather=tmp2;
                        tmp=tmp2->right;
                }
        }
        return root;
}

int maxDepth(BSTNode* root)
{
    if (root == NULL)
        return 0;
    else
    {
        int lDepth = maxDepth(root->left);
        int rDepth = maxDepth(root->right);
        if (lDepth > rDepth)
            return(lDepth + 1);
        else return(rDepth + 1);
    }
}


int main()
{
	int k1, k2, k3, k4;
	int X;
/*#pragma warning(disable : 4996)
	FILE* fp = fopen("inlab03.txt", "r");
	if (fp == NULL)
		return -1;
	fscanf(fp, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);  // wczytanie pliku
	fclose(fp);*/

	k1=45;
	k2=245;
	k3=1;
	k4=4;
	X=400;
	int N;


//czas start

	clock_t begin, end;
	double time_spent;
	srand((unsigned int)time(NULL));
	begin = clock();
	BSTNode* root=new BSTNode;

	/*dodaj(root,15);
        dodaj(root,10);
        dodaj(root,25);
        dodaj(root,5);
        dodaj(root,13);
        dodaj(root,20);
        dodaj(root,33);
        dodaj(root,22);
        dodaj(root,24);
        inorder(root);

        usun(root,33);
        //cout << "root:" << root << "  " << root->klucz<<endl;
        inorder(root);

        int wysokosc=maxDepth(root);
        cout<<"Wysokosc drzewa:"<<wysokosc<<endl;*/



	//inicjacja pustego drzewa
        //BSTNode* root=new BSTNode;// = new BSTNode;
        //root->right=nullptr;
        //root->left=nullptr;
        //root=dodaj(root,((rand() % 20000) - 1000));

	//usuń element o wartości klucza k1;
	cout << "Usuwanie elementu o wartosci klucza k1..." << endl;
	usun(root, k1);
	//wstaw element o wartości klucza k1;
	cout << "Dodawanie elementu o wartosci klucza k1..." << endl;

	dodaj(root, k1);
	//cout << root << endl;
	//wstaw X elementów do drzewa;
	cout << "Wstawianie X elementow do drzewa..." << endl;
	wstawianie(root, X);
	//wyświetl wszystkie klucze w trybie inorder;
	cout << "Przejscie w trybie inorder..." << endl;
	//inorder(root);
	//wyświetl wszystkie klucze w trybie preorder;
	cout << "Przejscie w trybie preorder..." << endl;
	//preorder(root);
	//wstaw element o wartości klucza k2;
	cout << "Dodawanie elementu o wartosci klucza k2..." << endl;
	dodaj(root, k2);
	//wyświetl wszystkie klucze w trybie inorder;
	cout << "Przejscie w trybie inorder..." << endl;
	//inorder(root);
	//wstaw element o wartości klucza k3;
	cout << "Dodawanie elementu o wartosci klucza k3..." << endl;
	dodaj(root, k3);
	//wstaw element o wartości klucza k4;
	cout << "Dodawanie elementu o wartosci klucza k4..." << endl;
	dodaj(root, k4);
	//usuń element o wartości klucza k1;
	cout << "Usuwanie elementu o wartosci klucza k1..." << endl;
	inorder(root);
	usun(root, k1);
	//wyświetl wszystkie klucze w trybie preorder;
	cout << "Przejscie w trybie preorder..." << endl;
	preorder(root);
	//wyszukaj element o wartości k1;
	cout << "Wyszukanie elementu o wartosci klucza k1..." << endl;
	search(root, k1);
	//usuń element o wartości klucza k2;
	cout << "Usuwanie elementu o wartosci klucza k2..." << endl;
	usun(root, k2);
	//wyświetl wszystkie klucze w trybie inorder;
	cout << "Przejscie w trybie inorder" << endl;
	//inorder(root);
	//usuń element o wartości klucza k3;
	cout << "Usuwanie elementu o wartosci klucza k3..." << endl;
	usun(root, k3);
	//usuń element o wartości klucza k4;
	cout << "Usuwanie elementu o wartosci klucza k4..." << endl;
	usun(root, k4);
        inorder(root);
        cout<<endl;
        //dodaj(root,4);
        //dodaj(root,4);
	inorder(root);
	int wysokosc=maxDepth(root);
        cout<<"Wysokosc drzewa:"<<wysokosc<<endl;
        root=make_backbone(root);
        wysokosc=maxDepth(root);
        cout<<"Wysokosc drzewa (lista):"<<wysokosc<<endl;
        root=make_perfect_tree(root,wysokosc);
        wysokosc=maxDepth(root);
        cout<<"Wysokosc drzewa po DSW:"<<wysokosc<<endl;
	usuwaj(root);
	root=new BSTNode;

	//czas stop;

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

//wypisz czas wykonania;
	cout << "Czas wykonania:" << time_spent << endl;

	//cout << "root:" << root << "  " << root->klucz<<endl;

    }