/* RBTree.java

	Purpose:
		
	Description:
		
	History:
		Oct 22, 2014 2:27:40 PM, Created by henrichen

	Copyright (C) 2014 Potix Corporation. All Rights Reserved.
*/
//Reference: http://en.wikipedia.org/wiki/Red-black_tree 

package org.zkoss.zssex.util;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/// Extensible RBTree where [K] is the type of the key and [V] is the type of
/// the value.
/// 
/// This implementation expose all methods that will change tree structure so
/// you can override them to maintain your tree value consistency:
/// * [insertDuplicate] - when trying to insert a node with same key.
/// * [insertLeft] - insert a node as left child of the parent.
/// * [insertRight] - insert a node as right child of the parent.
/// * [rightJumpUp] - move a right child node of left parent to be as grand 
///   parent.   
/// * [leftJumpUp] - move a left child node of right parent to be as grand 
///   parent.
/// * [rotateRight] - rotate right to make parent as grand parent.
/// * [rotateLeft] - rotate left to make parent as grand parent.
/// * [canDeleteNode] - Checks whether you really want to delete the node with
///   the given key and value.
/// * [replaceNode] - replace the contents of the to be deleted target node 
///   with the contents of the substitute sibling leaf node. 
/// * [fixUp] - fix up the rest of related ancestor nodes from youngest to 
///   oldest as an [Iterable] of [Traversal] after the tree is balanced. 
public class RBTree<K, V> implements Serializable {
	private static final long serialVersionUID = 8257535496613634916L;
	private static final boolean LEFT = true;
	private static final boolean RIGHT = false;
	/*package*/ static final boolean _RED = true;
	private static final boolean _BLACK = false;
	@SuppressWarnings({"rawtypes", "unchecked" })
	private static final Stack _EMPTY_STACK = new Stack<Object>(Collections.EMPTY_LIST);
	
	/// A tree traversal record which contains a RBNode and direction of its next
	/// traversal node.
	static class Traversal<K, V> {

		/*package*/ final RBNode<K, V> node;
		/*package*/ final boolean direction;
	  
		private Traversal(RBNode<K, V> node, boolean direction) {
			this.node = node;
			this.direction = direction;
		}

		@Override
		public String toString() {
		  return ""+ getClass().getName() + "(" + node.getKey() + ") -> " + (direction ? "LEFT" : "RIGHT");
		}
	}
	
	private static class RBNodeResult<K, V> {
		final Stack<Traversal<K,V>> lineal;
		final RBNode<K, V> node;
		RBNodeResult(Stack<Traversal<K, V>> lineal, RBNode<K, V> node) {
			this.lineal = lineal;
			this.node = node;
		};
	}

	private static class Stack<T> {
		final List<T> _inner;
		public Stack(List<T> inner) {
			this._inner = inner;
		}
		  
		/// Pop the last item of this stack; return null if no item.
		T pop() {
			return !_inner.isEmpty() ? _inner.remove(_inner.size() - 1) : null;
		}
		  
//		/// Peek (but not [pop]) the item of the specified [level] of this stack; 
//		/// return null if no item in the specified [level].
//		/// e.g.
//		/// * `peek()` returns the most top item of this stack.
//		/// * `peek(1)` returns the second top item of this stack.
//		T peek(int level) {
//			final int j = _inner.size() - level -1; 
//			return j < 0 ? null : _inner.get(j);
//		}
		  
		/// Push the item to this stack.
		void push(T item) {
			_inner.add(item);
		}
//		  
//		/// Check whether the stack is empty.
//		boolean isNotEmpty() {
//			return !isEmpty();
//		}
//		  
//		/// Check whether the stack is empty.
//		boolean isEmpty() {
//			return _inner.isEmpty();
//		}
		  
		@Override
		public String toString() {
			return _inner.toString();
		}
	}

	/// Constructor with a comparator; default will use `compareTo` method of
	/// Comparable on keys if comparator not provided.
	public RBTree(Comparator<K> comparator) {
		this.comparator = comparator;
	}
  
	/// Root node of this RBTree.
	RBNode<K, V> root;
  
	/// length of this RBTree.
	private int _length = 0;
  
