/**
 * Simplistic test class for BST.
 * @author  Dr. Jody Paul
 * @version CS3 Spring 2006
 */
public class BSTTest extends junit.framework.TestCase {
    // Instance Variables
    BST bstree;
    BTNode node10, node20, node30, node42, node50;
    BTNode nodeOne, nodeTwo;
    BST balancedTree, unbalancedTree, searchTree;
    BTNode nodeA, nodeB, nodeC, nodeD, nodeE, nodeF;
    
    /** Called before every test case method. */
    protected void setUp() {
        bstree = new BST();
        node10 = new BTNode(null, null, "BTNode 10", new Integer(10));
        node20 = new BTNode(null, null, "BTNode 20", new Integer(20));
        node30 = new BTNode(null, null, "BTNode 30", new Integer(30));
        node42 = new BTNode(null, null, "BTNode 42", new Integer(42));
        node50 = new BTNode(null, null, "BTNode 50", new Integer(50));
        nodeOne = new BTNode(null, null, "BTNode One", "One");
        nodeTwo = new BTNode(null, null, "BTNode Two", "Two");
        balancedTree = new BST();
        balancedTree.insert(new BTNode(null, null, "Dog", "D"));
        balancedTree.insert(new BTNode(null, null, "Egg", "E"));
        balancedTree.insert(new BTNode(null, null, "Boy", "B"));
        balancedTree.insert(new BTNode(null, null, "Ace", "A"));
        balancedTree.insert(new BTNode(null, null, "Car", "C"));
        unbalancedTree = new BST();
        unbalancedTree.insert(new BTNode(null, null, "Ace", "A"));
        unbalancedTree.insert(new BTNode(null, null, "Boy", "B"));
        unbalancedTree.insert(new BTNode(null, null, "Car", "C"));
        unbalancedTree.insert(new BTNode(null, null, "Dog", "D"));
        unbalancedTree.insert(new BTNode(null, null, "Egg", "E"));
        searchTree = new BST();
        nodeA = new BTNode(null, null, "-A-", "A");
        nodeB = new BTNode(null, null, "-B-", "B");
        nodeC = new BTNode(null, null, "-C-", "C");
        nodeD = new BTNode(null, null, "-D-", "D");
        nodeE = new BTNode(null, null, "-E-", "E");
        nodeF = new BTNode(null, null, "-F-", "F");
        searchTree.insert(nodeC);
        searchTree.insert(nodeE);
        searchTree.insert(nodeB);
        searchTree.insert(nodeA);
        searchTree.insert(nodeF);
        searchTree.insert(nodeD);
    }

    public void testConstruction() {
        assertTrue(new BST() != null);
    }

    public void testInsertIsEmptySize() {
        assertEquals(true, bstree.isEmpty());
        assertEquals(0, bstree.size());
        bstree.insert(node42);
        assertEquals(false, bstree.isEmpty());
        assertEquals(1, bstree.size());
        bstree.insert(node30);
        assertEquals(false, bstree.isEmpty());
        assertEquals(2, bstree.size());
        bstree.insert(node42);
        assertEquals(2, bstree.size());
        bstree.insert(node50);
        assertEquals(3, bstree.size());
        assertEquals(5, balancedTree.size());
        assertEquals(5, unbalancedTree.size());
        try {
            bstree.insert(nodeOne);
		    assertTrue("Did not throw exception" == null);
        } catch (ClassCastException cce) {
            assertTrue(true);
        }
    }

	public void testHeight() {
		assertEquals(0, bstree.height());
		assertEquals(3, balancedTree.height());
		assertEquals(5, unbalancedTree.height());
		assertEquals(3, searchTree.height());
	}

	public void testFind() {
		assertEquals(null, bstree.find("A"));
		assertEquals(null, bstree.find(null));
		assertEquals(null, bstree.find(new Integer(42)));
		assertEquals("C", searchTree.find("C").getKey());
		assertEquals("F", searchTree.find("F").getKey());
		assertEquals("A", searchTree.find("A").getKey());
		assertEquals(null, searchTree.find("X"));
		try {
		    searchTree.find(new Integer(42));
		    assertTrue("Did not throw exception" == null);
		} catch (ClassCastException cce) {
		    assertTrue(true);
		}
	}

