Create A Program to Implement Classes and Methods in Java Assignment Solution
- Instructions
- Objective
- Requirements and Specifications
Instructions
Objective
Write a java assignment program to implement classes and methods.
Requirements and Specifications
Source Code
SSL NODE
package tests;
/*
* Template for nodes in a singly-linked list.
*/
public class SLLNode {
private E element;
private SLLNode next;
public SLLNode(E e, SLLNode n) {
element = e;
next = n;
}
public E getElement() {
return element;
}
public SLLNode getNext() {
return next;
}
public void setNext(SLLNode n) {
next = n;
}
public void setElement(E e) {
element = e;
}
}
STARTER TEST
package tests;
import static org.junit.Assert.*;
import org.junit.Test;
import model.TreeUtilities;
/*
* Study carefully the test methods below. They suggest:
* - the required class(es) and method(s) to be implement in the `model` package
* - how the required class(es) and method(s) should be implemented
*
* Requirements:
* + Do ***not*** create any new class that is not required by the starter tests.
* All such classes will be ***disregarded*** when grading.
*
* + Any classes you create must reside in the `model` package and be imported properly.
* For example, creating a new class `Foo` in the `model` package should result in:
* import model.Foo;
*
* + For this assignment, you should not need to declare attributes.
* But if you really want to, all attributes you declare in the model classes must be private.
*
* + If necessary, you may define private helper methods.
*/
public class StarterTests {
/*
* Programming Requirements:
*
* - This assignment focuses on the manipulation of:
* + linked-node based trees (see the given TreeNode class)
* + singly-linked nodes (see the given SLLNode class)
*
* Therefore, you are forbidden to use primitive arrays (e.g., Integer[], int[], String[])
* for declaring attributes or local variables. Use only the TreeNode and SLLNode classes given to you.
*
* - In addition, any use of a Java library class or method is also forbidden
* (that is, use selections and loops to build your solution from scratch instead):
*
* - Here are some examples of forbidden classes/methods:
* - Arrays class (e.g., Arrays.copyOf)
* - System class (e.g., System.arrayCopy)
* - ArrayList class
* - String class (e.g., substring).
*
* - The use of some library classes does not require an import statement,
* but these classes are also forbidden to be used.
* - Here are the exceptions (library methods which you are allowed to use if needed):
* - String class (equals, format, length, charAt)
*
* Violating the above programming requirements will result in a penalty (see the assignment instructions for details).
*
* Tests included in this class serve as documentation on how instances of Tree Utilities operate.
*
* Before attempting this assignment,
* it is expected that you already completed background study materials as outlined in the assignment instructions.
*
* Be sure to also read the following sections from your Assignment 1 instructions PDF:
* - The `Requirements of this Assignment` section (page 3)
* - Sections 0 and 1 on the background studies
* - Section 2 on the programming tasks (particularly the hints on tasks on page 7).
*/
/*
* Be sure to study how the TreeNode and SLLNode classes are supposed to work together
* as illustrated in the TestGeneralTrees JUnit class.
*/
/*
* Tests related to getElementsOfRanks
*/
@Test
public void test_getElementsOfRanks_1() {
TreeNode n1 = new TreeNode<>(23);
TreeNode n2 = new TreeNode<>(46);
TreeNode n3 = new TreeNode<>(69);
TreeNode n4 = new TreeNode<>(92);
TreeNode n5 = new TreeNode<>(115);
TreeNode n6 = new TreeNode<>(138);
TreeNode n7 = new TreeNode<>(161);
n2.addChild(n1); n1.setParent(n2);
n2.addChild(n5); n5.setParent(n2);
n2.addChild(n7); n7.setParent(n2);
n1.addChild(n4); n4.setParent(n1);
n1.addChild(n3); n3.setParent(n1);
n5.addChild(n6); n6.setParent(n5);
/*
* Hint: Visualize the tree constructed from the above nodes.
*/
TreeUtilities u = new TreeUtilities();
/*
* Input:
* + The root node `n` of some general tree (see the TreeNode class) storing integers.
* + An integer `i` denoting some lower bound.
* + An integer `j` denoting some upper bound.
* Assumptions:
* 1. Input `n` is not null.
* 2. The organization of nodes in the input tree rooted at `n` is arbitrary:
* no ordering among child node elements can be assumed.
* 3. Input `i` is larger than or equal to 1.
* 4. Input `j` is less than or equal to the size of the tree rooted at `n`.
* 5. i <= j
* Output:
* Return the head node (see the SLLNode class) of a sorted list enumerating
* from the (i)th smallest value to the (j)th smallest value in the input tree rooted at `n`.
*/
SLLNode output = u.getElementsOfRanks(n2, 1, 1);
assertTrue(output.getElement() == 23);
assertNull(output.getNext());
output = u.getElementsOfRanks(n2, 4, 4);
assertTrue(output.getElement() == 92);
assertNull(output.getNext());
output = u.getElementsOfRanks(n2, 7, 7);
assertTrue(output.getElement() == 161);
assertNull(output.getNext());
}
@Test
public void test_getElementsOfRanks_2() {
TreeNode n1 = new TreeNode<>(23);
TreeNode n2 = new TreeNode<>(46);
TreeNode n3 = new TreeNode<>(69);
TreeNode n4 = new TreeNode<>(92);
TreeNode n5 = new TreeNode<>(115);
TreeNode n6 = new TreeNode<>(138);
TreeNode n7 = new TreeNode<>(161);
n2.addChild(n1); n1.setParent(n2);
n2.addChild(n5); n5.setParent(n2);
n2.addChild(n7); n7.setParent(n2);
n1.addChild(n4); n4.setParent(n1);
n1.addChild(n3); n3.setParent(n1);
n5.addChild(n6); n6.setParent(n5);
TreeUtilities u = new TreeUtilities();
SLLNode output = u.getElementsOfRanks(n2, 1, 2);
assertTrue(output.getElement() == 23);
assertTrue(output.getNext().getElement() == 46);
assertNull(output.getNext().getNext());
output = u.getElementsOfRanks(n2, 4, 5);
assertTrue(output.getElement() == 92);
assertTrue(output.getNext().getElement() == 115);
assertNull(output.getNext().getNext());
output = u.getElementsOfRanks(n2, 6, 7);
assertTrue(output.getElement() == 138);
assertTrue(output.getNext().getElement() == 161);
assertNull(output.getNext().getNext());
}
@Test
public void test_getElementsOfRanks_3() {
TreeNode n1 = new TreeNode<>(23);
TreeNode n2 = new TreeNode<>(46);
TreeNode n3 = new TreeNode<>(69);
TreeNode n4 = new TreeNode<>(92);
TreeNode n5 = new TreeNode<>(115);
TreeNode n6 = new TreeNode<>(138);
TreeNode n7 = new TreeNode<>(161);
n2.addChild(n1); n1.setParent(n2);
n2.addChild(n5); n5.setParent(n2);
n2.addChild(n7); n7.setParent(n2);
n1.addChild(n4); n4.setParent(n1);
n1.addChild(n3); n3.setParent(n1);
n5.addChild(n6); n6.setParent(n5);
TreeUtilities u = new TreeUtilities();
SLLNode output = u.getElementsOfRanks(n2, 1, 3);
assertTrue(output.getElement() == 23);
assertTrue(output.getNext().getElement() == 46);
assertTrue(output.getNext().getNext().getElement() == 69);
assertNull(output.getNext().getNext().getNext());
output = u.getElementsOfRanks(n2, 3, 5);
assertTrue(output.getElement() == 69);
assertTrue(output.getNext().getElement() == 92);
assertTrue(output.getNext().getNext().getElement() == 115);
assertNull(output.getNext().getNext().getNext());
output = u.getElementsOfRanks(n2, 5, 7);
assertTrue(output.getElement() == 115);
assertTrue(output.getNext().getElement() == 138);
assertTrue(output.getNext().getNext().getElement() == 161);
assertNull(output.getNext().getNext().getNext());
}
@Test
public void test_getElementsOfRanks_4() {
TreeNode n1 = new TreeNode<>(23);
TreeNode n2 = new TreeNode<>(46);
TreeNode n3 = new TreeNode<>(69);
TreeNode n4 = new TreeNode<>(92);
TreeNode n5 = new TreeNode<>(115);
TreeNode n6 = new TreeNode<>(138);
TreeNode n7 = new TreeNode<>(161);
n2.addChild(n1); n1.setParent(n2);
n2.addChild(n5); n5.setParent(n2);
n2.addChild(n7); n7.setParent(n2);
n1.addChild(n4); n4.setParent(n1);
n1.addChild(n3); n3.setParent(n1);
n5.addChild(n6); n6.setParent(n5);
TreeUtilities u = new TreeUtilities();
SLLNode output = u.getElementsOfRanks(n2, 1, 7);
assertTrue(output.getElement() == 23);
assertTrue(output.getNext().getElement() == 46);
assertTrue(output.getNext().getNext().getElement() == 69);
assertTrue(output.getNext().getNext().getNext().getElement() == 92);
assertTrue(output.getNext().getNext().getNext().getNext().getElement() == 115);
assertTrue(output.getNext().getNext().getNext().getNext().getNext().getElement() == 138);
assertTrue(output.getNext().getNext().getNext().getNext().getNext().getNext().getElement() == 161);
assertNull(output.getNext().getNext().getNext().getNext().getNext().getNext().getNext());
}
/*
* Jackie's suggestions:
* + Try more test cases with trees of different shapes.
* + Try more test cases with different combinations of lower and upper bounds.
*/
/*
* Tests related to getStats
*/
@Test
public void test_getStats_1() {
TreeNode n1 = new TreeNode<>(23);
TreeNode n2 = new TreeNode<>(46);
TreeNode n5 = new TreeNode<>(115);
TreeNode n7 = new TreeNode<>(161);
n2.addChild(n1); n1.setParent(n2);
n2.addChild(n5); n5.setParent(n2);
n2.addChild(n7); n7.setParent(n2);
/*
* Hint: Visualize the tree constructed from the above nodes storing integers.
*/
TreeUtilities u = new TreeUtilities();
/*
* Input:
* + The root node `n` of some general tree (see the TreeNode class) storing integers.
*
* Assumptions:
* 1. Input `n` is not null.
* 2. The organization of nodes in the input tree rooted at `n` is arbitrary:
* no ordering among child node elements can be assumed.
*
* Output:
* Return the root node (see the TreeNode class) of a string tree which:
* - has the same branching structure as the input integer tree (rooted at `n`)
* - stores in each node a string summarizing the following statistical information of the ***corresponding input node***:
* * Number of descendant nodes (See the definition of what a node's descendants are in Lecture W8.)
* * Sum of values stored in the input descendant nodes
*
* Hints:
* + See Section 2.3 (page 7) of the instructions PDF.
*
* Recommendation:
* + This exercise is meant to help you think recursively.
* + Do not waste the opportunity: your implemented method should run O(N),
* where `N` is the number of nodes contained in the tree rooted at input `n`.
*/
TreeNode output = u.getStats(n2);
assertNull(output.getParent());
assertEquals("Number of descendants: 4; Sum of descendants: 345", output.getElement());
SLLNode> levelOne = output.getChildren();
TreeNode levelOneChild0 = levelOne.getElement();
TreeNode levelOneChild1 = levelOne.getNext().getElement();
TreeNode levelOneChild2 = levelOne.getNext().getNext().getElement();
assertNull(levelOne.getNext().getNext().getNext());
/* child 0 */
assertTrue(output == levelOneChild0.getParent());
assertEquals("Number of descendants: 1; Sum of descendants: 23", levelOneChild0.getElement());
/* child 1 */
assertTrue(output == levelOneChild1.getParent());
assertEquals("Number of descendants: 1; Sum of descendants: 115", levelOneChild1.getElement());
/* child 2 */
assertTrue(output == levelOneChild2.getParent());
assertEquals("Number of descendants: 1; Sum of descendants: 161", levelOneChild2.getElement());
/*
* Hint: Visualize the tree constructed from the above nodes storing strings.
* How does this string tree correspond to the input integer tree?
*/
}
@Test
public void test_getStats_2() {
TreeNode n1 = new TreeNode<>(23);
TreeUtilities u = new TreeUtilities();
TreeNode output = u.getStats(n1);
assertNull(output.getParent());
assertNull(output.getChildren());
assertEquals("Number of descendants: 1; Sum of descendants: 23", output.getElement());
}
@Test
public void test_getStats_3() {
TreeNode n1 = new TreeNode<>(23);
TreeNode n2 = new TreeNode<>(46);
TreeNode n3 = new TreeNode<>(69);
TreeNode n4 = new TreeNode<>(92);
TreeNode n5 = new TreeNode<>(115);
TreeNode n6 = new TreeNode<>(138);
TreeNode n7 = new TreeNode<>(161);
n2.addChild(n1); n1.setParent(n2);
n2.addChild(n5); n5.setParent(n2);
n2.addChild(n7); n7.setParent(n2);
n1.addChild(n4); n4.setParent(n1);
n1.addChild(n3); n3.setParent(n1);
n5.addChild(n6); n6.setParent(n5);
/*
* Hint: Visualize the tree constructed from the above nodes storing integers.
*/
TreeUtilities u = new TreeUtilities();
/*
* See Section 2.3 (page 7) of the instructions PDF.
*/
TreeNode output = u.getStats(n2);
assertNull(output.getParent());
assertEquals("Number of descendants: 7; Sum of descendants: 644", output.getElement());
SLLNode> levelOne = output.getChildren();
TreeNode levelOneChild0 = levelOne.getElement();
TreeNode levelOneChild1 = levelOne.getNext().getElement();
TreeNode levelOneChild2 = levelOne.getNext().getNext().getElement();
assertNull(levelOne.getNext().getNext().getNext());
/* child 0 */
assertTrue(output == levelOneChild0.getParent());
assertEquals("Number of descendants: 3; Sum of descendants: 184", levelOneChild0.getElement());
/* child 1 */
assertTrue(output == levelOneChild1.getParent());
assertEquals("Number of descendants: 2; Sum of descendants: 253", levelOneChild1.getElement());
/* child 2 */
assertTrue(output == levelOneChild2.getParent());
assertEquals("Number of descendants: 1; Sum of descendants: 161", levelOneChild2.getElement());
SLLNode> levelTwo = levelOneChild0.getChildren();
TreeNode levelTwoChild0 = levelTwo.getElement();
TreeNode levelTwoChild1 = levelTwo.getNext().getElement();
assertNull(levelTwo.getNext().getNext());
levelTwo = levelOneChild1.getChildren();
TreeNode levelTwoChild2 = levelTwo.getElement();
assertNull(levelTwo.getNext());
/* child 0 */
assertTrue(levelOneChild0 == levelTwoChild0.getParent());
assertEquals("Number of descendants: 1; Sum of descendants: 92", levelTwoChild0.getElement());
/* child 1 */
assertTrue(levelOneChild0 == levelTwoChild1.getParent());
assertEquals("Number of descendants: 1; Sum of descendants: 69", levelTwoChild1.getElement());
/* child 2 */
assertTrue(levelOneChild1 == levelTwoChild2.getParent());
assertEquals("Number of descendants: 1; Sum of descendants: 138", levelTwoChild2.getElement());
/*
* Hint: Visualize the tree constructed from the above nodes storing strings.
* How does this string tree correspond to the input integer tree?
*/
}
/*
* Jackie's suggestion:
* + Try more test cases with trees of different shapes.
*/
}
TEST GENERAL TREES
package tests;
import static org.junit.Assert.*;
import org.junit.Test;
/*
* This test illustrates how the two classes SLLNode and TreeNode may be used together.
*/
public class TestGeneralTrees {
@Test
public void test_general_trees_construction_strings() {
TreeNode jonathan = new TreeNode<>("Jonathan");
TreeNode alan = new TreeNode<>("Alan");
TreeNode mark = new TreeNode<>("Mark");
TreeNode tom = new TreeNode<>("Tom");
/* Initially, no child nodes for jonathan */
assertNull(jonathan.getChildren());
/* Add the first child node for jonathan */
jonathan.addChild(alan);
alan.setParent(jonathan);
assertNull(jonathan.getParent());
assertTrue(jonathan == alan.getParent());
SLLNode> childList = jonathan.getChildren();
assertTrue(childList.getElement() == alan);
/*
* childList returns a SLLNode>
* childList.getElement() returns a TreeNode
* childList.getElement().getElement() returns a String
*/
assertTrue(childList.getElement().getElement().equals("Alan"));
assertNull(childList.getNext());
/* Add the second child node for jonathan */
jonathan.addChild(mark);
mark.setParent(jonathan);
assertNull(jonathan.getParent());
assertTrue(jonathan == alan.getParent());
assertTrue(jonathan == mark.getParent());
childList = jonathan.getChildren();
assertTrue(childList.getElement() == alan);
assertTrue(childList.getElement().getElement().equals("Alan"));
assertTrue(childList.getNext().getElement() == mark);
/*
* childList.getNext() returns a SLLNode>
* childList.getNext().getElement() returns a TreeNode
* childList.getNext().getElement().getElement() returns a String
*/
assertTrue(childList.getNext().getElement().getElement().equals("Mark"));
assertNull(childList.getNext().getNext());
/* Add the third child node for jonathan */
jonathan.addChild(tom);
tom.setParent(jonathan);
assertNull(jonathan.getParent());
assertTrue(jonathan == alan.getParent());
assertTrue(jonathan == mark.getParent());
assertTrue(jonathan == tom.getParent());
childList = jonathan.getChildren();
assertTrue(childList.getElement() == alan);
assertTrue(childList.getElement().getElement().equals("Alan"));
assertTrue(childList.getNext().getElement() == mark);
assertTrue(childList.getNext().getElement().getElement().equals("Mark"));
assertTrue(childList.getNext().getNext().getElement() == tom);
assertTrue(childList.getNext().getNext().getElement().getElement().equals("Tom"));
assertNull(childList.getNext().getNext().getNext());
}
@Test
public void test_general_trees_construction_integers() {
TreeNode i0 = new TreeNode<>(0);
TreeNode i1 = new TreeNode<>(1);
TreeNode i2 = new TreeNode<>(2);
TreeNode i3 = new TreeNode<>(3);
/* Initially, no child nodes for i0 */
assertNull(i0.getChildren());
/* Add the first child node for i0 */
i0.addChild(i1);
i1.setParent(i0);
assertNull(i0.getParent());
assertTrue(i0 == i1.getParent());
SLLNode> childList = i0.getChildren();
assertTrue(childList.getElement() == i1);
/*
* childList returns a SLLNode>
* childList.getElement() returns a TreeNode
* childList.getElement().getElement() returns a Integer
*/
assertTrue(childList.getElement().getElement().equals(1));
assertNull(childList.getNext());
/* Add the second child node for i0 */
i0.addChild(i2);
i2.setParent(i0);
assertNull(i0.getParent());
assertTrue(i0 == i1.getParent());
assertTrue(i0 == i2.getParent());
childList = i0.getChildren();
assertTrue(childList.getElement() == i1);
assertTrue(childList.getElement().getElement().equals(1));
assertTrue(childList.getNext().getElement() == i2);
/*
* childList.getNext() returns a SLLNode>
* childList.getNext().getElement() returns a TreeNode
* childList.getNext().getElement().getElement() returns a Integer
*/
assertTrue(childList.getNext().getElement().getElement().equals(2));
assertNull(childList.getNext().getNext());
/* Add the third child node for i0 */
i0.addChild(i3);
i3.setParent(i0);
assertNull(i0.getParent());
assertTrue(i0 == i1.getParent());
assertTrue(i0 == i2.getParent());
assertTrue(i0 == i3.getParent());
childList = i0.getChildren();
assertTrue(childList.getElement() == i1);
assertTrue(childList.getElement().getElement().equals(1));
assertTrue(childList.getNext().getElement() == i2);
assertTrue(childList.getNext().getElement().getElement().equals(2));
assertTrue(childList.getNext().getNext().getElement() == i3);
assertTrue(childList.getNext().getNext().getElement().getElement().equals(3));
assertNull(childList.getNext().getNext().getNext());
}
}
TREE NODE
package tests;
/*
* Template for nodes in a general tree.
* Notes:
* + This version of TreeNode is different from what's covered in the lecture.
* Specifically, the list of child nodes is implemented via a chain of singly-linked nodes (see the SLLNode class).
* + See the TestGeneralTrees class for how the TreeNode and SLLNode classes are supposed to work together.
*/
public class TreeNode {
private E element; /* data object */
private TreeNode parent; /* unique parent node */
private SLLNode> headOfChildList; /* head of list of child nodes */
private SLLNode> tailOfChildList; /* tail of list of child nodes */
public TreeNode(E element) {
this.element = element;
this.parent = null;
this.headOfChildList = null;
this.tailOfChildList = null;
}
public E getElement() {
return this.element;
}
public void setElement(E element) {
this.element = element;
}
public TreeNode getParent() {
return this.parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public SLLNode> getChildren() {
SLLNode> result = null;
SLLNode> currentResult = null;
SLLNode> currentChild = headOfChildList;
while (currentChild != null) {
SLLNode> n = new SLLNode<>(currentChild.getElement(), null);
if(result == null) {
result = n;
currentResult = result;
}
else {
currentResult.setNext(n);
currentResult = currentResult.getNext();
}
currentChild = currentChild.getNext();
}
return result;
}
public void addChild(TreeNode child) {
SLLNode> n = new SLLNode<>(child, null);
if(headOfChildList == null) {
headOfChildList = n;
tailOfChildList = headOfChildList;
}
else {
tailOfChildList.setNext(n);
tailOfChildList = tailOfChildList.getNext();
}
}
}
Similar Samples
Explore our diverse array of programming assignment samples at ProgrammingHomeworkHelp.com. These samples exemplify our proficiency across various languages and topics, providing comprehensive solutions with clear explanations. Whether you're navigating algorithms, data structures, or software projects, our samples showcase our commitment to delivering high-quality academic assistance. Discover how our solutions can enhance your understanding and proficiency in programming.
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java