#include <iostream>

class CRedBlackTree {
    enum colorType {red, black};
    struct node {
        colorType color;
        int data;
        node* left;
        node* right;
        node* parent;
    };

    /**
     * Strores the adress of root node of tree
     *
     * @type node*
     */
    node* root;

    /**
     * gets sibling of node
     *
     * @param node*
     * @return node* sibling of node n
     */
    node* sibling(node*) const;

    /**
     * get grandparent node of current node
     *
     * @param node*
     * @return node*
     */
    node* grandparent(node*) const;

    /**
     * get uncle node of current node
     *
     * @param node*
     * @return node*
     */
    node* uncle(node*) const;

    /**
     * Right rotate the node
     *
     * @return true | false
     */
    bool rightRotate(node*);

    /**
     * Left rotate the node
     *
     * @return true | false
     */
    bool leftRotate(node*);

    /**
     * Add item into tree but don't correct balance
     *
     * @return void
     */
    node* add(const int);

    /**
     * Change color two node for each
     *
     * @return void
     */
    void changeColor(node*&, node*&);

    /**
     * Print all node of tree
     *
     * @param node* the root node of tree
     */
    friend const void print(const node*);

public:
    /**
     * Constructor of class
     */
    CRedBlackTree();

    /**
     * Destructor of class
     */
    ~CRedBlackTree();

    /**
     * Search exist key in tree
     *
     * @param int
     * @return bool
     */
    bool search(const int);

    /**
     * Insert new node into root tree
     *
     * @return void
     */
    void insert(const int);

    /**
     * Delete node from tree
     *
     * @return void
     */
    void deleteNode(const int);

    /**
     * Free all allocated memory
     *
     * @return void
     */
    void clear();

    /**
     * Print all node
     *
     * @return void
     */
    const node* getRootNode() const;

    /**
     * Test the left and right rotate function
     *
     * @return void
     */
    void testRotate();
};

CRedBlackTree::CRedBlackTree() {
    root = NULL;
}

CRedBlackTree::~CRedBlackTree() {
    clear();
}

bool CRedBlackTree::search(int key) {
    node* temp = root;
    while (NULL != temp) {
        if (key < temp->data) {
            temp = temp->left;
        } else if (key > temp->data) {
            temp = temp->right;
        } else if (key == temp->data) {
            return true;
        }
    }

    return false;
}

CRedBlackTree::node* CRedBlackTree::sibling(node* n) const {
    if (NULL == n->parent || NULL == n) {
        return NULL;
    }
    if (n == n->parent->left) {
        return n->parent->right;
    } else if (n == n->parent->right) {
        return n->parent->left;
    }
}

CRedBlackTree::node* CRedBlackTree::grandparent(node* n) const {
    if (NULL == n->parent || NULL == n) {
        return NULL;
    }

    return n->parent->parent;
}

CRedBlackTree::node* CRedBlackTree::uncle(node* n) const {
    if (NULL == grandparent(n) || NULL == n) return NULL;
    if (grandparent(n)->left == n->parent) {
        return grandparent(n)->right;
    }

    return grandparent(n)->left;
}

bool CRedBlackTree::leftRotate(node* n) {
    node* r = n->right;
    if (NULL == r) {
        return false;
    }
    if (NULL != r->left) {
        r->left->parent = n;
    }
    n->right = r->left;
    r->left = n;
    if (root == n) {
        root = r;
        r->parent = NULL;
        n->parent = r;
    } else {
        node* p = n->parent;
        if (NULL == p) {
            return false;
        }
        if (n == p->right) {
            p->right = r;
        } else if (n == p->left) {
            p->left = r;
        }
        n->parent = r;
        r->parent = p;
    }

    return true;
}

