/* IntervalTree.java

	Purpose:
		
	Description:
		
	History:
		Oct 23, 2014 10:13:40 AM, Created by henrichen

	Copyright (C) 2014 Potix Corporation. All Rights Reserved.
*/
// Reference: http://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
package org.zkoss.zssex.util;

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

/// An extensible Interval Tree that you can keep payload of type [T] in
/// Interval.
public class IntervalTree<T> extends RBTree<Integer, Integer> {
	private static final long serialVersionUID = -2654053199525380277L;

	private static interface ApplyNode<T> extends Serializable {
		void apply(IntervalNode<T> node);
	}
	
	private static class MyComparator implements Comparator<Integer>, Serializable {
		private static final long serialVersionUID = 326442974529571847L;

		@Override
		public int compare(Integer a, Integer b) {
			return a.intValue() - b.intValue();
		}
	}
	
	private static Comparator<Integer> comparator = new MyComparator();
	
	/// Maximum allowed point for all [Interval]s in this tree
	final int maxLimit;
	
	/// Constructor
	public IntervalTree(int maxLimit) {
		super(comparator);
		this.maxLimit = maxLimit;
	}
	
	@SuppressWarnings("unchecked")
	@Override
	IntervalNode<T> getRoot() {
		return (IntervalNode<T>) root;
	}
	
	/// Insert an [interval] into this tree; return the inserted interval or
	/// the original interval in the tree if the given [interval] is duplicated.
	public Interval<T> insertInterval(Interval<T> interval, Object context) {
		final IntervalContext<T> ictx = new IntervalContext<T>(context, null);
		insert(new IntervalNode<T>(interval), ictx);
		return ictx.original == null ? interval : ictx.original;
	}

	/// Delete interval from the tree per the specified reference [interval];
	/// return the deleted interval in the tree if found.
	public Interval<T> deleteInterval(Interval<T> interval, Object context) {
	  final IntervalContext<T> ictx = new IntervalContext<T>(context, interval);
	  return delete(interval.getLow(), ictx) == null ? null : ictx.original;
	}
	
	/// Search interval from the tree per the specified reference [interval];
	/// return null if not found.
	@SuppressWarnings("unchecked")
	public Interval<T> searchInterval(Interval<T> interval) {
	  RBNode<Integer, Integer> node = search(Integer.valueOf(interval.getLow()));
	  return node == null ? null : ((IntervalNode<T>)node).searchInterval(interval);
	}

	/// Query for all [Interval]s which contains the given key [interval].
	@SuppressWarnings("unchecked")
	public Collection<Interval<T>> contains(final Interval<T> interval) {
		final List<Interval<T>> results = new ArrayList<Interval<T>>();
		_visitContains((IntervalNode<T>)root, interval, new ApplyNode<T>() {
			private static final long serialVersionUID = -495009088711483294L;

			@Override
			public void apply(IntervalNode<T> node) {
				node.contains(interval, results);
			}
		});
		return results;
	}
	
	/// Query for all [Interval]s which are contained by the given key [interval].
	@SuppressWarnings("unchecked")
	public Collection<Interval<T>> contained(final Interval<T> interval) {
		final List<Interval<T>> results = new ArrayList<Interval<T>>();
		_visitContained((IntervalNode<T>)root, interval, new ApplyNode<T>()  {
			private static final long serialVersionUID = 4431159001518937204L;

			@Override
			public void apply(IntervalNode<T> node) {
				node.contained(interval, results);
			}
		});
		return results;
	}
	
	/// Query for all [Interval]s which overlaps the given key [interval].
	@SuppressWarnings("unchecked")
	public Collection<Interval<T>> overlaps(final Interval<T> interval) {
		final List<Interval<T>> results = new ArrayList<Interval<T>>();
		_visitOverlaps((IntervalNode<T>)root, interval, new ApplyNode<T>() {
			private static final long serialVersionUID = -7582337954671821299L;

			@Override
			public void apply(IntervalNode<T> node) {
				node.overlaps(interval, results);
			}
		});
		return results;
	}

