/**
 * The test class BalancedBSTTest.
 * @author  Dr. Jody Paul
 * @version Fall 2005 - September 7
 */
public class BalancedBSTTest extends junit.framework.TestCase
{
    BTNode node3, node4, node5, node6, node7, node8, node9;
    BalancedBST balanced1;
    
    /** Default constructor for test class BalancedBSTTest */
    public BalancedBSTTest() { }

    /**
     * Sets up the test fixture.
     * Called before every test case method.
     */
    protected void setUp()
    {
        node3 = new BTNode(null, null, null, new Integer(3));
        node4 = new BTNode(null, null, null, new Integer(4));
        node5 = new BTNode(null, null, null, new Integer(5));
        node6 = new BTNode(null, null, null, new Integer(6));
        node7 = new BTNode(null, null, null, new Integer(7));
        node8 = new BTNode(null, null, null, new Integer(8));
        node9 = new BTNode(null, null, null, new Integer(9));

        balanced1 = new BalancedBST();
    }

    /**
     * Tears down the test fixture.
     * Called after every test case method.
     */
    protected void tearDown() { }

    public void testAdd()
    {
        assertEquals(0, balanced1.size());
        assertTrue(balanced1.add(node6));
        assertSame(node6, balanced1.getRoot());
        assertEquals(1, balanced1.size());
        assertTrue(node6.getKey().equals(new Integer(6)));
        assertTrue(balanced1.add(node3));
        assertEquals(2, balanced1.size());
        assertSame(node6, balanced1.getRoot());
        assertSame(node3, balanced1.getRoot().getLeftChild());
        assertTrue(balanced1.add(new BTNode(null, null, null, new Integer(6))));
        assertEquals(2, balanced1.size());
        assertTrue(balanced1.add(node9));
        assertEquals(3, balanced1.size());
        assertSame(balanced1.getRoot().getRightChild(), node9);
    }

    public void testIsEmpty()
    {
        assertTrue(balanced1.isEmpty());
        assertTrue(balanced1.add(node6));
        assertFalse(balanced1.isEmpty());
    }

    public void testGetRoot()
    {
        assertNull(balanced1.getRoot());
        assertTrue(balanced1.add(node6));
        assertNotNull(balanced1.getRoot());
        assertSame(node6, balanced1.getRoot());
    }

	public void testFirst()
	{
		assertNull(balanced1.first());
		assertEquals(true, balanced1.add(node7));
		assertEquals(node7, balanced1.first());
		assertEquals(true, balanced1.add(node4));
		assertSame(node4, balanced1.first());
		assertEquals(true, balanced1.add(node8));
		assertSame(node4, balanced1.first());
		assertEquals(true, balanced1.add(node3));
		assertSame(node3, balanced1.first());
	}
	
	public void testSize()
    {
        assertEquals(0, balanced1.size());
        assertTrue(balanced1.add(node6));
        assertEquals(1, balanced1.size());
        assertTrue(balanced1.add(node3));
        assertEquals(2, balanced1.size());
        assertTrue(balanced1.add(node9));
        assertEquals(3, balanced1.size());
    }

    public void testContains()
    {
        assertFalse(balanced1.contains(null));
        assertFalse(balanced1.contains(node6));
        assertTrue(balanced1.add(node6));
        assertTrue(balanced1.contains(node6));
        assertFalse(balanced1.contains(node3));
        assertTrue(balanced1.add(node9));
        assertTrue(balanced1.contains(node9));
    }

    public void testToList()
    {
        assertNull(balanced1.toList());
        assertTrue(balanced1.add(node6));
        java.util.ArrayList arrayList1 = (java.util.ArrayList)balanced1.toList();
        assertNotNull(arrayList1);
        assertEquals(1, arrayList1.size());
        assertEquals(node6, arrayList1.get(0));
        assertTrue(balanced1.add(node3));
        assertTrue(balanced1.add(node9));
        java.util.ArrayList arrayList2 = (java.util.ArrayList)balanced1.toList();
        assertNotNull(arrayList2);
        assertEquals(3, arrayList2.size());
        assertSame(node3, arrayList2.get(0));
        assertSame(node6, arrayList2.get(1));
        assertSame(node9, arrayList2.get(2));
    }

