//#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#include <time.h>

using namespace std;

struct wezel
{
	int key;
	wezel *left, *right;
};

wezel * root; //wskaznik globalny na korzen

wezel * &inicjalizacja();
void wstawianieNowegoElementu(wezel * &root, int k);
void wstawianieXElementow(wezel * &root, int x);
wezel * wyszukajWezel(wezel * &root, int k);
void usuwanieElementu(wezel * &root, int k);
void usuwanieDrzewa(wezel * &root);
void inorder(wezel * x);
void walk(wezel * x);
wezel * searchParent(wezel *&root, int x);
wezel * searchPoprzednik(wezel *&root, int x);
wezel * searchNastepnik(wezel *&root, int x);

int main(int argc, char *argv[])
{
	srand(time(NULL)); //zawsze przy uzywaniu randa, zeby liczby sie nie powtarzaly


	int X, k1, k2, k3, k4;
	FILE* fp = fopen("inlab03.txt", "r");
	if (fp == NULL)return -1;
	fscanf(fp, "%d %d %d %d %d", &X, &k1, &k2, &k3, &k4);
	fclose(fp);

	clock_t begin, end;
	double time_spent;     // czas start
	begin = clock();


	wezel * root = inicjalizacja();
	usuwanieElementu(root, k1);
	wstawianieXElementow(root, 12);
	wstawianieNowegoElementu(root, k1);
	wstawianieNowegoElementu(root, k2);
	wstawianieNowegoElementu(root, k3);
	wstawianieNowegoElementu(root, k4);
	usuwanieElementu(root, k1);
	wyszukajWezel(root, k1);
	usuwanieElementu(root, k2);
	usuwanieElementu(root, k3);
	usuwanieElementu(root, k4);
    usuwanieDrzewa(root);

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

	cout << "Czas: " << time_spent << endl;

	system("pause");

	return 0;
}

wezel * &inicjalizacja()
{
	root = NULL;
	return root;
}

void wstawianieNowegoElementu(wezel * &root, int k)
{
	wezel * parent = NULL;
	wezel * tmp;
	tmp = root;
	wezel * nowy = new wezel;
	nowy->left = NULL;
	nowy->right = NULL;
	nowy->key = k;
	if (root == NULL)
	{
		root = nowy;
	}
	else
	{
		while (tmp != NULL) //dopoki nie dojdziesz za lisc
		{
			if (k == tmp->key) // jesli klucz = dodawany to nic nie rob
			{
				return;
			}
			if (k>tmp->key && tmp->right == NULL)
			{
				//parent = tmp;
				tmp->right = nowy;

			}
			if (k<tmp->key && tmp->left == NULL) //jesli klucz dodawany jest mniejszy od tymczasowego ktory wskazuje na root oryginalny
			{
				//parent = tmp;
				tmp->left = nowy;
			}

			if (k>tmp->key && tmp->right != NULL)
			{
				//parent = tmp;
				tmp = tmp->right;

			}
			if (k<tmp->key && tmp->left != NULL) //jesli klucz dodawany jest mniejszy od tymczasowego ktory wskazuje na root oryginalny
			{
				//parent = tmp;
				tmp = tmp->left;
			}
			//if (tmp->right)

		}
		tmp = nowy;// przypisuje wartosc tymczasowa do nowo dodanego wezla
	}
}

void wstawianieXElementow(wezel * &root, int x)
{
	int liczbaLosowa;
	for (int i = 0; i < x; i++)
	{
		liczbaLosowa = (rand() % 1000009) + 10;
		wstawianieNowegoElementu(root, liczbaLosowa);
	}
}

wezel * wyszukajWezel(wezel * &root, int k)
{
	wezel * tmp;
	tmp = root;
	if (root == NULL)
	{

	}
	while ((tmp) && (tmp->key != k))
	{

		if (k < tmp->key)
		{
			if (tmp->left == NULL)
			{
				cout << "Szukany element: "<<k<<" nie istnieje" << endl;
				return NULL;
			}
			tmp = tmp->left;
		}
		else
		{
			if (tmp->right == NULL)
			{
				cout << "Szukany element: "<<k<<" nie istnieje" << endl;
				return NULL;
			}
			tmp = tmp->right;
		}
	}

	cout << "Wyszukiwany wezel wynosi " << tmp->key << endl;
	return (tmp);
}

void inorder(wezel * x)
{
	if (x)
	{
		inorder(x->left);
		cout << x->key << endl;  // tutaj przetwarzamy bieżący węzeł
		inorder(x->right);
	}
}

