package ex1;

import java.util.*;

public class Ex1Tester
{
	public static int[] sortInts(int[] arr)
	{
		int[] sortedArr = new int[arr.length];
		for (int j=0; j<arr.length; j++)
		{
			sortedArr[j] = arr[j];
		}
		Arrays.sort(sortedArr);
		return sortedArr;
	}
	
	public static boolean arraysIdentical(int[] arr1, int[] arr2)
	{
		if (arr1.length != arr2.length)
		{
			return false;
		}
		for (int j=0; j<arr1.length; j++)
		{
			if (arr1[j] != arr2[j])
			{
				return false;
			}
		}
		return true;
	}
	
	public static void main(String[] args)
	{
		// initialize tests success array to false
		boolean[] success = new boolean[10];
		for (int i=0; i<success.length; i++)
		{
			success[i] = false;
		}
		
		// create array of values between 500-1500
		// like this - 500, 501, 502, 503, 504
		int[] valuesTemp = new int[1000];
		for (int j=0; j<valuesTemp.length; j++)
		{
			valuesTemp[j] = 500 + j;
		}
		
		// mix the values - create a new list of values taken
		// one from the start one from the end, alternately
		// i.e. values[0], values[-1], values[1], values[-2] ...
		int[] values = new int[1000];
		{
			int k = 0;
			for (int j=0; j< (values.length / 2); j++)
			{
				values[k] = valuesTemp[j];
				k++;
				values[k] = valuesTemp[valuesTemp.length-1-j];
				k++;
			}
		}
		
		// create custom array of values
		int[] values3 = new int[] {11,6,1,19,17,3,2,10,12,18,
				20,15,4,13,7,16,9,5,8,14};
		
		
		RBTree rbTree = null;
		MyTree myTree = null;
		int last_value_removed = -1;
		
		for (int i=0; i<success.length; i++)
		{
			try
			{
				// Initialization
				if (i==0)
				{
					rbTree = new RBTree();
					success[i] = rbTree.empty() && rbTree.toIntArray().length == 0 && rbTree.isLegalRedBlackTree();
				}
				// Insert Sanity
				else if (i==1)
				{
					int n = 0;
					myTree = new MyTree();
					for (int j=0; j<values.length; j++)
					{
						rbTree.insert(values[j]);
						myTree.insert(values[j]);
						// check isComplete does not throw an exception
						rbTree.isComplete();
						if (!rbTree.isLegalRedBlackTree())
						{
							n++;
						}
					}
					for (int j=0; j<values.length; j++)
					{
						if (!rbTree.contains(values[j]) || !rbTree.isLegalRedBlackTree())
						{
							n++;
						}
					}
					success[i] = (n==0) && rbTree.toIntArray().length == values.length && rbTree.isLegalRedBlackTree(); 
				}
				// ToIntArray
				else if (i==2)
				{
					success[i] = arraysIdentical(sortInts(myTree.array()), 
							rbTree.toIntArray()) && rbTree.isLegalRedBlackTree();
				}
				// Delete
				else if (i==3 || i==5)
				{
					int n=0;
					
					// delete values going from the middle outwards
					// i.e. 1000, 1002, 998, ..
					// do it in 2 chunks
					int chunk_size = values.length/4;
					for (int j=0; j<2; j++)
					{
						// delete a chunk of values
						int start = j*chunk_size;
						for (int k=start; k < (start+chunk_size); k++)
						{
							rbTree.delete(values[values.length-1-k]);
							myTree.delete(values[values.length-1-k]);
							last_value_removed = values[values.length-1-k];
							if (!rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						// check correctness
						for (int k=0; k<values.length; k++)
						{
							if (rbTree.contains(values[k]) != myTree.contains(values[k]) 
									|| !rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						if (!arraysIdentical(rbTree.toIntArray(),
								sortInts(myTree.array())))
						{
							n++;
						}
					}
					success[i] = (n==0) && rbTree.isLegalRedBlackTree();
				}
				// Re-Insert
				else if (i==4)
				{
					int n=0;
					// add values going from the middle outwards
					// i.e. 1000, 1002, 998, ..
					// do it in 2 chunks
					int chunk_size = values.length/4;
					for (int j=0; j<2; j++)
					{
						// insert a chunk of values
						int start = j*chunk_size;
						for (int k=start; k < (start+chunk_size); k++)
						{
							rbTree.insert(values[values.length-1-k]);
							myTree.insert(values[values.length-1-k]);
							if (!rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						// check correctness
						for (int k=0; k<values.length; k++)
						{
							if (rbTree.contains(values[k]) != myTree.contains(values[k])
									|| !rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						if (!arraysIdentical(rbTree.toIntArray(),
								sortInts(myTree.array())))
						{
							n++;
						}
					}
					success[i] = (n==0) && rbTree.isLegalRedBlackTree();
				}
				// Min Max
				else if (i==6)
				{
					int n = 0;
					for (int j=0; values[j]!=last_value_removed; j++)
					{
						rbTree.delete(values[j]);
						myTree.delete(values[j]);
						int [] arr = rbTree.toIntArray();
						if (!rbTree.isLegalRedBlackTree())
						{
							n++;
						}
						if (values[j+1]==last_value_removed)
						{
							if (arr.length > 0)
							{
								n++;
							}
						}
						else
						{
							if (arr.length != myTree.size() ||
									arr[0] != rbTree.min() ||
									arr[0] != myTree.min() ||
									arr[arr.length-1] != rbTree.max() ||
									arr[arr.length-1] != myTree.max())
							{
								n++;
							}
						}
					}
					success[i] = (n == 0) && rbTree.empty() && rbTree.isLegalRedBlackTree() ;
				}
				// Insert random ordered ints
				else if (i==7)
				{
					int n=0;
					rbTree = new RBTree();
					myTree = new MyTree();
					for (int j=0; j<values3.length; j++)
					{
						if (j==0 || j==1 || j==3 || j==7 )
						{
							if (!rbTree.isComplete())
							{
								n++;
							}
						}
						else
						{
							if (rbTree.isComplete())
							{
								n++;
							}
						}
						rbTree.insert(values3[j]);
						myTree.insert(values3[j]);
						if (rbTree.max() != myTree.max() ||
								rbTree.min() != myTree.min() || !rbTree.isLegalRedBlackTree())
						{
							n++;
						}
						for (int k=0; k<values3.length; k++)
						{
							if (rbTree.contains(values3[k]) != myTree.contains(values3[k])
									|| !rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						if (!arraysIdentical(rbTree.toIntArray(),
								sortInts(myTree.array())))
						{
							n++;
						}
					}
					success[i] = (n == 0) && rbTree.isLegalRedBlackTree();
				}
				// pred && succ
				else if (i==8)
				{
					int n=0, j=0,num=rbTree.min();
					int[] sorted=sortInts(myTree.array());
					if (rbTree.succ(rbTree.max()) != -1 || rbTree.pred(rbTree.min()) != -1)
					{
						n++;
					}
					while (rbTree.succ(num) != -1)
					{
						if (num >= rbTree.succ(num) || 
								num != rbTree.pred(rbTree.succ(num)) || 
								num != sorted[j++] ||
								!rbTree.isLegalRedBlackTree())
						{
							n++;
						}
						num=rbTree.succ(num);
					}
					if (num != rbTree.max() || !rbTree.isLegalRedBlackTree())
					{
						n++;
					}
					while (rbTree.pred(num) != -1)
					{
						if (num <= rbTree.pred(num) || 
								num != rbTree.succ(rbTree.pred(num)) || 
								num != sorted[j--] ||
								!rbTree.isLegalRedBlackTree())
						{
							n++;
						}
						num=rbTree.pred(num);
					}
					if (num != rbTree.min())
					{
						n++;
					}
					success[i] = (n == 0) && rbTree.isLegalRedBlackTree();
				}
				else if (i==9)
				{
					int n=0;
					for (int j=0; j<values3.length; j++)
					{
						rbTree.delete(values3[values3[j]-1]);
						myTree.delete(values3[values3[j]-1]);
						if (myTree.size() > 0)
						{
							if (rbTree.max() != myTree.max() ||	rbTree.min() != myTree.min()
									|| !rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						else
						{
							if (!rbTree.empty() || !rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						for (int k=0; k<values3.length; k++)
						{
							if (rbTree.contains(values3[k]) != myTree.contains(values3[k])
									|| !rbTree.isLegalRedBlackTree())
							{
								n++;
							}
						}
						if (!arraysIdentical(rbTree.toIntArray(),
								sortInts(myTree.array())))
						{
							n++;
						}
					}
					success[i] = (n == 0) && rbTree.isLegalRedBlackTree();
				} 
			}
			catch (Exception e)
			{
				System.out.println("Exception Caught On Test" + i + " : "+e);
			}
			System.out.println("Success On Test " + i + " = " + success[i]);
		}

		int n = 0;
		for (boolean value : success)
		{
			if (value)
			{
				n++;
			}
		}
		System.out.println("=========================================");
		System.out.println("Total : " + n + "/" + success.length);
	}

}