/*
 * File:   redblacktree.cpp
 * Author: Pawel Banasiak http://banasiak.net
 * License: BSD
 *
 * Created on 23.11.2008, 15:20
 */

#include <iostream>
#include "redblacktree.h"
#define BLACK nodeElement::black
#define RED nodeElement::red
#define NIL this->nil

template <class param>
redBlackTree<param>::redBlackTree(int (*compare)(const param *, const param *)) {
    try {
        this->compare = compare;
        this->nil = new nodeElement();
        this->nil->color = BLACK;
        this->nil->element = 0;
        this->nil->leftChild = this->nil;
        this->nil->rightChild = this->nil;
        this->top = NIL;
    } catch (...) {
        throw;
    }
}

template <class param>
redBlackTree<param>::~redBlackTree() {
    while (this->top != NIL)
        this->deleteNode2(this->top, false);
    delete this->nil;
}

template <class param>
redBlackTree<param>::nodeElement::~nodeElement() {
    delete this->element;
}

template <class param>
int redBlackTree<param>::insertNode(param node) {
    nodeElement *n, *actualNode;
    param *tmp;
    try {
        tmp = new param;
        *tmp = node;
        n = new nodeElement();
        n->element = tmp;
        n->parent = NIL;
        n->leftChild = NIL;
        n->rightChild = NIL;
        n->color = RED;
        if (this->top == NIL) {
            n->color = BLACK;
            this->top = n;
            return redBlackTree::ok;
        }
        actualNode = this->top;
        int compareResult;
        while (true) {
            compareResult = this->compare(&node, actualNode->element);
            if (compareResult == 0) {
                delete tmp;
                delete n;
                return redBlackTree::alreadyExists;
            } else if (compareResult < 0) {
                if (actualNode->leftChild == NIL) {
                    actualNode->leftChild = n;
                    n->parent = actualNode;
                    break;
                }
                actualNode = actualNode->leftChild;
            } else {
                if (actualNode->rightChild == NIL) {
                    actualNode->rightChild = n;
                    n->parent = actualNode;
                    break;
                }
                actualNode = actualNode->rightChild;
            }
        }
        if (n->parent->color == RED) {
            this->repairAfterInsert(n);
        }
        return redBlackTree::ok;
    } catch (std::bad_alloc) {
        delete tmp;
        delete n;
        return redBlackTree::badAlloc;
    } catch (...) {
        delete tmp;
        delete n;
        return redBlackTree::undefinedError;
    }
}

