#include <iostream>
#include <string>
#include <fstream>
#include <cstdlib>
#include <string>

using namespace std;

struct Drzewo
{
    string liczba;
    Drzewo *lewy;
    Drzewo *prawy;
    int waga;
};

int ilosc_prefiksow = 0; // trzeba zerowaæ przed kazdym uzyciem


Drzewo *nowyWezel(string liczba)
{
    Drzewo* wezel = new Drzewo;
    wezel->liczba = liczba;
    wezel->lewy = NULL;
    wezel->prawy = NULL;
    wezel->waga = 0;
    return(wezel);
}

int wysokosc(Drzewo* wez)
{
    if (wez == NULL) return 0;
    else
    {
        // compute the height of each subtree
        int lheight = wysokosc(wez->lewy);
        int rheight = wysokosc(wez->prawy);

        // use the larger one
        if (lheight > rheight) return(lheight + 1);
        else return(rheight + 1);
    }
}

Drzewo *rotacjaP(Drzewo *wezel) // ?*
{
    Drzewo *tempL = wezel->lewy;
    Drzewo *tempP = tempL->prawy;

    tempL->prawy = wezel;
    wezel->lewy = tempP;

    wezel->waga = wysokosc(wezel->lewy) - wysokosc(wezel->prawy);
    tempL->waga = wysokosc(tempL->lewy) - wysokosc(tempL->prawy);

    return tempL;
}

Drzewo *rotacjaL(Drzewo *wezel)
{
    Drzewo *tempP = wezel->prawy;
    Drzewo *tempL = tempP->lewy;

    tempP->lewy = wezel;
    wezel->prawy = tempL;

    wezel->waga = wysokosc(wezel->lewy) - wysokosc(wezel->prawy);
    tempP->waga = wysokosc(tempP->lewy) - wysokosc(tempP->prawy);

    return tempP;
}

Drzewo *dodaj(Drzewo* wezel, string l)
{
    if (wezel == NULL) return(nowyWezel(l));

    else if (l < wezel -> liczba)
        wezel->lewy = dodaj(wezel->lewy, l);

    else if (l > wezel -> liczba )
        wezel->prawy = dodaj(wezel->prawy, l);

    else return wezel;

    wezel -> waga = wysokosc(wezel -> lewy) - wysokosc(wezel -> prawy);

    // RR
    if (wezel -> waga > 1 && (l < wezel -> lewy -> liczba))
    {
        return rotacjaP(wezel);
    }

    // LL
    if (wezel->waga < -1 && (l > wezel -> liczba ))
    {
        return rotacjaL(wezel);
    }

    // Left Right Case
    if (wezel->waga > 1 && (l > wezel -> liczba))
    {
        wezel->lewy = rotacjaL(wezel->lewy);
        return rotacjaP(wezel);
    }

    // Right Left Case
    if (wezel->waga < -1 && (l < wezel -> lewy -> liczba))
    {
        wezel->prawy = rotacjaP(wezel->prawy);
        return rotacjaL(wezel);
    }

    return wezel;
}


