#include <iostream>
#include <stack>
#include <ctime>

using namespace std;

class Node{
public:
    Node(int);
    int key;
    Node* leftChild;
    Node* rightChild;
    char charArray[10];
};

Node::Node(int k){
    this->key = k;
    this->rightChild = nullptr;
    this->leftChild = nullptr;
    string keyString = to_string(k);
    int keyLength = keyString.length();
    for (int i=0;i<keyLength;i++){
        this->charArray[i] = keyString[i];
    }
}

class BinarySearchTree{
    stack<Node*> nodesStack;

public:
    Node* root;
    BinarySearchTree();
    bool insertNode(int);
    void insertNodesBulk(int);
    Node* findNode(int);
    void rotateRight(Node*, Node*, Node*);
    void rotateLeft(Node*, Node*, Node*);
    void display(Node*,int);
    int makeBackbone(Node*);
    void makePerfectTree(int);
    int calculateHeight(Node*);
    bool removeNode(int);
};
int BinarySearchTree::calculateHeight(Node* current) {
    if (current == nullptr)
        return 0;
    else
    {
        int lDepth = calculateHeight(current->leftChild);
        int rDepth = calculateHeight(current->rightChild);

        if (lDepth > rDepth)
            return(lDepth + 1);
        else return(rDepth + 1);
    }
}

void BinarySearchTree::makePerfectTree(int N){
    Node* grandfather = nullptr;
    Node* tmp = root;
    int m = 1;
    while ( m <= N ){
        m = 2 * m + 1;
    }
    m = m / 2;
    for (int i = 0; i < (N-m); i++)
    {
        Node* tmp2 = tmp->rightChild;
        if ( tmp2 != nullptr ){
            rotateLeft(grandfather, tmp, tmp->rightChild);
            grandfather = tmp2;
            tmp = tmp2->rightChild;
        }
    }
    while (m>1){
        m = m/2;
    grandfather = nullptr;
    tmp = root;
        for (int i = 0; i < m; i++)
        {
            Node* tmp2 = tmp->rightChild;
            rotateLeft(grandfather, tmp, tmp->rightChild);
            grandfather = tmp2;
            tmp = tmp2->rightChild;
        }
    }
}
int BinarySearchTree::makeBackbone(Node* root) {
        Node* grandfather = nullptr;
        Node* tmp = root;
        int c =0;
        while (tmp != nullptr)
        {
            c++;
            if ((tmp->leftChild) != nullptr)//UWAGA: zmiana „root’a” obsłużona w rotacji!
            {
                Node* tmp2 = tmp->leftChild;
                rotateRight(grandfather, tmp, tmp->leftChild);
                tmp = tmp2;
                c--;
            }
            else {
                grandfather = tmp;
                tmp = tmp->rightChild;
            }

        }// Złożoność I fazy algorytmu DSW O(N)
        return c;
    }//



void BinarySearchTree::rotateLeft(Node* grandfather, Node* parent, Node* child){
    if(grandfather!=nullptr){
        if(grandfather->rightChild == parent){
            grandfather->rightChild = child;
        }else{
            grandfather->leftChild = child;
        }
    }else {
        root = child;
    }
    Node* tmp = child->leftChild;
    child->leftChild = parent;
    parent->rightChild = tmp;
    return;
}

void BinarySearchTree::rotateRight(Node* grandfather, Node* parent, Node* child){
    if(grandfather!=nullptr){
        if(grandfather->rightChild == parent){
            grandfather->rightChild = child;
        }else{
            grandfather->leftChild = child;
        }
    }else {
        root = child;
    }
    Node* tmp = child->rightChild;
    child->rightChild = parent;
    parent->leftChild = tmp;
    return;
    }


