Complete the following methods and make sure all the JUnit tests pass nodeExists
ID: 3813749 • 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
HI, PLease find my implementation.
Please let me know in case of any issue.
import java.util.AbstractSet;
import java.util.Iterator;
/**
* Implementation of an abstract set using an array-based binary tree. This is used to help teach binary trees and will
* have more details explained in future lectures.
*
* @param Data type (which must be Comparable) of the elements in this tree.
*/
public class ArrayBinaryTree<E extends Comparable<E>> extends AbstractSet {
/** Index where the root node can be found. */
private static final int ROOT = 0;
/** Array used to store the elements in the binary tree. */
private E[] store;
/** Number of elements within the tree. */
private int size;
/**
* Initializes this ArrayBinaryTree object to be empty. This creates the array in which items will be stored.
*/
@SuppressWarnings("unchecked")
public ArrayBinaryTree() {
store = (E[]) new Comparable[31];
size = 0;
}
/**
* 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(idx < 0 || idx >= store.length)
return false;
if(store[idx] != null)
return true;
else
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(idx < 0 || idx >= size)
return null;
for(int i=idx+1; i<size; i++)
if(store[idx] != null)
return store[idx];
return null;*/
int leftChildIndex = idx*2 + 1;
if(leftChildIndex < 0 || leftChildIndex >= store.length)
return null;
return store[leftChildIndex];
}
/**
* 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(idx == 0) // root does not have parent
return null;
int parentIndex = (idx-1)/2;
if(parentIndex < 0 || parentIndex >= store.length)
return null;
return store[parentIndex];
}
/**
* Returns the size of this ArrayBinaryTree object.
*
* @return the size of this ArrayBinaryTree object.
*/
@Override
public int size() {
return size;
}
/**
* Returns an iterator that will return the elements in this ArrayBinaryTree, but without any specific ordering.
*
* @return Iterator positioned at the smallest element in this ArrayBinaryTree object.
*/
@Override
public Iterator iterator() {
// Skipped for now.
throw new UnsupportedOperationException();
}
/**
* Determines if there is at least one element in this ArrayBinaryTree object that equals a specified element.
*
* @param obj - the element sought in this ArrayBinaryTree object.
* @return true - if there is an element in this ArrayBinaryTree object that equals obj; otherwise, return false.
* @throws ClassCastException - if obj cannot be compared to the elements in this ArrayBinaryTree object.
* @throws NullPointerException - if obj is null.
*/
@Override
public boolean contains(Object obj) {
int index = getIndex(obj);
return index != -1;
}
/**
* Finds the index at which a specified element exist or -1 if the object is not in the tree.
*
* @param obj Element whose Entry is sought.
* @return Element in the treeEntry object in the ArrayBinaryTree that holds obj; if no Entry exists, returns null.
*/
protected int getIndex(Object obj) {
// Handle the special case of obj being null -- we can return null since we
// KNOW this not to be in the tree. By definition, we are to throw this exception.
if (obj == null) {
throw new NullPointerException();
}
// Keep searching while there might be a node at the current index within the tree
for (int idx = ROOT; idx < store.length; idx++ ) {
// If we have fallen off the bottom of the tree, obj cannot be found
// within it.
if (store[idx] == null) {
return -1;
}
E curElement = store[idx];
@SuppressWarnings("unchecked")
int comp = curElement.compareTo((E) obj);
if (comp == 0) {
return idx;
}
}
// We made it through the tree and did not find the element; return that it was not found.
return -1;
}
}
/*
Sample run:
PASSED: testLeftChildNoEntry
PASSED: testLeftChildNullEntry
PASSED: testLeftChildValid
PASSED: testNoParent
PASSED: testNodeExistsNoEntry
PASSED: testNodeExistsNullEntry
PASSED: testNodeExistsValid
PASSED: testParentValid
===============================================
Default test
Tests run: 8, Failures: 0, Skips: 0
===============================================
===============================================
Default suite
Total tests run: 8, Failures: 0, Skips: 0
===============================================
*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.