/* IntervalTreeTest.jaLACKvante

	Purpose:
		
	Description:
		
	History:
		Oct 23, 2014 2:50:25 PM, Created by henrichen

	Copyright (C) 2014 Potix Corporation. All Rights Reserved.
*/
package org.zkoss.zssex.util;

import static org.junit.Assert.*;

import org.junit.After;
import org.junit.Before;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Date;
import java.util.Collection;
import java.util.Set;

public class IntervalTreeTest {
	private static final boolean RED = true;
	private static final boolean BLACK = false;
	// how many intervals
	private static final int MAX_KEY = 10000;
	// maxium high end point
	private static final int MAX_END_POINT = 10000;
	// number of test sample intervals for overlapping test
	private static final int NUM_SAMPLES = 10000;
	
	IntervalTree tree;
	Random random;
	IntervalSamples samples;

	@Before
	public void setUp() throws Exception {
		tree = new IntervalTree(MAX_END_POINT);
		random = new Random(new Date().getTime());
		samples = randomIntervals(MAX_KEY);
	}

	@After
	public void tearDown() throws Exception {
		tree = null;
	}

	@Test
	public void testInsertIntervals() {
		testInsert(tree);
	}
	
	@Test
	public void testDeleteIntervals() {
		Set<Interval> intervals = new HashSet<Interval>(samples.intervals);
		final boolean testIntegrity = false;
		constructTree(tree, intervals, testIntegrity);
		testDelete(tree, intervals);
	}
	
	@Test
	public void testOverlapsIntervals() {
		Set<Interval> intervals = new HashSet<Interval>(samples.intervals);
		final boolean testIntegrity = false;
		constructTree(tree, intervals, testIntegrity);
		testOverlaps(tree, intervals);
	}
	
	@Test
	public void testContainsIntervals() {
		Set<Interval> intervals = new HashSet<Interval>(samples.intervals);
		final boolean testIntegrity = false;
		constructTree(tree, intervals, testIntegrity);
		testContains(tree, intervals);
	}
	
	@Test
	public void testContainedIntervals() {
		Set<Interval> intervals = new HashSet<Interval>(samples.intervals);
		final boolean testIntegrity = false;
		constructTree(tree, intervals, testIntegrity);
		testContained(tree, intervals);
	}
	
	//-- overlaps --//
	void testOverlaps(IntervalTree tree, Collection<Interval> intervals) {
		testOverlaps0(tree, intervals);
		profileOverlaps0(tree, intervals);
	}
	
	void testOverlaps0(IntervalTree tree, Collection<Interval> intervals) {
		List<Interval> keys = randomIntervals(NUM_SAMPLES).intervals;
		Set<Interval> dkeys = new HashSet<Interval>(keys);
		final int n = dkeys.size();
		print(">> overlaps checking " + n + " attempts and check integrities... would cost some time");
		Collection<Interval> collect;
		for (Interval key : dkeys) {
			collect = tree.overlaps(key);
			testOverlapsIntegrity(tree, intervals, key, collect);
		}
		print(">> done overlaps checking " + n +" attempts");
	}

	void testOverlapsIntegrity(IntervalTree tree, 
			Collection<Interval> intervals, 
			Interval key,
			Collection<Interval> collect) {
		Set<Interval> collect0 = new HashSet<Interval>();
		int low = key.getLow();
		int high = key.getHigh();
		for (Interval interval : intervals) {
			if (high < interval.getLow() || low > interval.getHigh())
				continue;
			collect0.add(interval);
		}
		if (collect0.size() != collect.size()) {
			print("key: "+key);
			print("by tree: "+ sort(collect));
			print("by scan: "+ sort(collect0));
			throw new RuntimeException("Something wrong with collection size");
		}
		assertEquals("key("+low+":"+ high + "), overlaps size: ", collect0.size(), collect.size());
		for (Interval interval : collect) {
			assertTrue("key("+low+":"+ high + "), interval("+interval.getLow()+":"+interval.getHigh()+")", collect0.contains(interval));
		}
	}

	void profileOverlaps0(IntervalTree tree, Collection<Interval> intervals) {
		Set<Interval> dkeys = new HashSet<Interval>(randomIntervals(NUM_SAMPLES).intervals);
		final int n = dkeys.size();
		print("profile overlaps " + n + " attemps");
		
		long b = new Date().getTime();
		for (Interval key : dkeys) {
			tree.overlaps(key);
		}
		
		long e = new Date().getTime();
		long diff = e - b;
		double avg = ((double)diff) / n;
		print("Total time: " + diff + " ms");
		print("average test overlaps time in millisecond per attempt: " + avg);
		print("---------------------------------------------------------");
	}
	