	void _visitContains(IntervalNode<T> node, Interval<T> interval, 
		  ApplyNode<T> visitNode) {
	
		// if key interval's high point is to the right of the topHigh point of
		// the node, no way its children can contains the interval because their
		// high point will be ever smaller
		//      ----|     // node's topHigh
		//        ----|   // inteval.high
		if (node == null || node.getValue() < interval.getHigh()) return;
		
		// check left children
		if (node.getLeft() != null) {
			_visitContains((IntervalNode<T>)node.getLeft(), interval, visitNode);
		}
		
		// check right children
		// if key interval's low point is to the left of the low point of the
		// node, no way to match in the node's right child which has even higher
		// low point
		//     |-------   // node's low point
		//   |------      // interval's low point
		if (interval.getLow() > node.getKey() && node.getRight() != null) {
			_visitContains((IntervalNode<T>)node.getRight(), interval, visitNode);
		}
		
		// visit intervals of this node
		visitNode.apply(node);
	}

	void _visitContained(IntervalNode<T> node, Interval<T> interval, 
		  ApplyNode<T> visitNode) {

	    // if key interval's low point is to the right of the topHigh point of
	    // this node, no way to be contained
	    //      ----|      // node's topHigh
	    //           |---  // inteval.low
	    if (node == null || node.getValue() < interval.getLow()) return;
	
	    // if key interval's low point is to the right of this node's low point,
	    // no way can match in the node's left child which has ever lower low
	    // point.
	    //    |-----       // node's low end point
	    //      |------    // interval.low
	    if (node.getKey() > interval.getLow() && node.getLeft() != null) {
	    	_visitContained((IntervalNode<T>)node.getLeft(), interval, visitNode);
	    }
	
	    // check right children
	    // if key interval's high point is to the left of the low point of this
	    // node, no way to match in right child who has even higher start points
	    //          |---   // node's low end point
	    //     ----|       // interval.high
	    if (interval.getHigh() >= node.getKey() && node.getRight() != null) {
	    	_visitContained((IntervalNode<T>)node.getRight(), interval, visitNode);
	    }
	
	    // visit intervals of this node
	    visitNode.apply(node);
	}

	void _visitOverlaps(IntervalNode<T> node, Interval<T> interval,
	    ApplyNode<T> visitNode) {
	
		// if key interval's low point is to the right of the rightmost point of
		// any [Interval]s in this node and its offsprings, no way to match
		// this node, no way to be contained
		//      ----|      // node's topHigh
		//           |---  // inteval.low
		if (node == null || node.getValue() < interval.getLow()) return;
		
		// check left children
		if (node.getLeft() != null) {
			_visitOverlaps((IntervalNode<T>)node.getLeft(), interval, visitNode);
		}
		
		// check right children
		// if key interval's high point is to the left of the low point of this
		// node, no way to match in right child who has even higher start points
		//          |---   // node's low end point
		//     ----|       // interval.high
		if (interval.getHigh() >= node.getKey() && node.getRight() != null) {
			_visitOverlaps((IntervalNode<T>)node.getRight(), interval, visitNode);
		}
		
		// visit intervals of this node
		visitNode.apply(node);
	}

	/// Trying to insert a duplicate node with same key.
	@Override
	@SuppressWarnings("unchecked")
	protected void insertDuplicate(RBNode<Integer, Integer> original, 
			RBNode<Integer, Integer> newone, Object context) {
		
		final IntervalNode<T> org = (IntervalNode<T>) original;
		final IntervalNode<T> none = (IntervalNode<T>) newone;
		for (Interval<T> intv : none.intervals) {
			org.insertInterval(intv, context);
		}
		
		org.updateTopHigh();
	}
	
	/// Trying to insert [child] into [parent] node as left child node.
	@Override
	@SuppressWarnings("unchecked")
	protected void insertLeft(RBNode<Integer, Integer> parent, RBNode<Integer, Integer> child) {
	  // connect nodes
	  super.insertLeft(parent, child);
	
	  // maintain parent's max
	  _updateTopHigh((IntervalNode<T>)parent);
	}
	
