//SDIZO I1 212A LAB03
//Szymon Lisiecki
//ls39343@zut.edu.pl

#include <iostream>
#include <ctime>
#include <fstream>

using namespace std;

// Węzeł drzewa
struct Wezel{
    int klucz;
    char tab[11];                              // do konwersji z inta na chara: zrobić coś w stylu, że  korzeń->tab[11] = konwersja, funkcja konwersji
    Wezel *leweDziecko, *praweDziecko;
};

// drzewo
struct Drzewo {
    Wezel *korzen;
};

static int licznikInOrder;
static int licznikPreOrder;
static int licznikPostOrder;

// inicjalizacja drzewa
void Zeruj(Drzewo *choinka) {

    choinka->korzen = NULL;

}

// usuwa element o wartosci klucza
Wezel* Usun(Drzewo *choinka, int klucz) {
    if (choinka->korzen == NULL)    return NULL;

    Wezel *aktualny, *cel, *poprzedni;

    aktualny = choinka->korzen;
    cel = NULL;
    poprzedni = NULL;

    while (1) {
        if (aktualny->klucz == klucz)
            cel = aktualny;

        if (klucz < aktualny->klucz) {
            if (aktualny->leweDziecko == NULL)
                break;
            poprzedni = aktualny;
            aktualny = aktualny->leweDziecko;
        }
        else {
            if (aktualny->praweDziecko == NULL)
                break;
            poprzedni = aktualny;
            aktualny = aktualny->praweDziecko;
        }
    }

    if (cel == NULL)
        return false;
    else {
        if (poprzedni == NULL) {
            delete aktualny;
            choinka->korzen = NULL;
        }
        else {
            // Łączenie wskaznikami
            // aktualny wezel wskazuje na zmieniony
            cel->klucz = aktualny->klucz;
            if (poprzedni->leweDziecko == aktualny)

                if (aktualny->praweDziecko != NULL && aktualny->praweDziecko->praweDziecko == NULL && aktualny->praweDziecko->leweDziecko)
                    poprzedni->leweDziecko = aktualny->praweDziecko;
                else
                    poprzedni->leweDziecko = aktualny->leweDziecko;

            else
                if (aktualny->leweDziecko != NULL && aktualny->leweDziecko->praweDziecko == NULL && aktualny->leweDziecko->leweDziecko)
                    poprzedni->praweDziecko = aktualny->leweDziecko;
                else
                    poprzedni->praweDziecko = aktualny->praweDziecko;


            delete aktualny;
        }
    }

}


// lewo -> korzen -> prawo
void Wyswietl_InOrder(Wezel *choinka) {
    if (choinka == NULL) return;

    licznikInOrder++;

    Wyswietl_InOrder(choinka->leweDziecko);
    cout << choinka->klucz << endl;
    Wyswietl_InOrder(choinka->praweDziecko);

}

// korzen -> lewo -> prawo
void Wyswietl_PreOrder(Wezel *choinka) {
    if (choinka == NULL) return;
    licznikPreOrder++;

    cout << choinka->klucz << endl;
    Wyswietl_PreOrder(choinka->leweDziecko);
    Wyswietl_PreOrder(choinka->praweDziecko);

}
// lewo -> prawo -> korzen
//void Wyswietl_PostOrder(Wezel *choinka) {
//  if (choinka == NULL) return;
//  licznikPostOrder++;
//
//  Wyswietl_PostOrder(choinka->leweDziecko);
//  Wyswietl_PostOrder(choinka->praweDziecko);
//  cout << choinka->klucz << endl;
//}


bool Szukaj(Drzewo *choinka, int klucz) {
    if (choinka->korzen == NULL) return false;

    Wezel* pomocniczy = choinka->korzen;
    Wezel* rodzic = nullptr;

    while (pomocniczy != NULL && pomocniczy->klucz != klucz) {
        //rodzic jest aktualnym
        rodzic = pomocniczy;

        //jak klucz jest mniejszy od pomocniczego to idz do lewego dziecka, else..
        if (klucz < pomocniczy->klucz)
            pomocniczy = pomocniczy->leweDziecko;
        else
            pomocniczy = pomocniczy->praweDziecko;
    }

    if (pomocniczy == NULL)
    {
        //cout << "Nie znaleziono wezla o podanym kluczu." << endl;
        return false;
    }

    //cout << "Znaleziono wezel o podanym kluczu" << endl;
    return true;

}
// znajduje wezel o zadanej wartosci klucza