bool CRedBlackTree::rightRotate(node* n) {
    node* l = n->left;
    std::cout<<n<<std::endl;
    if (NULL == l) {
        return false;
    }
    if (NULL != l->right) {
        l->right->parent = n;
    }
    n->left = l->right;
    l->right = n;
    if (root == n) {
        root = l;
        l->parent = NULL;
        n->parent = l;
    } else {
        node* p = n->parent;
        if (NULL == p) {
            return false;
        }
        if (n == p->right) {
            p->right = l;
        } else if (n == p->left) {
            p->left = l;
        }
        n->parent = l;
        l->parent = p;
    }

    return true;
}

void CRedBlackTree::testRotate() {
    node* temp = root;
    node* last;
    while (NULL != temp) {
        last = temp;
        temp = temp->left;
    }
    rightRotate(last);
}

CRedBlackTree::node* CRedBlackTree::add(const int key) {
    node* newNode = new node;
    newNode->data = key;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = NULL;
    newNode->color = red;
    if (NULL == root) {
        root = newNode;
        return newNode;
    }
    node* last;
    node* temp = root;
    while (NULL != temp) {
        if (key < temp->data) {
            last = temp;
            temp = temp->left;
        } else {
            last = temp;
            temp = temp->right;
        }
    }
    newNode->parent = last;
    if (key < last->data) {
        last->left = newNode;
    } else last->right = newNode;

    return newNode;
}

void CRedBlackTree::changeColor(node*& a, node*& b) {
    colorType temp;
    temp = a->color;
    a->color = b->color;
    b->color = temp;
}

void CRedBlackTree::insert(const int key) {
    node* n;
    if (!search(key)) {
        n = this->add(key);
    } else {
        n = root;
        while (key != n->data) {
            if (key > n->data) {
                n = n->right;
            } else {
                n = n->left;
            }
        }
    }

    // case 1: add into root tree
    if (NULL == n->parent) {
        n->color = black;
        return;
    }

    // case 2: color of insert-node is black
    if (black == n->parent->color) {
        return;
    }

    // case 3: color of uncle and parent is red, then we change color to black
    if (NULL != uncle(n) && red == uncle(n)->color) {
        n->parent->color = black;
        uncle(n)->color = black;
        grandparent(n)->color = red;
        if (root == uncle(n)) {
            grandparent(n)->color = black;
            return;
        }

        return insert(grandparent(n)->data);
    }

    // case 4: when insert-node, parent and grandparent are not the same direction
    if (n == n->parent->right && n->parent == grandparent(n)->left) {
        leftRotate(n->parent);
        n = n->left;
        return insert(n->data);
    } else if (n == n->parent->left && n->parent == grandparent(n)->right) {
        rightRotate(n->parent);
        n = n->right;
        return insert(n->data);
    }

    // case 5: when insert-node, parent and grandparent are the same direction
    n->parent->color = black;
    grandparent(n)->color = red;
    if (n == n->parent->left && n->parent == grandparent(n)->left) {
        rightRotate(grandparent(n));
        return insert(n->data);
    } else if (n == n->parent->right && n->parent == grandparent(n)->right) {
        leftRotate(grandparent(n));
        return insert(n->data);
    }
}