	/// Trying to insert [child] into [parent] node as right child node.
	@Override
	@SuppressWarnings("unchecked")
	protected void insertRight(RBNode<Integer, Integer> parent, RBNode<Integer, Integer> child) {
	  // connect nodes
	  super.insertRight(parent, child);
	
	  // maintain parent's max
	  _updateTopHigh((IntervalNode<T>)parent);
	}
	
	/// 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
	@Override
	@SuppressWarnings("unchecked")
	protected void rightJumpUp(RBNode<Integer, Integer> g) {
		final IntervalNode<T> p = (IntervalNode<T>) g.getLeft();
		final IntervalNode<T> n = (IntervalNode<T>) p.getRight();
		super.rightJumpUp(g);
		
		_updateTopHigh(p);
		_updateTopHigh((IntervalNode<T>)g);
		_updateTopHigh(n);
	}
	
	/// 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
	@Override
	@SuppressWarnings("unchecked")
	protected void leftJumpUp(RBNode<Integer, Integer> g) {
	  final IntervalNode<T> p = (IntervalNode<T>) g.getRight();
	  final IntervalNode<T> n = (IntervalNode<T>) p.getLeft();
	  super.leftJumpUp(g);
	
	  _updateTopHigh((IntervalNode<T>) g);
	  _updateTopHigh(p);
	  _updateTopHigh(n);
	}
	
	/// 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
	@Override
	@SuppressWarnings("unchecked")
	protected void rotateRight(RBNode<Integer, Integer> g) {
	  final IntervalNode<T> p = (IntervalNode<T>) g.getLeft();
	  super.rotateRight(g);
	
	  _updateTopHigh((IntervalNode<T>)g);
	  _updateTopHigh(p);
	}
	
	/// 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
	@Override
	@SuppressWarnings("unchecked")
	protected void rotateLeft(RBNode<Integer, Integer> g) {
	  final IntervalNode<T> p = (IntervalNode<T>) g.getRight();
	  super.rotateLeft(g);
	
	  _updateTopHigh((IntervalNode<T>)g);
	  _updateTopHigh(p);
	}
	
	/// Trying to fix up the rest of lineal ancestors from leaf to root
	/// in the tree as a [List] of [Traversal]; Note that lineal is ordered
	/// from root to leaf
	@Override
	@SuppressWarnings("unchecked")
	protected void fixUp(List<Traversal<Integer, Integer>> lineal) {
	  for (int j = lineal.size(); --j >= 0; ) {
	    final Traversal<Integer, Integer> tr = lineal.get(j);
	    if (_updateTopHigh((IntervalNode<T>)tr.node)) break;
	  }
	}
	
	/// 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.
	@Override
	@SuppressWarnings("unchecked")
	protected void replaceNode(RBNode<Integer, Integer> target, RBNode<Integer, Integer> substitute) {
	  target.setKey(substitute.getKey());
	  ((IntervalNode<T>)target).intervals = ((IntervalNode<T>)substitute).intervals;
	
	  _updateTopHigh((IntervalNode<T>)target);
	}
	
	/// Check whether really want to delete the found node with the reference
	/// [interval] passed in from [delete] method.
	@Override
	@SuppressWarnings("unchecked")
	protected boolean canDeleteNode(RBNode<Integer, Integer> n, Object ctx) {
		IntervalContext<T> ictx = (IntervalContext<T>) ctx;
		IntervalNode<T> node = (IntervalNode<T>) n;
		if (ictx != null) {
			final Interval<T> result = node.deleteInterval(ictx.original, ictx.context);
			ictx.original = result;
		}
		// Delete node only if no intervals in the node
		return node.intervals == null || node.intervals.isEmpty();
	}
	
	/// update to top high value of the node; return true if no change
	boolean _updateTopHigh(IntervalNode<T> p) {
		return p.updateTopHigh();
	}
}
