import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import static org.junit.Assert.*;

import org.junit.AfterClass;
import org.junit.Test;

public class Testing {
	
	private static int points = 0;
	

	@Test
	public void testInsertAndToString(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		assertEquals("[]", b.toString());
		b.insert(7);
		assertEquals("[7]", b.toString());
		b.insert(4);
		assertEquals("[4, 7]", b.toString());	
		b.insert(10);
		assertEquals("[4, 7, 10]", b.toString());	
		b.insert(2);
		assertEquals("[2, 4, 7, 10]", b.toString());	
		b.insert(5);
		assertEquals("[2, 4, 5, 7, 10]", b.toString());	
		assertFalse(b.insert(5));
		assertTrue(b.insert(1));
		try {
			b.insert(null);
			fail("Did not throw IllegalArgumentException");
		} catch (Exception e){
			if (!(e instanceof IllegalArgumentException)) {
				fail("Did not throw IllegalArgumentException");				
			}
		}
		points += 10;
	}
	

	@Test
	// For your reference, the following test code should take about 0.220 seconds
	public void testInsertPerformance(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		int size = 1048576;
		int v = size / 2;
		int temp;
		while (v > 0) {
			temp = v;
			while (temp < size){
				b.insert(temp);
				temp += v;
				}
			v = v / 2;
		}
		assertEquals(size-1, b.size());
		assertEquals(19, b.height());
		Iterator<Integer> i = b.iterator();
		Integer prev = i.next();
		int count = 1;
		Integer current;
		while (i.hasNext()){
			current = i.next();
			count++;
			if (current < prev) fail("Not a BST at: " + prev + " " +  current);
		}
		if (!(count == size-1)) fail("Something appears to be wrong with your in-order iterator");
		points += 5;
	}
	
	
	@Test
	public void testHeight(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		assertEquals(-1, b.height());
		b.insert(3);
		assertEquals(0, b.height());	
		b.insert(4);
		b.insert(5);
		assertEquals(2, b.height());
		b.insert(1);
		b.insert(2);
		assertEquals(2, b.height());	
		b.insert(6);
		b.insert(7);
		assertEquals(4, b.height());
		points += 5;
	}

	@Test
	public void testSize(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		assertEquals(0, b.size());		
		b.insert(3);
		assertEquals(1, b.size());
		b.insert(4);
		b.insert(5);
		assertEquals(3, b.size());
		b.insert(5);
		assertEquals(3, b.size());
		b.insert(2);
		assertEquals(4, b.size());
		points += 3;
	}

	@Test
	public void testIsEmpty(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		assertTrue(b.isEmpty());
		b.insert(3);
		assertFalse(b.isEmpty());
		points += 2;
	}

	@Test
	public void testToArray(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		assertEquals(0, b.toArray().length);
		b.insert(3);
		b.insert(4);
		b.insert(5);
		b.insert(1);
		b.insert(2);
		Object[] temp = {1,2,3,4,5};
		Object[] foo = b.toArray();
		for (int j = 0; j < temp.length; j++){
			assertEquals(temp[j], foo[j]);			
		}
		points += 3;
	}
	
	@Test
	public void testIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		Iterator<Integer> i = b.iterator();
		assertFalse(i.hasNext());
		b.insert(3);
		b.insert(5);
		b.insert(4);
		b.insert(1);
		b.insert(2);
		b.insert(6);
		b.insert(9);
		b.insert(8);

