// Copyright 2003 Adam Megacz, see the COPYING file for licensing [GPL]
package org.xwt.util;

// Implemented from http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/red_black.html

// 1. Every node is either red or black.
// 2. Every leaf node is black; if a red node has no right or left child,
//    pretend that an imaginary (sentinel) black node is there.
// 3. If a node is red, then both its children are black.
// 4. Every simple path from a node to a descendant leaf contains the
//    same number of black nodes.


/** a red-black tree of arbitrary objects */
public class RedBlackTree {

    private static final boolean RED = false;
    private static final boolean BLACK = true;

    private static final int DELETE = 0; 
    private static final int INSERT = 1;

    // These arrays are indexed by "slot", a totally meaningless number
    // assigned to each object object[slot] has index index[slot] and
    // color color[slot].  Note that slot 0 is reserved as "null".

    private Object[] objects;    ///< every object in the tree has an entry here; ordering is completely random

    // FEATURE: use a bitmask?
    private boolean[] color;     ///< the color of each object

    private int[] left;          ///< the slot of this object's left child
    private int[] right;         ///< the slot of this object's right child
    private int[] index;         ///< the index of each element; ie how many objects are "before" it in the logical ordering

    private int root = 0;               ///< the slot of the root element


    //    parent             parent
    //      |                  |
    //      b                  d 
    //     / \                / \
    //    a   d    < == >    b   e
    //       / \            / \
    //      c   e          a   c
    void rotate(boolean toTheLeft, int b, int parent) {
        int[] left = toTheLeft ? this.left : this.right;
        int[] right = toTheLeft ? this.right : this.left;
        if (b == 0) throw new Error("rotate called on the null slot");
        int d = right[b];
        if (d == 0) throw new Error("attempted to rotate a node with only one child in the wrong direction");
        int c = left[d];
        left[d] = b;
        right[b] = c;
        if (parent == 0)              root = d;
        else if (left[parent] == b)   left[parent] = d;
        else if (right[parent] == b)  right[parent] = d;
        else throw new Error("rotate called with invalid parent");
    }

    /** seeks to the node specified by slot/idx and performs operation on it */
    private int seek(int slot, int idx, int cur, int operation, int parent, int grandparent, int greatgrandparent) {

        int ret = 0;
        if (index[cur] > idx && left[cur] != 0) {
            ret = seek(slot, idx, left[cur], operation, cur, parent, grandparent);
            if (ret > 0) return ret - 1;

        } else if (index[cur] < idx && right[cur] != 0) {
            ret = seek(slot, idx, right[cur], operation, cur, parent, grandparent);
            if (ret > 0) return ret - 1;

        } else switch(operation) {
            case INSERT: (index[cur] > idx ? left : right)[cur] = slot; break;
            case DELETE: {
                int swap = 0;
                if (right[left[slot]] != 0)         swap = right[left[slot]];
                else if (left[right[slot]] != 0)    swap = left[right[slot]];
                else if (left[slot] != 0)           for(swap = left[slot]; right[swap] != 0;) swap = right[swap];
                else if (right[slot] != 0)          for(swap = right[slot]; left[swap] != 0;) swap = left[swap];
                else swap = slot;
                //swapAndDelete(swap, slot);
            }
        }

        // grandparent cannot be null since root is always BLACK
        if (parent == 0) { color[slot] = BLACK; return Integer.MAX_VALUE; }
        
        switch(operation) {
            // FIXME check for nulls
            // FIXME only move up the tree when explicitly told to do so
            case DELETE: {
                int[] left = slot == this.left[parent] ? this.left : this.right;
                int[] right = slot == this.left[parent] ? this.right : this.left;
                if (color[slot] == RED) { color[slot] = BLACK; return Integer.MAX_VALUE; }
                int sib = right[parent];
                if (color[sib] == RED) {
                    color[sib] = BLACK;
                    color[parent] = RED;
                    rotate(left == this.left, parent, grandparent);
                    parent = grandparent;
                    grandparent = greatgrandparent;
                    greatgrandparent = 0;
                    ret += 1;
                    sib = right[parent];
                }
                if (color[left[sib]] == BLACK && color[right[sib]] == BLACK) { color[sib] = RED; break; }
                if (color[right[sib]] == BLACK) {
                    color[left[sib]] = BLACK;
                    color[sib] = RED;
                    rotate(left != this.left, sib, parent);
                    sib = right[parent];
                }
                color[sib] = color[parent];
                color[parent] = BLACK;
                color[right[sib]] = BLACK;
                rotate(left == this.left, parent, grandparent);
                ret += 1;
                //x = root /* is this right? */;
            }

            case INSERT: {
                if (parent == 0 || color[parent] == BLACK) return Integer.MAX_VALUE;
                int[] left = parent == this.left[grandparent] ? this.left : this.right;
                int[] right = parent == this.left[grandparent] ? this.right : this.left;
                if(color[right[grandparent]] == RED) {
                    color[parent] = BLACK;
                    color[right[grandparent]] = BLACK;
                    color[grandparent] = RED;
                    return 1;
                } else {
                    if (slot == right[parent]) {
                        ret = 1;                                        // skip our parent
                        rotate(left == this.left, slot, parent);        // then make him our child
                        color[slot] = BLACK;                            // same as else block
                        color[grandparent] = RED;                       // same as else block
                        rotate(left == this.left, parent, grandparent); // same as else block
                    } else {
                        color[parent] = BLACK;
                        color[grandparent] = RED;
                        rotate(left != this.left, grandparent, greatgrandparent);
                    }
                }
            }
        }
        return ret;
    }


}