#include <iostream>
#include <string>
#include <fstream>
using namespace std;

class Node
{
public:
string pol;
string eng;
Node *left;
Node *right;
int height;
};


Node* newNode(string pol_,string eng_)
{
        Node* node = new Node();
        node->pol = pol_;
        node->eng = eng_;
        node->left = NULL;
        node->right = NULL;
        node->height = 1; //lisc

        return(node);
}
int height(Node *N)
{
        if (N == NULL)
                return 0;
        return N->height;
}
Node *rotacjaPrawo(Node *y)
{
        Node *x = y->left;
        Node *T2 = x->right;

        // Perform rotation
        x->right = y;
        y->left = T2;

        // Update heights
        y->height = max(height(y->left),
                        height(y->right)) + 1;
        x->height = max(height(x->left),
                        height(x->right)) + 1;

        // Return new root
        return x;
}
Node *rotacjaLewo(Node *x)
{
        Node *y = x->right;
        Node *T2 = y->left;

        // Perform rotation
        y->left = x;
        x->right = T2;

        // Update heights
        x->height = max(height(x->left),
                        height(x->right)) + 1;
        y->height = max(height(y->left),
                        height(y->right)) + 1;

        // Return new root
        return y;
}
int getBalance(Node *N)
{
        if (N == NULL)
                return 0;
        return height(N->left) -
               height(N->right);
}
Node* dodajNode(Node* node, string pol,string eng)
{
        /* 1. Perform the normal BST rotation */
        if (node == NULL)
                return(newNode(pol,eng));

        if (pol < node->pol)
                node->left = dodajNode(node->left, pol,eng);
        else if (pol > node->pol)
                node->right = dodajNode(node->right, pol,eng);
        else // Equal pols not allowed
                return node;

        /* 2. Update height of this ancestor node */
        node->height = 1 + max(height(node->left),
                               height(node->right));

        /* 3. Get the balance factor of this
           ancestor node to check whether
           this node became unbalanced */
        int balance = getBalance(node);

        // If this node becomes unbalanced,
        // then there are 4 cases

        // Left Left Case
        if (balance > 1 && pol < node->left->pol)
                return rotacjaPrawo(node);

        // Right Right Case
        if (balance < -1 && pol > node->right->pol)
                return rotacjaLewo(node);

        // Left Right Case
        if (balance > 1 && pol > node->left->pol)
        {
                node->left = rotacjaLewo(node->left);
                return rotacjaPrawo(node);
        }

        // Right Left Case
        if (balance < -1 && pol < node->right->pol)
        {
                node->right = rotacjaPrawo(node->right);
                return rotacjaLewo(node);
        }

        /* return the (unchanged) node pointer */
        return node;
}
void przejKlp(Node *root)
{
        if(root != NULL)
        {
                cout << root->pol << " " << root->eng << " ";
                przejKlp(root->left);
                przejKlp(root->right);
        }
}


Node * minWartoscNode(Node* node)
{
        Node* current = node;


        while (current->left != NULL)
                current = current->left;

        return current;
}
Node * maxWartoscNode(Node* node)
{
        Node* current = node;


        while (current->right != NULL)
                current = current->right;

        return current;
}

Node* usuwanie(Node* root, string pol)
{

        //zaczynam zwykle usuwanie bst
        if (root == NULL)
                return root;

        // jesli polskie slowo ktore usuwam mniejsze od korzenia ide w lewo
        if ( pol < root->pol )
                root->left = usuwanie(root->left, pol);

        // jesli polskie slowo ktore usuwam wieksze od korzenia ide w prawo

        else if( pol > root->pol )
                root->right = usuwanie(root->right, pol);

        // jesli takie samo jak korzen to wlasnie jego szukam
        else
        {
                // wezly z jednym synem lub zadnym
                if( (root->left == NULL) ||
                    (root->right == NULL) )
                {
                        Node *temp = root->left ?
                                     root->left :
                                     root->right;

                        // No child case
                        if (temp == NULL)
                        {
                                temp = root;
                                root = NULL;
                        }
                        else // przypadek gdy jeden syn
                                *root = *temp; // przechowanie zawartosci syna
                        free(temp);
                }
                else
                {
                        // wezel z dwoma synami , maxWartoscNode szukam najwieksego elementu lewego poddrezwa
                        Node* temp = maxWartoscNode(root->left);


                        root->pol = temp->pol;
                        root->eng = temp->eng;

                        root->left = usuwanie(root->left,
                                              temp->pol);
                }
        }

        //drzewo mialo tylko jeden wezel
        if (root == NULL)
                return root;

        // aktualizacja wysokosci obecnego wezla
        root->height = 1 + max(height(root->left),
                               height(root->right));

        // sprawdzanie bilansu wysokosci
        int balance = getBalance(root);

        // rozwiazanie problemow gdy wezel nie jest zbliansowany

        // lewo lewo
        if (balance > 1 &&
            getBalance(root->left) >= 0)
                return rotacjaPrawo(root);

        // lewo prawo ( podwojna rotacja )
        if (balance > 1 &&
            getBalance(root->left) < 0)
        {
                root->left = rotacjaLewo(root->left);
                return rotacjaPrawo(root);
        }

        // prawo prawo
        if (balance < -1 &&
            getBalance(root->right) <= 0)
                return rotacjaLewo(root);

        // prawo lewo ( podwojna rotacja )
        if (balance < -1 &&
            getBalance(root->right) > 0)
        {
                root->right = rotacjaPrawo(root->right);
                return rotacjaLewo(root);
        }

        return root;
}

// pomaga ustawiac wartosci alfabetycznie poprez porownywanie dwoch stringow
string max(string a,string b){
        if(a>b) return a;
        else return b;
}

// zapis do pliku
void savetotxt(Node *root,fstream &plik){
        if(root != NULL)
        {
                plik << root->pol << " " << root->eng << " ";
                savetotxt(root->left,plik);
                savetotxt(root->right,plik);
        }
}
// zapis do pliku
void saveavl(Node *root)
{
        fstream plik;
        plik.open("OUTAVL.txt",ios::out);
        savetotxt(root,plik);

        plik.close();
}

Node* wyszukiwanie(string pol, Node* node);
int main(int argc, char const *argv[]) {
        Node *root = NULL;

        // odczytanie danych z pliku
        ifstream infile("INAVL.txt");
        string a,b;
        if(infile.fail())
                cout << "error" << endl;
        while(!infile.eof()) {
                infile>>a>>b;
                root = dodajNode (root,a,b);
        }
        infile.close();

        cout<<endl;
        cout << "Przejscie KLP\n";
        przejKlp(root);
        cout<<endl;

        root = usuwanie(root,"FSI");
        cout<<endl;
        cout << "Przejscie KLP\n";
        przejKlp(root);
        root = usuwanie(root,"COT");
        cout << "Przejscie KLP\n";
        przejKlp(root);
        cout<<endl;
        // wyszukiwanie słowa polskiego i jego tłumaczenia
        wyszukiwanie("A",root);
        // zapisz przejscie KLP do pliku
        saveavl(root);
        return 0;
}
Node* wyszukiwanie(string pol, Node* node) {
        if(node == nullptr) return nullptr;

        if(pol < node->pol)  {
                node->left = wyszukiwanie(pol, node->left);
        }
        else if(pol > node->pol) {
                node->right = wyszukiwanie(pol, node->right);
        }
        else if(node->pol == pol)  {
                cout << node->pol << " " << node->eng << endl;
        }
        else {
                cout << "Takie słowo nie istnieje" << endl;
        }
        return node;
}