bool Wstaw_PoKluczu(Drzewo *choinka, int klucz) {
    Wezel *pomocniczy, *rodzic;

    if (Szukaj(choinka, klucz)==true) return false; // jeżeli znajdzie klucz to zwraca false

    Wezel *aktualnyWezel = new Wezel();
    aktualnyWezel->klucz = klucz;

    char aktualnaTablica[11]; //deklaracja chara
    sprintf_s(aktualnaTablica, "%d", klucz);  //konwersja z int na char
    aktualnyWezel->tab[11] = aktualnaTablica[11]; //nadanie charowi wyrazenia z inta



    if (choinka->korzen == NULL) {
        choinka->korzen = aktualnyWezel; // jeżeli było puste to teraz ma korzeń
        aktualnyWezel->leweDziecko = NULL;
        aktualnyWezel->praweDziecko = NULL;
        pomocniczy = choinka->korzen;
    } else {
        pomocniczy = choinka->korzen;
        while (pomocniczy != NULL)
        {
            if (pomocniczy->klucz > klucz)
            {
                rodzic = pomocniczy;
                pomocniczy = pomocniczy->leweDziecko;
            }
            else {
                rodzic = pomocniczy;
                pomocniczy = pomocniczy->praweDziecko;
            }
        }
        aktualnyWezel->klucz = klucz;
        aktualnyWezel->leweDziecko = NULL;
        aktualnyWezel->praweDziecko = NULL;

        if (rodzic->klucz > klucz)
            rodzic->leweDziecko = aktualnyWezel;
        else
            rodzic->praweDziecko = aktualnyWezel;
    }

    return true;
}

// losowanie klucza i wstawianie do funkcji Wstaw_
void WstawLosowo(Drzewo *choinka, int iloscWezlow) {
    srand(time(NULL));

    while (iloscWezlow-- > 0) {
        int klucz = (rand() % 20000) - 10000;

        Wstaw_PoKluczu(choinka, klucz);
    }

}


int main() {
    clock_t czasPoczatkowy = clock();
    ifstream plik("inlab03.txt");
    if (plik.fail()) return -1;

    int x, k1, k2, k3, k4;

    plik >> x >> k1 >> k2 >> k3 >> k4;

    cout << "Liczba elementow do wylosowania: " << x << endl;
    cout << "Wartosc klucza k1: " << k1 << endl;
    cout << "Wartosc klucza k2: " << k2 << endl;
    cout << "Wartosc klucza k3: " << k3 << endl;
    cout << "Wartosc klucza k4: " << k4 << endl;
    cout << endl;


    Drzewo choinka;
    Zeruj(&choinka);   //drzewo puste

    Usun(&choinka, k1);

    Wstaw_PoKluczu(&choinka, k1);

    WstawLosowo(&choinka, x);

    cout << "Wyswietlanie in-order: " << endl;
    Wyswietl_InOrder(choinka.korzen);
    cout << "Liczba odwiedzonych wezlow: ";
    cout << licznikInOrder << endl;
    licznikInOrder = 0;

    cout << "Wyswietlanie pre-order: " << endl;
    Wyswietl_PreOrder(choinka.korzen);
    cout << "Liczba odwiedzonych wezlow: ";
    cout << licznikPreOrder << endl;
    licznikPreOrder = 0;

    Wstaw_PoKluczu(&choinka, k2);

    cout << "Wyswietlanie in-order: " << endl;
    Wyswietl_InOrder(choinka.korzen);
    cout << "Liczba odwiedzonych wezlow: ";
    cout << licznikInOrder << endl;
    licznikInOrder = 0;

    Wstaw_PoKluczu(&choinka, k3);
    Wstaw_PoKluczu(&choinka, k4);
    Usun(&choinka, k1);

    cout << "Wyswietlanie pre-order: " << endl;
    Wyswietl_PreOrder(choinka.korzen);
    cout << "Liczba odwiedzonych wezlow: ";
    cout << licznikPreOrder << endl;
    licznikPreOrder = 0;

    Szukaj(&choinka, k1);

    Usun(&choinka, k2);

    cout << "Wyswietlanie in-order: " << endl;
    Wyswietl_InOrder(choinka.korzen);
    cout << "Liczba odwiedzonych wezlow: ";
    cout << licznikInOrder << endl;
    licznikInOrder = 0;

    Usun(&choinka, k3);
    Usun(&choinka, k4);

    /*cout << "Wyswietlanie post-order: " << endl;
    Wyswietl_PostOrder(choinka.korzen);
    cout << "Liczba odwiedzonych wezlow: ";
    cout << licznikPostOrder << endl;*/

    clock_t czasKoncowy = clock();
    double roznicaCzasow = (double)(czasKoncowy - czasPoczatkowy) / CLOCKS_PER_SEC;
    cout << "program wykonywal sie w " << roznicaCzasow << " sekund" << endl;

    getchar();
    getchar();
    return 0;
}