/* RBTreeTest.java

	Purpose:
		
	Description:
		
	History:
		Oct 22, 2014 7:25:18 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.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;

/**
 * @author henri
 *
 */
public class RBTreeTest {

	private static final boolean RED = true;
	private static final boolean BLACK = false;
	private static final int MAX_KEY = 10000;
	
	RBTree<Integer, Integer> tree;
	Random random;
	
	/**
	 * @throws java.lang.Exception
	 */
	@Before
	public void setUp() throws Exception {
		tree = new RBTree<Integer, Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer a, Integer b) {
				return a.intValue() - b.intValue();
			}
		});
		random = new Random(new Date().getTime());
	}

	/**
	 * @throws java.lang.Exception
	 */
	@After
	public void tearDown() throws Exception {
		tree = null;
	}

	@Test
	public void testInsertAndDeleteNodes() {
		List<Integer> keys = testInsert(tree, MAX_KEY);
		testDelete(tree, new ArrayList<Integer>(keys));
	}

	List<Integer> testInsert(RBTree<Integer, Integer> tree, int n) {
		List<Integer> keys = new ArrayList<Integer>();
		
		for (int j = 0; j < n; ++j) {
			Integer key = Integer.valueOf(random.nextInt(n));
			keys.add(key);
		}
		
		_testInsert0(tree, keys);
		
		_profileInsert0(tree, keys);
		
		return keys;
	}
	
	void _testInsert0(RBTree<Integer, Integer> tree, Collection<Integer> keys) {
		final int n = keys.size();
		print(">> insert " + n +" nodes");
//		int j= 0;
		for (Integer key : keys) {
			tree.insert(new RBNode<Integer, Integer>(key, key), null);
//			printTree(tree);
			testIntegrityTree(tree);
		}
	
//		printTree(tree);
		testIntegrityTree(tree);
		
		print(">> done insert " + keys.size() + " nodes");
	}
	
	void _profileInsert0(RBTree<Integer, Integer> tree, Collection<Integer> keys) {
		  final int n = keys.size();
		  print("profile insert " + n +" nodes");
		  
		  long b = new Date().getTime();
		  
//		  int j= 0;
		  for (Integer key : keys) {   
		    tree.insert(new RBNode<Integer, Integer>(key, 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 ms/attempt: " + avg);
	}
	
	void testDelete(RBTree<Integer, Integer> tree, Collection<Integer> keys) {
	//  List<int> dkeys = [90, 68];
	//  var dkeys = [0];
	  Set<Integer> dkeys = new HashSet<Integer>(keys);
	 
	  _testDelete0(tree, dkeys);

	  _profileDelete0(tree, dkeys);
	}

	void _testDelete0(RBTree<Integer, Integer> tree, Collection<Integer> keys) {
	  int n = keys.size();
	  print(">> delete " + n + " nodes");
	  for (Integer key : keys) {
//	    print(" --------- del ${j++}:$key");
	    
//	    if (key == 0) {
//	      print("bug point");
	    
	    tree.delete(key, key);
//	    printTree(tree);
//	    testIntegrityTree(tree);
	  }
	//  printTree(tree);
	  testIntegrityTree(tree);
	  
	  print(">> done delete " + n + " nodes");
	}
	
	void _profileDelete0(RBTree<Integer, Integer> tree, Collection<Integer> keys) {
		  int n = keys.size();
		  print("profile delete " + n + " nodes");
		  
		  long b = new Date().getTime();
		  
		  for (Integer key : keys) {
		    tree.delete(key, key);
		  }
		  long e = new Date().getTime();
		  
		  long diff = e - b;
		  double avg = ((double)diff) / n;
		  
		  print("total time: " + diff + " ms");
		  print("average delete time ms/attempt: " + avg);
	}
	
	void printNode(RBNode<Integer, 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 ? "*" : "") + node.getKey().toString());
		  
		  if (node.getLeft() != null)
		    printNode(node.getLeft(), level + 1);
	}

	
	int len(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];
	}
	
	void testIntegrityTree(RBTree<Integer, Integer> tree) {
		  RBNode<Integer, Integer> root = tree.root;
		  if (root == null) {
			  return;
		  }
		  
		  assertEquals(BLACK, root.getColor()); //root is always black!
		  int[] rootCount = integrityNode(root);
		  assertEquals(tree.size(), count(rootCount));
	}

	
	//[length, redCount]
	int[] integrityNode(RBNode<Integer, Integer> node) {
		  int[] right = new int[3];
		  int[] left = new int[3];
		  
		  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());
		  }
		  
		  assertTrue(len(right) == len(left)); //left and right black length should be equal 
		 
		  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[] {len(left), 1, count(left) + count(right) + 1}; //
		  } else {
			  return new int[] {len(left) + 1, 0, count(left) + count(right) + 1};
		  }
	}
	
	private void print(String str) {
		System.out.println(str);
	}
}
