00001 00005 package edu.mit.csail.sdg.squander.examples.bst; 00006 00007 import static org.junit.Assert.assertEquals; 00008 import static org.junit.Assert.assertTrue; 00009 00010 import org.junit.Assert; 00011 import org.junit.Before; 00012 import org.junit.Test; 00013 00014 import edu.mit.csail.sdg.squander.examples.bst.BinarySearchTree; 00015 import edu.mit.csail.sdg.squander.examples.bst.BinarySearchTree.Node; 00016 import edu.mit.csail.sdg.squander.util.test.TestUtils; 00017 00018 00019 public class BinarySearchTreeTest { 00020 00021 private BinarySearchTree bst; 00022 private int[] keys; 00023 private Node[] nodes; 00024 00025 @Before 00026 public void before() { 00027 keys = new int[] { 3, -4, -2, 2, 6}; 00028 initBinarySearchTree(); 00029 } 00030 00031 private void initBinarySearchTree() { 00032 nodes = new Node[keys.length]; 00033 for (int i = 0; i < keys.length; i++) 00034 nodes[i] = new Node(keys[i]); 00035 bst = new BinarySearchTree(); 00036 for (Node n : nodes) 00037 bst.insert(n); 00038 } 00039 00040 @Test 00041 public void testMin_squander() { 00042 assertEquals("Wrong return value for the min_squander method", -4, bst.min_squander()); 00043 assertTrue("repOK failed after calling max method", bst.repOk()); 00044 BinarySearchTree emptyBst = new BinarySearchTree(); 00045 assertEquals("expected to get -1 as min on empty BST", -1, emptyBst.min_squander()); 00046 assertTrue("repOK on empty BST failed after calling max method", emptyBst.repOk()); 00047 } 00048 00049 @Test 00050 public void testMax_squander() { 00051 assertEquals("Wrong return value for the max_squander method", 6, bst.max_squander()); 00052 assertTrue("repOK failed after calling min method", bst.repOk()); 00053 BinarySearchTree emptyBst = new BinarySearchTree(); 00054 assertEquals("expected to get -1 as max on empty BST", -1, emptyBst.max_squander()); 00055 assertTrue("repOK on empty BST failed after calling min method", emptyBst.repOk()); 00056 } 00057 00058 @Test 00059 public void testFindNode_squander() { 00060 for (Node n : nodes) { 00061 assertEquals("Wrong node found using findNode", n, bst.findNode_squander(n.getKey())); 00062 assertTrue("repOK failed after calling findNode for key " + n.getKey(), bst.repOk()); 00063 } 00064 int nonExistentKey = 0; 00065 assertEquals("Expected to get null for the non-existend node", null, bst.findNode_squander(nonExistentKey)); 00066 } 00067 00068 @Test 00069 public void testRemoveNode_squander() { 00070 for (int i = 0; i < nodes.length; i++) { 00071 Node n = nodes[i]; 00072 bst.removeNode_squander(n); 00073 assertTrue("repOK failed after calling removeNode for key " + n.getKey(), bst.repOk()); 00074 assertEquals(nodes.length - i - 1, bst.size()); 00075 assertTrue("nodeToRemove is still there", bst.findNode(n.getKey()) == null); 00076 } 00077 } 00078 00079 @Test 00080 public void testInsertNode_squander() { 00081 BinarySearchTree bst = new BinarySearchTree(); 00082 for (int i = 0; i < keys.length; i++) { 00083 Node n = new Node(i); 00084 bst.insertNode_squander(n); 00085 assertTrue("repOK failed after calling insertNode for key " + n.getKey(), bst.repOk()); 00086 assertEquals(i + 1, bst.size()); 00087 assertTrue("nodeToInsert is not there", bst.findNode(n.getKey()) != null); 00088 } 00089 } 00090 00091 @Test 00092 public void testInsertKey_squander() { 00093 BinarySearchTree bst = new BinarySearchTree(); 00094 for (int i = 0; i < keys.length; i++) { 00095 bst.insertKey_squander(i); 00096 assertTrue("repOK failed after calling insertNode for key " + i, bst.repOk()); 00097 assertEquals(i + 1, bst.size()); 00098 assertTrue("nodeToInsert is not there", bst.findNode(i) != null); 00099 } 00100 } 00101 00102 @Test 00103 public void testGetAllNodes_squander() { 00104 Node[] nodes = bst.getAllNodes_squander(); 00105 Assert.assertNotNull(nodes); 00106 int[] keys = new int[nodes.length]; 00107 int idx = 0; 00108 for (Node node : nodes) { 00109 keys[idx++] = node.key; 00110 } 00111 TestUtils.assertArraysEqualNoOrdering(new int[] {2, -2, -4, 3, 6}, keys); 00112 } 00113 00114 @Test 00115 public void testInsertMix() { 00116 BinarySearchTree bst = new BinarySearchTree(); 00117 for (int i = 0; i < keys.length; i++) { 00118 Node n = new Node(i); 00119 if (i % 2 == 0) 00120 bst.insertNode_squander(n); 00121 else 00122 bst.insert(n); 00123 assertTrue("repOK failed after calling insertNode for key " + n.getKey(), bst.repOk()); 00124 assertEquals(i + 1, bst.size()); 00125 assertTrue("nodeToInsert is not there", bst.findNode(n.getKey()) != null); 00126 } 00127 } 00128 00129 public static void main(String[] args) { 00130 org.junit.runner.JUnitCore.main(BinarySearchTreeTest.class.getName()); 00131 } 00132 00133 }