//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 X1,X2;
	FILE* fp = fopen("inlab04.txt", "r");
    	if (fp == NULL)
        	return -1;
    	fscanf(fp, "%d %d", &X1, &X2);  // wczytanie pliku
    	fclose(fp);

//czas start

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






	//wstaw X elementów do drzewa;
	cout << "Wstawianie X elementow do drzewa..." << endl;
	wstawianie(root, X1);
	int wysokosc1=maxDepth(root);
	cout<<"Wysokosc:"<<wysokosc1<<endl;
	root=make_backbone(root);
	root=make_perfect_tree(root,wysokosc1);
	wysokosc1=maxDepth(root);
	cout<<"Wysokosc po DSW:"<<wysokosc1<<endl;

	usuwaj(root);
	root=new BSTNode;
	wstawianie(root,X2);
	int wysokosc2=maxDepth(root);
	cout<<"Wysokosc:"<<wysokosc2<<endl;
	root=make_backbone(root);
	root=make_perfect_tree(root,wysokosc2);
	wysokosc2=maxDepth(root);
	cout<<"Wysokosc po DSW:"<<wysokosc2<<endl;






	//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;

    }