// lab3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <iomanip>

using namespace std;

struct Node
{
    int value;
    Node *left, *right;
} root;

Node *Create(int value);
void Add(int value, Node *root);
void Scan_preorder(Node *root);
void Scan_inorder(Node *root);
void Scan_postorder(Node *root);
void Print(Node *root);
Node *Find(int value, Node *root);
Node *Min(Node *root);
Node *Parent(Node *root, Node *son);
void Remove(int value, Node *&root);
void Free(Node *&root);
Node *DSW_1(Node *&root);
Node *DSW_2(Node *&root);
void rot_left(Node *&root, Node *to_rot);
void rot_right(Node *&root, Node *to_rot);
int Log2(int x);
unsigned int Depth(Node *root);
void Queue(int * queue, Node * root, int index);
void Draw(Node * root, int block_width);

int main()
{
    int x = 1, value_to_delete, value_to_add, value_to_find;
    Node *root = 0, *value_found;

    while (x)
    {
        cout << "--------========= MENU =========----------" << endl;
        cout << "Wcisnij:" << endl;
        cout << "\t1 - aby stworzyc drzewo" << endl;
        cout << "\t2 - aby dodac wezel do drzewa" << endl;
        cout << "\t3 - aby usunac wezel z drzewa" << endl;
        cout << "\t4 - aby wypisac drzewo" << endl;
        cout << "\t5 - aby znalezc element drzewa" << endl;
        cout << "\t6 - aby zwolnic cala pamiec" << endl;
        cout << "\t7 - aby zrownowazyc drzewo algorytmen DSW - faza 1" << endl;
        cout << "\t8 - aby zrownowazyc drzewo algorytmen DSW - faza 2" << endl;
        cout << "\t0 - aby wyjsc" << endl << endl;
        cin >> x;
        cout << endl << endl;

        switch (x)
        {
        case 1:
        {
            cout << "Podaj wartosc korzenia drzewa:" << endl;
            cin >> value_to_add;

            root = Create(value_to_add);
            break;
        }
        case 2:
        {
            cout << "Podaj wartosc do dodania:" << endl;
            cin >> value_to_add;
            Add(value_to_add, root);
            break;
        }
        case 3:
        {
            cout << "Podaj wartosc do usuniecia:" << endl;
            cin >> value_to_delete;

            Remove(value_to_delete, root);
            break;
        }
        case 4:
        {
            Print(root);
            break;
        }
        case 5:
        {
            cout << "Podaj wartosc do znalezienia:" << endl;
            cin >> value_to_find;

            value_found = Find(value_to_find, root);

            if (!value_found)
                cout << "Nie ma wezla o podanej wartosci" << endl;
            else
                cout << "Znaleziono wezel o wartsci " << value_found->value << endl;
            break;
        }
        case 6:
        {
            Free(root);
            break;
        }
        case 7:
        {
            root = DSW_1(root);
            break;
        }
        case 8:
        {
            root = DSW_2(root);
            break;
        }
        case 0:
        default:
            break;
        }
    }

    return 0;
}

Node *Create(int value)
{
    Node *new_node = new Node;

    new_node->value = value;
    new_node->left = NULL;
    new_node->right = NULL;

    return new_node;
}

void Add(int value, Node *root)
{
    Node *p = root;

    if (p->value == value)
    {
        cout << "Wezel o podanej wartosci juz istnieje" << endl;
        return;
    }

    if (!p)
        Create(value);
    else if (value < p->value)
    {
        if (p->left != NULL)
            Add(value, p->left);
        else
            p->left = Create(value);
    }
    else
    {
        if (p->right != NULL)
            Add(value, p->right);
        else
            p->right = Create(value);
    }
}

void Scan_preorder(Node *root)
{
    if (root != NULL)
    {
        cout << root->value << " ";
        Scan_preorder(root->left);
        Scan_preorder(root->right);
    }
}

void Scan_inorder(Node *root)
{
    if (root != NULL)
    {
        Scan_inorder(root->left);
        cout << root->value << " ";
        Scan_inorder(root->right);
    }
}

void Scan_postorder(Node *root)
{
    if (root != NULL)
    {
        Scan_postorder(root->left);
        Scan_postorder(root->right);
        cout << root->value << " ";
    }
}

void Print(Node *root)
{
    int x = 1;

    if (!root)
    {
        cout << "Drzewo jest puste" << endl;
        return;
    }

    while (x)
    {
        cout << endl << "W jakiej kolejnosci wyswietlic drzewo?" << endl;
        cout << "1 - preorder" << endl;
        cout << "2 - inorder" << endl;
        cout << "3 - postorder" << endl;
        cout << "4 - rysuj" << endl;
        cout << "0 - wyjscie" << endl;
        cin >> x;

        switch (x)
        {
        case 1:
        {
            Scan_preorder(root);
            cout << endl;
            break;
        }
        case 2:
        {
            Scan_inorder(root);
            cout << endl;
            break;
        }
        case 3:
        {
            Scan_postorder(root);
            cout << endl;
            break;
        }
        case 4:
        {
            Draw(root, 3);
            break;
        }
        case 0:
        default:
            break;
        }
    }
}

Node *Find(int value, Node *root)
{
    if (!root || root->value == value)
        return root;
    if (value < root->value)
        return Find(value, root->left);
    else if (value > root->value)
        return Find(value, root->right);
}

Node *Min(Node *root)
{
    while (root->left)
        root = root->left;
    return root;
}

Node *Parent(Node *root, Node *son)
{
    Node *p = NULL;

    while (root != son)
    {
        p = root;
        if (son->value < root->value)
            root = root->left;
        else
            root = root->right;
    }
    return p;
}