	RBNode<K, V> getRoot() {
		return root;
	}
	
	int size() {
		return _length;
	}
	
	/// Comparator used in this RBTree; default to [_DEFAULT_COMPARATOR].
	final Comparator<K> comparator;
  
	/// Checks whether [node] is a red node; null is deemed as black.
	boolean isRed(RBNode<K, V> node) {
		return node != null && node.getColor() == _RED;
	}

	/// Checks whether this tree has any node.
	public boolean isEmpty() {
		return root == null;
	}

	/// Search a node with the [key].
	public RBNode<K, V> search(K key) {
		RBNode<K, V> x = root;
    
		while (x != null) {
		    final int cmp = comparator.compare(key, x.getKey());
		    if (cmp == 0) return x; //found
		    x = cmp < 0 ? x.getLeft() : x.getRight();
		}
	    
	    return null;
	}
  
	/// Insert a [node]; return the inserted node or the original tree node if 
	/// the [node] is duplicated.
	public RBNode<K, V> insert(RBNode<K, V> node, Object context) {
		final RBNodeResult<K,V> result = _insert0(node, context);
		Stack<Traversal<K,V>> lineal = result.lineal;
		fixUp(lineal._inner);
		return result.node;
	}
  
	/// Delete a node with the [key] and an optional [context]; return the deleted
	/// node or null if not found.
	public RBNode<K, V> delete(K key, Object context) {
		if (key == null) return null;
		RBNodeResult<K,V> result = _delete0(key, context);
		fixUp(result.lineal._inner);
		return result.node;
	}
  
	/// Trying to insert a duplicate node with same key; default operation
	/// assigns the value of the [original] node with the value of the [newone] 
	/// one.
	protected void insertDuplicate(RBNode<K, V> original, RBNode<K, V> newone, Object context) {
		original.setValue(newone.getValue());
	}
  
	/// Trying to insert [child] into [parent] node as left child node.
	protected void insertLeft(RBNode<K, V> parent, RBNode<K, V> child) {
		parent.setLeft(child);
	}
  
	/// Trying to insert [child] into [parent] node as right child node.
	protected void insertRight(RBNode<K, V> parent, RBNode<K, V> child) {
		parent.setRight(child);
	}
 
	/// Trying to jump from right child node to be as grand parent node and return 
	/// it.
	/// >     /            /
	/// >     G            N
	/// >    / \         /   \
	/// >   P   U   =>   P    G
	/// >    \           \   / \
	/// >     N          Nl Nr  U
	/// >    / \
	/// >   Nl Nr
	protected void rightJumpUp(RBNode<K, V> g) {
		final RBNode<K, V> p = g.getLeft();
		final RBNode<K, V> n = p.getRight();
		p.setRight(n.getLeft());
		g.setLeft(n.getRight());
		n.setRight(g);
		n.setLeft(p);
	}
  
	/// Trying to jump from left child node to be as grand parent node and return it.
	/// >     /             /
	/// >     G             N
	/// >    / \          /   \
	/// >   U   P   =>   G     P
	/// >      /        / \   /
	/// >     N        U  Nl Nr
	/// >    / \
	/// >   Nl Nr
	protected void leftJumpUp(RBNode<K, V> g) {
		final RBNode<K, V> p = g.getRight();
		final RBNode<K, V> n = p.getLeft();
		p.setLeft(n.getRight());
		g.setRight(n.getLeft());
		n.setLeft(g);
		n.setRight(p);
	}

	/// Trying to rotate right to make parent node as grand parent node and return
	/// it.
	/// >     /            /
	/// >     G            P
	/// >    / \          / \
	/// >   P   U   =>   N   G
	/// >  / \              / \ 
	/// > N  Pr            Pr  U
	protected void rotateRight(RBNode<K, V> g) {
		final RBNode<K, V> p = g.getLeft();
		g.setLeft(p.getRight());
		p.setRight(g);
	}

	/// Trying to rotate left to make parent node as grand parent node and return
	/// it.
	/// >    /            /
	/// >    G            P
	/// >   / \          / \
	/// >  U   P   =>   G   N
	/// >     / \      / \ 
	/// >    Pl  N    U  Pl
	protected void rotateLeft(RBNode<K, V> g) {
		final RBNode<K, V> p = g.getRight();
		g.setRight(p.getLeft());
		p.setLeft(g);
	}
  