		i = b.iterator();
		int k = 0;
		Integer[] temp = {1, 2, 3, 4, 5, 6, 8, 9};
		boolean[] tempValues = {true, true, true, true, true, true, true, false};
		assertEquals(true, i.hasNext());		
		while (i.hasNext()){
			assertEquals(temp[k], i.next());	
			assertEquals(tempValues[k++], i.hasNext());
		}
		try {
			i.next();
			fail("Did not throw NoSuchElementException");
		} catch (Exception e){
			if (!(e instanceof NoSuchElementException)) {
				fail("Did not throw NoSuchElementException");				
			}
		}
		points += 5;
	}
	
	@Test
	public void testPerformanceInOrderIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		int nums = 1000000;
		for (int i = 0; i < nums; i++){
			b.insert((int)(Math.random()*nums));
		}
		int count = b.size();
		Iterator<Integer> i = b.iterator();
		assertTrue(i.hasNext());
		Integer current = i.next();
		count--;
		Integer prev;
		while (i.hasNext()){
			prev = current;
			current = i.next();
			count--;
			if (current < prev) fail("Not a BST at: " + prev + " " +  current);
		}
		if (count != 0) fail("Something appears to be wrong with your in-order iterator");
		points += 2;
	}
	
	@Test
	public void testPreOrderIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		Iterator<Integer> i = b.preOrderIterator();
		assertFalse(i.hasNext());
		b.insert(3);
		b.insert(5);
		b.insert(4);
		b.insert(1);
		b.insert(2);
		b.insert(8);
		b.insert(7);
		b.insert(9);
		b.insert(6);
		i = b.preOrderIterator();
		int k = 0;
		Integer[] temp = {3, 1, 2, 5, 4, 8, 7, 6, 9};
		boolean[] tempValues = {true, true, true, true, true, true, true, true, false};
		assertEquals(true, i.hasNext());
		while (i.hasNext()){
			assertEquals(temp[k], i.next());	
			assertEquals(tempValues[k++], i.hasNext());
		}
		try {
			i.next();
			fail("Did not throw NoSuchElementException");
		} catch (Exception e){
			if (!(e instanceof NoSuchElementException)) {
				fail("Did not throw NoSuchElementException");				
			}
		}
		points += 5;
	}
	
	@Test
	public void testPerformancePreOrderIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		int nums = 10000;
		for (int i = 0; i < nums; i++){
			b.insert(i);
		}
		Iterator<Integer> it = b.preOrderIterator();
		for (int i = 0; i < nums; i++){
			assertTrue(it.hasNext());
			assertEquals(new Integer(i), it.next());
		}
		points += 2;
	}
	
	@Test
	public void testDescendingIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		Iterator<Integer> i = b.descendingIterator();
		assertFalse(i.hasNext());
		b.insert(3);
		b.insert(5);
		b.insert(4);
		b.insert(1);
		b.insert(2);
		b.insert(6);
		b.insert(9);
		b.insert(8);

		i = b.descendingIterator();
		int k = 0;
		Integer[] temp = {9, 8, 6, 5, 4, 3, 2, 1};
		boolean[] tempValues = {true, true, true, true, true, true, true, false};
		assertEquals(true, i.hasNext());		
		while (i.hasNext()){
			assertEquals(temp[k], i.next());	
			assertEquals(tempValues[k++], i.hasNext());
		}
		try {
			i.next();
			fail("Did not throw NoSuchElementException");
		} catch (Exception e){
			if (!(e instanceof NoSuchElementException)) {
				fail("Did not throw NoSuchElementException");				
			}
		}
		points += 5;
	}
	
	@Test
	public void testPerformanceDescendingIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		int nums = 1000000;
		for (int i = 0; i < nums; i++){
			b.insert((int)(Math.random()*nums));
		}
		int count = b.size();
		Iterator<Integer> i = b.descendingIterator();
		assertTrue(i.hasNext());
		Integer current = i.next();
		count--;
		Integer prev;
		while (i.hasNext()){
			prev = current;
			current = i.next();
			count--;
			if (current > prev) fail("Not a BST at: " + prev + " " +  current);
		}
		if (count != 0) fail("Something appears to be wrong with your in-order iterator");
		points += 2;
	}
	
	@Test
	public void testLevelOrderIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		Iterator<Integer> i = b.levelOrderIterator();
		assertFalse(i.hasNext());
		b.insert(3);
		b.insert(5);
		b.insert(4);
		b.insert(1);
		b.insert(2);
		b.insert(8);
		b.insert(7);
		b.insert(9);
		b.insert(6);
		i = b.levelOrderIterator();
		int k = 0;
		Integer[] temp = {3, 1, 5, 2, 4, 8, 7, 9, 6};
		boolean[] tempValues = {true, true, true, true, true, true, true, true, false};
		assertEquals(true, i.hasNext());		
		while (i.hasNext()){
			assertEquals(temp[k], i.next());	
			assertEquals(tempValues[k++], i.hasNext());
		}
		try {
			i.next();
			fail("Did not throw NoSuchElementException");
		} catch (Exception e){
			if (!(e instanceof NoSuchElementException)) {
				fail("Did not throw NoSuchElementException");				
			}
		}
		points += 5;
	}
	
	
	@Test
	public void testPerformanceLevelOrderIterator(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		int nums = 10000;
		for (int i = 0; i < nums; i++){
			b.insert(i);
		}
		Iterator<Integer> it = b.levelOrderIterator();
		for (int i = 0; i < nums; i++){
			assertTrue(it.hasNext());
			assertEquals(new Integer(i), it.next());
		}
		points += 2;
	}
	
	
	// Removal
	
	@Test
	public void testRemoveNullElement(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		try {
			b.remove(null);
			fail("Did not throw IllegalArgumentException");
		} catch (Exception e){
			if (!(e instanceof IllegalArgumentException)) {
				fail("Did not throw IllegalArgumentException");				
			}
		}
		points += 2;
	}
	
	@Test
	public void testRemoveFromEmptyTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		assertEquals("[]", b.toString());
		assertFalse(b.remove(7));
		assertEquals(0, b.size());
		points += 2;
	}

	@Test
	public void testRemoveJustRoot(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(4);
		assertTrue(b.remove(4));
		assertEquals("[]", b.toString());
		assertFalse(b.remove(4));
		assertEquals(0, b.size());
		points += 3;
	}
		
	@Test
	public void testRemoveRightChildInSimpleTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(4);
		b.insert(14);
		assertTrue(b.remove(14));
		Integer[] a = {10, 4};
		boolean[] bool = {true, false};
		Iterator<Integer> i = b.preOrderIterator();
		assertTrue(i.hasNext());
		for (int k = 0; k < a.length; k++){
			assertEquals(a[k], i.next());
			assertEquals(bool[k], i.hasNext());
		}
		assertEquals(2, b.size());
		points += 3;
	}
	
	@Test
	public void testRemoveLeftChildInSimpleTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(4);
		b.insert(14);
		assertTrue(b.remove(4));
		
		Integer[] a = {10, 14};
		boolean[] bool = {true, false};
		Iterator<Integer> i = b.preOrderIterator();
		assertTrue(i.hasNext());
		for (int k = 0; k < a.length; k++){
			assertEquals(a[k], i.next());
			assertEquals(bool[k], i.hasNext());
		}
		assertEquals(2, b.size());
		points += 3;
	}
	
	@Test
	public void testRemoveRootInSimpleTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(4);
		b.insert(14);
		assertTrue(b.remove(10));
		Integer[] a = {4, 14};
		boolean[] bool = {true, false};
		Iterator<Integer> i = b.preOrderIterator();
		assertTrue(i.hasNext());
		for (int k = 0; k < a.length; k++){
			assertEquals(a[k], i.next());
			assertEquals(bool[k], i.hasNext());
		}
		assertEquals(2, b.size());
		points += 3;
	}
		
	@Test
	public void testRemoveLeafFromComplexTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(15);
		b.insert(5);
		b.insert(2);
		b.insert(7);
		b.insert(1);
		b.insert(3);
		b.remove(7);
		assertEquals("[1, 2, 3, 5, 10, 15]", b.toString());
		Integer[] m = {10, 5, 2, 1, 3, 15};
		boolean boo[] = {true, true, true, true, true, false}; 
		Iterator<Integer> i = b.preOrderIterator();
		assertTrue(i.hasNext());
		for (int k = 0; k < m.length; k++){
			assertEquals(m[k], i.next());
			assertEquals(boo[k], i.hasNext());
		}
		assertEquals(6, b.size());
		points += 3;
	}
	
	@Test
	public void testRemoveNodeWithOneChildFromComplexTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(15);
		b.insert(5);
		b.insert(2);
		b.insert(1);
		b.insert(3);
		assertEquals("[1, 2, 3, 5, 10, 15]", b.toString());
		b.remove(5);
		assertEquals("[1, 2, 3, 10, 15]", b.toString());
		Integer[] n = {10, 2, 1, 3, 15};
		boolean boo2[] = {true, true, true, true, false}; 
		Iterator<Integer> i = b.preOrderIterator();
		assertTrue(i.hasNext());
		for (int k = 0; k < n.length; k++){
			assertEquals(n[k], i.next());
			assertEquals(boo2[k], i.hasNext());
		}
		assertEquals(5, b.size());
		points += 3;

	}
	
	@Test
	public void testRemoveNodeWithTwoChildrenFromComplexTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(15);
		b.insert(12);
		b.insert(17);
		b.insert(13);
		b.insert(14);
		b.insert(5);
		b.insert(2);
		b.insert(1);
		b.insert(3);
		assertEquals("[1, 2, 3, 5, 10, 12, 13, 14, 15, 17]", b.toString());
		b.remove(15);
		assertEquals("[1, 2, 3, 5, 10, 12, 13, 14, 17]", b.toString());
		Integer[] p = {10, 5, 2, 1, 3, 14, 12, 13, 17};
		boolean boo3[] = {true, true, true, true, true, true, true, true, false}; 
		Iterator<Integer> i = b.preOrderIterator();
		assertTrue(i.hasNext());
		for (int k = 0; k < p.length; k++){
			assertEquals(p[k], i.next());
			assertEquals(boo3[k], i.hasNext());
		}
		assertEquals(9, b.size());
		points += 3;

	}
	
	@Test
	public void testRemoveRootFromComplexTree(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(15);
		b.insert(12);
		b.insert(17);
		b.insert(13);
		b.insert(14);
		b.insert(5);
		b.insert(2);
		b.insert(1);
		b.insert(3);
		assertEquals("[1, 2, 3, 5, 10, 12, 13, 14, 15, 17]", b.toString());
		b.remove(10);
		assertEquals("[1, 2, 3, 5, 12, 13, 14, 15, 17]", b.toString());
		Integer[] p = {5, 2, 1, 3, 15, 12, 13, 14, 17};
		boolean boo3[] = {true, true, true, true, true, true, true, true, false}; 
		Iterator<Integer> i = b.preOrderIterator();
		assertTrue(i.hasNext());
		for (int k = 0; k < p.length; k++){
			assertEquals(p[k], i.next());
			assertEquals(boo3[k], i.hasNext());
		}
		assertEquals(9, b.size());
		points += 3;
	}
	
	@Test
	public void testRemoveNonExistingElement(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(15);
		b.insert(12);
		b.insert(17);
		b.insert(13);
		b.insert(14);
		b.insert(5);
		b.insert(2);
		b.insert(1);
		b.insert(3);
		assertEquals("[1, 2, 3, 5, 10, 12, 13, 14, 15, 17]", b.toString());
		assertFalse(b.remove(16));
		assertEquals(10, b.size());
		points += 2;
	}
	
	@Test
	public void testRemoveAllElements(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		b.insert(10);
		b.insert(15);
		b.insert(12);
		b.insert(17);
		b.insert(13);
		b.insert(14);
		b.insert(5);
		b.insert(2);
		b.insert(1);
		b.insert(3);
		assertEquals("[1, 2, 3, 5, 10, 12, 13, 14, 15, 17]", b.toString());
		assertTrue(b.remove(10));
		assertTrue(b.remove(5));
		assertTrue(b.remove(3));
		assertTrue(b.remove(2));
		assertEquals("[1, 12, 13, 14, 15, 17]", b.toString());
		assertTrue(b.remove(1));
		assertEquals("[12, 13, 14, 15, 17]", b.toString());
		assertTrue(b.remove(12));
		assertTrue(b.remove(13));
		assertTrue(b.remove(14));
		assertTrue(b.remove(15));
		assertTrue(b.remove(17));
		assertEquals("[]", b.toString());
		assertEquals(0, b.size());
		points += 3;
	}
	
	
	@Test
	public void testPerformanceRegularRemove(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		int nums = 1000000;
		for (int i = 0; i < nums; i++){
			b.insert((int)(Math.random()*nums));
		}
		nums = 1000000;
		for (int i = 0; i < nums; i++){
			b.remove((int)(Math.random()*nums));
		}
		points += 3; 
	}

	@AfterClass
	public static void testDoNothing(){
		System.out.println("Points: " + points);
	}

	
}