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