template <class param>
void redBlackTree<param>::repairAfterInsert(nodeElement *node) {
    nodeElement *tmp;
    while (node->parent->color == RED) {
        if (node->parent == node->parent->parent->leftChild) {
            tmp = node->parent->parent->rightChild;
            if (tmp->color == RED) {
                node->parent->color = BLACK;
                tmp->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->rightChild) {
                    node = node->parent;
                    this->leftRotate(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                this->rightRotate(node->parent->parent);
            }
        } else {
            tmp = node->parent->parent->leftChild;
            if (tmp->color == RED) {
                node->parent->color = BLACK;
                tmp->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            } else {
                if (node == node->parent->leftChild) {
                    node = node->parent;
                    this->rightRotate(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                this->leftRotate(node->parent->parent);
            }
        }
    }
    this->top->color = BLACK;
}

template <class param>
void redBlackTree<param>::leftRotate(nodeElement *node) {
    nodeElement *tmp = node->rightChild;
    node->rightChild = tmp->leftChild;
    tmp->leftChild->parent = node;
    tmp->parent = node->parent;
    if (node->parent == NIL) {
        this->top = tmp;
    } else {
        if (node == node->parent->leftChild)
            node->parent->leftChild = tmp;
        else
            node->parent->rightChild = tmp;
    }
    tmp->leftChild = node;
    node->parent = tmp;
}

template <class param>
void redBlackTree<param>::rightRotate(nodeElement *node) {
    nodeElement *tmp = node->leftChild;
    node->leftChild = tmp->rightChild;
    tmp->rightChild->parent = node;
    tmp->parent = node->parent;
    if (node->parent == NIL) {
        this->top = tmp;
    } else {
        if (node == node->parent->rightChild)
            node->parent->rightChild = tmp;
        else
            node->parent->leftChild = tmp;
    }
    tmp->rightChild = node;
    node->parent = tmp;
}

template <class param>
int redBlackTree<param>::deleteNode(param node) {
    nodeElement *toDelete;
    this->findNodeForDelete(&node, &toDelete);
    return this->deleteNode2(toDelete);
}

template <class param>
int redBlackTree<param>::deleteNode2(nodeElement *toDelete, bool repair = true) {
    nodeElement *successor, *tmp;
    if (toDelete == NIL)
        return redBlackTree::notFound;
    if (toDelete->leftChild == NIL || toDelete->rightChild == NIL) {
        successor = toDelete;
    } else {
        if (toDelete->rightChild != NIL) {
            successor = toDelete->rightChild;
            while (successor->leftChild != NIL)
                successor = successor->leftChild;
        } else {
            successor = toDelete->parent;
            tmp = toDelete;
            while (successor != NIL && successor->rightChild == tmp) {
                tmp = successor;
                successor = successor->parent;
            }
        }
    }
    if (successor->leftChild != NIL)
        tmp = successor->leftChild;
    else
        tmp = successor->rightChild;
    tmp->parent = successor->parent;
    if (successor->parent == NIL) {
        this->top = tmp;
    } else {
        if (successor == successor->parent->leftChild)
            successor->parent->leftChild = tmp;
        else
            successor->parent->rightChild = tmp;
    }
    if (successor != toDelete) {
        delete toDelete->element;
        toDelete->element = successor->element;
        successor->element = 0;
    }
    if (successor->color == BLACK && repair)
        this->repairAfterDelete(tmp);
    delete successor;
    return redBlackTree::ok;
}

template <class param>
void redBlackTree<param>::repairAfterDelete(nodeElement *node) {
    nodeElement *tmp;
    while (node != this->top && node->color == BLACK) {
        if (node == node->parent->leftChild) {
            tmp = node->parent->rightChild;
            if (tmp->color == RED) {
                tmp->color = BLACK;
                node->parent->color = RED;
                this->leftRotate(node->parent);
                tmp = node->parent->rightChild;
            }
            if (tmp->leftChild->color == BLACK && tmp->rightChild->color == BLACK) {
                tmp->color = RED;
                node = node->parent;
            } else {
                if (tmp->rightChild->color == BLACK) {
                    tmp->leftChild->color = BLACK;
                    tmp->color = RED;
                    this->rightRotate(tmp);
                    node->parent = tmp->parent->parent;
                    tmp = node->parent->rightChild;
                }
                tmp->color = node->parent->color;
                node->parent->color = BLACK;
                tmp->rightChild->color = BLACK;
                this->leftRotate(node->parent);
                node = this->top;
            }
        } else {
            tmp = node->parent->leftChild;
            if (tmp->color == RED) {
                tmp->color = BLACK;
                node->parent->color = RED;
                this->rightRotate(node->parent);
                tmp = node->parent->leftChild;
            }
            if (tmp->leftChild->color == BLACK && tmp->rightChild->color == BLACK) {
                tmp->color = RED;
                node = node->parent;
            } else {
                if (tmp->leftChild->color == BLACK) {
                    tmp->rightChild->color = BLACK;
                    tmp->color = RED;
                    this->leftRotate(tmp);
                    node->parent = tmp->parent->parent;
                    tmp = node->parent->leftChild;
                }
                tmp->color = node->parent->color;
                node->parent->color = BLACK;
                tmp->leftChild->color = BLACK;
                this->rightRotate(node->parent);
                node = this->top;
            }
        }
    }
    node->color = BLACK;
}

template <class param>
param *redBlackTree<param>::findNode(param node) {
    int compareResult;
    nodeElement *actualNode = this->top;
    while (true) {
        if (actualNode == NIL)
            return reinterpret_cast<param *> (0);
        compareResult = this->compare(&node, actualNode->element);
        if (compareResult == 0) {
            return actualNode->element;
        } else if (compareResult < 0) {
            actualNode = actualNode->leftChild;
        } else {
            actualNode = actualNode->rightChild;
        }
    }
}

template <class param>
void redBlackTree<param>::findNodeForDelete(param *node, nodeElement **ret) {
    int compareResult;
    nodeElement *actualNode = this->top;
    while (true) {
        if (actualNode == NIL) {
            *ret = NIL;
            return;
        }
        compareResult = this->compare(node, actualNode->element);
        if (compareResult == 0) {
            *ret = actualNode;
            return;
        } else if (compareResult < 0) {
            actualNode = actualNode->leftChild;
        } else {
            actualNode = actualNode->rightChild;
        }
    }
}