package jdsl.tree;

import jdsl.Key;
import jdsl.Decorable;
import jdsl.DecorableKeyManager;
import jdsl.InvalidKeyException;

import jdsl.Position;
import jdsl.InvalidPositionException;

import jdsl.tree.BinaryTree;
import jdsl.tree.Searchable;


public class RedBlackTree implements BinaryTree , 
                                     Searchable ,
                                     DecorableKeyManager {

    final static short BLACK = 0;
    final static short RED   = 1;


    private int KEY_NUM = 0;

    public class RBKey implements Key {
	int key;

	RBKey( ) {
	    this.key = KEY_NUM++;
	}
    }

    public Key requestKey( )
	throws InvalidKeyException {

	return new RBKey( );
    }

    public void returnKey(Key key) 
	throws InvalidKeyException {

	// currently do nothing
    }


    class Node implements Position  ,
                          Decorable {

	InternalNode parent = null;

	short  color        = RED;

	Object element      = null;
	Object container    = null;

	public Object element( ) {
	    return element;
	}

	public Object container( ) {
	    return container;
	}

	
	Object[] comps = new Object[KEY_NUM];

	public final void insertComponent(Key key, Object comp) {
	    try {
		if (comps.length < KEY_NUM) {

		    Object[] tmp = new Object[KEY_NUM];
		    System.arraycopy(comps, 0, tmp, 0, comps.length);
		    comps  = tmp;
		}

		comps[((RBKey) key).key] = comp;
	    }
	    catch (ClassCastException e) {
		throw new InvalidKeyException( );
	    }
	}

	public final Object getComponent(Key key) {
	    try {
		return comps[((RBKey) key).key];
	    }
	    catch (ClassCastException e) {
		throw new InvalidKeyException( );
	    }
	}

	public final Object removeComponent(Key key) {
	    try {
		Object ret = comps[((RBKey) key).key];
		comps[((RBKey) key).key] = null;

		return ret;
	    }
	    catch (ClassCastException e) {
		throw new InvalidKeyException( );
	    }
	}


	Node( ) {
	}
    }

    class InternalNode extends Node {
	
	Node left   = null;
	Node right  = null;

	InternalNode( ) {
	    super( );
	}
    }

    class ExternalNode extends Node {
	ExternalNode( ) {
	    super( );

	    color = BLACK;
	}
    }


    Node root;

    public RedBlackTree( ) {
	root = new ExternalNode( );
    }


    public final boolean isRoot(Position pos) throws
        InvalidPositionException {

	try {
	    return ((Node) pos) == root;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
    }

    public final boolean isInternal(Position pos) throws
	InvalidPositionException {

	try {
	    return ((Node) pos) instanceof InternalNode;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
    }

    public final boolean isExternal(Position pos) throws
	InvalidPositionException {

	try {
	    return ((Node) pos) instanceof ExternalNode;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
    }


    public Position root( ) {
	return root;
    }

    public final Position parent(Position pos) throws
	InvalidPositionException {

	try {
	    return ((Node) pos).parent;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }

    public final Position leftChild(Position pos) throws 
	InvalidPositionException {

	try {
	    return ((InternalNode) pos).left;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }

    public final Position rightChild(Position pos) throws
	InvalidPositionException {

	try {
	    return ((InternalNode) pos).right;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }


    public final Position sibling(Position pos) throws
        InvalidPositionException {

	try {
	    InternalNode parent = ((InternalNode) pos).parent;

	    return (parent.left == pos) ? parent.right : parent.left;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException("sibling( ) called on root");
	}
    }


    public void swap(Position one, Position two) throws
	InvalidPositionException {

	try {
	    Object tmp           = ((Node) one).element;
	    ((Node) one).element = ((Node) two).element;
	    ((Node) two).element = tmp;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException( );
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException("Null Position");
        }
    }

    public Object replace(Position pos, Object item) throws
	InvalidPositionException {

	try {
	    Object ret           = ((Node) pos).element;
	    ((Node) pos).element = item;

	    return ret;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException ( );
	}
    }

    public Position expandExternal(Position pos) throws
	InvalidPositionException {

	try {
	    ExternalNode left = (ExternalNode) pos;
	    InternalNode centr = new InternalNode( );
	    ExternalNode right = new ExternalNode( );

	    centr.parent = left.parent;
	    centr.left   = left;
	    centr.right  = right;

	    left.parent  = centr;
	    right.parent = centr;

	    if (centr.parent != null) {
		if (centr.parent.left == left)
		    centr.parent.left  = centr;
		else
		    centr.parent.right = centr;

		remedyDoubleRed(centr);
	    }
	    else {
		centr.color = BLACK;
		root        = centr;
	    }

	    return centr;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Not an External Node");
	}
    }

    public Object removeAboveExternal(Position pos) throws
	InvalidPositionException {

	try {
	    ExternalNode child = (ExternalNode) pos;
	    InternalNode paren =  child.parent;
	    Node         siblg = (paren.left == child) ? 
		paren.right : 
		paren.left  ;

	    siblg.parent = paren.parent;

	    child.parent = null;

	    paren.parent = null;
	    paren.left   = null;
	    paren.right  = null;

	    if (siblg.parent != null) {
		if (siblg.parent.left == paren)
		    siblg.parent.left  = siblg;
		else
		    siblg.parent.right = siblg;

		if      (paren.color == BLACK && siblg.color == RED  )
		    siblg.color  = BLACK;
		else if (paren.color == BLACK && siblg.color == BLACK)
		    remedyDoubleBlack(siblg);
	    }
	    else {
		siblg.color = BLACK;
		root        = siblg;
	    }

	    return paren.element;
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Not an External Node");
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException(
		"removeAboveExternal( ) called on root" );
	}
    }

    protected InternalNode doubleRotate(InternalNode c_node,
					InternalNode l_node,
					InternalNode r_node,
					InternalNode parent,
					InternalNode child ) {

	r_node.left         = c_node.right;
	r_node.left.parent  = r_node;

	l_node.right        = c_node.left;
	l_node.right.parent = l_node;

	c_node.parent = parent;

	if (c_node.parent != null) {
	    if (c_node.parent.left == child)
		c_node.parent.left  = c_node;
	    else 
		c_node.parent.right = c_node;
	}
	else 
	    root = c_node;

	c_node.left   = l_node;
	l_node.parent = c_node;
	c_node.right  = r_node;
	r_node.parent = c_node;

	return c_node;
    }

    protected InternalNode restructure(InternalNode a) throws
        InvalidPositionException {

	try {
	    InternalNode b = a.parent;
	    InternalNode c = b.parent;

	    if      (c.right == b && b.left  == a) 
		return doubleRotate(a, c, b, c.parent, c);

	    else if (c.left  == b && b.right == a) 
		return doubleRotate(a, b, c, c.parent, c);

	    else {

		if (c.right == b && b.right == a) {
		    c.right        = b.left;
		    b.left.parent  = c;
		    b.left         = c;
		}
		else {
		    c.left         = b.right;
		    b.right.parent = c;
		    b.right        = c;
		}

		b.parent = c.parent;
		c.parent = b;

		if (b.parent != null) {
		    if (b.parent.left == c)
			b.parent.left  = b;
		    else
			b.parent.right = b;
		}
		else 
		    root = b;

		return b;
	    }
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException( );
	}
    }

    protected void remedyDoubleRed(InternalNode pos) throws
	InvalidPositionException {

	try {
	    InternalNode parent = pos.parent;
	    
	    if (parent == root || parent.color == BLACK)
		return;

	    Node siblng = (parent.parent.left == parent) ? 
		parent.parent.right : 
		parent.parent.left  ;

	    if (siblng.color == BLACK) {

		parent = restructure(pos);

		parent.color       = BLACK;
		parent.left.color  = RED;
		parent.right.color = RED;
	    }
	    else {

		parent.color = BLACK;
		siblng.color = BLACK;

		parent = parent.parent;
		if (parent == root)
		    return;

		parent.color = RED;
		remedyDoubleRed(parent);
	    }
	}
	catch (NullPointerException e) {
	    throw new InvalidPositionException
		("Restructure called on root" );
	}
    }

    protected void remedyDoubleBlack(Node node) {

	if (node == root)
	    return;

	InternalNode paren = node.parent;
	InternalNode siblg = (paren.left == node) ?
	    (InternalNode) paren.right :
	    (InternalNode) paren.left  ;

	if (siblg.color == BLACK) {

	    if (siblg.left.color  == BLACK &&
		siblg.right.color == BLACK ) {
		
		siblg.color = RED;
		    
		if (paren.color == RED)
		    paren.color  = BLACK;
		else 
		    remedyDoubleBlack(paren);
		
		return;
	    }

	    InternalNode tmp;
	    
	    if (siblg.left.color  == RED)
		tmp = restructure((InternalNode) siblg.left );
	    else 
		tmp = restructure((InternalNode) siblg.right);

	    tmp.color       = paren.color;
	    tmp.left.color  = BLACK;
	    tmp.right.color = BLACK;
	}
	else {

	    if (paren.right == siblg)
		restructure((InternalNode) siblg.right);
	    else 
		restructure((InternalNode) siblg.left );

	    siblg.color = BLACK;
	    paren.color = RED;

	    remedyDoubleBlack(node);
	}
    }


    public Position findFirst(Comparable key) 
	throws InvalidPositionException {

	Node next = root;
	Node prev = next;

	try {
	    while (true) {
		if (next instanceof ExternalNode)
		    return prev;

		int cmp = key.compareTo((Comparable) next.element);
		
		if (cmp == 0) 
		    prev = next;

		if (cmp  < 0)
		    next = ((InternalNode) next).left;
		else
		    next = ((InternalNode) next).right;
	    }
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Position not comparable" );
	}
    }
    
    public Position findLast(Comparable key)
	throws InvalidPositionException {

	Node next = root;
	Node prev = next;

	try {
	    while (true) {
		if (next instanceof ExternalNode)
		    return prev;

		int cmp = key.compareTo((Comparable) next.element);

		if (cmp == 0) 
		    prev = next;

		if (cmp <= 0)
		    next = ((InternalNode) next).left;
		else
		    next = ((InternalNode) next).right;
	    }
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Position not comparable");
	}
    }

    public Position findExternal(Comparable key) 
	throws InvalidPositionException {

	Node node = root;

	try {
	    while (true) {
		if (node instanceof ExternalNode)
		    return node;

		int cmp = key.compareTo((Comparable) node.element);
		
		if (cmp < 0)
		    node = ((InternalNode) node).left;
		else 
		    node = ((InternalNode) node).right;
	    }
	}
	catch (ClassCastException e) {
	    throw new InvalidPositionException("Position not comparable");
	}
    }
}