void Remove(int value, Node *&root)
{
    Node *p = root, *parent, *to_delete, *pred, *temp = 0;
    bool check = false;

    to_delete = Find(value, root);

    if (to_delete)
    {
        parent = Parent(p, to_delete);
        if ((to_delete->left == NULL && to_delete->right != NULL) || (to_delete->left != NULL && to_delete->right == NULL)) //jedno dziecko - lewe lub prawe
        {
            if (to_delete->left == NULL && to_delete->right) //prawe dziecko
            {
                if (parent)
                {
                    if (parent->left == to_delete)  //lewy syn rodzica
                    {
                        parent->left = to_delete->right;
                        delete to_delete;
                    }
                    else    //prawy syn rodzica
                    {
                        parent->right = to_delete->right;
                        delete to_delete;
                    }
                }
                else // korzen z prawym synem
                {
                    root = to_delete->right;
                    delete to_delete;
                }
            }
            else //lewe dziecko
            {
                if (parent)
                {

                    if (parent->left == to_delete)  //lewy syn rodzica
                    {
                        parent->left = to_delete->left;
                        delete to_delete;
                    }
                    else    //prawy syn rodzica
                    {
                        parent->right = to_delete->left;
                        delete to_delete;
                    }
                }
                else // korzen z lewym synem
                {
                    root = to_delete->left;
                    delete to_delete;
                }
            }
            return;
        }

        if (to_delete->left == NULL && to_delete->right == NULL) //lisc
        {
            parent = Parent(p, to_delete);

            if (!parent) //sam korzeń
            {
                delete to_delete;
                root = NULL;
                return;
            }

            if (parent->left == to_delete)
                parent->left = NULL;
            else
                parent->right = NULL;

            delete to_delete;
            return;
        }

        if (to_delete->left && to_delete->right)
        {
            pred = to_delete->left;

            while (pred->right != NULL)
            {
                check = true;
                temp = pred;
                pred = pred->right;
            }

            to_delete->value = pred->value;

            if (check)
                temp->right = NULL;
            else
                to_delete->left = pred->left;
            delete pred;

            return;
        }
    }
    else
    {
        cout << "Brak podanego elementu" << endl;
        return;
    }

}

void Free(Node *&root)
{
    if (root)
    {
        Free(root->left);
        Free(root->right);

        delete root;

        root = NULL;
    }
}

int n;  // globalny licznik wierszy

Node *DSW_1(Node *&root)
{
    Node *p;

    n = 0;
    p = root;

    while (p)
    {
        if (p->left)
        {
            rot_right(root, p);
            p = Parent(root, p);
        }
        else
        {
            n++;
            p = p->right;
        }
    }

    return root;
}

Node *DSW_2(Node *&root)
{
    Node *p = root, *parent;
    int licznik, i;

    licznik = n + 1 - Log2(n + 1); // liczba lisci na najnizszym poziomie

    for (i = 0; i < licznik; i++)
    {
        rot_left(root, p);
        parent = Parent(root, p);
        p = parent->right;
    }

    n -= licznik;

    while (n > 1)
    {
        n >>= 1;
        p = root;

        for (i = 0; i < n; i++)
        {
            rot_left(root, p);
            parent = Parent(root, p);
            p = parent->right;
        }
    }
    return root;
}

void rot_left(Node *&root, Node *to_rot)
{
    Node *p, *parent;

    p = to_rot->right;

    if (!p)
        return;

    parent = Parent(root, to_rot);
    to_rot->right = p->left;
    p->left = to_rot;

    if (!parent)
    {
        root = p;
        return;
    }

    if (parent->left == to_rot)
        parent->left = p;
    else
        parent->right = p;
}

void rot_right(Node *&root, Node *to_rot)
{
    Node *p, *parent;

    p = to_rot->left;

    if (!p)
        return;

    parent = Parent(root, to_rot);
    to_rot->left = p->right;
    p->right = to_rot;

    if (!parent)
    {
        root = p;
        return;
    }

    if (parent->left == to_rot)
        parent->left = p;
    else
        parent->right = p;
}

int Log2(int x)
{
    int y = 1;

    while ((x >>= 1) > 0)
        y <<= 1;

    return y;
}

unsigned int Depth(Node *root)
{
    if (!root)
        return 0;

    unsigned int left_depth = Depth(root->left);
    unsigned int right_depth = Depth(root->right);

    return (left_depth > right_depth) ? left_depth + 1 : right_depth + 1;
}

void Queue(int * queue, Node * root, int index)
{
    if (!root)
        return;

    if (index == 0)
        queue[0] = root->value;

    if (root->left)
    {
        queue[2 * index + 1] = root->left->value;
        Queue(queue, root->left, 2 * index + 1);
    }
    if (root->right)
    {
        queue[2 * index + 2] = root->right->value;
        Queue(queue, root->right, 2 * index + 2);
    }
}

void Draw(Node * root, int block_width)
{
    int depth = Depth(root);
    int max_blocks = pow(2, depth - 1);
    int blocks_count = 0;
    for (int i = 0; i < depth; ++i)
    {
        blocks_count += pow(2, i);
    }

    int * queue = new int[blocks_count];
    for (int i = 0; i < blocks_count; queue[i++] = -1);
    Queue(queue, root, 0);

    int width = max_blocks * block_width;
    int begin = 0;
    for (int i = 0; i < depth; ++i)
    {
        int current_width = width / pow(2, i);
        for (int j = begin; j < begin + pow(2, i); ++j)
        {
            if (j == begin)
                cout << setw(current_width / 2);
            else
                cout << setw(current_width);

            if (queue[j] != -1)
                cout << queue[j];
            else
                cout << " ";
        }
        begin += pow(2, i);
        cout << "\n";
    }
}