I need help with the following Java code /** * An interface for describing basic
ID: 3910650 • Letter: I
Question
I need help with the following Java code
/**
* An interface for describing basic getter functionality for a node
*
* @author
*
* @param <K>
* @param <V>
*/
public interface EntryNode<K, V> {
/**
* Returns the parent node of this node. If there is no parent node,
* <code>null</code> is returned.
*
* @return
*/
public EntryNode<K, V> parent();
/**
*
* <p>
* Returns the child node of this node. If a node has multiple children,
* then this returns the left-most child. E.g.,
* </p>
*
* <pre>
* Parent
* |
* null <-> Child <-> Sibling <-> Sibling ...
* </pre>
* <p>
* If there is no child node, <code>null</code> is returned.
* </p>
*
* @return
*/
public EntryNode<K, V> child();
/**
* Returns the next sibling of this node. If there is no next sibling,
* <code>null</code> is returned.
*
* @return
*/
public EntryNode<K, V> next();
/**
* Returns the previous sibling of this node. If there is no previous
* sibling, <code>null</code> is returned.
*
* @return
*/
public EntryNode<K, V> prev();
/**
* Returns the (non-null) key for this node.
*
* @return
*/
public K key();
/**
* Returns the value for this node.
*
* @return
*/
public V value();
}
An entry tree is a rooted tree with each node having any number of unordered children that are each given a unique key of type K. The root node is a dummy node with no key (key is null). Since the children of each node have different keys, a unique sequence of keys is obtained by walking down any path from the root to any other node and concatenating the keys at these nodes in order. So each path from the root to any other node corresponds to a unique sequence of keys. In addition to the key type K, there is another data type V called a value type. The root has no value (value is null), whereas every leaf node that is not the root has a value. Any internal node that is not the root either has a value or has no value. A pair of key sequence and value is called an entry. An entry tree is used to represent a mapping from key sequences to values with the property that if a node other than the root has a value, then key sequence on the path from the root to the node is mapped to the value. Entry trees are useful as a data structure for representing a dictionary with the key type K being Character and the value type V being String, and an Internet IP address directory in which each unique IP address as a sequence of Integer is assigned to an organization as a value.
An entry tree is implemented by using a linked structure,
import java.util.Arrays;
/**
*
*@author
*
* An entry tree class
* Add Javadoc comments to each method
*/
public class EntryTree<K, V> {
/**
* dummy root node made public for grading
*/
protected Node root;
/**
* prefixlen is the largest index such that the keys in the subarray keyarr
* from index 0 to index prefixlen - 1 are, respectively, with the nodes on
* the path from the root to a node. prefixlen is computed by a private
* method shared by both search() and prefix() to avoid duplication of code.
*/
protected int prefixlen;
protected class Node implements EntryNode<K, V> {
protected Node child; // link to the first child node
protected Node parent; // link to the parent node
protected Node prev; // link to the previous sibling
protected Node next; // link to the next sibling
protected K key; // the key for this node
protected V value; // the value at this node
public Node(K aKey, V aValue) {
key = aKey;
value = aValue;
child = null;
parent = null;
prev = null;
next = null;
}
@Override
public EntryNode<K, V> parent() {
// TODO Auto-generated method stub
return null;
}
@Override
public EntryNode<K, V> child() {
// TODO Auto-generated method stub
return null;
}
@Override
public EntryNode<K, V> next() {
// TODO Auto-generated method stub
return null;
}
@Override
public EntryNode<K, V> prev() {
// TODO Auto-generated method stub
return null;
}
@Override
public K key() {
// TODO Auto-generated method stub
return null;
}
@Override
public V value() {
// TODO Auto-generated method stub
return null;
}
}
public EntryTree() {
root = new Node(null, null);
}
/**
* Returns the value of the entry with a specified key sequence, or null if
* this tree contains no entry with the key sequence.
*
* @param keyarr
* @return
*/
public V search(K[] keyarr) {
// TODO
return null;
}
/**
* The method returns an array of type K[] with the longest prefix of the
* key sequence specified in keyarr such that the keys in the prefix label
* the nodes on the path from the root to a node. The length of the returned
* array is the length of the longest prefix.
*
* @param keyarr
* @return
*/
public K[] prefix(K[] keyarr) {
// TODO
return null; // TODO
// Hint: An array of the same type as keyarr can be created with
// Arrays.copyOf().
}
/**
* The method locates the node P corresponding to the longest prefix of the
* key sequence specified in keyarr such that the keys in the prefix label
* the nodes on the path from the root to the node. If the length of the
* prefix is equal to the length of keyarr, then the method places aValue at
* the node P and returns true. Otherwise, the method creates a new path of
* nodes (starting at a node S) labelled by the corresponding suffix for the
* prefix, connects the prefix path and suffix path together by making the
* node S a child of the node P, and returns true.
*
* @param keyarr
* @param aValue
* @return
*/
public boolean add(K[] keyarr, V aValue) {
// TODO
return false;
}
/**
* Removes the entry for a key sequence from this tree and returns its value
* if it is present. Otherwise, it makes no change to the tree and returns
* null.
*
* @param keyarr
* @return
*/
public V remove(K[] keyarr) {
// TODO
return null;
}
/**
* The method prints the tree on the console in the output format shown in
* an example output file.
*/
public void showTree() {
// TODO
}
/**
* Returns all values in this tree together with their keys.
* The order of outputs would be similar to level order traversal,
* i.e., first you would get all values together with their keys in
* first level from left to right, then second level, and so on.
* If tree has no values then it would return null.
*
* For example, for the example image given in description, the returned
* String[][] would be equal to {{"IA","Grow"},{"ISU","CS228"}};
*
*/
public String[][] getAll()
{
// TODO
return null;
}
}
Explanation / Answer
I have implemented everything except the getAll method because only this method was not described properly. Please post a different question for getAll method with more description.
Below is your code of EntryTree.java
/**
*
* @author
*
*
*
* An entry tree class
*
* Add Javadoc comments to each method
*
*/
public class EntryTree<K, V> {
/**
*
* dummy root node made public for grading
*
*/
protected Node root;
/**
*
* prefixlen is the largest index such that the keys in the subarray keyarr
*
* from index 0 to index prefixlen - 1 are, respectively, with the nodes on
*
* the path from the root to a node. prefixlen is computed by a private
*
* method shared by both search() and prefix() to avoid duplication of code.
*
*/
protected int prefixlen;
protected class Node implements EntryNode<K, V> {
protected Node child; // link to the first child node
protected Node parent; // link to the parent node
protected Node prev; // link to the previous sibling
protected Node next; // link to the next sibling
protected K key; // the key for this node
protected V value; // the value at this node
public Node(K aKey, V aValue) {
key = aKey;
value = aValue;
child = null;
parent = null;
prev = null;
next = null;
}
@Override
public EntryNode<K, V> parent() {
// TODO Auto-generated method stub
return parent;
}
@Override
public EntryNode<K, V> child() {
// TODO Auto-generated method stub
return child;
}
@Override
public EntryNode<K, V> next() {
// TODO Auto-generated method stub
return next;
}
@Override
public EntryNode<K, V> prev() {
// TODO Auto-generated method stub
return prev;
}
@Override
public K key() {
// TODO Auto-generated method stub
return key;
}
@Override
public V value() {
// TODO Auto-generated method stub
return value;
}
}
public EntryTree() {
root = new Node(null, null);
}
/**
*
* Returns the value of the entry with a specified key sequence, or null if
*
* this tree contains no entry with the key sequence or its length is 0.
*
* If any element of keyarr is null, then the method throws a
* NullPointerException.
*
* @param keyarr
*
* @return
*
*/
public V search(K[] keyarr) {
// Start at the root
Node cursor = root;
// Advance through each layer, looking for the correct key value from
// each child
for (int i = 0; i < keyarr.length; i++) {
cursor = findChildWithKey(cursor, keyarr[i]);
if (cursor == null) {
return null;
}
}
return cursor.value;
}
/**
*
* The method returns an array of type K[] with the longest prefix of the
*
* key sequence specified in keyarr such that the keys in the prefix label
*
* the nodes on the path from the root to a node. The length of the returned
*
* array is the length of the longest prefix.
*
* Returns null is keyarr is null or length is 0.
*
* If any element of keyarr is null, then the method throws a
* NullPointerException.
*
* @param keyarr
*
* @return
*
*/
public K[] prefix(K[] keyarr) {
// Check for bad values
if (keyarr == null || keyarr.length == 0) {
return null;
}
int retLength = 0;
// Start at the root
Node cursor = root;
for (int i = 0; i < keyarr.length; i++) {
if (keyarr[i] == null) {
throw new NullPointerException();
}
cursor = findChildWithKey(cursor, keyarr[i]);
if (cursor == null) {
break;
}
retLength++;
}
K[] ret = Arrays.copyOf(keyarr, retLength);
return ret;
}
/**
*
* The method locates the node P corresponding to the longest prefix of the
*
* key sequence specified in keyarr such that the keys in the prefix label
*
* the nodes on the path from the root to the node. If the length of the
*
* prefix is equal to the length of keyarr, then the method places aValue at
*
* the node P and returns true. Otherwise, the method creates a new path of
*
* nodes (starting at a node S) labelled by the corresponding suffix for the
*
* prefix, connects the prefix path and suffix path together by making the
*
* node S a child of the node P, and returns true.
*
*
*
* @param keyarr
*
* @param aValue
*
* @return
*
*/
public boolean add(K[] keyarr, V aValue) {
// Check for bad values
if (keyarr == null || keyarr.length == 0 || aValue == null) {
return false;
}
// Start at the root
Node cursor = root;
for (int i = 0; i < keyarr.length; i++) {
if (keyarr[i] == null) {
throw new NullPointerException();
}
Node childNode = findChildWithKey(cursor, keyarr[i]);
if (childNode == null) {
// Witness the awesome power of childbirth
childNode = new Node(keyarr[i], null);
childNode.parent = cursor;
if (cursor.child == null) {
childNode.parent.child = childNode;
}
// Link to siblings
else {
Node siblingCursor = cursor.child;
while (siblingCursor.next != null) {
siblingCursor = siblingCursor.next;
}
siblingCursor.next = childNode;
childNode.prev = siblingCursor;
}
}
cursor = childNode;
}
cursor.value = aValue;
return true;
}
/**
*
* Removes the entry for a key sequence from this tree and returns its value
*
* if it is present. Otherwise, it makes no change to the tree and returns
*
* null.
*
*
*
* @param keyarr
*
* @return
*
*/
public V remove(K[] keyarr) {
// Check for bad values
if (keyarr == null || keyarr.length == 0) {
return null;
}
// Start at the root
Node cursor = root;
V ret;
// Advance through every keyarr value
for (int i = 0; i < keyarr.length; i++) {
// Check for null values (I put this here to save a loop)
if (keyarr[i] == null) {
throw new NullPointerException();
}
// Find the child with the key value
cursor = findChildWithKey(cursor, keyarr[i]);
// If no child with key value, return null (keyarr does not exist)
if (cursor == null) {
return null;
}
}
// At this point we've found the cursor that corresponds to the given
// keyarr
ret = cursor.value;
// Set that Node's value to null, so it can be checked for leaf removal
cursor.value = null;
// Trim the tree
removeLeafNodesUpward(cursor);
return ret;
}
/**
*
* The method prints the tree on the console in the output format shown in
*
* an example output file.
*
*/
public void showTree() {
Node cursor = root;
printChildrenRecursive(0, cursor);
}
private Node findChildWithKey(Node cursor, K key) {
if (cursor.child == null) {
return null;
}
// Sets the cursor to the first child in the linked list
cursor = cursor.child;
while ((cursor != null) && !cursor.key.equals(key)) {
// Go to the next sibling
cursor = cursor.next;
}
return cursor;
}
private void printChildrenRecursive(int numLevels, Node cursor) {
// If this cursor doesn't exist, then we have nothing to print
if (cursor == null) {
return;
}
// Advance through the siblings
while (cursor != null) {
// Put dem tabs in to make it saucy lookin'
for (int i = 0; i < numLevels; i++) {
System.out.print(" ");
}
// Print out the key and value
System.out.print(cursor.key + " -> " + cursor.value + " ");
// Recursive call - Prints all of this Node's children
printChildrenRecursive(numLevels + 1, cursor.child);
// Advance to next sibling
cursor = cursor.next;
}
}
private void removeLeafNodesUpward(Node cursor) {
// If cursor is null, get out of here
if (cursor == null) {
return;
}
if (cursor.child == null && cursor.value == null) {
if (cursor.parent != null && cursor.parent.child.equals(cursor)) {
cursor.parent.child = cursor.next;
removeLeafNodesUpward(cursor.parent);
}
if (cursor.next != null) {
cursor.next.prev = cursor.prev;
}
if (cursor.prev != null) {
cursor.prev.next = cursor.next;
}
}
}
/**
*
* Returns all values in this tree together with their keys.
*
* The order of outputs would be similar to level order traversal,
*
* i.e., first you would get all values together with their keys in
*
* first level from left to right, then second level, and so on.
*
* If tree has no values then it would return null.
*
*
*
* For example, for the example image given in description, the returned
*
* String[][] would be equal to {{"IA","Grow"},{"ISU","CS228"}};
*
*
*
*/
public String[][] getAll()
{
// TODO
return null;
}
}