bool BinarySearchTree::removeNode(int k){
    Node* current = this->root;
    if(current == nullptr){
        return false;
    }
    nodesStack.push(current);
    while((current!=nullptr && current->key!=k)){
        if(current->key < k){
                current = current->rightChild;
                }
            else{
                current = current->leftChild;
        }
        nodesStack.push(current);
    }

    if(current == nullptr){
        return false;
    }
    current = nodesStack.top();

    //wezel jest lisciem
    if(current->leftChild == nullptr && current->rightChild == nullptr){
        nodesStack.pop();
        Node* parent = nodesStack.top();
        if(parent->leftChild == current){
            parent->leftChild = nullptr;
        }else{
            parent->rightChild = nullptr;
        }
        delete current;
    }
    //wezel ma dwoch potomkow
    else if(current->leftChild != nullptr && current->rightChild != nullptr){
        Node* nodeToRemove = current;
        current = current->rightChild;
        nodesStack.push(current);
        while(current->leftChild != nullptr){
            current = current->leftChild;
            nodesStack.push(current);
        }
        Node* successor = nodesStack.top();
        nodesStack.pop();
        if(successor->rightChild != nullptr){
            nodesStack.top()->leftChild = successor->rightChild;
        }else{
            nodesStack.top()->leftChild == nullptr;
        }
        successor->leftChild = nodeToRemove->leftChild;
        successor->rightChild = nodeToRemove->rightChild;
        if(nodeToRemove == root){
            root = successor;
        }
        else{
            while(nodesStack.top() != nodeToRemove && !nodesStack.empty()){
                nodesStack.pop();
            }
            nodesStack.pop();
            if(nodesStack.top()->leftChild == nodeToRemove){
                nodesStack.top()->leftChild = successor;
            }else{
                nodesStack.top()->rightChild = successor;
            }
        }
        delete nodeToRemove;
    }
    //wezel ma lewego potomka
    else if(current->leftChild != nullptr && current->rightChild == nullptr){
        nodesStack.pop();
        if(nodesStack.top()->leftChild == current) {
            nodesStack.top()->leftChild = current->leftChild;
        }else{
            nodesStack.top()->rightChild=current->leftChild;
        }

    }
    else if(current->rightChild!=nullptr && current->leftChild == nullptr){
        nodesStack.pop();
        if(nodesStack.top()->leftChild == current){
            nodesStack.top()->leftChild = current->rightChild;
        }else{
            nodesStack.top()->rightChild = current->rightChild;
        }
    }
    while(!nodesStack.empty()){
        nodesStack.pop();
    }
    return true;
}
//zwraca wskaznik na wezel o podanym kluczu. Zwraca wskaznik na nullptr jesli nie znaleziono klucza.
Node* BinarySearchTree::findNode(int k){
    Node* current = this->root;
    nodesStack.push(current);
    while((current!=nullptr && current->key!=k)){
        if(current->key < k)
                current = current->rightChild;
            else
                current = current->leftChild;
        nodesStack.push(current);
    }

    return current;
}

BinarySearchTree::BinarySearchTree(){
    this->root = nullptr;
}
//zwraca true jesli udalo sie wprowadzic wezel do BST
bool BinarySearchTree::insertNode(int k){

    if (this->root == nullptr){
        this->root = new Node(k);
    }
    Node* current = this->root;
    Node* parent = nullptr;
    while(current!=nullptr){
        if(current->key == k)
            return false;
        parent = current;
        if(current->key < k){
            current = current->rightChild;
        }
        else{
            current = current->leftChild;}
    }
    if(parent->key >k){
            parent->leftChild = new Node(k);
    }
    else{
    parent->rightChild = new Node(k);
    }
    return true;
}


void BinarySearchTree::insertNodesBulk(int n){
    int currentInserted = 0;
    while(currentInserted <n-1){
        if(insertNode(((rand() % 20001) - 10000)) == true){
            currentInserted++;
        }
    }
}

int main()
{
    srand(time(NULL));
    clock_t begin, end;
    double time_spent;
    FILE* fp = fopen("inlab04.txt", "r");
    int X1;
    int X2;
    if (fp == NULL)
        return -1;
    fscanf (fp, "%d %d", &X1 ,&X2);
    fclose(fp);
    begin = clock();

    BinarySearchTree* bst = new BinarySearchTree();
    bst->insertNodesBulk(X1);
    cout << bst->calculateHeight(bst->root) << endl;

    int height = bst->makeBackbone(bst->root);
    bst->makePerfectTree(height);

    cout << bst->calculateHeight(bst->root) << endl;
    bst->root = nullptr;
    bst->insertNodesBulk(X2);
    cout << bst->calculateHeight(bst->root) << endl;

    height = bst->makeBackbone(bst->root);
    bst->makePerfectTree(height);

    cout << bst->calculateHeight(bst->root) << endl;
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    cout << endl << to_string(time_spent);
    return 0;
}