////////////////
//  rb_tree.h
//
//  author: Wei Ke
//  file created: 7/14/2002 3:06:41 AM
//  file last modified: 7/25/2002 6:10:33 PM

#ifndef __RB_TREE_H
#define __RB_TREE_H

#pragma pack(push, 4)
////////////////

template<typename T>
struct rb_tree {
    typedef T node_type;
    typedef node_type *p_node_type;
    typedef node_type const *cp_node_type;
    typedef typename node_type::key_type key_type;

    static p_node_type Find(p_node_type Tree, key_type Key);
    static p_node_type Insert(p_node_type Tree, p_node_type Node);
    static p_node_type Delete(p_node_type Tree, p_node_type Node);

private:
    static p_node_type Rotate_left(p_node_type Tree, p_node_type Node) {
        p_node_type R = Get_right(Node), RL = Get_left(R), Pa = Get_parent(Node);
        Set_parent(R, Pa);
        Set_parent(Node, R);
        Set_right(Node, RL);
        Set_left(R, Node);
        Set_parent_ignore_nil(RL, Node);

        if ( Pa ) {
            if ( Get_left(Pa) == Node )
                Set_left(Pa, R);
            else
                Set_right(Pa, R);
            return Tree;
        } else 
            return R;
    }

    static p_node_type Rotate_right(p_node_type Tree, p_node_type Node) {
        p_node_type L = Get_left(Node), LR = Get_right(L), Pa = Get_parent(Node);
        Set_parent(L, Pa);
        Set_parent(Node, L);
        Set_left(Node, LR);
        Set_right(L, Node);
        Set_parent_ignore_nil(LR, Node);

        if ( Pa ) {
            if ( Get_left(Pa) == Node )
                Set_left(Pa, L);
            else
                Set_right(Pa, L);
            return Tree;
        } else 
            return L;
    }

    static p_node_type Tree_succ(p_node_type Node) {
        p_node_type P = Get_right(Node);

        p_node_type L;
        while ( (L = Get_left(P)) )
            P = L;

        return P;
    }

    static p_node_type Delete_fixup(p_node_type Tree, p_node_type Parent, p_node_type Node) {
        p_node_type Pa = Parent, P = Node, Tr = Tree;
        p_node_type Q;

        while ( Pa && Is_black_or_nil_node(P) ) {
            if ( P == Get_left(Pa) ) {
                Q = Get_right(Pa);
                if ( Is_red_node(Q) ) {
                    Set_red_node(Q, false);
                    Set_red_node(Pa, true);
                    Tr = Rotate_left(Tr, Pa);
                    Q = Get_right(Pa);
                }

                if ( Is_black_or_nil_node(Get_left(Q)) && Is_black_or_nil_node(Get_right(Q)) ) {
                    Set_red_node(Q, true);
                    P = Pa;
                    Pa = Get_parent(P);
                } else {
                    if ( Is_black_or_nil_node(Get_right(Q)) ) {
                        Set_red_node(Get_left(Q), false);
                        Set_red_node(Q, true);
                        Tr = Rotate_right(Tr, Q);
                        Q = Get_right(Pa);
                    }
                    Set_red_node(Q, Is_red_node(Pa));
                    Set_red_node(Pa, false);
                    Set_red_node(Get_right(Q), false);
                    Tr = Rotate_left(Tr, Pa);
                    P = Tr;
                    Pa = 0;
                }
            } else {
                Q = Get_left(Pa);
                if ( Is_red_node(Q) ) {
                    Set_red_node(Q, false);
                    Set_red_node(Pa, true);
                    Tr = Rotate_right(Tr, Pa);
                    Q = Get_left(Pa);
                }

                if ( Is_black_or_nil_node(Get_left(Q)) && Is_black_or_nil_node(Get_right(Q)) ) {
                    Set_red_node(Q, true);
                    P = Pa;
                    Pa = Get_parent(P);
                } else {
                    if ( Is_black_or_nil_node(Get_left(Q)) ) {
                        Set_red_node(Get_right(Q), false);
                        Set_red_node(Q, true);
                        Tr = Rotate_left(Tr, Q);
                        Q = Get_left(Pa);
                    }
                    Set_red_node(Q, Is_red_node(Pa));
                    Set_red_node(Pa, false);
                    Set_red_node(Get_left(Q), false);
                    Tr = Rotate_right(Tr, Pa);
                    P = Tr;
                    Pa = 0;
                }
            }
        }
        if ( P )
            Set_red_node(P, false);

        return Tr;
    }

