#include <iostream>

using namespace std;

enum Color {BLACK, RED};
bool colorD;

struct Node
{
    int from;
    int to;
    int mx;
    Color color;
    Node *left, *right, *parent;

    // Constructor
    Node(int from , int to)
    {
       this->from = from;
       this->to = to;
       left = right = parent = NULL;
       this->color = RED;
       this->mx = to;
    }
    Node()
    {

    }
};

struct RBT
{
    Node* root;

    RBT()
    {
        root = NULL;
    }

    void insert(int from , int to)
    {
        //cout<<value<<endl;
        Node* pt = new Node(from , to);
        if(root == NULL)
        {
            root = pt;
            root->color = BLACK;
            return;
        }
        bool dir;
        Node* loc = root;
        Node* locP;
        while(loc != NULL)
        {
            locP = loc;

            if(pt->from < loc->from)
            {
                loc = locP->left;
                dir = false;
            }
            else
            {
                loc = locP->right;
                dir = true;
            }
        }
        pt->parent = locP;
        if(dir)
            locP->right = pt;
        else locP->left = pt;

        insertFix(pt);
    }

    void insertFix(Node* x)
    {
        Node* original = x;

        while(x != root && x->parent->color == RED)
        {
            if(x->parent->parent->left == x->parent)
            {
                Node* y = x->parent->parent->right;
                if(y != NULL && y->color == RED)
                {
                    x->parent->color = BLACK;
                    y->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                }
                else
                {
                    if(x->parent->right == x)
                    {
                        x = x->parent;
                        leftRotate(x);
                    }
                    x->parent->color = BLACK;
                    x->parent->parent->color = RED;
                    rightRotate(x->parent->parent);
                }
            }
            else
            {
                Node* y = x->parent->parent->left;
                if(y != NULL && y->color == RED)
                {
                    x->parent->color = BLACK;
                    y->color = BLACK;
                    x->parent->parent->color = RED;
                    x = x->parent->parent;
                }
                else
                {
                    if(x->parent->left == x)
                    {
                        x = x->parent;
                        rightRotate(x);
                    }
                    x->parent->color = BLACK;
                    x->parent->parent->color = RED;
                    leftRotate(x->parent->parent);
                }
            }
        }
        if(x == root)
            x->color = BLACK;

        fixMax(original);
    }

    void leftRotate(Node* x)
    {
        Node* y = x->right;
        int dir = -1;
        if(x != root && x->parent->left == x)
            dir = 0;
        else if(x != root)
            dir = 1;

        x->right = y->left;
        if(y->left != NULL)
            y->left->parent = x;

        if(dir != -1)
        {
            if(dir == 0)
                x->parent->left = y;
            else x->parent->right = y;

            y->parent = x->parent;
        }
        if(x == root)
        {
            y->parent = NULL;
            root = y;
        }

        y->left = x;
        x->parent = y;

        fixMax(x);
    }

    void rightRotate(Node* y)
    {
        Node* x = y->left;
        int dir = -1;
        if(y != root && y->parent->left == y)
            dir = 0;
        else if(y != root)
            dir = 1;

        y->left = x->right;
        if(x->right != NULL)
            x->right->parent = y;

        if(dir != -1)
        {
            if(dir == 0)
                y->parent->left = x;
            else y->parent->right = x;

            x->parent = y->parent;
        }
        if(y == root)
        {
            x->parent = NULL;
            root = x;
        }

        x->right = y;
        y->parent = x;

        fixMax(y);
    }

    void fixMax(Node* x)
    {
        //cout<<x->from<<endl;
        x->mx = x->to;

        if(x->left != NULL)
            x->mx = max(x->mx , x->left->mx);
        if(x->right != NULL)
            x->mx = max(x->mx , x->right->mx);

        if(x != root)
            fixMax(x->parent);
    }

    bool overlaps(Node* x , Node* y)
    {
        if((y->from >= x->from && y->from <= x->to)||
           (y->to <= x->to && y->to >= x->from)||
           (y->from <= x->from && y->to >= x->to))
            return true;
        return false;
    }

