// ALGO2 IS1 212B LAB05
// Marcel Iwanicki
// im44337@zut.edu.pl

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <fstream>

namespace util {
    inline int generateRandomInteger(int min, int max) {
        return (std::rand() % (max - min)) + min;
    }

    inline unsigned int max(unsigned int a, unsigned int b) {
        if(a > b)
            return a;
        return b;
    }
}

struct Node {
    int key;
    char key_string[10];

    Node* leftChild;
    Node* rightChild;

    Node(int key) : key(key) {
        leftChild = nullptr;
        rightChild = nullptr;

        std::sprintf(key_string, "%d", key);
    }


    bool isLeaf() {
        return (leftChild == nullptr && rightChild == nullptr);
    }

    bool hasOnlyOneChild() {
        return hasOnlyLeftChild() || hasOnlyRightChild();
    }

    bool hasOnlyLeftChild() {
        return (rightChild == nullptr);
    }

    bool hasOnlyRightChild() {
        return (leftChild == nullptr);
    }

    bool hasTwoChildren() {
        return (leftChild != nullptr && rightChild != nullptr);
    }

    Node* getSmallestNodeInRightSubtree() {
        Node *tmp = this->rightChild;

        while(tmp != nullptr && tmp->leftChild != nullptr) {
            tmp = tmp->leftChild;
        }

        return tmp;
    }

    void assignValues(const Node* node) {
        this->key = node->key;
        std::strcpy(this->key_string, node->key_string);
    }

    friend std::ostream&operator<<(std::ostream& out, const Node* node) {
        std::cout << "Node={key=" << node->key << ", key_string=" << std::string(node->key_string) << "}";
        return out;
    }

};

class BinarySearchTree {
private:
    Node* root;
    unsigned int size;

public:
    BinarySearchTree() {
        std::srand(std::time(nullptr));
        root = nullptr;
        size = 0;
    }

    bool add(int key) {
        Node* node = new Node(key);
        if(root == nullptr) { // nie istnieje korzen
            root = node;
            size++;
            return true;
        } else { // korzen juz istnieje
            Node* tmp = root;
            while(true) {
                if(node->key < tmp->key) {
                    if(tmp->leftChild == nullptr) { // znaleziono miejsce
                        tmp->leftChild = node;
                        size++;

                        return true;
                    }
                    tmp = tmp->leftChild;

                } else if(node->key > tmp->key) {
                    if(tmp->rightChild == nullptr) { // znaleziono miejsce
                        tmp->rightChild = node;
                        size++;

                        return true;
                    }
                    tmp = tmp->rightChild;

                } else {
                    std::cout << "ERROR: w drzewie JUZ znajduje sie wezel o kluczu " << node->key << std::endl;
                    return false;
                }
            }
        }
    }

    void addManyRandom(unsigned int n) {
        for (int i = 0; i < n; ++i) {
            unsigned int key = util::generateRandomInteger(-1000, 1000);
            while(!this->add(key)) {
                key = util::generateRandomInteger(-1000, 1000);
            }
        }
    }

    Node* find(int key) {
        Node* tmp = root;
        while(tmp != nullptr) {
            if(key < tmp->key) {
                tmp = tmp->leftChild;
            } else if(key > tmp->key) {
                tmp = tmp->rightChild;
            } else { //znaleziono wezel
                return tmp;
            }
        }
        return nullptr;
    }

    void show(int key) {
        Node* result = this->find(key);
        if(result == nullptr)
            std::cout << "ERROR: nie znaleziono wezla o kluczu " << key << std::endl;
        else
            std::cout << result << std::endl;
    }

    Node *getParent(int key) {
        if(key == root->key) {
            return nullptr;
        }

        Node* tmp = root;
        while(tmp != nullptr) {
            if((tmp->leftChild != nullptr && tmp->leftChild->key == key)
               || (tmp->rightChild != nullptr && tmp->rightChild->key == key))
                return tmp;

            if(key < tmp->key) {
                tmp = tmp->leftChild;
            } else if(key > tmp->key) {
                tmp = tmp->rightChild;
            }
        }

        return nullptr;
    }

    bool remove(int key) {
        Node* found = this->find(key);
        if(found == nullptr) { // nie znaleziono wezla
            return false;
        }

        Node* parent = this->getParent(key);

        if(found->isLeaf()) {
            removeLeaf(found, parent);
            size--;

            return true;
        }
        else if(found->hasOnlyOneChild()) {
            removeNodeWithOnlyOneChild(found, parent);
            size--;

            return true;
        }
        else if (found->hasTwoChildren()){
            removeNodeWithBothChildren(found, parent);
            size--;

            return true;
        }

        return false;
    }

    void removeLeaf(Node* leaf, Node* parent) {
        if(parent->leftChild == leaf) { // leaf jest lewym dzieckiem
            parent->leftChild = nullptr;
            delete parent->leftChild;
        } else if(parent->rightChild == leaf) { // leaf jest prawym dzieckiem
            parent->rightChild = nullptr;
            delete parent->rightChild;
        }
    }

    void removeNodeWithOnlyOneChild(Node* node, Node* parent) {
        if(node == root) {
            if(root->leftChild != nullptr) {
                root = root->leftChild;
            }
            else if(root->rightChild != nullptr) {
                root = root->rightChild;
            }
        }

        else if(node->hasOnlyLeftChild()) {
            if(parent->leftChild == node) { // node jest lewym dzieckiem
                parent->leftChild = node->leftChild;
                delete node;
            } else if(parent->rightChild == node) {// node jest prawym dzieckiem
                parent->rightChild = node->leftChild;
                delete node;
            }

        } else if(node->hasOnlyRightChild()) {
            if (parent->leftChild == node) { // node jest lewym dzieckiem
                parent->leftChild = node->rightChild;
                delete node;
            } else if (parent->rightChild == node) {// node jest prawym dzieckiem
                parent->rightChild = node->rightChild;
                delete node;
            }
        }
    }

