/* ParallelIntervals.java

	Purpose:
		
	Description:
		
	History:
		Oct 23, 2014 10:31:04 AM, Created by henrichen

	Copyright (C) 2014 Potix Corporation. All Rights Reserved.
*/

package org.zkoss.zssex.util;

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

/**
 * Collection of Intervals which has the same low end point but different
 * high end point. T is the type of the payload of the included Intervals.
 * 
 * @author henrichen
 *
 */
class ParallelIntervals<T> implements Iterable<Interval<T>>, Serializable {
	private static final long serialVersionUID = -7745165987819212136L;

	@SuppressWarnings("rawtypes")
	private static Comparator<Interval> comparator = 
		new Comparator<Interval>() {
			@Override
			public int compare(Interval a, Interval b) {
				return a.getHigh() - b.getHigh();
			}
		};
			
	/// [Interval]s with high end points ordered from low to high while with same
	/// low end point.
	List<Interval<T>> intervals;
	
	/// Insert an interval; return null if not the same low end point; return
	/// original Interval instance if exist; return the input interval if not
	/// existed.
	IntervalResult<T> insertInterval(Interval<T> interval) {
		if (intervals != null) {
			if (!intervals.isEmpty() && intervals.get(0).getLow() != interval.getLow()) {
				return null;
			}
		} else {
			intervals = new ArrayList<Interval<T>>(1);
		}
		int j = Collections.binarySearch(intervals, interval, comparator); 
		
		if (j < 0) {
			intervals.add(-j-1, interval);
			return new IntervalResult<T>(interval, j);
		} else { // exists
			return new IntervalResult<T>(intervals.get(j), j);
		}
	}
	
	/// search the specified interval; return negative number 
	/// (-(insert point) - 1) if not found; or the index.
	IntervalResult<T> searchInterval(Interval<T> interval) {
		if (intervals != null && !intervals.isEmpty()) {
			final int j = Collections.binarySearch(intervals, interval, comparator);
			if (j >= 0) {
				return new IntervalResult<T>(intervals.get(j), j); 
			}
		}
		return null;
	}
	
	/// delete the specified interval and return it.
	Interval<T> deleteInterval(int index) {
		if (intervals == null || index < 0 || intervals.isEmpty()) {
			return null;
		}
		final Interval<T> intv = intervals.remove(index);
		if (intervals.isEmpty()) {
			intervals = null;
		}
		return intv;
	}
	
	/// Returns the maximum high end point in this collection.
	int getMax() {
		return intervals == null || intervals.isEmpty() ? -1 : intervals.get(intervals.size() - 1).getHigh();
	}
	
	/// Returns the minimum high end point in this collection.
	int getMin() {
		return intervals == null || intervals.isEmpty() ? -1 : intervals.get(0).getHigh();
	}
	/// Returns the low end point of this collection.
	int getLow() {
		return intervals == null || intervals.isEmpty() ? -1 : intervals.get(0).getLow();
	}

	/// Collect [Intervals] in this node that contains the specified [interval].
	void contains(Interval<T> interval, Collection<Interval<T>> results) {
	  if (intervals == null || interval.getHigh() > getMax() || interval.getLow() < getLow()) return;
	
	  // low >= key ...
	  // find those intervals whose high end point is to the right of the
	  // reference interval's high point
	  final int j = Collections.binarySearch(intervals, interval, comparator);
	  for (int k = j < 0 ? -(j + 1) : j, len = intervals.size(); k < len; ++k) {
		  results.add(intervals.get(k));
	  }
	}
	
	/// Collect [Interval]s in this node that overlapped with the specified
	/// [interval].
	void overlaps(Interval<T> interval, Collection<Interval<T>> results) {
		final int l = interval.getLow();
		if (l > getMax() || interval.getHigh() < getLow()) return;
		
		// All intervals of this node are overlapped with the key interval because
		// the key interval's low point is to the left of the node's key(which is the
		// low point of all intervals of this node)
		if (l <= getLow()) {
		  results.addAll(intervals);
		  return;
		}
		
		// low > key ...
		// find those intervals whose high point is to the right of the key
		// interval's low point
		final int j = Collections.binarySearch(intervals, new Interval<T>(l, l, null), comparator);
		for (int k = j < 0 ? -(j + 1) : j, len = intervals.size(); k < len; ++k) {
		  results.add(intervals.get(k));
		}
	}

	/// Collect [Interval] in this node that are contained by the specified
	/// [interval].
	void contained(Interval<T> interval, Collection<Interval<T>> results) {
	  if (interval.getLow() > getLow()) return;
	
	  // low <= key ...
	  // find those intervals whose high point is to the left of the key
	  // interval's high point
	  final int j = Collections.binarySearch(intervals, interval, comparator);
	  final int e = j < 0 ? -(j + 1) : j + 1;
	  for (int k = 0; k < e; ++k) {
	    results.add(intervals.get(k));
	  }
	}
	
	boolean isEmpty() {
		return intervals == null || intervals.isEmpty();
	}

	static class IntervalResult<T> {
		final Interval<T> interval;
		final int index;
		IntervalResult(Interval<T> interval, int index) {
			this.interval = interval;
			this.index = index;
		}
	}


	//--Iterable--//
	@SuppressWarnings("unchecked")
	@Override
	public Iterator<Interval<T>> iterator() {
		return intervals == null ? 
				Collections.EMPTY_LIST.iterator() : intervals.iterator();
	}
}
