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

#ifndef _REDBLACKTREE_H
#define	_REDBLACKTREE_H

template <class param>
class redBlackTree {
public:

    class nodeElement {
    public:

        enum {
            red, black
        } color;
        nodeElement *parent;
        nodeElement *leftChild;
        nodeElement *rightChild;
        param *element;
        virtual ~nodeElement();
    };
public:
    redBlackTree(int (*)(const param *, const param *));
    int insertNode(param);
    int deleteNode(param);
    param *findNode(param);
    virtual ~redBlackTree();
    typedef int status;
    const static int ok = 1;
    const static int alreadyExists = -1001;
    const static int notFound = -1003;
    const static int badAlloc = -1002;
    const static int undefinedError = -1000;
private:
    int (*compare)(const param *, const param *);
    nodeElement *nil;
    nodeElement *top;
    int deleteNode2(nodeElement *, bool);
    void repairAfterInsert(nodeElement *);
    void repairAfterDelete(nodeElement *);
    void findNodeForDelete(param *, nodeElement **);
    void leftRotate(nodeElement *);
    void rightRotate(nodeElement *);
};

#endif	/* _REDBLACKTREE_H */