I need help with the following Java code An entry tree is a rooted tree with eac
ID: 3910651 • Letter: I
Question
I need help with the following Java code
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 Vcalled 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, see the image below.
I
n this structure, the children of a node are stored in a double linked list with no dummy node and not circular. Each node has a child link referring to the first node of the doubly linked list for its children. The child link of the node is null if it has no children. The nodes in the doubly linked list are connected together with links prevand next. The prev link of the first node in any doubly linked list is always null; the next link of the last node in any doubly linked list is always null. Each node has a parent link; the parent link of the root node is always null. The parent link of every child node refers to its parent node. In addition, each node has two types of data: keyof type K and a value of type V. The key and value fields of the root node are always null. Every other node has a key field that is not null. If a node has no value, then its value field is null. The value field of every leaf node that is not the root is never null.
Requirement for class EntryTree<K, V>
Write a public class named EntryTree with six public methods. The specification of each method is given below. You should introduce common private methods to avoid duplication of code. Note that a recursive method is easier to write than an iterative method. Both types of methods are acceptable for this assignment, with only exception of the add method, which you must implement using iterative version instead of recursive. We suggest that you first write the showTree method so that you can check if the constructed tree by other methods is correct by printing out the tree.
The method
public V search(K[] keyarr)
The method
public K[] prefix(K[] keyarr)
The method
public boolean add(K[] keyarr, V aValue)
returns false if keyarr is null, its length is 0, or aValue is null. If any element of keyarr is null, then the method throws a NullPointerException. 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 (in place of its old value) 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.
The method
public V remove(K[] keyarr)
returns null if keyarr is null or its length is 0. If any element of keyarr is null, then the method throws a NullPointerException. The method returns null if the tree contains no entry with the key sequence specified in keyarr. Otherwise, the method finds the path with the key sequence, saves the value field of the node at the end of the path, sets the value field to null. The following rules are used to decide whether the current node and higher nodes on the path need to be removed. Consider a non-root node whose value is null. If the node is a leaf node (has no children), then the node is removed. Otherwise, if the node is the parent of an only child and the child node is removed, then the node is removed. Finally, the method returns the saved old value.
The method
public void showTree()
prints the tree on the console in the output format shown below. If the tree has no entry, then the method just prints out the line for the dummy root node. One more method named getAll is described in the given template.
/**
* An interface for describing basic getter functionality for a node
*/
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();
}
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 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) {
// 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.
* 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) {
// 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;
}
}
root prev parent key value child next null nu nu null null add ISU CS228 prev parent key value child next add IA Grow null null null prev parent key value child next prev parent key value child next null null "Grow" |null null prev parent key value child next null "CS228" null nullExplanation / Answer
I have implemented all the functions except getAll method. Because the description of only that method was not that clear. Please post this method only saperatly with little more description.
Below is your EntryTree.java class.
/**
*
* @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;
}
}