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;
	}

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

	
}