//#include "pch.h"
#include <ctime>
#include <iostream>
#include <cstdlib>
#include <cstring>

using namespace std;

class BST
{
    struct Node
    {
        int key;
        Node *left;
        Node *right;
    };

    int _length = 0;

    Node *findParent(Node *node, Node *root)
    {
        static Node *parent = nullptr;
        if (root)
        {
            if (root->left == node || root->right == node)
            {
                parent = root;
            }
            else
            {
                parent = findParent(node, root->left);
                if (!parent)
                {
                    findParent(node, root->right);
                }
            }
        }

        return parent;
    }


    Node * findPredecessor(Node *node)
    {
        Node *temp = node->left;
        while (temp->right)
        {
            temp = temp->right;
        }
        return temp;
    }

    void inorderSupport(Node *node)
    {
        if (node != nullptr)
        {
            inorderSupport(node->left);
            cout << node->key << "\t";
            inorderSupport(node->right);
        }

    }

public:
    Node *root;

    BST()
    {
        root = nullptr;
    }

    ~BST() {}

    void insertElement(int key)
    {
        Node *toInsert = new Node;
        toInsert->key = key;
        toInsert->left = nullptr;
        toInsert->right = nullptr;

        if (root == nullptr)
        {
            root = toInsert;
            _length++;
        }
        else
        {
            Node *temp = root;
            while (1)
            {
                if (key == temp->key)
                {
                    /// juz taki istnieje
                    break;
                }
                else if (key < temp->key)
                {
                    if (!temp->left)
                    {
                        temp->left = toInsert;
                        _length++;
                        break;
                    }
                    temp = temp->left;
                }
                else
                {
                    if (!temp->right)
                    {
                        temp->right = toInsert;
                        _length++;
                        break;
                    }
                    temp = temp->right;
                }
            }
        }
    }


    void insertXElements(int x)
    {
        for (int i = 0; i < x; i++)
        {
            insertElement(rand() % 20001 - 10000);
        }
    }

    bool findElement(int key)
    {
        if (root == nullptr)
        {
            cout << "Nie udalo sie odnalezc elementu o kluczu " << key << ", poniewaz drzewo jest puste.\n\n";
            return false;
        }
        else
        {
            Node *temp = root;
            while (temp)
            {
                if (key == temp->key)
                {
                    //cout << "Znaleziono element o kluczu " << key << "\n\n";
                    return true;
                }
                if (key < temp->key) temp = temp->left;
                else temp = temp->right;
            }
            return false;
        }
    }