	/// Trying to fix up the rest of lineal ancestors from leaf to root
	/// in the tree as a List of [Traversal]; default to do nothing.
	/// 
	/// Note that [lineal] is ordered from root to leaf
	protected void fixUp(List<Traversal<K, V>> lineal) {
	    // do nothing
	}

	/// Trying to replace the contents of the to be deleted [target] node with the 
	/// contents of its sibling [substitute] leaf node; the substitute node would 
	/// be then the one that really get deleted from tree if required.
	void replaceNode(RBNode<K, V> target, RBNode<K, V> substitute) {
		target.setKey(substitute.getKey());
		target.setValue(substitute.getValue());
	}
  
	/// Check whether really want to delete the found node with the [context] 
	/// passed in from [delete] method; default to true.
	boolean canDeleteNode(RBNode<K, V> node, Object context) {
		return true;
	}
  
	private <T> List<T> newList(T obj) {
		List<T> list = new ArrayList<T>(1);
		list.add(obj);
		return list;
	}
	
	private RBNodeResult<K,V> _insert0(RBNode<K, V> node, Object context) {
		final K key = node.getKey();
		final Stack<Traversal<K, V>> lineal = 
				new Stack<Traversal<K, V>>(new ArrayList<Traversal<K, V>>());
		
		int cmp;
		for (RBNode<K, V> x = root; x != null; ) {
			cmp = comparator.compare(key, x.getKey());
			if (cmp == 0) {
			    insertDuplicate(x, node, context); //found node with same key
			    return new RBNodeResult<K, V>(lineal, x);
			}
			lineal.push(new Traversal<K, V>(x, cmp < 0)); // LEFT == true
			x = cmp < 0 ? x.getLeft() : x.getRight();
		}
		
		//insert the new node
		Traversal<K, V> t = lineal.pop();
		_insertNode(t, node);
		++_length;
		
		//simple case
		if (node == root) {
		  return new RBNodeResult<K, V>(lineal, root);
		}
		  
		RBNode<K, V> p = t.node;
		boolean pd = t.direction;
		while (p != null) {
			// insert case2 (parent is black)
			if (!isRed(p)) {
				return new RBNodeResult<K, V>(lineal, node); 
			}
		  
			// insert case3 
			// (parent is red, uncle is red)
			// (node is left child or right child)
			// >     |           ||            |           ||
			// >     G            G            G            G
			// >   // \\         / \         // \\         / \
			// >   P   U   =>   P   U        U   P   =>   U   P
			// >  ||           ||               ||           ||
			// >   N            N                N            N
			t = lineal.pop();
			final RBNode<K, V> g = t.node; // grandparent
			final boolean gd = t.direction; // grandparent direction
			final RBNode<K, V> u = gd ? g.getRight() : g.getLeft(); // uncle
			if (isRed(u)) {
				p.setColor(_BLACK);
				u.setColor(_BLACK);
				g.setColor(_RED);
				node = g;
					
				// give the grand parent a chance to fix itself
				fixUp(newList(new Traversal<K, V>(g, gd))); 
					
				// prepare parent of next iteration
				t = lineal.pop();
				if (t != null) {
					p = t.node;
					pd = t.direction;
					// give the parent a chance to fix itself
					fixUp(newList(new Traversal<K, V>(p, pd))); 
				} else {
					p = null;
				}
				continue;
			}
		
			// insert case4 + insert case5 
			// (parent is red, uncle is black, parent and node are opsite side children)
			// >     |             |             |             |
			// >     G             N             G             N
			// >   // \         //   \\         / \\        //   \\
			// >   P   U   =>   P     G        U   P   =>   G     P
			// >   \\            \   / \          //       / \   /
			// >    N            Nl Nr  U         N       U  Nl Nr
			// >   / \                           / \
			// >  Nl Nr                         Nl Nr
			if (!pd && gd) { // node is RIGHT child while parent is LEFT child
				g.setColor(_RED);
				node.setColor(_BLACK);
				rightJumpUp(g);
				break;
			} else if (pd && !gd) { // node is LEFT while parent is RIGHT child
				g.setColor(_RED);
				node.setColor(_BLACK);
				leftJumpUp(g);
				break;
			}
		  
			// insert case5
			// (parent is red, uncle is black, parent and node are same side children)
			// >     |            |             |            |
			// >     G            P             G            P
			// >   // \         // \\          / \\        // \\
			// >   P   U   =>   N   G         U   P   =>   G   N
			// > // \              / \           / \\     / \ 
			// > N  Pr            Pr  U         Pl  N    U  Pl
			if (pd) { // node is LEFT child
				p.setColor(_BLACK);
				g.setColor(_RED);
				rotateRight(g);
			} else {
				p.setColor(_BLACK);
				g.setColor(_RED);
				rotateLeft(g);
			}
			node = p;
			break;
		} //while()
		
		_insertNode(lineal.pop(), node);
		
		return new RBNodeResult<K, V>(lineal, node);
	}