void CRedBlackTree::deleteNode(const int key) {
    if (false == search(key)) {
        std::cout<<"Not match key"<<std::endl;
        return;
    }

    node* matchNode = root;
    while (key != matchNode->data) {
        if (matchNode->data < key) {
            matchNode = matchNode->right;
        } else if (matchNode->data > key) {
            matchNode = matchNode->left;
        }
    }

    node* parent = matchNode->parent;

    if (NULL == matchNode->left && NULL == matchNode->right) {
        if (parent->data > key) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
        delete matchNode;
    } else if (NULL == matchNode->left && NULL != matchNode->right) {        
        if (black == matchNode->color) {
            if (red == matchNode->right->color) {
                if (parent->data > matchNode->data) {
                    parent->left = matchNode->right;
                    matchNode->right->parent = parent->left;
                } else {
                    parent->right = matchNode->right;
                    matchNode->right->parent = parent->right;
                }
                matchNode->right->color = black;
                return deleteNode(matchNode->data);
            }
            if (NULL == matchNode) {
                return;
            }
            if (red == sibling(matchNode)->color) {
                matchNode->parent->color = red;
                sibling(matchNode)->color = black;
                if (matchNode == matchNode->parent->left) {
                    leftRotate(matchNode->parent);
                } else {
                    rightRotate(matchNode->parent);
                }
                return deleteNode(matchNode->data);
            }
            if (black == matchNode->parent->color &&
                    black == sibling(matchNode)->color &&
                    black == sibling(matchNode)->left->color &&
                    black == sibling(matchNode)->right->color) {
                sibling(matchNode)->color = red;
                return deleteNode(matchNode->data);
            } else return deleteNode(matchNode->data);
            if (red == matchNode->parent->color &&
                    black == sibling(matchNode)->color &&
                    black == sibling(matchNode)->left->color &&
                    black == sibling(matchNode)->right->color) {
                sibling(matchNode)->color = red;
                matchNode->parent->color = black;
            } else return deleteNode(matchNode->data);
            if (matchNode == matchNode->parent->left &&
                black == sibling(matchNode)->color&&
                red == sibling(matchNode)->left->color &&
                black == sibling(matchNode)->right->color)
            {
                sibling(matchNode)->color = red;
                sibling(matchNode)->left->color = black;
                rightRotate(sibling(matchNode));
                return deleteNode(matchNode->data);
            }
            else if (matchNode == matchNode->parent->right &&
                     black == sibling(matchNode)->color&&
                     red == sibling(matchNode)->right->color &&
                     black == sibling(matchNode)->left->color)
            {
                sibling(matchNode)->color = red;
                sibling(matchNode)->right->color = black;
                leftRotate(sibling(matchNode));
                return deleteNode(matchNode->data);
            }
            sibling(matchNode)->color = matchNode->parent->color;
            matchNode->parent->color = black;
            if (matchNode == matchNode->parent->left) {
                sibling(matchNode)->right->color = black;
                leftRotate(matchNode->parent);
                return deleteNode(matchNode->data);
            } else {
                sibling(matchNode)->left->color = black;
                rightRotate(matchNode->parent);
                return deleteNode(matchNode->data);
            }
        }
        delete matchNode;
    } else if (NULL != matchNode->left && NULL == matchNode->right) {
        if (parent->data > matchNode->data) {
            parent->left = matchNode->left;
            matchNode->left->parent = parent->left;
        } else {
            parent->right = matchNode->left;
            matchNode->left->parent = parent->right;
        }
        delete matchNode;
    }

    // In this case the balance of tree is not changed
    else if (NULL != matchNode->left && NULL != matchNode->right) {
        node* temp = matchNode->left;
        node* parentTemp;
        while (NULL != temp) {
            parentTemp = temp;
            temp = temp->right;
        }
        int saved = parentTemp->data;
        deleteNode(parentTemp->data);
        matchNode->data = saved;
    }
}

const CRedBlackTree::node* CRedBlackTree::getRootNode() const {
    return root;
}

void CRedBlackTree::clear() {
    if (root == NULL) {
        delete root;
        return;
    }
    node* tempLeft = root->left;
    node* tempRight = root->right;
    delete root;
    root = tempLeft;
    clear();
    root = tempRight;
    clear();
}

const void print(const CRedBlackTree::node* root) {
    if (NULL == root) {
        std::cout<<"NIL"<<std::endl;
        return;
    }
    std::cout<<"node: "<<root->data<<" with color: "<<root->color
             <<" parent: "<<(NULL == root->parent ? 0 : root->parent->data)
             <<std::endl;
    print(root->left);
    print(root->right);
}

int main() {
    CRedBlackTree root;
    root.insert(11);
    root.insert(2);
    root.insert(14);
    root.insert(1);
    root.insert(7);
    root.insert(15);
    root.insert(5);
    root.insert(8);
    root.insert(4);
    root.testRotate();
    root.deleteNode(15);
    print(root.getRootNode());

    return 0;
}