    void removeElement(int key)
    {
        if (root == nullptr)
        {
            cout << "Nie udalo sie usunac elementu o kluczu " << key << ", poniewaz drzewo jest puste.\n";
            return;
        }
        else
        {
            Node *temp = root;
            if (root->key = key && !(root->left && root->right))
            {
                cout << "wchodze w usuwanie roota ktory nie ma 2 dzieci\n";
                if (!root->left && !root->right)
                {
                    temp = nullptr;
                    delete temp;
                    return;
                }
                else if (!root->right)
                {
                    root = temp->left;
                    temp = nullptr;
                    delete temp;
                    return;
                }
                else
                {
                    root = temp->right;
                    temp = nullptr;
                    delete temp;
                    return;
                }
            }
            while (temp)
            {
                if (key == temp->key)
                {
                    ///usuwanie

                    if (key == temp->key)
                    {
                        ///usuwanie
                        if (temp == root && !(temp->left && temp->right))
                        {
                            if (!temp->left && !temp->right)
                            {
                                delete root;
                                return;
                            }
                            else if (!temp->right)
                            {
                                root = temp->left;
                                delete temp;
                                return;
                            }
                            else
                            {
                                root = temp->right;
                                delete temp;
                                return;
                            }
                        }
                    }
                    if (!temp->left && !temp->right) /// brak synow
                    {
                        cout << "wchodze w usuwanie bez synow";
                        if (key > findParent(temp, root)->key)
                        {
                            findParent(temp, root)->right = nullptr;
                            temp = nullptr;
                            delete temp;
                        }
                        else
                        {
                            findParent(temp, root)->left = nullptr;
                            temp = nullptr;
                            delete temp;
                        }
                        _length--;
                        cout << "usuniety bez synow\n";
                        return;
                    }
                    else if (!temp->right)///tylko lewy syn
                    {
                        cout << "wchodze w usuwanie z lewym synem";
                        if (key > findParent(temp, root)->key)
                        {
                            findParent(temp, root)->right = temp->left;
                            temp = nullptr;
                            delete temp;
                        }
                        else
                        {
                            findParent(temp, root)->left = temp->left;
                            temp = nullptr;
                            delete temp;
                        }
                        _length--;
                        cout << "usuniety z lewym synem\n";
                        return;
                    }
                    else if (!temp->left)///tylko prawy syn
                    {
                        cout << "wchodze w usuwanie z prawym synem";
                        if (key > findParent(temp, root)->key)
                        {
                            findParent(temp, root)->right = temp->right;
                            temp = nullptr;
                            delete temp;
                        }
                        else
                        {
                            findParent(temp, root)->left = temp->right;
                            temp = nullptr;
                            delete temp;
                        }
                        _length--;
                        cout << "usuniety z prawym synem\n";
                        return;
                    }
                    else /// ma dwoch synow
                    {
                        cout << "wchodze w usuwanie z 2 synami";
                        Node * predecessor = findPredecessor(temp);
                        if (predecessor->left)
                        {
                            findParent(predecessor, root)->right = predecessor->left;
                        }
                        Node *predParent = findParent(predecessor, root);
                        if (predParent->key > predecessor->key)
                        {
                            predParent->left = nullptr;
                        }
                        else
                        {
                            predParent->right = nullptr;
                        }
                        predecessor->right = temp->right;
                        predecessor->left = temp->left;

                        cout << "halko zaraz sprawdzacz rootowy\n";
                        if (temp == root)
                        {
                            cout << "wchodze w usuwanie roota!\n";
                            root = predecessor;
                            temp = nullptr;
                            delete temp;
                            _length--;
                            cout << "usuniety root\n";
                            return;
                        }

                        Node *tempParent = findParent(temp, root);

                        if (key > tempParent->key)
                        {
                            tempParent->right = predecessor;
                        }
                        else
                        {
                            tempParent->left = predecessor;
                        }
                        temp = nullptr;
                        delete temp;
                        _length--;
                        cout << "usuniety z 2 synami\n";
                        return;
                    }
                }
                if (key < temp->key)
                {
                    temp = temp->left;
                }
                else
                {
                    temp = temp->right;
                }
            }
            /// nie usunieto
        }
    }

    void inorder()
    {
        cout << "\nWyswietlanie w trybie inorder:\n";
        inorderSupport(root);
        cout << "\nLiczba elementow: " << _length << "\n";
    }


    int getRoot()
    {
        return root->key;
    }


    void insertXElementsR(int x)
    {
        time_t begin, end;
        double time;
        begin = clock();
        for (int i = 0; i < x; i++)
        {

            insertElement((rand()*rand()) % 100000);
        }

        end = clock();
        time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
        cout << "Udalo sie dodac " << _length << " elementow\n"
            << "Czas: " << time << "ms\n";
    }

    void insertXElementsN(int x)
    {
        clock_t begin, end;
        double time;
        int toInsert = 1;

        begin = clock();
        for (int i = 0; i < x; i++)
        {
            if (i % 2 == 0)
            {
                insertElement((rand()*rand()) % 100000);
            }
            else
            {
                insertElement(toInsert);
                toInsert++;
            }
        }
        end = clock();
        time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
        cout << "Udalo sie dodac " << _length << " elementow\n"
            << "Czas: " << time << " ms\n";

    }

    void findNElements(int n)
    {
        clock_t begin, end;
        double time;
        int found = 0;
        begin = clock();
        for (int i = 0; i < n; i++)
        {
            if (findElement((rand()*rand()) % 100000)) found++;
        }
        end = clock();
        time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
        cout << "Udalo sie odnalezc " << found << " elementow\n"
            << "Czas: " << time << " ms\n";
    }

    void removeXElements(int x)
    {
        int lengthBefore = _length;
        time_t begin, end;
        double time;
        begin = clock();
        for (int i = 0; i < x; i++)
        {
            removeElement((rand()*rand() % 100000));
        }
        end = clock();
        time = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
        cout << "Udalo sie usunac " << lengthBefore - _length << " elementow\n"
            << "Czas: " << time << " ms\n";
    }


};





int main(int argc, char *argv[])
{
    srand(time(nullptr));

    int size = atoi(argv[1]);
    BST drzewo;


    if (strcmp(argv[2], "-r") == 0)
    {
        drzewo.insertXElementsR(size);
    }
    else if (strcmp(argv[2], "-n") == 0)
    {
        drzewo.insertXElementsN(size);
    }
    else
    {
        cout << "Bledny przelacznik";
        return -1;
    }

    drzewo.findNElements(size);
    drzewo.removeXElements(size);
}