BSTTest.java

import static org.junit.Assert.*;

import org.junit.Test;
import org.junit.Ignore;
import org.junit.Before;

import java.util.ArrayList;

public class BSTTest {
  private BST<Integer> tree;
	private Integer a, b, c, d, e, f, g, h, i, j, k, l;
	
	@Before
	public void setUp()
	{
		tree = new BST<Integer>();
		a = new Integer(1);
		b = new Integer(2);
		c = new Integer(3);
		d = new Integer(4);
		e = new Integer(5);
		f = new Integer(6);
		g = new Integer(7);
		h = new Integer(8);
		i = new Integer(9);
		j = new Integer(10);
		k = new Integer(11);
		l = new Integer(12);
	}
	
	public void resetTree()
	{
		tree = new BST<Integer>();
	}
	
	public void addElements(BST<Integer> _tree)
	{
		
		_tree.add(e);
		_tree.add(b);
		_tree.add(g);
		_tree.add(a);
		_tree.add(d);
		_tree.add(i);
		_tree.add(f);
		_tree.add(c);
		_tree.add(h);
		_tree.add(null);
		_tree.add(j);
	}
	
	@Test
	public final void testAdd() {
		tree.add(e);
		assertEquals(tree.getRoot().getData(), e);
		tree.add(b);
		assertEquals(tree.getRoot().getLeft().getData(), b);
		tree.add(g);
		assertEquals(tree.getRoot().getRight().getData(), g);
		tree.add(a);
		assertEquals(tree.getRoot().getLeft().getLeft().getData(), a);
		tree.add(d);
		assertEquals(tree.getRoot().getLeft().getRight().getData(), d);
		tree.add(i);
		assertEquals(tree.getRoot().getRight().getRight().getData(), i);
		tree.add(f);
		assertEquals(tree.getRoot().getRight().getLeft().getData(), f);
		tree.add(c);
		assertEquals(tree.getRoot().getLeft().getRight().getLeft().getData(), c);
		tree.add(h);
		assertEquals(tree.getRoot().getRight().getRight().getLeft().getData(), h);
		tree.add(null);
		assertEquals(tree.getRoot().getRight().getRight().getRight().getData(), null);
		tree.add(j);
		assertEquals(tree.getRoot().getRight().getRight().getRight().getLeft().getData(), j);
		tree.add(k);
		assertEquals(tree.getRoot().getRight().getRight().getRight().getLeft().getRight().getData(), k);
		tree.add(l);
		assertEquals(tree.getRoot().getRight().getRight().getRight().getLeft().getRight().getRight().getData(), l);
		assertEquals(tree.size(), 13);
		
	}

	@Test
	public final void testAddAll() {
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(e);
		list.add(b);
		list.add(g);
		list.add(a);
		list.add(d);
		list.add(i);
		list.add(f);
		list.add(c);
		list.add(h);
		list.add(null);
		
		tree.addAll(list);
		
		assertEquals(tree.getRoot().getData(), e);
		assertEquals(tree.getRoot().getLeft().getData(), b);
		assertEquals(tree.getRoot().getRight().getData(), g);
		assertEquals(tree.getRoot().getLeft().getLeft().getData(), a);
		assertEquals(tree.getRoot().getLeft().getRight().getData(), d);
		assertEquals(tree.getRoot().getRight().getRight().getData(), i);
		assertEquals(tree.getRoot().getRight().getLeft().getData(), f);
		assertEquals(tree.getRoot().getLeft().getRight().getLeft().getData(), c);
		assertEquals(tree.getRoot().getRight().getRight().getLeft().getData(), h);
		assertEquals(tree.getRoot().getRight().getRight().getRight().getData(), null);
		assertEquals(tree.size(), 10);
		
		resetTree();
		boolean thrown = false;
		try {
			tree.addAll(null);
		}
		catch (NullPointerException e)
		{
			thrown = true;
		}
		assertTrue(thrown);
	}
	
//	@Test
//	public final void testFindNodeParent()
//	{
//		addElements(tree);
//		assertEquals(tree.findNodeParent(tree.getRoot().getLeft(), tree.getRoot()), tree.getRoot());
//		assertEquals(tree.findNodeParent(tree.getRoot().getRight(), tree.getRoot()), tree.getRoot());
//
//		assertEquals(tree.findNodeParent(tree.getRoot().getRight().getRight().getRight().getLeft(), tree.getRoot()), tree.getRoot().getRight().getRight().getRight());
//		tree.add(k);
//		tree.add(l);
//		assertEquals(tree.findNodeParent(tree.getRoot().getRight().getRight().getRight().getLeft().getRight().getRight(), tree.getRoot()), tree.getRoot().getRight().getRight().getRight().getLeft().getRight());
//	}
	
	@Test
	public final void testRemove() {
		addElements(tree);
		tree.remove(c);
		// No children
		assertEquals(tree.getRoot().getLeft().getRight().getLeft(), null);
		tree.add(c);
		
		// One child
		tree.remove(d);
		assertEquals(tree.getRoot().getLeft().getRight().getData(), c);
		assertEquals(tree.getRoot().getLeft().getRight().getLeft(), null);
		
		// Two children
		tree.remove(b);
		assertEquals(tree.getRoot().getLeft().getData(), a);
		assertEquals(tree.getRoot().getLeft().getLeft(), null);
		
		// More complicated one child
		tree.add(k);
		tree.add(l);
		
		tree.remove(null);
		assertEquals(tree.getRoot().getRight().getRight().getRight().getData(), j);
		assertEquals(tree.getRoot().getRight().getRight().getRight().getRight().getRight().getData(), l);
		
		// More complicated two child
		resetTree();
		tree.add(g);
		tree.add(d);
		tree.add(b);
		tree.add(a);
		tree.add(c);
		tree.add(f);
		tree.add(e);
		tree.remove(d);
		assertEquals(tree.getRoot().getLeft().getData(), c);
		assertTrue(tree.getRoot().getLeft().getLeft().getRight() == null);
	}

	@Ignore
	@Test
	public final void testContains() {
		fail("Not yet implemented"); // TODO
	}

	@Ignore
	@Test
	public final void testPreOrder() {
		fail("Not yet implemented"); // TODO
	}

	@Ignore
	@Test
	public final void testInOrder() {
		fail("Not yet implemented"); // TODO
	}

	@Ignore
	@Test
	public final void testPostOrder() {
		fail("Not yet implemented"); // TODO
	}

	@Ignore
	@Test
	public final void testIsEmpty() {
		fail("Not yet implemented"); // TODO
	}

	@Ignore
	@Test
	public final void testClear() {
		fail("Not yet implemented"); // TODO
	}

	@Ignore
	@Test
	public final void testSize() {
		fail("Not yet implemented"); // TODO
	}

	@Ignore
	@Test
	public final void testReconstruct() {
		fail("Not yet implemented"); // TODO
	}

}