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_noSpecFld;
00016 import edu.mit.csail.sdg.squander.examples.bst.BST_noSpecFld.Node;
00017 import edu.mit.csail.sdg.squander.util.test.TestUtils;
00018
00019
00020 public class BST_noSpecFldTest {
00021
00022 private BST_noSpecFld 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_noSpecFld();
00037 for (Node n : nodes)
00038 bst.insertNode(n);
00039 }
00040
00041 @Test
00042 public void testMin_squander() {
00043
00044
00045
00046
00047 BST_noSpecFld emptyBst = new BST_noSpecFld();
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
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_noSpecFld emptyBst = new BST_noSpecFld();
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_noSpecFld().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_noSpecFld bst = new BST_noSpecFld();
00094 BST_noSpecFld bstSq = new BST_noSpecFld();
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_noSpecFld bst = new BST_noSpecFld();
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_noSpecFld bst = new BST_noSpecFld();
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_noSpecFldTest.class.getName());
00146 }
00147
00148 }