#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cstring>

using namespace std;

typedef struct BST {
  string valuecal;
  string valueczesc;
  struct BST *left;
  struct BST *right;
} BST;

BST *root = NULL;


int komparatorstringow(string jedencal,string jedenczesc,string dwacal,string dwaczesc){
    if(jedencal.length()>dwacal.length()) return 1;
    else if (dwacal.length()>jedencal.length()) return 2;
    else if (jedencal.length()==dwacal.length()){
        if(jedencal>dwacal) return 1;
        else if(dwacal>jedencal) return 2;
        else if(jedencal==dwacal){
            if(jedenczesc>dwaczesc) return 1;
            else if(dwaczesc>jedenczesc) return 2;
            else return 0;
        }
    }
}

void insert(string valcal,string valczesc){

    BST* v = new BST;
    BST* rodzic;
    v->left = NULL;
    v->right = NULL;
    v->valuecal = valcal;
    v->valueczesc = valczesc;

if(root==NULL) root=v;
  else
  {
    //Note: ALL insertions are as leaf nodes
    BST* obecny;
    obecny = root;
    // Find the Node's parent

    while(obecny)
    {
        rodzic = obecny;
        komparatorstringow(v->valuecal,v->valueczesc,obecny->valuecal,obecny->valueczesc);{
        if(1) obecny = obecny->right;
        else if(2) obecny = obecny->left;
        else return;
            }
        }
    }
    komparatorstringow(v->valuecal,v->valueczesc,rodzic->valuecal,rodzic->valueczesc);{
    if(1)rodzic->left = v;
    else if(2)rodzic->right = v;
    else return;
    }
  }

int napisyzplikuW(string temp){
    int x=temp.find(',');
    string a;
    string b;
    for(int i=0;i<x;i++){
        a=temp[i];
    }
    for(int i=x+1; i<temp.length();i++){
        b=temp[i];
    }
    insert(a,b);
}
void search(string dcal,string dczesc){
bool found=false;
    if(root==NULL)
    {
        cout<<" Drzewo jest puste! "<<endl;
        return;
    }
    BST* obecny;
    BST* rodzic;
    obecny = root;
    while(obecny != NULL)
    {
         if(obecny->valuecal == dcal && obecny->valueczesc == dczesc)
         {
            found = true;
            break;
         }
         else
         {
             rodzic = obecny;
             if(dcal > obecny->valuecal)
             obecny = obecny->right;
             else obecny = obecny->left;
         }
    }
    if(!found)
         {
        cout<<" Nie znaleziono elementu! "<<endl;
        system("pause");
        }
    else
    {
        cout<<" Znaleziono podany element!"<<endl;

    }
}
int napisyzplikuS(string temp){
    int x=temp.find(',');
    string a;
    string b;
    for(int i=0;i<x;i++){
        a=temp[i];
    }
    for(int i=x+1; i<temp.length();i++){
        b=temp[i];
    }
    search(a,b);
}

void searchilecal(BST *v, string dcal){
    int x=0;
        if(v==NULL)
        return ;
    else if(v!=NULL)
    {
        if(v->left) searchilecal(v->left,dcal);
        if(v->right) searchilecal(v->right,dcal);
    }
    cout<<x;
}


