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

#include "stdafx.h"
#include <string>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <conio.h>


using namespace std;


struct RBNode {
    RBNode() : left(NULL), right(NULL), up(NULL), color('R'), key(0) {}
    RBNode(int k) : left(NULL), right(NULL), up(NULL), color('R') {
        key = k;
    }
    RBNode *left;
    RBNode *right;
    RBNode *up;
    char color;
    int key;
};

void print(RBNode *root, RBNode *sentinel, ofstream& output) {
    if (root->left != sentinel) {
        print(root->left, sentinel, output);
    }
    output << root->key << " ";
    if (root->right != sentinel) {
        print(root->right, sentinel, output);
    }
}
void printBT(string sp, string sn, RBNode * v, RBNode *sentinel, ofstream &output) {
    string s, cr = "  ", cl = "  ", cp = "  ";
    cr[0] = 'r'; cr[1] = '-';
    cl[0] = 'L'; cl[1] = '-';
    cp[0] = 'I';
    if (v) {
        s = sp;
        if (sn == cr) s[s.length() - 2] = ' ';
        if (v->right != sentinel) printBT(s + cp, cr, v->right, sentinel, output);

        s = s.substr(0, sp.length() - 2);
        output << s << sn << v->key << ":" << v->color << endl;

        s = sp;
        if (sn == cl) s[s.length() - 2] = ' ';
        if (v->left != sentinel)printBT(s + cp, cl, v->left, sentinel, output);
    }
}
void rotateLeft(RBNode **root, RBNode *x) { //rotację wykonujemy na x
    RBNode *y = x->right;
    x->right = y->left;
    if (y->left != (*root)->up) {
        y->left->up = x;
    }
    y->up = x->up;
    if (x->up == (*root)->up) {
        *root = y;
    } else if (x == x->up->left) {
        x->up->left = y;
    } else {
        x->up->right = y;
    }
    y->left = x;
    x->up = y;
}
void rotateRight(RBNode **root, RBNode *x) { //rotację wykonujemy na x
    RBNode *y = x->left;
    x->left = y->right;
    if (y->right != (*root)->up) {
        y->right->up = x;
    }
    y->up = x->up;
    if (x->up == (*root)->up) {
        *root = y;
    } else if (x == x->up->right) {
        x->up->right = y;
    } else {
        x->up->left = y;
    }
    y->right = x;
    x->up = y;
}
void RBInsertFix(RBNode *&root, RBNode *z) { //z to node dodany w RBInsert
    while (z->up->color == 'R') {
        if (z->up == z->up->up->left) {
            RBNode *y = z->up->up->right;
            if (y->color == 'R') {
                z->up->color = 'B';
                y->color = 'B';
                z->up->up->color = 'R';
                z = z->up->up;
            } else if (z == z->up->right) {
                z = z->up;
                rotateLeft(&root, z);
            } else {
                z->up->color = 'B';
                z->up->up->color = 'R';
                rotateRight(&root, z->up->up);

            }
        } else if (z->up == z->up->up->right) {
            RBNode *y = z->up->up->left;
            if (y->color == 'R') {
                z->up->color = 'B';
                y->color = 'B';
                z->up->up->color = 'R';
                z = z->up->up;
            } else if (z == z->up->left) {
                z = z->up;
                rotateRight(&root, z);
            } else {
                z->up->color = 'B';
                z->up->up->color = 'R';
                rotateLeft(&root, z->up->up);
            }
        }
    }
    root->color = 'B';
}
void RBInsert(RBNode *&root, int value) {
    RBNode *newNode = new RBNode(value);
    if (root == NULL) {
        newNode->color = 'B';
        root = newNode;
        root->up = new RBNode();
        root->up->color = 'B';
        root->up->key = 1337;
        root->left = root->up;
        root->right = root->up;
    } else {
        RBNode *y = root->up;
        RBNode *x = root;
        while (x != root->up) {
            y = x;
            if (newNode->key < x->key) {
                x = x->left;
            } else {
                x = x->right;
            }
        }
        newNode->up = y;
        if (y == root->up) {
            root = newNode;
        } else if (newNode->key < y->key) {
            y->left = newNode;
        } else {
            y->right = newNode;
        }
        newNode->left = root->up;
        newNode->right = root->up;
    }
    RBInsertFix(root, newNode);
}
void RBTransplant(RBNode *&root, RBNode *u, RBNode *v) {
    if (u->up == root->up) {
        root = v;
    } else if (u == u->up->left) {
        u->up->left = v;
    } else {
        u->up->right = v;
    }
    v->up = u->up;
}
RBNode *findMin(RBNode *root, RBNode *sentinel) {
    while (root->left != sentinel) {
        root = root->left;
    }
    return root;
}
RBNode *findValue(RBNode *root, int value) {
    RBNode *sentinel = root->up;
    while (true) {
        if (value == root->key) {
            return root;
        } else if (root->right != sentinel && value > root->key) {
            root = root->right;
        } else if (root->left != sentinel && value < root->key) {
            root = root->left;
        } else return NULL;
    }
}
void RBDeleteFix(RBNode *&root, RBNode *x) {
    RBNode *w = new RBNode();
    while (x != root && x->color == 'B') {
        if (x == x->up->left) {
            w = x->up->right;
            if (w->color == 'R') {
                w->color = 'B';
                x->up->color = 'R';
                rotateLeft(&root, x->up);
                w = x->up->right;
            }
            if (w->left->color == 'B' && w->right->color == 'B') {
                w->color = 'R';
                x = x->up;
            } else if (w->right->color == 'B') {
                w->left->color = 'B';
                w->color = 'R';
                rotateRight(&root, w);
                w = x->up->right;
            } else {
                w->color = x->up->color;
                x->up->color = 'B';
                w->right->color = 'R';
                rotateLeft(&root, x->up);
                x = root;
            }
        } else {
            w = x->up->left;
            if (w->color == 'R') {
                w->color = 'B';
                x->up->color = 'R';
                rotateRight(&root, x->up);
                w = x->up->left;
            }
            if (w->right->color == 'B' && w->left->color == 'B') {
                w->color = 'R';
                x = x->up;
            } else if (w->left->color == 'B') {
                w->right->color = 'B';
                w->color = 'R';
                rotateLeft(&root, w);
                w = x->up->left;
            } else {
                w->color = x->up->color;
                x->up->color = 'B';
                w->left->color = 'R';
                rotateRight(&root, x->up);
                x = root;
            }
        }
    }
    x->color = 'B';
}
void RBDelete(RBNode *&root, int value) {
    RBNode *sentinel = root->up;
    RBNode *z = findValue(root, value);
    RBNode *y = z;
    RBNode *x = new RBNode();
    char yOrginalColor = y->color;
    if (z->left == sentinel) {
        x = z->right;
        RBTransplant(root, z, z->right);
    } else if (z->right == sentinel) {
        x = z->left;
        cout << '2' << endl;
        RBTransplant(root, z, z->left);
    } else {
        y = findMin(z->right, sentinel);
        yOrginalColor = y->color;
        x = y->right;
        if (y->up == z) {
            x->up = y;
        } else {
            cout << 5 << endl;
            RBTransplant(root, y, y->right);
            y->right = z->right;
            y->right->up = y;
        }
        RBTransplant(root, z, y);
        y->left = z->left;
        y->left->up = y;
        y->color = z->color;
    }
    if (yOrginalColor == 'B') {
        RBDeleteFix(root, x);
    }
}
int myrandom(int i) { return std::rand() % i; }