    void findOverlap(int from , int to)
    {
        Node* temp = this->root;
        Node* key = new Node(from , to);

        while(temp != NULL)
        {
            if(overlaps(key , temp))
            {
                cout<<"\nOverlaps with [" << temp->from << " , " << temp->to << "]\n";
                return;
            }
            if(temp->left !=NULL && key->from <= temp->left->mx)
                temp = temp->left;
            else
                temp = temp->right;
        }
        cout<<"\nNo Overlaps\n";
    }

    void print()
    {
        cout<<"\nInorder Traversal :\n";
        inorder(root);
        cout<<"\nPreorder Traversal :\n";
        preorder(root);
    }
    void inorder(Node* root)
    {
        if(root == NULL)
            return;
        inorder(root->left);
        cout<<root->from<<" "<<root->to<<endl;
        inorder(root->right);
    }
    void preorder(Node* root)
    {
        if(root == NULL)
            return;
        cout<<root->from<<" "<<root->to<<endl;
        preorder(root->left);
        preorder(root->right);
    }

    void deleteRBT(Node* z)
    {
        Node* y = z;
        Node* x = NULL;
        Color yColor = y->color;
        if (z->left == NULL) {
            x = z->right;
            tranplant(z, z->right);
        } else if (z->right == NULL) {
            x = z->left;
            tranplant(z, z->left);
        } else {
            y = treeMin(z->right);
            yColor  = y->color;
            x = y->right;
            if (x != NULL && y->parent == z)
                x->parent = y;
            else {
                tranplant(y, y->right);
                y->right = z->right;
                if (y->right != NULL)
                    y->right->parent = y;
            }
            tranplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }
        if (yColor == BLACK)
            deleteFix(x);
    }

    void deleteRBT(int from, int to) {
        Node* x = root;
        while (x != NULL) {
            if (x->from == from && x->to == to) {
                deleteRBT(x);
                return;
            }
            if (x->from < from)
                x = x->right;
            else
                x = x->left;
        }
    }

    void deleteFix(Node* x)
    {
        while (x != root && x != NULL && x->color != BLACK) {
            if (x == x->parent->left) {
                Node* w = x->parent->right;
                if (w->color == RED) { // case 1
                    w->color = BLACK;
                    x->parent->color = RED;
                    leftRotate(x->parent);
                    w = x->parent->right;
                }
                if (w->left->color == BLACK &&
                        w->right->color == BLACK) { // case 2
                    w->color = RED;
                    x = x->parent;
                } else if (w->right->color == BLACK) { // case 3
                    w->left->color = BLACK;
                    w->color = RED;
                    rightRotate(w);
                    w = w->parent->right;
                }
                // case 4
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                leftRotate(x->parent);
                x = root;
            } else {
                Node* w = x->parent->left;
                if (w->color == RED) { // case 1
                    w->color = BLACK;
                    x->parent->color = RED;
                    rightRotate(x->parent);
                    w = x->parent->left;
                }
                if (w->left->color == BLACK &&
                        w->right->color == BLACK) { // case 2
                    w->color = RED;
                    x = x->parent;
                } else if (w->left->color == BLACK) { // case 3
                    w->right->color = BLACK;
                    w->color = RED;
                    leftRotate(w);
                    w = w->parent->left;
                }
                // case 4
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rightRotate(x->parent);
                x = root;
            }
        }
        if (x != NULL)
            x->color = BLACK;
    }

    Node* treeMin(Node* node)
    {
        while (node->left != NULL)
            node = node->left;
        return node;
    }

    void tranplant(Node* u, Node* v)
    {
        if (u->parent == NULL)
            root = v;
        else if (u == u->parent->left)
            u->parent->left = v;
        else
            u->parent->right = v;
        if (v != NULL)
            v->parent = u->parent;
    }
};

int main()
{
    RBT x;
    int from , to;

    x.insert(20, 30);
    x.insert(30, 30);
    x.insert(35, 30);
    x.insert(25, 30);
    x.insert(10, 30);

    x.print();
    x.deleteRBT(30, 30);
    x.print();

    // cout<<"Number of Nodes :\n";
    // int n = 0;
    // // cin>>n;
    // cout<<"Intervals :\n";
//
    // for(int i=0; i<n; i++)
    // {
        // //cin>>from>>to;
        // x.insert(from , to);
    // }
//
    // x.print();
//
    // cout<<"Search for Interval :\n";
    // // cin>>from>>to;
    // //x.findOverlap(from , to);
//
    // cout<<"Delete Interval :\n";
//

    return 0;
}