	public void testRemove() {
		assertEquals(null, bstree.remove(null));
		assertEquals(null, bstree.remove("A"));
		assertEquals(null, searchTree.remove("X"));
		assertEquals("C", searchTree.remove("C").getKey());
		assertEquals(5, searchTree.size());
		assertEquals(null, searchTree.find("C"));
		assertEquals("A", searchTree.remove("A").getKey());
		assertEquals(4, searchTree.size());
		assertEquals(null, searchTree.find("A"));
		assertEquals(null, searchTree.remove("A"));
		assertEquals("E", searchTree.remove("E").getKey());
		assertEquals("D", searchTree.remove("D").getKey());
		assertEquals("B", searchTree.remove("B").getKey());
		assertEquals("F", searchTree.find("F").getKey());
		assertEquals(1, searchTree.size());
		assertEquals("F", searchTree.remove("F").getKey());
		assertTrue(searchTree.isEmpty());
	}

	public void testIsBalanced() {
		assertEquals(true, bstree.isBalanced());
		assertEquals(true, searchTree.isBalanced());
		assertEquals(false, unbalancedTree.isBalanced());
		assertEquals(true, balancedTree.isBalanced());
	}

	public void testBalance() {
		assertEquals(0, bstree.height());
		bstree.balance();
		assertEquals(0, bstree.height());
		assertEquals(6, searchTree.size());
		assertEquals(3, searchTree.height());
		searchTree.balance();
		assertEquals(3, searchTree.height());
		assertEquals(6, searchTree.size());
		assertEquals(5, unbalancedTree.size());
		assertEquals(5, unbalancedTree.height());
		assertEquals(false, unbalancedTree.isBalanced());
		unbalancedTree.balance();
		assertEquals(true, unbalancedTree.isBalanced());
		assertEquals(5, unbalancedTree.size());
		assertEquals(3, unbalancedTree.height());
		searchTree.insert(new BTNode(null, null, "-K-", "K"));
		searchTree.insert(new BTNode(null, null, "-J-", "J"));
		searchTree.insert(new BTNode(null, null, "-I-", "I"));
		searchTree.insert(new BTNode(null, null, "-H-", "H"));
		searchTree.insert(new BTNode(null, null, "-G-", "G"));
		assertEquals(false, searchTree.isBalanced());
		searchTree.balance();
		assertEquals(true, searchTree.isBalanced());
		assertEquals(11, searchTree.size());
		assertEquals(4, searchTree.height());
	}

	public void testInorderTraversal()
	{
		assertEquals(0, bstree.inOrderTraversal().size());
		java.util.List<BTNode> inorder = unbalancedTree.inOrderTraversal();
		assertEquals(5, inorder.size());
		assertEquals(true, inorder.get(0).getKey().equals("A"));
		assertEquals(true, inorder.get(1).getData().equals("Boy"));
		inorder = searchTree.inOrderTraversal();
		assertEquals(6, inorder.size());
		assertEquals(true, inorder.get(inorder.size() - 1).getData().equals("-F-"));
		inorder = balancedTree.inOrderTraversal();
		assertEquals(5, inorder.size());
		assertEquals(true, inorder.get(2).getKey().equals("C"));
	}

	public void testIsBST() {
		assertEquals(true, bstree.isBST());
		assertEquals(true, searchTree.isBST());
		assertEquals(true, unbalancedTree.isBST());
		assertEquals(true, balancedTree.isBST());
		// The following exploits the mutators in BTNode to violate the BST properties
		BST badTree = searchTree;
		BTNode badNode = badTree.find("F");
		badNode.setKey("B");
		badNode.setData("Doubly Bad Node!");
		assertEquals(false, badTree.isBST());
		badTree = balancedTree;
		badNode = badTree.find("B");
		badNode.setKey("A");
		badNode.setData("Duplicate!");
		assertEquals(false, badTree.isBST());
	}
}