int main(int argc, char* argv[]) {
    ofstream output("drzewo.txt");
    RBNode *tree = NULL;
    ifstream input("dane.txt");
    while (!input.eof()) {
        int dana;
        input >> dana;
        if(dana>=0)RBInsert(tree, dana);
    }
    if (argc > 1) {
        string c = argv[1];
        if (c == "help") {
            cout << "MENU:" << endl;
            cout << "1.Utworz nowe drzewo." << endl;
            cout << "2.Dodaj wartosci do drzewa." << endl;
            cout << "3.Usun wartosci z drzewa." << endl;
            _getch();
        } else if (c == "1") {
            ofstream clear("dane.txt");
            ofstream clear1("drzewo.txt");
        } else if (c == "2") {
            ofstream dane("dane.txt", ios::app);
            for (int i = 2; i < argc; i++) {
                RBInsert(tree, atoi(argv[i]));
                dane << atoi(argv[i]) << " ";
                ofstream output("drzewo.txt");
                printBT("", "", tree, tree->up, output);
            }
        } else if (c == "3") {
            for (int i = 2; i < argc; i++) {
                RBDelete(tree, atoi(argv[i]));
                ofstream dane("dane.txt");
                print(tree, tree->up, dane);
                ofstream output("drzewo.txt");
                printBT("", "", tree, tree->up, output);
            }
        }
    } else {
        int a = 0;
        while (a != -1) {
            system("cls");
            ofstream output("drzewo.txt");
            if (tree != NULL) {
                printBT("", "", tree, tree->up, output);
            }
            cout << "Menu: " << endl;
            cout << "1. Dodaj element do drzewa." << endl;
            cout << "2. Usun element z drzewa." << endl;
            cin >> a;
            switch (a) {
            case 1:
                cout << "Podaj wartosc dodawanego elementu: ";
                cin >> a;
                RBInsert(tree, a);
                break;
            case 2:
                cout << "Podaj wartosc usuwanego elementu: ";
                cin >> a;
                RBDelete(tree, a);
                break;
            }

        }
    }

    return 0;
}