    public void testToArray()
    {
        BTNode[] nodeArray1 = (BTNode[])balanced1.toArray();
        assertNotNull(nodeArray1);
        assertEquals(nodeArray1.length, 0); 
        assertTrue(balanced1.add(node6));
        BTNode[] nodeArray2 = (BTNode[])balanced1.toArray();
        assertEquals(nodeArray2.length, 1);
        assertTrue(nodeArray2[0].equals(node6));
        assertTrue(balanced1.add(node3));
        assertTrue(balanced1.add(node9));
        BTNode[] nodeArray3 = (BTNode[])balanced1.toArray();
        assertEquals(nodeArray3.length, 3);
        assertTrue(nodeArray3[0].equals(node3));
        assertTrue(nodeArray3[1].equals(node6));
        assertTrue(nodeArray3[2].equals(node9));
    }

    public void testIterator()
    {
        java.util.Iterator iterator1 = (java.util.Iterator)balanced1.iterator();
        assertFalse(iterator1.hasNext());
        assertTrue(balanced1.add(node6));
        java.util.Iterator iterator2 = (java.util.Iterator)balanced1.iterator();
        assertTrue(iterator2.hasNext());
        assertTrue(node6.equals((BTNode)iterator2.next()));
        assertFalse(iterator2.hasNext());       
        assertTrue(balanced1.add(node3));
        java.util.Iterator iterator3 = (java.util.Iterator)balanced1.iterator();
        assertTrue(iterator3.hasNext());
        assertTrue(node3.equals((BTNode)iterator3.next()));
        assertTrue(iterator3.hasNext());        
        assertTrue(node6.equals((BTNode)iterator3.next()));
        assertFalse(iterator3.hasNext());       
    }

    public void testRemove()
    {
        assertTrue(balanced1.remove(node6));
        assertTrue(balanced1.add(node6));
        assertTrue(balanced1.contains(node6));
        assertTrue(balanced1.add(node3));
        assertTrue(balanced1.contains(node3));
        assertTrue(balanced1.add(node9));
        assertTrue(balanced1.remove(node3));
        assertFalse(balanced1.contains(node3));
        assertTrue(balanced1.remove(node6));
        assertFalse(balanced1.contains(node6));
        assertTrue(balanced1.remove(node9));
        assertTrue(balanced1.isEmpty());
    }


    public void testBalance()
    {
        assertTrue(balanced1.add(node9));
        assertTrue(balanced1.add(node6));
        assertTrue(balanced1.add(node3));
        assertSame(node6, balanced1.getRoot());
        balanced1 = new BalancedBST();
        assertTrue(balanced1.add(node3));
        assertTrue(balanced1.add(node6));
        assertTrue(balanced1.add(node9));
        assertSame(node6, balanced1.getRoot());
        balanced1 = new BalancedBST();
        assertTrue(balanced1.add(node9));
        assertTrue(balanced1.add(node8));
        assertTrue(balanced1.add(node7));
        assertTrue(balanced1.add(node6));
        assertTrue(balanced1.add(node5));
        assertTrue(balanced1.add(node4));
        assertTrue(balanced1.add(node3));
        assertTrue(node6.equals(balanced1.getRoot())
                || node5.equals(balanced1.getRoot())
                || node7.equals(balanced1.getRoot()));
        balanced1 = new BalancedBST();
        assertTrue(balanced1.add(node3));
        assertTrue(balanced1.add(node4));
        assertTrue(balanced1.add(node5));
        assertTrue(balanced1.add(node6));
        assertTrue(balanced1.add(node7));
        assertTrue(balanced1.add(node8));
        assertTrue(balanced1.add(node9));
        assertTrue(node6.equals(balanced1.getRoot())
                || node5.equals(balanced1.getRoot())
                || node7.equals(balanced1.getRoot()));
    }


	public void testToString()
	{
		assertEquals("java.lang.String", balanced1.toString().getClass().getName());
		assertEquals(true, balanced1.add(node5));
		assertNotNull(balanced1.toString());
	}
}