Drzewo* usun(Drzewo* wezel, string liczba)
{
    bool znaleziony = false;

    Drzewo* curr;
    Drzewo* parent = 0;
    curr = wezel;
    while (curr != NULL)
    {
        if (curr -> liczba == liczba) // =
        {
            znaleziony = true;
            break;
        }
        else
        {
            parent = curr;
            if (liczba > curr -> liczba)// >

                curr = curr -> prawy;
            else curr = curr -> lewy;
        }
    }
    if (!znaleziony)
    {
        cout << " Data not found! " << endl;
        return wezel;
    }

    bool usunieto = false;


    if (!usunieto)
    {
        if ((curr->lewy == NULL && curr->prawy != NULL) || (curr->lewy != NULL && curr->prawy == NULL))
        {
            if (curr->lewy == NULL && curr->prawy != NULL)
            {
                if (parent->lewy == curr)
                {
                    parent->lewy = curr->prawy;
                    delete curr;
                }
                else
                {
                    parent->prawy = curr->prawy;
                    delete curr;
                }
            }
            else
            {
                if (parent->lewy == curr)
                {
                    parent->lewy = curr->lewy;
                    delete curr;
                }
                else
                {
                    parent->prawy = curr->lewy;
                    delete curr;
                }
            }
            usunieto = true;
        }
    }

    if (!usunieto)
    {
        if (curr->lewy == NULL && curr->prawy == NULL)
        {
            if (parent->lewy == curr) parent->lewy = NULL;
            else parent->prawy = NULL;
            delete curr;
            usunieto = true;
        }
    }

    if (!usunieto)
    {
        if (curr->lewy != NULL && curr->prawy != NULL)
        {
            Drzewo* chkr;
            chkr = curr->prawy;
            if ((chkr->lewy == NULL) && (chkr->prawy == NULL))
            {
                curr = chkr;
                delete chkr;
                curr->prawy = NULL;
            }
            else
            {
                if ((curr->prawy)->lewy != NULL)
                {
                    Drzewo* lcurr;
                    Drzewo* lcurrp;
                    lcurrp = curr->prawy;
                    lcurr = (curr->prawy)->lewy;
                    while (lcurr->lewy != NULL)
                    {
                        lcurrp = lcurr;
                        lcurr = lcurr->lewy;
                    }
                    curr->liczba = lcurr->liczba;
                    delete lcurr;
                    lcurrp->lewy = NULL;
                }
                else
                {
                    Drzewo* tmp;
                    tmp = curr -> prawy;
                    curr -> liczba = tmp -> liczba;
                    curr -> prawy = tmp -> prawy;
                    delete tmp;
                }

            }
            usunieto = true;
        }
    }

    wezel -> waga = wysokosc(wezel -> lewy) - wysokosc(wezel -> prawy);

    // Left Left Case
    if (wezel -> waga > 1 && liczba < wezel->lewy->liczba)
    {
        return rotacjaP(wezel);
    }

    // Right Right Case
    if (wezel -> waga < -1 && liczba > wezel -> prawy -> liczba)
    {
        return rotacjaL(wezel);
    }

    // Left Right Case
    if (wezel -> waga > 1 && liczba > wezel -> lewy -> liczba)
    {
        wezel -> lewy = rotacjaL(wezel -> lewy);
        return rotacjaP(wezel);
    }

    // Right Left Case
    if (wezel -> waga < -1 && liczba < wezel -> prawy->liczba)
    {
        wezel -> prawy = rotacjaP(wezel -> prawy);
        return rotacjaL(wezel);
    }

    return wezel;
}

// szuka podanego slowa w drzewie
bool szukaj(Drzewo* korzen, string liczba)
{
    while (korzen != NULL)
    {
        if (liczba == korzen -> liczba)
            return true;
        if (liczba > korzen -> liczba)
            korzen = korzen->prawy;
        else korzen = korzen->lewy;
    }
    return false;
}

// szuka podanego slowa w drzewie
void prefiks(Drzewo *korzen, string liczba)
{
    if (korzen != NULL)
    {
        if (korzen -> liczba.find(liczba) == 0) ilosc_prefiksow++;
        prefiks(korzen -> lewy, liczba);
        prefiks(korzen -> prawy, liczba);
    }
}

int zliczPrefiks(Drzewo *korzen, string liczba)
{
    ilosc_prefiksow = 0;

    prefiks(korzen, liczba);

    return ilosc_prefiksow;
}

// Print nodes at a given level
void wypiszPoziom(Drzewo* korzen, int level)
{
    if (korzen == NULL)
    {
        //if( to jest najnizszy poziom drzewa) cout << "--";
        cout << "  ";
        return;
    }
    if (level == 1) cout << korzen->liczba << "   ";
    else if (level > 1)
    {
        wypiszPoziom(korzen->lewy, level - 1);
        wypiszPoziom(korzen->prawy, level - 1);
    }
}

void wypisz(Drzewo* korzen)
{
    int h = wysokosc(korzen);;
    int i;
    for (i = 1; i <= h; i++)
    {
        for (int j = h; j > i; j--) cout << " ";
        wypiszPoziom(korzen, i);
        cout << endl << endl;
    }
}


int main()
{
    Drzewo *korzen = NULL;

    fstream plik;
    plik.open("in.txt");
    int ile;
    plik >> ile;

    char p;
    string x;

    for (int i = 0; i < ile; i++)
    {
        plik >> p >> x;
        cout << "Polecenie: " << p << " x: " << x << endl;


        if (p == 'W') korzen = dodaj(korzen, x);
        if (p == 'U') korzen = usun(korzen, x);
        if (p == 'S')
        {
            if (szukaj(korzen, x)) cout << "TAK" << endl;
            else cout << "NIE" << endl;
        }
        if (p == 'L') cout << zliczPrefiks(korzen,x) << endl;
    }
    // nie ma rotacji jak w ostatnim przykladzie z pdfa !!!!!!!!!!!!!!!!!!!

    wypisz(korzen);
    system("PAUSE");
    return 0;
}

// --------------------------------- K O N I E C ---------------------------------------------