void remove(string dcal,string dczesc)
{
    {
    bool found=false;
    if(root==NULL)
    {
        cout<<" Drzewo jest puste, nie ma co usuwac! "<<endl;
        return;
    }
    BST* obecny;
    BST* rodzic;
    obecny = root;
    while(obecny != NULL)
    {
         if(obecny->valuecal == dcal && obecny->valueczesc == dczesc)
         {
            found = true;
            break;
         }
         else
         {
             rodzic = obecny;
             if(dcal >obecny->valuecal)
             obecny = obecny->right;
             else if(dcal<obecny->valuecal)
             obecny = obecny->left;
             else if(dcal==obecny->valuecal)
                if(dczesc>obecny->valueczesc)
                obecny=obecny->right;
                else
                obecny = obecny->left;
         }
    }
    if(!found)
         {
        cout<<" Nie znaleziono elementu! "<<endl;
        return;
        }
    else
    {
        cout<<" Znaleziono podany element, usunieto!"<<endl;
    }

         // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children

    // Node with single child
    if((obecny->left == NULL && obecny->right != NULL)|| (obecny->left != NULL&& obecny->right == NULL))
    {
       if(obecny->left == NULL && obecny->right != NULL)
       {
           if(rodzic->left == obecny)
           {
             rodzic->left = obecny->right;
             delete obecny;
           }
           else
           {
             rodzic->right = obecny->right;
             delete obecny;
           }
       }
       else // left child present, no right child
       {
          if(rodzic->left == obecny)
           {
             rodzic->left = obecny->left;
             delete obecny;
           }
           else
           {
             rodzic->right = obecny->left;
             delete obecny;
           }
       }
     return;
    }

         //We're looking at a leaf node
         if( obecny->left == NULL && obecny->right == NULL)
    {
        if(rodzic->left == obecny) rodzic->left = NULL;
        else rodzic->right = NULL;
                 delete obecny;
                 return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
    if (obecny->left != NULL && obecny->right != NULL)
    {
        BST* temp;
        temp = obecny->right;
        if((temp->left == NULL) && (temp->right == NULL))
        {
            obecny = temp;
            delete temp;
            obecny->right = NULL;
        }
        else // right child has children
        {
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((obecny->right)->left != NULL)
            {
                BST *ltemp;
                BST *rtemp;
                ltemp = obecny->right;
                rtemp = (obecny->right)->left;
                while(ltemp->left != NULL)
                {
                   rtemp = ltemp;
                   ltemp = ltemp->left;
                }
                obecny->valuecal = ltemp->valuecal;
                obecny->valueczesc = ltemp->valueczesc;
                delete ltemp;
                rtemp->left = NULL;
           }
           else
           {
               BST* temp2;
               temp2 = obecny->right;
               obecny->valuecal = temp2->valuecal;
               obecny->valueczesc = temp2->valueczesc;
               obecny->right = temp2->right;
               delete temp2;
           }

        }
         return;
    }
}
}
int napisyzplikuU(string temp){
    int x=temp.find(',');
    string a;
    string b;
    for(int i=0;i<x;i++){
        a=temp[i];
    }
    for(int i=x+1; i<temp.length();i++){
        b=temp[i];
    }
    remove(a,b);
}
void inorder(BST* v)
{
    if(v==NULL)
        return ;
    else if(v!=NULL)
    {
        if(v->left) inorder(v->left);
        cout<<" "<<v->valuecal<<","<<v->valueczesc<<" ";
        if(v->right) inorder(v->right);
    }
    else return;
}

void wypiszpodanypoziom(struct BST *v, int level)
{
    if (v == NULL) return;
    if (level == 1) cout << v->valuecal <<","<<v->valueczesc<<  " ";
    else if (level > 1)
    {
        wypiszpodanypoziom(v->left, level - 1);
        wypiszpodanypoziom(v->right, level - 1);
    }
}
int wysokosc(struct BST* v)
{
    if (v == NULL) return 0;
    else
    {
        int lwysokosc = wysokosc(v->left);
        int rwysokosc = wysokosc(v->right);

        if (lwysokosc > rwysokosc)
            return(lwysokosc + 1);
        else return(rwysokosc + 1);
    }
}
void printLevelOrder(struct BST* v)
{
    int h = wysokosc(v);;
    int i;
    for (i = 1; i <= h; i++)
    {
        for (int j = h; j > i; j--) cout << " ";
        wypiszpodanypoziom(v, i);
        cout << endl << endl;
    }
}

int main(){

    /*int l_polecen;
    char polecenie;
    string liczba;
    fstream file;
    file.open("in.txt", ios::in);

    file>>l_polecen;

    for(int i=0; i<l_polecen;i++){
        file>>polecenie;
        if(polecenie=='W'){
            file>>liczba;
            cout<<polecenie<<" "<<liczba<<endl;
            napisyzplikuW(liczba);
        }
        else if(polecenie=='U'){
            file>>liczba;
            cout<<polecenie<<" "<<liczba<<endl;
            napisyzplikuU(liczba);
        }
        else if (polecenie=='S'){
            file>>liczba;
            cout<<polecenie<<" "<<liczba<<endl;
            napisyzplikuS(liczba);
        }
        /*else if(polecenie=='L'){
            file>>liczba;
            cout'polecenie'<<" "<<liczba<<endl;
            //ile liczb posiada czesc calkowita rowna x
            //file2<<wynik
        }

    }*/
    int wybor;
    string temp,temp2;
    while(1)
    {
       cout<<" Drzewo BST "<<endl;
       cout<<" 1. Dodawanie"<<endl;
       cout<<" 2. Usuwanie elementu "<<endl;
       cout<<" 3. Wyswietlanie drzewa "<<endl;
       cout<<" 4. Wyszukiwanie elementu"<<endl;
       cout<<" 5. Wypisz drzewo In-order"<<endl;
       cout<<" 7. Ile wystapien danej calkowitej"<<endl;
       cout<<" 6. Wyjscie "<<endl;
       cout<<" Wprowadz wybor : ";
       cin>>wybor;
       switch(wybor)
       {
           case 1 : system("cls");
                    cout<<" Podaj wartosc przed przecinkiem jaka chcesz dodac do drzewa :"<<endl;
                    cin>>temp;
                    cout<<" Podaj wartosc po przecinku"<<endl;
                    cin>>temp2;
                    insert(temp,temp2);
                    break;
           case 2 : system("cls");
                    cout<<endl;
                    cout<<" Podaj czesc calkowita elementu, ktory chcesz usunac z drzewa: "<<endl;
                    cin>>temp;
                    cout<<" Oraz czesc po przecinku:"<<endl;
                    cin>>temp2;
                    remove(temp,temp2);
                    break;
           case 3 : system("cls");
                    cout<<endl;
                    printLevelOrder(root);
                    cout<<endl<<endl;
                    break;
           case 4 : system("cls");
                    cout<<endl;
                    cout<<" Podaj element, ktorego wystepowanie chcesz sprawdzic "<<endl;
                    cin>>temp;
                    cout<<" Czesc po przecinka element:"<<endl;
                    cin>>temp2;
                    search(temp,temp2);
                    break;
           case 5 : system("cls");
                    cout<<endl;
                    inorder(root);
                    cout<<endl<<endl;
                    break;
           case 6 : system("cls");
                    system("pause");
                    return 0;
                    break;
           case 7 : system("cls");
                    cout<<endl;
                    cout<<" Podaj element calkowity, ktorego liczbe wystapien chcesz policzyc"<<endl;
                    cin>>temp;
                    searchilecal(root,temp);
                    cout<<endl<<endl;
       }
    }



return 0;
}