	//-- insert --//
	void testInsert(IntervalTree tree) {
	//  List<Interval> keys = genIntervals(
//	      [
//	        [83, 86],
//	        [83, 89],
//	        [83, 91],
//	        [83, 94],
//	        [85, 93],
//	        [85, 102],
//	      ]);
	  
		List<Interval> intervals = samples.intervals;
		int topHigh = samples.topHigh;
	
		_testInsert0(tree, intervals, topHigh);
		_profileInsert0(tree, intervals);
	}

	void constructTree(IntervalTree tree, Collection<Interval> keys, boolean testIntegrity) {
		final int n = keys.size();
		print(">> insert " + n + " intervals" + 
				(testIntegrity ? " and check integrities... would cost some time..." : "."));
		for (Interval key : keys) {
			tree.insertInterval(key, null);
			if (testIntegrity) {
				testIntegrityTree(tree);
			}
		}
		print(">> done insert " + keys.size() +" intervals");
	}
	
	void _testInsert0(IntervalTree tree, Collection<Interval> keys, int topHigh) {
		final boolean testIntegrity = true;
		constructTree(tree, keys, testIntegrity);
		
	//	printTree(tree);
		print(">> check integrity...");
		testIntegrityTree(tree);
		if (tree.getRoot() != null) {
			assertEquals(topHigh, ((Integer)tree.getRoot().getValue()).intValue());
		}
		print(">> OK.");
	}

	void _profileInsert0(IntervalTree tree, Collection<Interval> keys) {
		final int n = keys.size();
		print("profile insert " + n + " intervals");
		
		long b = new Date().getTime();
		
//		int j= 0;
		for (Interval key : keys) {   
			tree.insertInterval(key, null);
		}
		
		long e = new Date().getTime();
		long diff = e - b;
		double avg = ((double)diff) / n;
		print("Total time: " + diff + " ms");
		print("average insert time in millisecond per attempt: " + avg);
		print("---------------------------------------------------------");
	}

	void testDelete(IntervalTree tree, Collection<Interval> dkeys) {
		_testDelete0(tree, dkeys);

		_profileDelete0(tree, dkeys);
	}

	void _testDelete0(IntervalTree tree, Collection<Interval> keys) {
		int n = keys.size();
		print(">> delete " + n + " intervals and check integrities... would cost some time");
//	  	int j = 0;
		for (Interval key : keys) {
//	    	if (j == 0) {
//	      		print("bug point");
//			}
//	    	print(" --------- del ${j}:$key");
			tree.deleteInterval(key, null);
//	    	printTree(tree);
			testIntegrityTree(tree);
//	    	++j;
		}
//	  	printTree(tree);
		testIntegrityTree(tree);
	  
	  print(">> done delete "+ n +" intervals");
	}

	void _profileDelete0(IntervalTree tree, Collection<Interval> keys) {
		// reprepare the tree
		tree = new IntervalTree(MAX_END_POINT);
		final boolean testIntegrity = false;
		constructTree(tree, keys, testIntegrity);
		
		// start profile
		int n = keys.size();
		print("profile delete " + n +" intervals");
		long b = new Date().getTime();
		for (Interval key : keys) {
		  tree.deleteInterval(key, null);
		}
		long e = new Date().getTime();
		
		long diff = e - b;
		double avg = ((double)diff) / n;
		print("Total time: " + diff + " ms");
		print("average delete time in millisecond per attempt: " + avg);
		print("---------------------------------------------------------");
	}

	String intervals(IntervalNode<Integer> node) {
		StringBuffer sb = new StringBuffer();
		sb.append("(" + node.getKey() + ":" + node.getValue() + ") ");
		for (Interval intv : node.intervals) {
		  sb.append(intv.toString());
		}
		return sb.toString();
	}

	void printNode(IntervalNode<Integer> node, int level) {
		if (level > 32) {
			print("** Something wrong: LEVEL > 32 **");
			return;
		}
		if (node.getRight() != null)
			printNode(node.getRight(), level + 1);
		
		StringBuffer sb = new StringBuffer();
		for (int j = 0; j < level; ++j)
			sb.append("   ");
		print(sb.toString() + (node.getColor() == RED ? "*" : "") + intervals(node));
		
		if (node.getLeft() != null)
			printNode(node.getLeft(), level + 1);
	}

