Create a generic class that implements the interface with the methods directions
ID: 3865176 • Letter: C
Question
Create a generic class that implements the interface with the methods directions given:
---------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------------
interface LinkedConverterTreeInterface<T>
All Known Implementing Classes:
MorseCodeTree
This is a generic LinkedConverterTreeInterface It is intended for creation of LinkedTrees that do conversion using a LinkedTree Note: usually addNode, fetchNode and LNROutputTraversal would be private
getRoot
Returns a reference to the root
Returns:
reference to root
setRoot
sets the root of the Tree
Parameters:
newNode - a TreeNode that will be the new root
insert
Adds result to the correct position in the tree based on the code This method will call the recursive method addNode
Parameters:
code - the code for the new node to be added
Returns:
the linkedConverterTree with the new node added
addNode
This is a recursive method that adds element to the correct position in the tree based on the code.
Parameters:
root - the root of the tree for this particular recursive instance of addNode
code - the code for this particular recursive instance of addNode
letter - the data of the new TreeNode to be added
fetch
Fetch the data in the tree based on the code This method will call the recursive method fetchNode
Parameters:
code - the code that describes the traversals within the tree
Returns:
the result that corresponds to the code
fetchNode
This is the recursive method that fetches the data of the TreeNode that corresponds with the code
Parameters:
root - the root of the tree for this particular recursive instance of addNode
code - the code for this particular recursive instance of fetchNode
Returns:
the data corresponding to the code
delete
This operation is not supported for a LinkedConverterTree
Parameters:
data - data of node to be deleted
Returns:
reference to the current tree
Throws:
java.lang.UnsupportedOperationException
update
This operation is not supported for a LinkedConverterTree
Returns:
reference to the current tree
Throws:
java.lang.UnsupportedOperationException
buildTree
This method builds the LinkedConverterTree by inserting TreeNodes into their proper locations
toArrayList
Returns an ArrayList of the items in the linked converter Tree in LNR (Inorder) Traversal order Used for testing to make sure tree is built correctly
Returns:
an ArrayList of the items in the linked Tree
LNRoutputTraversal
The recursive method to put the contents of the linked converter tree in an ArrayList LNR (Inorder)
Parameters:
root - the root of the tree for this particular recursive instance
list - the ArrayList that will hold the contents of the tree in LNR order
-----------------------------------------------------------------------------------
Method Summary void addNode(TreeNode root<T>, T code, T letter)This is a recursive method that adds element to the correct position in the tree based on the code. void buildTree()
This method builds the LinkedConverterTree by inserting TreeNodes into their proper locations LinkedConverterTreeInterface delete(T data)
This operation is not supported for a LinkedConverterTree T fetch(java.lang.String code)
Fetch the data in the tree based on the code This method will call the recursive method fetchNode T fetchNode(TreeNode<T> root, T code)
This is the recursive method that fetches the data of the TreeNode that corresponds with the code TreeNode getRoot()
Returns a reference to the root LinkedConverterTreeInterface insert(T code, T result)
Adds result to the correct position in the tree based on the code This method will call the recursive method addNode void LNRoutputTraversal(TreeNode<T> root, java.util.ArrayList<T> list)
The recursive method to put the contents of the linked converter tree in an ArrayList LNR (Inorder) void setRoot(TreeNode<T> newNode)
sets the root of the Tree java.util.ArrayList toArrayList()
Returns an ArrayList of the items in the linked converter Tree in LNR (Inorder) Traversal order Used for testing to make sure tree is built correctly LinkedConverterTreeInterface update()
This operation is not supported for a LinkedConverterTree
Explanation / Answer
MorseCodeTreeTest.java
import static org.junit.Assert.*;
import java.util.ArrayList;
import org.junit.After;
import org.junit.Before;
import org.junit.Test;
public class MorseCodeTreeTest {
MorseCodeTree tree = new MorseCodeTree();
@Before
public void setUp() throws Exception {
}
@After
public void tearDown() throws Exception {
tree = null;
}
@Test
public void testInsert() {
// Since this method calls the recursive method addNode, it will act as a test for the addNode method as well.
// I will add the number 1 into the binary tree, since all the letters have already been added in the initialization of the MorseCodeTree.
// The code for the number 1 is ".----"
// This will create a 5th level in the binary tree, which will store the number 1
tree.insert(".----", "1");
// Now use the morse code for the number 1, to see if it fetches the correct number from the tree. This will let us know
// if it was added into the tree or not.
String letterFetched = tree.fetch(".----");
assertEquals("1", letterFetched);
}
@Test
public void testGetRoot() {
String root;
root = tree.getRoot().getData();
assertEquals("", root);
}
@Test
public void testSetRoot() {
String newRoot;
// the root is initially an empty string
assertEquals("", tree.getRoot().getData());
// Create a new node, which will be use to set as the new root
TreeNode<String> name = new TreeNode <String> ("Nabeel");
// Set the root to be the new node that was created
tree.setRoot(name);
newRoot = tree.getRoot().getData();
assertEquals("Nabeel", newRoot);
}
@Test
public void testFetch() {
// Since this method calls the recursive method fetchNode, it will act as a test for the fetchNode method as well.
String letterFetched;
// "-." is the morse code for the letter n.
letterFetched = tree.fetch("-.");
assertEquals("n", letterFetched);
String letterFetched2;
// "--.-" is the morse code for the letter q.
letterFetched2 = tree.fetch("--.-");
assertEquals("q", letterFetched2);
}
@Test
public void testToArrayList() {
// Since this method calls the LNRoutputTraversal method to arrange the ArrayList in inorder, it will act as a test for the LNRoutputTraversal method as well.
ArrayList<String> list = new ArrayList<String>();
list = tree.toArrayList();
assertEquals("h", list.get(0));
assertEquals("s", list.get(1));
assertEquals("v", list.get(2));
assertEquals("i", list.get(3));
assertEquals("f", list.get(4));
assertEquals("u", list.get(5));
assertEquals("e", list.get(6));
assertEquals("l", list.get(7));
assertEquals("r", list.get(8));
assertEquals("a", list.get(9));
assertEquals("p", list.get(10));
assertEquals("w", list.get(11));
assertEquals("j", list.get(12));
assertEquals("", list.get(13));
assertEquals("b", list.get(14));
assertEquals("d", list.get(15));
assertEquals("x", list.get(16));
assertEquals("n", list.get(17));
assertEquals("c", list.get(18));
assertEquals("k", list.get(19));
assertEquals("y", list.get(20));
assertEquals("t", list.get(21));
assertEquals("z", list.get(22));
assertEquals("g", list.get(23));
assertEquals("q", list.get(24));
assertEquals("m", list.get(25));
assertEquals("o", list.get(26));
}
}
MorseCodeTree.java
import java.util.ArrayList;
public class MorseCodeTree implements LinkedConverterTreeInterface<java.lang.String>
{
private TreeNode<String> root = null; //root of the tree, which is set to null when the tree is empty
private String fetchedLetter; // variable to hold the String letter, which the fetch method will return
/**
* Constructor - calls the buildTree method
*/
public MorseCodeTree()
{
buildTree(); // call the buildTree method to create the tree, and place the letters for the morse code decoder in the correct position.
}
/**
* This is a recursive method that adds element to the correct position in the tree based on the code.
* A '.' (dot) means traverse to the left. A "-" (dash) means traverse to the right.
* The code ".-" would be stored as the right child of the left child of the root.
* Algorithm for the recursive method:
* 1. if there is only one character
* a. if the character is '.' (dot) store to the left of the current root
* b. if the character is "-" (dash) store to the right of the current root
* c. return
*
* 2. if there is more than one character
* a. if the first character is "." (dot) new root becomes the left child
* b. if the first character is "-" (dash) new root becomes the right child
* c. new code becomes all the remaining charcters in the code (beyond the first character)
* d. call addNode(new root, new code, letter)
*
* @param root the root of the tree for this particular recursive instance of addNode
* @param code the code for this particular recursive instance of addNode
* @param letter the data of the new TreeNode to be added
*/
@Override
public void addNode(TreeNode<String> root, String code, String letter)
{
// If there is only one character in the morse code
if(code.length() == 1)
{
// if the character is '.' (dot) store to the left of the current root
if (code.equals("."))
{
root.lc = new TreeNode<String>(letter);
}
// else if the character is "-" (dash) store to the right of the current root
else
{
root.rc = new TreeNode<String>(letter);
}
return;
}
else
{
// if the first character is '.' (dot) new root becomes the left child
if(code.substring(0, 1).equals("."))
{
// recursively call addNode(new root, new code, letter)
//new code becomes all the remaining characters in the code (beyond the first character)
addNode(root.lc, code.substring(1), letter);
}
// else if the first character is "-" (dash) new root becomes the right child
else
{
// recursively call addNode(new root, new code, letter)
//new code becomes all the remaining characters in the code (beyond the first character)
addNode(root.rc, code.substring(1), letter);
}
}
}
/**
* Adds element to the correct position in the tree based on the code
* This method will call the recursive method addNode
*
* @param code the code for the new node to be added
* @param letter the letter for the new node to be added, example "r"
* @return
*/
@Override
public MorseCodeTree insert(java.lang.String code, java.lang.String letter)
{
// calls the recursive method addNode
addNode(root, code, letter);
return this;
}
/**
* This method builds the MorseCodeTree by inserting the nodes of the tree level by level based on the code.
* The root will have a value of "" (empty string)
* level one: insert(".", "e"); insert("-", "t");
* level two: insert("..", "i"); insert(".-", "a"); insert("-.", "n"); insert("--", "m"); etc.
* Look at the tree and the table of codes to letters in the assignment description.
*/
@Override
public void buildTree()
{
//The root will have a value of "" (empty string)
root = new TreeNode<String>("");
// First Level
insert(".", "e");
insert("-", "t");
//Second Level
insert("..", "i");
insert(".-", "a");
insert("-.", "n");
insert("--", "m");
//Third Level
insert("...", "s");
insert("..-", "u");
insert(".-.", "r");
insert(".--", "w");
insert("-..", "d");
insert("-.-", "k");
insert("--.", "g");
insert("---", "o");
//Fourth Level
insert("....", "h");
insert("...-", "v");
insert("..-.", "f");
insert(".-..", "l");
insert(".--.", "p");
insert(".---", "j");
insert("-...", "b");
insert("-..-", "x");
insert("-.-.", "c");
insert("-.--", "y");
insert("--..", "z");
insert("--.-", "q");
}
/**
* Returns a reference to the root
* @return reference to root
*/
@Override
public TreeNode<String> getRoot()
{
return this.root;
}
/**
* sets the root of the of the MorseCodeTree
*
* @param newNode a copy of newNode will be the new root
*/
@Override
public void setRoot(TreeNode<String> newNode) {
root = newNode;
}
/**
* Fetch the data in the tree based on the code
* This method will call the recursive method fetchNode
*
* @param code the code that describes the traversals within the tree
* @return the string (letter) that corresponds to the code
*/
@Override
public java.lang.String fetch(java.lang.String code)
{
// calls the recursive method fetchNode
String letter = fetchNode(root, code);
return letter;
}
/**
* This is the recursive method that fetches the data of the TreeNode that corresponds with the code
* A '.' (dot) means traverse to the left. A "-" (dash) means traverse to the right.
* The code ".-" would fetch the data of the TreeNode stored as the right child of the left child of the root
*
* @param root the root of the tree for this particular recursive instance of addNode
* @param code the code for this particular recursive instance of fetchNode
* @return the string (letter) corresponding to the code
*/
@Override
public java.lang.String fetchNode(TreeNode<java.lang.String> root, java.lang.String code)
{
// If there is only one character in the morse code
if(code.length() == 1)
{
// if the character is '.' (dot) retrieve the data from the left child of root
if (code.equals("."))
{
fetchedLetter = root.lc.getData();
}
// else if the character is '-' (dash) retrieve the data from the right child of root
else
{
fetchedLetter = root.rc.getData();
}
}
else
{
// if the first character is '.' (dot) new root becomes the left child
if(code.substring(0, 1).equals("."))
{
// recursively call fetchNode(new root, new code)
//new code becomes all the remaining characters in the code (beyond the first character)
fetchNode(root.lc, code.substring(1));
}
// if the first character is '-' (dash) new root becomes the right child
else
{
// recursively call fetchNode(new root, new code)
//new code becomes all the remaining characters in the code (beyond the first character)
fetchNode(root.rc, code.substring(1));
}
}
// Return the corresponding letter to the morse code
return fetchedLetter;
}
/**
* Returns an ArrayList of the items in the linked Tree in LNR (Inorder) Traversal order. Used for testing to make sure tree is built correctly
*
* @return an ArrayList of the items in the linked Tree
*/
@Override
public java.util.ArrayList<java.lang.String> toArrayList()
{
ArrayList<String> printTree = new ArrayList<String>();
LNRoutputTraversal(root, printTree);
return printTree;
}
/**
* The recursive method to put the contents of the tree in an ArrayList in LNR (Inorder)
*
* @param root the root of the tree for this particular recursive instance
* @param list the ArrayList that will hold the contents of the tree in LNR order
*/
@Override
public void LNRoutputTraversal(TreeNode<java.lang.String> root, java.util.ArrayList<java.lang.String> list)
{
if(root != null)
{
// recursive method to traverse through the binary tree in LNR (Inorder)
LNRoutputTraversal(root.lc, list);
list.add(root.getData());
LNRoutputTraversal(root.rc, list);
}
}
/**
* This operation is not supported for a LinkedConverterTree
* @param data data of node to be deleted
* @return reference to the current tree
* @throws UnsupportedOperationException
*/
@Override
public LinkedConverterTreeInterface<String> delete(String data) throws UnsupportedOperationException {
return null;
}
/**
* This operation is not supported for a LinkedConverterTree
* @return reference to the current tree
* @throws UnsupportedOperationException
*/
@Override
public LinkedConverterTreeInterface<String> update() throws UnsupportedOperationException {
return null;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.