void walk(wezel * x)
{
	cout << x->key << " : Left-> ";
	if (x->left) cout << x->left->key;
	else         cout << "NULL";
	cout << ", Right-> ";
	if (x->right) cout << x->right->key;
	else         cout << "NULL";
	cout << endl;
	if (x->left)  walk(x->left);
	if (x->right) walk(x->right);
}

wezel * searchParent(wezel *&root, int k)
{
	wezel *tmp = root;
	wezel *parent = NULL;

	if (root == NULL)
	{
	    return 0;
	}
	while ((tmp) && (tmp->key != k))
	{
		parent = tmp;
		if (k < tmp->key)
		{
			if (tmp->left == NULL)
			{
				cout << "Element nie istnieje" << endl;
				return NULL;
			}
			tmp = tmp->left;
		}
		else
		{
			if (tmp->right == NULL)
			{
				cout << "Element nie istnieje" << endl;
				return NULL;
			}
			tmp = tmp->right;
		}
	}

	return (parent);
}

wezel * searchPoprzednik(wezel *&root, int x)
{
	wezel *tmp = root;

	while (tmp && (x != tmp->key))
	{
		if (tmp->key < x)
			tmp = tmp->right;
		else
			tmp = tmp->left;
	}
	if (tmp != NULL)
	{

		if (tmp->left != NULL)
		{
			tmp = tmp->left;

			while (tmp->right)
			{
				tmp = tmp->right;
			}
		}
	}

	return tmp;
}

wezel * searchNastepnik(wezel *&root, int x)
{
	wezel *tmp = root;

	while (tmp && (x != tmp->key))
	{
		if (tmp->key < x)
			tmp = tmp->right;
		else
            tmp = tmp->left;
	}
	if (tmp != NULL)
	{
		if (tmp->right != NULL)
		{
			tmp = tmp->right;

			while (tmp->left)
			{
				tmp = tmp->left;
			}
		}
	}

	return tmp;
}

void usuwanieElementu(wezel * &root, int k)
{

    wezel* toRemove = root;

    while (toRemove && (k != toRemove->key))
	{
		if (toRemove->key < k)
			toRemove = toRemove->right;
		else
			toRemove = toRemove->left;
	}

     if(toRemove != NULL)
     {
      wezel* parent = searchParent(root, toRemove->key);
    // jesli wezel ma dwojke dzieci
if ( toRemove -> left != NULL && toRemove -> right != NULL )
    {
        wezel* pop = NULL;
        cout<<"Wybierz forme usuwania:"<<endl;
        cout<<"1 - nastepnik"<<endl;
        cout<<"2 - poprzednik"<<endl;
        int a = 0;
        cin>>a;

        if(a==1)
        {
           pop = searchNastepnik(root, k);
        }
        else
        {
         if(a==2)
         {
           pop = searchPoprzednik(root, k);
         }
         else
         {
           usuwanieElementu(root, k);
           return;
         }
        }
        parent = searchParent(root, pop->key);
        toRemove->key = pop->key;
        toRemove = pop;
    }

     // jesli wezel nie ma dzieci
if ( toRemove -> left == NULL && toRemove -> right == NULL )
    {
        if(parent != NULL)
        {

        if ( parent -> right == toRemove )
            parent -> right = NULL ;
        else
            parent -> left = NULL ;

        }
        else
        {
            root = NULL;
        }

        delete toRemove ;
        return;
    }

      // jesli wezel ma tylko prawe dziecko
if ( toRemove -> left == NULL && toRemove -> right != NULL )
    {
        if(parent != NULL)
        {

        if ( parent -> left == toRemove )
            parent -> left = toRemove -> right;
        else
            parent -> right = toRemove -> right;

        }
        else
        {
            root = toRemove->right;
        }

        delete toRemove ;
        return;
    }

   // jesli wezel ma tylko lewe dziecko
if ( toRemove -> left != NULL && toRemove -> right== NULL )
    {
        if(parent != NULL)
        {

        if ( parent -> left == toRemove )
            parent -> left= toRemove -> left;
        else
            parent -> right = toRemove -> left;

        }
        else
        {
            root = toRemove->left;
        }

        delete toRemove ;
        return;
    }
     }
     else
     {
         cout<<"Nie mozna usunac wezla o kluczu: "<<k<<endl;
     }
}

void usuwanieDrzewa(wezel * &root)
{
     if(root != NULL)
     usuwanieElementu(root, root->key);

     if(root != NULL)
     usuwanieDrzewa(root);
}