    static int Comp_key_node(key_type Key, cp_node_type Node) {return node_type::Comp_key_node(Key, Node);}
    static int Comp_node_node(cp_node_type Node_1, cp_node_type Node_2) {return node_type::Comp_node_node(Node_1, Node_2);}
    static bool Is_red_node(cp_node_type Node) {return node_type::Is_red_node(Node);}
    static bool Is_black_or_nil_node(cp_node_type Node) {return !Node || !Is_red_node(Node);}
    static void Set_red_node(p_node_type Node, bool Red) {node_type::Set_red_node(Node, Red);}
    static p_node_type Get_left(cp_node_type Node) {return node_type::Get_left(Node);}
    static void Set_left(p_node_type Node, p_node_type Left) {node_type::Set_left(Node, Left);}
    static p_node_type Get_right(cp_node_type Node) {return node_type::Get_right(Node);}
    static void Set_right(p_node_type Node, p_node_type Right) {node_type::Set_right(Node, Right);}
    static p_node_type Get_parent(cp_node_type Node) {return node_type::Get_parent(Node);}
    static void Set_parent(p_node_type Node, p_node_type Parent) {node_type::Set_parent(Node, Parent);}
    static void Set_parent_ignore_nil(p_node_type Node, p_node_type Parent) {if ( Node ) Set_parent(Node, Parent);}
};

template<typename T>
rb_tree<T>::p_node_type rb_tree<T>::Find(rb_tree<T>::p_node_type Tree, rb_tree<T>::key_type Key)
{
    p_node_tree P = Tree;

    while ( P ) {
        int Comp = Comp_key_node(Key, P);
        if ( Comp == 0 )
            break;

        P = ( Comp < 0 )? Get_left(P) : Get_right(P);
    }

    return P;
}

template<typename T>
rb_tree<T>::p_node_type rb_tree<T>::Insert(rb_tree<T>::p_node_type Tree, rb_tree<T>::p_node_type Node)
{
    if ( !Node )
        return Tree;

    Set_left(Node, 0);
    Set_right(Node, 0);

    if ( !Tree ) {
        Set_red_node(Node, false);
        Set_parent(Node, 0);

        return Node;
    }
    
    p_node_type P = Tree, Q;

    do {
        Q = P;
        if ( Comp_node_node(Node, Q) < 0 ) {
            P = Get_left(Q);
            if ( !P )
                Set_left(Q, Node);
        } else {
            P = Get_right(Q);
            if ( !P )
                Set_right(Q, Node);
        }
    } while ( P );

    Set_parent(Node, Q);
    Set_red_node(Node, true);

    P = Node;
    p_node_type Pa, Pa2, Tr = Tree;

    while ( P != Tr && Is_red_node(Pa = Get_parent(P)) ) {
        if ( Pa == Get_left(Pa2 = Get_parent(Pa)) ) {
            Q = Get_right(Pa2);
            if ( !Is_black_or_nil_node(Q) ) {
                Set_red_node(Pa, false);
                Set_red_node(Q, false);
                Set_red_node(Pa2, true);
                P = Pa2;
            } else {
                if ( P == Get_right(Pa) ) {
                    P = Pa;
                    Tr = Rotate_left(Tr, P);
                    Pa = Get_parent(P);
                    Pa2 = Get_parent(Pa);
                }
                Set_red_node(Pa, false);
                Set_red_node(Pa2, true);
                Tr = Rotate_right(Tr, Pa2);
            }
        } else {
            Q = Get_left(Pa2);
            if ( !Is_black_or_nil_node(Q) ) {
                Set_red_node(Pa, false);
                Set_red_node(Q, false);
                Set_red_node(Pa2, true);
                P = Pa2;
            } else {
                if ( P == Get_left(Pa) ) {
                    P = Pa;
                    Tr = Rotate_right(Tr, P);
                    Pa = Get_parent(P);
                    Pa2 = Get_parent(Pa);
                }
                Set_red_node(Pa, false);
                Set_red_node(Pa2, true);
                Tr = Rotate_left(Tr, Pa2);
            }
        }
    }

    Set_red_node(Tr, false);

    return Tr;
}