    void removeNodeWithBothChildren(Node* node, Node* parent) {
        Node* smallestNodeInRightSubtree = node->getSmallestNodeInRightSubtree();
        Node* smallestNodeInRightSubtree_parent = getParent(smallestNodeInRightSubtree->key);

        node->assignValues(smallestNodeInRightSubtree);

        if(smallestNodeInRightSubtree->isLeaf()) {
            removeLeaf(smallestNodeInRightSubtree, smallestNodeInRightSubtree_parent);
        }
        else if(smallestNodeInRightSubtree->hasOnlyOneChild()) {
            removeNodeWithOnlyOneChild(smallestNodeInRightSubtree, smallestNodeInRightSubtree_parent);
        }
    }

    enum class DfsType {
        PRE_ORDER,
        IN_ORDER,
        POST_ORDER,
    };

    void dfs(DfsType type) {
        switch (type) {
            case DfsType::PRE_ORDER:
                std::cout << "\n===: PreOrder Depth First Search :===" << std::endl;
                dfsPreOrder(root);
                break;
            case DfsType::IN_ORDER:
                std::cout << "\n===: InOrder Depth First Search :===" << std::endl;
                dfsInOrder(root);
                break;
            case DfsType::POST_ORDER:
                std::cout << "\n===: PostOrder Depth First Search :===" << std::endl;
                dfsPostOrder(root);
                break;
            default:
                std::cout << "NIEPOPRAWNY WYBOR DFS" << std::endl;
                break;
        }
    }

    void makeBackbone() {
        Node* parentTmp = root;
        Node* grandFather = nullptr;

        while(parentTmp != nullptr) {
            if(parentTmp->leftChild == nullptr) {
                Node* grandFather = parentTmp;
                parentTmp = parentTmp->rightChild;
            } else {
                Node * childTmp = parentTmp->leftChild;
                rotateRight(childTmp, parentTmp, grandFather);
                parentTmp = childTmp;
            }
        }
    }

    void performDsw() {

        Node* childTmp = nullptr;
        Node* parentTmp = root;
        Node* grandParentTmp = nullptr;

        unsigned int treeSize = getSize();
        unsigned int k = 1;
        while(k <= treeSize)
            k = 2*k+1;
        k = k / 2;

        for (int i = 0; i < (treeSize - k); ++i) {

            childTmp = parentTmp->rightChild;
            if(childTmp != nullptr) {
                rotateLeft(parentTmp->rightChild, parentTmp, grandParentTmp);
                grandParentTmp = childTmp;
                parentTmp = childTmp->rightChild;
            }
        }

        while (k > 1) {
            k = k / 2;
            grandParentTmp = nullptr;
            parentTmp = root;
            for (int i = 0; i < k; ++i) {

                childTmp = parentTmp->rightChild;
                rotateLeft(parentTmp->rightChild, parentTmp, grandParentTmp);
                grandParentTmp = childTmp;
                parentTmp = childTmp->rightChild;
            }
        }
    }

    unsigned int getHeight(Node* current) {
        if(current == nullptr) { // root jest nullem
            return 0;
        }

        unsigned int leftHeight = getHeight(current->leftChild);
        unsigned int rightHeight = getHeight(current->rightChild);
        return (util::max(leftHeight, rightHeight) + 1);
    }

    unsigned int getHeight() {
        return getHeight(root);
    }

    unsigned int getSize() const {
        return size;
    }

private:
    void dfsPreOrder(Node* start) {
        if(start == nullptr)
            return;

        std::cout << start << std::endl;
        dfsPreOrder(start->leftChild);
        dfsPreOrder(start->rightChild);
    }


    void dfsInOrder(Node* start) {
        if(start == nullptr)
            return;

        dfsInOrder(start->leftChild);
        std::cout << start << std::endl;
        dfsInOrder(start->rightChild);
    }

    void dfsPostOrder(Node* start) {
        if(start == nullptr)
            return;

        dfsPostOrder(start->leftChild);
        dfsPostOrder(start->rightChild);
        std::cout << start << std::endl;
    }

    void rotateLeft(Node* child, Node* parent, Node* grandParent) {

        if (grandParent != nullptr) {
            if (grandParent->rightChild == parent)
                grandParent->rightChild = child;
            else if (grandParent->leftChild == parent)
                grandParent->leftChild = child;
        } else {
            root = child;
        }

        Node *tmp = child->leftChild;
        child->leftChild = parent;
        parent->rightChild = tmp;

    }

    void rotateRight(Node* child, Node* parent, Node* grandParent) {

        if (grandParent != nullptr) {

            if (grandParent->rightChild == parent)
                grandParent->rightChild = child;
            else if (grandParent->leftChild == parent)
                grandParent->leftChild = child;

        } else {
            root = child;
        }

        Node *tmp = child->rightChild;
        child->rightChild = parent;
        parent->leftChild = tmp;

    }
};

struct FileStructure {
    unsigned int X1;
    unsigned int X2;
};

FileStructure readFile(const std::string& path);

int main() {
    FileStructure fileStructure = readFile("inlab05.txt");
    BinarySearchTree tree;

    tree.addManyRandom(fileStructure.X1);
    std::cout << tree.getHeight() << std::endl;
    tree.makeBackbone();
    tree.performDsw();
    std::cout << tree.getHeight() << std::endl;
//    tree.removeAll();
}

FileStructure readFile(const std::string& path) {
    FileStructure fileStructure;
    std::fstream file;
    file.open(path);

    if(file.good()) {
        file >> fileStructure.X1;
        file >> fileStructure.X2;
    }

    return fileStructure;
}