	//[height, red, length, max]
	int[] integrityNode(IntervalNode<Integer> node) {
		int[] right = new int[4];
		int[] left = new int[4];
	  
		if (node.getRight() != null) {
			right = integrityNode(node.getRight());
			assertTrue(node.getKey() < node.getRight().getKey()); 
		}
		
		if (node.getLeft() != null) {
			left = integrityNode(node.getLeft());
			assertFalse(node.getKey() < node.getLeft().getKey());
		}
		
		//left and right black height should be equal
		assertTrue(height(right) == height(left));
		
		int key = node.getKey();
		
		// 1. Intevals.high is ordered from low to high
		// 2. key would be equals to low of each Interval.low
		int pre = -1;
		for (Interval intv : node.intervals) {
			assertTrue(pre < intv.getHigh());
		  	assertEquals(intv.getLow(), key);
		  	pre = intv.getHigh();
		}
		
		// max must be bigger or equals to left.max, right.max
		assertTrue(node.getValue() >= max(left));
		assertTrue(node.getValue() >= max(right));
		
		if (node.getColor() == RED) {
			assertEquals(0, red(left));//I am red then my left child cannot be red!
			assertEquals(0, red(right)); //I am red then my right child cannot be red!
			return new int[] {height(left), 1, count(left) + count(right) + 1, node.getValue()}; //
		} else {
			return new int[] {height(left) + 1, 0, count(left) + count(right) + 1, node.getValue()};
		}
	}
	
	IntervalSamples randomIntervals(int n) {
		List<Interval> keys = new ArrayList<Interval>();
		int max = 0;
		for (int j = 0; j < n; ++j) {
			Interval key = randomInterval(n);
			keys.add(key);
			if (max < key.getHigh()) max = key.getHigh();
		}
		return new IntervalSamples(keys, max);
	}
	
	
	Interval randomInterval(int n) {
		int key = random.nextInt(n);
		int value = key + random.nextInt(20);
		return new HashableInterval(key, value, null);
	}

//	List<Interval> genIntervals(List<int[]> values) {
//		List<Interval> keys = new ArrayList<Interval>();
//		for (int[] intv : values) {
//		  keys.add(new Interval(intv[0], intv[1], null));
//		}
//		return keys;
//	}
	
	int height(int[] left) {
		return left == null ? 0 : left[0];
	}
	int red(int[] left) {
		return left == null ? 0 : left[1];
	}
	int count(int[] left) {
		return left == null ? 0 : left[2];
	}
    int max(int[] left) {
    	return left == null ? 0 : left[3];
    }
	
	void testIntegrityTree(IntervalTree tree) {
		IntervalNode<Integer> root = tree.getRoot();
		if (root == null) {
		    return;
		}
		
		assertEquals(BLACK, root.getColor()); //root is always black!
		int[] rootCount = integrityNode(root);
		assertEquals(tree.size(), count(rootCount));
	}
	
	void printTree(IntervalTree tree) {
		print(""); //new line
		IntervalNode<Integer> root = tree.getRoot();
		if (tree.root == null)
			print("<empty tree>");
		else
			printNode(root, 0);
	}
	
	private void print(String str) {
		System.out.println(str);
	}
	
	private static class IntervalSamples {
		final List<Interval> intervals;
		final int topHigh;
		IntervalSamples(List<Interval> intervals, int topHigh) {
			this.intervals = intervals;
			this.topHigh = topHigh;
		}
	}
	
	// Interval that will hash on low and high
	private static class HashableInterval extends Interval {
		HashableInterval(int low, int high, Integer payload) {
			super(low, high, payload);
		}
		
		@Override
		public int hashCode() {
			return getLow() * 31 ^ getHigh();
		}
		
		@SuppressWarnings("unchecked")
		@Override
		public boolean equals(Object other) {
			if (this == other)
				return true;
			if (!(other instanceof Interval))
				return false;
			Interval o = (Interval) other;
			return o.getLow() == this.getLow() && o.getHigh() == this.getHigh();
		}
	}

	List<Interval> sort(Collection<Interval> collect) {
		List<Interval> treeCollect = new ArrayList<Interval>(collect);
		Collections.sort(treeCollect, new Comparator<Interval>() {
			@Override
			public int compare(Interval a, Interval b) {
				return a.getHigh() - b.getHigh();
			}
		}); 
		return treeCollect;
	}