	/// Delete a node with the [key].
	@SuppressWarnings("unchecked")
	private RBNodeResult<K,V> _delete0(K key, Object context) {
	    final Stack<Traversal<K, V>> lineal = 
	    		new Stack<Traversal<K, V>>(new ArrayList<Traversal<K, V>>());
	    
	    RBNode<K, V> node = null, node0 = null;
	    for (RBNode<K, V> x = root; x != null; ) {
	    	final int cmp = comparator.compare(key, x.getKey());
	    	if (cmp == 0) { //found the node with same key
	    		// check whether we really want to delete this node 
	    		// per the given key and context
	    		if (!canDeleteNode(x, context)) {
	    			return new RBNodeResult<K, V>(lineal, x);
	    		}
	    		node0 = node = x;
	    		break;
	    	}
	    	lineal.push(new Traversal<K, V>(x, cmp < 0)); // LEFT == true
	    	x = cmp < 0 ? x.getLeft() : x.getRight();
	    }
	    
	    // Not found the node; return
	    if (node == null) {
	    	return new RBNodeResult<K, V>(_EMPTY_STACK, node0);
	    }
	    
	    // try to get the sibling substitute leaf node
	    if (node.getRight() != null) {
	    	lineal.push(new Traversal<K, V>(node, RIGHT));
	    	for (RBNode<K, V> x = node.getRight(); x != null; x = x.getLeft()) {
	    		lineal.push(new Traversal<K, V>(x, LEFT));
	    	}
	    } else {
	    	lineal.push(new Traversal<K, V>(node, LEFT));
	    	for (RBNode<K, V> x = node.getLeft(); x != null; x = x.getRight()) {
	    		lineal.push(new Traversal<K, V>(x, RIGHT));
	    	}
	    }
	
	    Traversal<K, V> t = lineal.pop(); 
	    RBNode<K, V> replace = t == null ? null : t.node; // sibling substitute leaf node
	    if (replace != node) {
	      replaceNode(node, replace);
	      node0 = node = replace;
	    }
	    
	    final RBNode<K, V> c = node.getRight() == null ? node.getLeft() : node.getRight();
	
	    t = lineal.pop(); 
	    _insertNode(t, c);
	    --_length;
	    
	    // simple case
	    if (isRed(node) || isRed(c) || root == c) {
	    	if (c != null) c.setColor(_BLACK);
	    	return new RBNodeResult<K, V>(lineal, node0);
	    }
	    
	    RBNode<K, V> p = t.node;
	    RBNode<K, V> g = null;
	    boolean pd = t.direction;
	    boolean gd = false;  //grand parent and its direction
	    node = c;
	    while (p != null) {
	    	// delete case2
	    	// >   |              |             |            |
	    	// >   P              S             P            S
	    	// >  / \\          // \          // \          / \\
	    	// > N   S   =>    P              S   N    =>      P
	    	// >    / \       / \            / \              / \
	    	// >   Sl        N  Sl             Sr            Sr  N
	      
	    	RBNode<K, V> s = pd ? p.getRight() : p.getLeft();
	    	if (isRed(s)) {
	    		p.setColor(_RED);
	    		s.setColor(_BLACK);
	    		g = s; // remember the grand parent
	    		gd = pd;
	    		if (pd) { // node is LEFT child
	    			rotateLeft(p);
	    			s = p.getRight();
	    		} else {
	    			rotateRight(p);
	    			s = p.getLeft();
	    		}
	    	}
	      
	    	// delete case3
	    	// >   |             |             |             |
	    	// >   P             P             P             P
	    	// >  / \           / \\          / \          // \
	    	// > N   S   =>    N   S         S   N    =>   S   N
	    	// >    / \           / \       / \           / \
	    	// >   Sl Sr         Sl Sr     Sl Sr         Sl  Sr
	    	if (!isRed(p) && !isRed(s) && !isRed(s.getLeft()) && !isRed(s.getRight())) {
	    		s.setColor(_RED);
	    		node = p;
	        
	    		// prepare parent for next iteration
	    		t = lineal.pop();
	    		if (t != null) {
	    			p = t.node; // next parent
	    			pd = t.direction;
	    		} else {
	    			p = null;
	    		}
	    		continue;
	    	}
	
	    	// delete case4
	    	// >  ||             |            ||            |
	    	// >   P             P             P            P
	    	// >  / \           / \\          / \          // \
	    	// > N   S   =>    N   S         S   N    =>   S   N
	    	// >    / \           / \       / \           / \
	    	// >   Sl Sr         Sl Sr     Sl Sr         Sl  Sr
	    	if (isRed(p) && !isRed(s) && !isRed(s.getLeft()) && !isRed(s.getRight())) {
	    		s.setColor(_RED);
	    		p.setColor(_BLACK);
	    		node = p;
	    		break;
	    	}
	      
	    	// either Sl or Sr is Red because both Black case is handled by 
	    	// case2 ~ case4
	      
	    	// delete case5 + delete case6
	    	// >   ^             ^               ^             ^
	    	// >   P             Sl              P             Sr
	    	// >  / \           / \             / \           / \
	    	// > N   S   =>    P   S           S   N    =>   S   P
	    	// >   // \       /     \         / \\          /     \
	    	// >  Sl         N                   Sr                N
	    	if (pd && !isRed(s.getRight())) { // node is LEFT child
	    		s.getLeft().setColor(p.getColor());
	    		p.setColor(_BLACK);
	    		node = s.getLeft();
	    		leftJumpUp(p);
	    		break;
	    	} else if (!pd && !isRed(s.getLeft())) { // node is RIGHT child
	    		s.getRight().setColor(p.getColor());
	    		p.setColor(_BLACK);
	    		node = s.getRight();
	    		rightJumpUp(p);
	    		break;
	    	}
	      
	    	// delete case6
	    	// >   ^             ^              ^            ^
	    	// >   P             S              P            S
	    	// >  / \           / \            / \          / \
	    	// > N   S   =>    P   Sr         S   N    =>  Sl  P
	    	// >     \\       /              //                 \
	    	// >      Sr     N               Sl                  N
	    	s.setColor(p.getColor());
	    	p.setColor(_BLACK);
	    	if (pd) { // node is LEFT child
	    		s.getRight().setColor(_BLACK);
	    		rotateLeft(p);
	    	} else {
	    		s.getLeft().setColor(_BLACK);
	    		rotateRight(p);
	    	}
	    	node = s;
	    	break;
	    } // while()
	    
	    // there is grand parent
	    if (g != null) { 
	    	_insertNode0(g, gd, node);
	    	node = g;
	    }
	    
	    _insertNode(lineal.pop(), node);
	    
	    return new RBNodeResult<K, V>(lineal, node0);
	}

	void _insertNode(Traversal<K, V> t, RBNode<K, V> node) {
		if (t == null) { // no parent
			root = node; // node is root
			if (root != null) root.setColor(_BLACK); // root is always black
		} else {
			_insertNode0(t.node, t.direction, node);
		}
	}
  
	void _insertNode0(RBNode<K, V> p, boolean left, RBNode<K, V> node) {
		if (left) // node is LEFT child
			insertLeft(p, node);
		else
			insertRight(p, node);
	}
}


