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 testInsert(){
		BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
		assertEquals("[]", b.toString());
		points += 1;
		b.insert(7);
		assertEquals("[7]", b.toString());
		points += 2;
		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());	
		points += 12;
		assertFalse(b.insert(5));
		points += 2;
		assertTrue(b.insert(1));
		points += 4;
		try {
			b.insert(null);
			fail("Did not throw IllegalArgumentException");
		} catch (Exception e){
			if (!(e instanceof IllegalArgumentException)) {
				fail("Did not throw IllegalArgumentException");				
			}
		}
		points += 2;
	}
	

	@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());
		points += 1;
		
		b.insert(3);
		assertEquals(0, b.height());
		points += 2;
		
		b.insert(4);
		b.insert(5);
		assertEquals(2, b.height());
		points += 2;
	}

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

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

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

	
}