Complete the following methods and make sure all the JUnit tests pass nodeExists
ID: 3813473 • Letter: C
Question
Complete the following methods and make sure all the JUnit tests pass
nodeExists(int idx) -- this should return true if the tree has an element at index idx and false when there is no such element
leftChild(int idx) -- returns the element that is the left child of the one at index idx. Your method should return null if idx does not have a left child.
parent(int idx) -- returns the element that is the parent of the one at index idx. Your method should return null if idx does not have a parent.
---------------------------------------------------------------------------------------------------------------------------------------------------------
Make sure you code pass all the JUnit tests.
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNotNull;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
import java.lang.reflect.Field;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import org.junit.Before;
import org.junit.Test;
public class ArrayBinaryTreeTest {
@Test
public void testNodeExistsValid() throws IllegalAccessException, IllegalArgumentException, InvocationTargetException {
for (int i = 0; i < ELEMENT_INDEX.length; i++ ) {
assertTrue("nodeExists() should return true when an element is in the backing store at that index (" +
ELEMENT_INDEX[i] + ")", nodeExists(instance, ELEMENT_INDEX[i]));
Comparable[] backingStore = getStore(instance);
assertNotNull("nodeExists() should not make any assignments to store.", backingStore);
assertEquals("nodeExists() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("nodeExists() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
}
}
@Test
public void testNodeExistsNullEntry() throws IllegalAccessException, IllegalArgumentException,
InvocationTargetException {
for (int idx = 11; idx < 31; idx++ ) {
if ((idx != 20) && (idx != 21)) {
assertFalse("nodeExists() should return false when backing store has null at a given index (" + idx + ")",
nodeExists(instance, idx));
Comparable[] backingStore = getStore(instance);
assertNotNull("nodeExists() should not make any assignments to store.", backingStore);
assertEquals("nodeExists() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("nodeExists() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
}
}
}
@Test
public void testNodeExistsNoEntry() throws IllegalAccessException, IllegalArgumentException {
try {
assertFalse("nodeExists() should return false alled with an index equal to the backing store size (31)",
nodeExists(instance, 31));
Comparable[] backingStore = getStore(instance);
assertNotNull("nodeExists() should not make any assignments to store.", backingStore);
assertEquals("nodeExists() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("nodeExists() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
} catch (InvocationTargetException ioobe) {
fail("nodeExists() should return false (rather than create an IndexOutOfBoundsException) when called with an index equal to the backing store size (31).");
}
try {
assertFalse("nodeExists() should return false alled with an index larger than the backing store size (35)",
nodeExists(instance, 35));
Comparable[] backingStore = getStore(instance);
assertNotNull("nodeExists() should not make any assignments to store.", backingStore);
assertEquals("nodeExists() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("nodeExists() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
} catch (InvocationTargetException ioobe) {
fail("nodeExists() should return false (rather than create an IndexOutOfBoundsException) when called with an index larger than the backing store size (35).");
}
}
@Test
public void testLeftChildValid() throws IllegalAccessException, IllegalArgumentException, InvocationTargetException {
for (int i = 0; i < ELEMENT_INDEX.length; i++ ) {
if (LEFT_VALUE[i] != null) {
assertEquals("leftChild() should return element from backing store's entry where the left child exists (idx was " +
ELEMENT_INDEX[i] + ")", LEFT_VALUE[i], leftChild(instance, ELEMENT_INDEX[i]));
Comparable[] backingStore = getStore(instance);
assertNotNull("leftChild() should not make any assignments to store.", backingStore);
assertEquals("leftChild() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("leftChild() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
}
}
}
@Test
public void testLeftChildNullEntry() throws IllegalAccessException, IllegalArgumentException,
InvocationTargetException {
for (int i = 0; i < ELEMENT_INDEX.length; i++ ) {
if (LEFT_VALUE[i] == null) {
assertNull("leftChild() should return null when the backing store has a null at the entry where the left child should appear (idx was " +
ELEMENT_INDEX[i] + ")", leftChild(instance, ELEMENT_INDEX[i]));
Comparable[] backingStore = getStore(instance);
assertNotNull("leftChild() should not make any assignments to store.", backingStore);
assertEquals("leftChild() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("leftChild() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
}
}
}
@Test
public void testLeftChildNoEntry() throws IllegalAccessException, IllegalArgumentException {
try {
assertNull("leftChild() should return null when called with an index whose left child is beyond the bounds of the backing store (20 so left child of 41)",
leftChild(instance, 20));
Comparable[] backingStore = getStore(instance);
assertNotNull("leftChild() should not make any assignments to store.", backingStore);
assertEquals("leftChild() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("leftChild() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
} catch (InvocationTargetException ioobe) {
fail("leftChild() should return null (rather than create an IndexOutOfBoundsException) when called with an index whose left child is beyond the bounds of the backing store (20 so left child of 41).");
}
try {
assertNull("leftChild() should return null when called with an index whose left child is beyond the bounds of the backing store (15 so left child of 31)",
leftChild(instance, 15));
Comparable[] backingStore = getStore(instance);
assertNotNull("leftChild() should not make any assignments to store.", backingStore);
assertEquals("leftChild() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("leftChild() should not make any assignments to the entries in store. At index " +
ELEMENT_INDEX[j], ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
} catch (InvocationTargetException ioobe) {
fail("leftChild() should return null (rather than create an IndexOutOfBoundsException) when called with an index whose left child is beyond the bounds of the backing store (15 so left child of 31).");
}
}
@Test
public void testParentValid() throws IllegalAccessException, IllegalArgumentException, InvocationTargetException {
for (int i = 0; i < ELEMENT_INDEX.length; i++ ) {
if (PARENT_VALUE[i] != null) {
assertEquals("parent() should return element from backing store's entry where the entry was not the root (idx was " +
ELEMENT_INDEX[i] + ")", PARENT_VALUE[i], parent(instance, ELEMENT_INDEX[i]));
Comparable[] backingStore = getStore(instance);
assertNotNull("parent() should not make any assignments to store.", backingStore);
assertEquals("parent() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("parent() should not make any assignments to the entries in store. At index " + ELEMENT_INDEX[j],
ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
}
}
}
@Test
public void testNoParent() throws IllegalAccessException, IllegalArgumentException, InvocationTargetException {
assertNull("parent() should return null when root index is passed in", parent(instance, ELEMENT_INDEX[0]));
Comparable[] backingStore = getStore(instance);
assertNotNull("parent() should not make any assignments to store.", backingStore);
assertEquals("parent() should not make any assignments to store.", 31, backingStore.length);
for (int j = 0; j < ELEMENT_INDEX.length; j++ ) {
assertEquals("parent() should not make any assignments to the entries in store. At index " + ELEMENT_INDEX[j],
ELEMENT_VALUE[j], backingStore[ELEMENT_INDEX[j]]);
}
}
private static final int[] ELEMENT_INDEX = { 0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 20, 21 };
private static final String[] ELEMENT_VALUE = { "h", "g", "i", "c", "f", "j", "a", "b", "d", "e",
"Why be consistent?", "k" };
private static final String[] LEFT_VALUE = { "g", "c", null, "a", "d", null, null, null, null, "k", null, null };
private static final String[] PARENT_VALUE = { null, "h", "h", "g", "g", "i", "c", "c", "f", "f", "d", "e" };
private Field storeField;
private Field sizeField;
private Method nodeExistsMethod;
private Method leftChildMethod;
private Method parentMethod;
private ArrayBinaryTree instance;
public void setSize(ArrayBinaryTree tree, int newSize) throws IllegalArgumentException,
IllegalAccessException {
sizeField.setInt(tree, newSize);
}
public Comparable[] getStore(ArrayBinaryTree tree) throws IllegalArgumentException,
IllegalAccessException {
return (Comparable[]) storeField.get(tree);
}
public boolean nodeExists(ArrayBinaryTree tree, int idx) throws IllegalAccessException,
IllegalArgumentException, InvocationTargetException {
return (boolean) nodeExistsMethod.invoke(tree, idx);
}
public String leftChild(ArrayBinaryTree tree, int idx) throws IllegalAccessException,
IllegalArgumentException, InvocationTargetException {
return (String) leftChildMethod.invoke(tree, idx);
}
public String parent(ArrayBinaryTree tree, int idx) throws IllegalAccessException, IllegalArgumentException,
InvocationTargetException {
return (String) parentMethod.invoke(tree, idx);
}
@Before
public void setUp() throws IllegalArgumentException, IllegalAccessException {
Class arrayBinaryTreeKlass = ArrayBinaryTree.class;
try {
storeField = arrayBinaryTreeKlass.getDeclaredField("store");
assertTrue("ArrayBinaryTree class should not have its fields changed -- "store" is not available as the backing store.",
storeField.getType().isArray());
assertEquals("ArrayBinaryTree class should not have its fields changed -- "store" is not available as the backing store.",
Comparable.class, storeField.getType().getComponentType());
storeField.setAccessible(true);
} catch (Exception e) {
fail("ArrayBinaryTree class should not have its fields changed -- "store" is not available as the backing store.");
}
try {
sizeField = arrayBinaryTreeKlass.getDeclaredField("size");
sizeField.setAccessible(true);
} catch (Exception e) {
fail("ArrayBinaryTree class should not have its fields changed -- "size" is not available to record the size.");
}
try {
nodeExistsMethod = arrayBinaryTreeKlass.getDeclaredMethod("nodeExists", Integer.TYPE);
nodeExistsMethod.setAccessible(true);
} catch (Exception e) {
fail("ArrayBinaryTree class still needs the nodeExists(int) method");
}
try {
leftChildMethod = arrayBinaryTreeKlass.getDeclaredMethod("leftChild", Integer.TYPE);
leftChildMethod.setAccessible(true);
} catch (Exception e) {
fail("ArrayBinaryTree class still needs the leftChild(int) method");
}
try {
parentMethod = arrayBinaryTreeKlass.getDeclaredMethod("parent", Integer.TYPE);
parentMethod.setAccessible(true);
} catch (Exception e) {
fail("ArrayBinaryTree class still needs the parent(int) method");
}
instance = new ArrayBinaryTree<>();
Comparable[] backingStore = getStore(instance);
for (int i = 0; i < ELEMENT_INDEX.length; i++ ) {
backingStore[ELEMENT_INDEX[i]] = ELEMENT_VALUE[i];
}
setSize(instance, ELEMENT_INDEX.length);
}
}
Explanation / Answer
Here is the code for the three methods you asked for:
/**
* Checks if the binary tree contains an element at the given index. This requires checking both that the array is
* large enough (to avoid triggering an exception) AND (when the array is large enough) that the array has a non-null
* value at that index.
*
* @param idx Index to be checked out.
* @return True if there is an element at the given index; false otherwise.
*/
private boolean nodeExists(int idx) {
if(store[idx] == null) //If the given idx doesn't have valid element.
return false; //return false.
if(idx >= 0 && idx < size && store[idx] != null) //If the index is in valid range, and holds a non-null value.
return true; //return true.
return false; //return false.
}
/**
* Given an index, returns the element in that node's left child. If the left child node does not exist, null should
* be returned. It is important that this NOT trigger an index out of bounds exception.
*
* @param idx Index of the node for which we want the left child.
* @return Value of the node's left child or null if no left child exists.
*/
private E leftChild(int idx) {
if(store[idx] == null) //If the given idx doesn't have valid element.
return null; //return null.
int temp = (idx + 1) * 2 - 1; //Calculate left child location.
if(nodeExists(temp)) //If the left child exists.
return store[temp]; //Return left child.
return null; //Return null otherwise.
}
/**
* Given an index, returns the value of that node's parent. If the node is the root (and so has no parent), null
* should be returned. It is important that this NOT trigger an index out of bounds exception.
*
* @param idx Index of the node for which we want the parent.
* @return Value of the node's parent or null if no parent exists.
*/
private E parent(int idx) {
if(store[idx] == null) //If the given idx doesn't have valid element.
return null; //return null.
int temp = (idx - 1) / 2; //Calculate parent location.
if(nodeExists(temp)) //If parent location exists.
return store[temp]; //Return parent.
return null; //Return null.
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.