template<typename T>
rb_tree<T>::p_node_type rb_tree<T>::Delete(rb_tree<T>::p_node_type Tree, rb_tree<T>::p_node_type Node)
{
    if ( !Tree || !Node )
        return Tree;

    p_node_type P, Pa;

    if ( !Get_left(Node) || !Get_right(Node) ) {
        P = Get_right(Node);
        if ( !P )
            P = Get_left(Node);
        Pa = Get_parent(Node);
        Set_parent_ignore_nil(P, Pa);
        if ( Pa ) {
            if ( Node == Get_left(Pa) )
                Set_left(Pa, P);
            else
                Set_right(Pa, P);
            return ( Is_red_node(Node) )? Tree : Delete_fixup(Tree, Pa, P);
        } else
            return ( Is_red_node(Node) )? P : Delete_fixup(P, 0, P);
    }

    p_node_type Q = Tree_succ(Node);
    P = Get_right(Q);
    Pa = Get_parent(Q);
    Set_parent_ignore_nil(P, Pa);

    if ( Q == Get_left(Pa) )
        Set_left(Pa, P);
    else
        Set_right(Pa, P);
    
    p_node_type Pa2 = Get_parent(Node);
    Set_parent(Q, Pa2);
    Set_left(Q, Get_left(Node));
    Set_parent_ignore_nil(Get_left(Node), Q);
    Set_right(Q, Get_right(Node));
    Set_parent_ignore_nil(Get_right(Node), Q);

    bool Red = Is_red_node(Q);
    Set_red_node(Q, Is_red_node(Node));

    if ( Pa == Node )
        Pa = Q;

    if ( Pa2 ) {
        if ( Node == Get_left(Pa2) )
            Set_left(Pa2, Q);
        else
            Set_right(Pa2, Q);
        return ( Red )? Tree : Delete_fixup(Tree, Pa, P);
    } else 
        return ( Red )? Q : Delete_fixup(Q, Pa, P);
}

template<typename T>
struct rb_tree_node {
    typedef T node_type;
    typedef node_type *p_node_type;
    typedef node_type const *cp_node_type;
    
    static p_node_type Get_left(cp_node_type Node) {return static_cast<const rb_tree_node*>(Node)->m_Left;} 
    static void Set_left(p_node_type Node, p_node_type Left) {static_cast<rb_tree_node*>(Node)->m_Left = Left;} 
    static p_node_type Get_right(cp_node_type Node) {return static_cast<const rb_tree_node*>(Node)->m_Right;} 
    static void Set_right(p_node_type Node, p_node_type Right) {static_cast<rb_tree_node*>(Node)->m_Right = Right;} 
    static p_node_type Get_parent(cp_node_type Node) {return static_cast<const rb_tree_node*>(Node)->m_Parent;} 
    static void Set_parent(p_node_type Node, p_node_type Parent) {static_cast<rb_tree_node*>(Node)->m_Parent = Parent;} 
    static bool Is_red_node(cp_node_type Node) {return static_cast<const rb_tree_node*>(Node)->m_Red;} 
    static void Set_red_node(p_node_type Node, bool Red) {static_cast<rb_tree_node*>(Node)->m_Red = Red;} 
private:
    p_node_type m_Left, m_Right, m_Parent;
    bool m_Red;
};

////////////////
#pragma pack(pop)
#endif