	//--- Contains ---//
	void testContains(IntervalTree tree, Collection<Interval> intervals) {
		testContains0(tree, intervals);
		profileContains0(tree, intervals);
	}
	
	void testContains0(IntervalTree tree, Collection<Interval> intervals) {
		Set<Interval> keys = new HashSet<Interval>(randomIntervals(NUM_SAMPLES).intervals);
		final int n = keys.size();
		print(">> contains checking " + n + " attempts and check integrities... would cost some time");
		Collection<Interval> collect;
		for (Interval key : keys) {
			collect = tree.contains(key);
			testContainsIntegrity(tree, intervals, key, collect);
		}
		print(">> done contains checking " + n +" attempts");
	}

	void testContainsIntegrity(IntervalTree tree, 
			Collection<Interval> intervals, 
			Interval key,
			Collection<Interval> collect) {
		Set<Interval> collect0 = new HashSet<Interval>();
		int low = key.getLow();
		int high = key.getHigh();
		// directly scan to get result collection
		for (Interval interval : intervals) {
			if (interval.getLow() <= low && high <= interval.getHigh()) {
				collect0.add(interval);
			}
		}
		if (collect0.size() != collect.size()) {
			print("key: "+key);
			print("by tree: "+ sort(collect));
			print("by scan: "+ sort(collect0));
		}
		assertEquals("key("+low+":"+ high + "), contains size: ", collect0.size(), collect.size());
		for (Interval interval : collect) {
			assertTrue("key("+low+":"+ high + "), interval("+interval.getLow()+":"+interval.getHigh()+")", collect0.contains(interval));
		}
	}

	void profileContains0(IntervalTree tree, Collection<Interval> intervals) {
		Set<Interval> keys = new HashSet<Interval>(randomIntervals(NUM_SAMPLES).intervals);
		final int n = keys.size();
		print("profile contains " + n + " attemps");
		
		long b = new Date().getTime();
		for (Interval key : keys) {
			tree.contains(key);
		}
		
		long e = new Date().getTime();
		long diff = e - b;
		double avg = ((double)diff) / n;
		print("Total time: " + diff + " ms");
		print("average test contains time in millisecond per attempt: " + avg);
		print("---------------------------------------------------------");
	}
	
	//-- Contained --//
	void testContained(IntervalTree tree, Collection<Interval> intervals) {
		testContained0(tree, intervals);
		profileContained0(tree, intervals);
	}
	
	void testContained0(IntervalTree tree, Collection<Interval> intervals) {
		Set<Interval> keys = new HashSet<Interval>(randomIntervals(NUM_SAMPLES).intervals);
		final int n = keys.size();
		print(">> contained checking " + n + " attempts and check integrities... would cost some time");
		Collection<Interval> collect;
		for (Interval key : keys) {
			collect = tree.contained(key);
			testContainedIntegrity(tree, intervals, key, collect);
		}
		print(">> done contained checking " + n +" attempts");
	}

	void testContainedIntegrity(IntervalTree tree, 
			Collection<Interval> intervals, 
			Interval key,
			Collection<Interval> collect) {
		Set<Interval> collect0 = new HashSet<Interval>();
		int low = key.getLow();
		int high = key.getHigh();
		for (Interval interval : intervals) {
			if (low <= interval.getLow() && interval.getHigh() <= high) {
				collect0.add(interval);
			}
		}
		if (collect0.size() != collect.size()) {
			print("key: "+key);
			print("by tree: "+ sort(collect));
			print("by scan: "+ sort(collect0));
		}
		assertEquals("key("+low+":"+ high + "), contained size: ", collect0.size(), collect.size());
		for (Interval interval : collect) {
			assertTrue("key("+low+":"+ high + "), interval("+interval.getLow()+":"+interval.getHigh()+")", collect0.contains(interval));
		}
	}

	void profileContained0(IntervalTree tree, Collection<Interval> intervals) {
		Set<Interval> keys = new HashSet<Interval>(randomIntervals(NUM_SAMPLES).intervals);
		final int n = keys.size();
		print("profile contained " + n + " attemps");
		
		long b = new Date().getTime();
		for (Interval key : keys) {
			tree.contained(key);
		}
		
		long e = new Date().getTime();
		long diff = e - b;
		double avg = ((double)diff) / n;
		print("Total time: " + diff + " ms");
		print("average test contained time in millisecond per attempt: " + avg);
		print("---------------------------------------------------------");
	}
	
}
