Assignment 4
ASSIGNMENT 4: LinkedLists and Recursion COMP 1020 Winter 2020 Page 1 of 7 DUE DATE: APRIL 3RD, 2020 AT 11:59PM Instructions: • Read the SubmissionProcedures.PDF and the Standards.java carefully BEFORE you start. • Let me know about any typos, clarifications or questions you may have right away. Don’t wait. • Read the whole assignment before you start. • Start right away. The sooner you get stuck, the sooner you can get help to get un-stuck. Assignment overview Learning outcomes: • Learning to extend your previous assignments • An understanding of object hierarchies and use subclasses to extend other classes. • An understanding of how use LinkedLists. • Familiarity with StdDraw to create more complex animation sequences • Familiarity using recursion Additional Notes: Read Standards.java and SubmissionGuidelines.PDF Carefully & before you start. Several Classes will be provided as a starting point including some that you developed or worked with in A3. You can either continue from your own solution to A3 (I will give a couple of bonus marks for this if you can adapt your current code to work) or start from the handout. As before, you should be tracking your project in git and using all the best practices we have been discussing so far. Please provide detailed commenting and commit your code often!!! Tips: Start early. Read the assignment fully before beginning. We will go through it in the first class after it has been handed out. You can also email questions or join in on the Zoom video chat channel to ask questions. I will be checking email often and exploring new platforms for handling this distance ed situation but if you have any suggestions I am open to hearing them. Notes on Academic Misconduct: Your code should be done entirely by you. Any suspicion of Academic Misconduct or plagiarism will be fully investigated and can lead to serious academic penalties including 0 on the assignment for a first office, or an F in the course. Third offences could lead to expulsion from ICM. If you have any questions as to what qualifies as Academic Misconduct, please discuss it with me. Phase 0: Introduction Before you start. I am providing a framework of the methods here with the understanding that you will create a GameController class that contains your main method and a TestClass for testing all of your methods as you progress. It can be useful in your TestClass to create several static methods that each test one phase, or part of a phase. This way you can easily focus your attention on the most relevant information while maintaining an ability to run tests on earlier classes easily (in case you break them along the way). ASSIGNMENT 4: LinkedLists and Recursion COMP 1020 Winter 2020 Page 2 of 7 Phase 1: Node Object The Start of Linked Lists The Node class will store a Vector2 object as well as the next Node in the sequence and is a part of your LinkedList. It will contain the following: Variables: private Vector2 data stores a single Vector2 object. private Node next stores the next Node in the LinkedList Methods You should create a constructor that accepts both a Vector2 data value and a Node (the next Node) (in that order). It should also contain basic accessor and mutator methods public void setData(Vector2 data) public void setLink(Node next) public Vector2 getData() public Node getLink() Next, you will create a toString() method which should return the Vector2 with the following format: N(0.001, 0.123) Where N represents a Node, and 0.001 is the x values of the Vector2, 0.123 is the y value of the Vector2. They should include the brackets and comma and be rounded to 3 decimal places. You can use the Vector2 toString() method to help with this. ASSIGNMENT 4: LinkedLists and Recursion COMP 1020 Winter 2020 Page 3 of 7 Phase 2: Basic Linked List operations Fundamentals of LinkedLists You will be creating a LinkedList class. It will hold a list of Nodes and allow for several operations on them. This particular LinkedList will hold Nodes which contain Vector2 values, allowing for some specific methods related to geometry. Your linked list only needs a single variable, Node top. This points to the first Node in the list or null if the list is empty. Create a Constructor that accepts no parameters. boolean isEmpty() will return true if the list is empty and false otherwise. public Node getTop() will return the first Node in the list. public int size() will return the total number of Nodes stored in the list. This should be calculated each time size() is called, rather then being stored as it was in our partially full array. void add(Vector2 data) will add the given Vector2 into the LinkedList as the first Node. It will need to create a new Node to hold it. void add(Node newNode) will add the given Node to the front of the LinkedList void addLast(Vector2 data) will add a new Node to the LinkedList with the data value given. Vector2 remove() will remove the first Node in the list and return the value. If the list is empty it should return null (however you should avoid calling this method if the list is empty so check first). String toString() will return a String that includes ALL the nodes in the list. It should create this String by stepping through the LinkedList an calling toString on each individual Node. ASSIGNMENT 4: LinkedLists and Recursion COMP 1020 Winter 2020 Page 4 of 7 Phase 3: Recursion – Weights and Values A Thing to hold other Things, but how much is in that Thing? We can currently store a list of Things in a ContainerThing. Since ContainerThing is itself a Thing, this should mean that you should be able to store ContainerThings in other ContainerThings. This is the essence of recursion. Complete the modifications necessary to enable ContainerThing to calculate the total weight of all Things inside itself, including other ContainerThings. This must be done recursively to return a final sum of ALL Things, even Things within other Things. You should edit the totalWeight() method in the ContainerThing and other classes (Thing, QuantityThing) to allow the Container to recursively search for the weight of all things it holds. It should also support You should also update your Thing (and subclasses) toString() methods to work recursively in this same way. Up until now, we have been just storing the value of a Thing as a primitive value in the Thing super class but we should be able to calculate the total value of all Things in a ContainerThing, including other ContainerThings which in turn may contain even more Things. Add a method double totalValue() to all Thing objects (including subclasses) which will return the value of the specified Thing. If it is a ContainerThing, it should also include the value of any Thing objects stored inside it recursively. Again, this should work recursively even if you can find an iterative solution. Example: ContainerThing item1 has a weight of 1 item1 contains ContainerThing item2 which also has a weight of 1 item2 contains ContainerThing item3 which has a weight of 3 item2 contains a Thing object item4 which has a weight of 5 This gives us item1 (1) + item2 (1) + item3 (3) + item4 (5) so item1.totalWeight() returns 9 while item2.totalWeight would return 8. ASSIGNMENT 4: LinkedLists and Recursion COMP 1020 Winter 2020 Page 5 of 7 Phase 4: More Complex LinkedLists void drawLine() Will iterate through the LinkedList and draw a line that connects all points. This method assumes that the points represent positions on the GUI (rather than Vectors). public double totalLength() will return the total distance between all the Nodes. This should return 0 if there are less than 2 Nodes. To do this, you will find the distance between Node0 and Node1, then add that to the distance between Node1 and Node2, then add that to the distance between Node 2 and Node 3, until all the Nodes have been included. void insert(int index, Vector2 data) will insert a new Node containing in the nth position. if index is greater than the last Node, add it to the end but print a warning to the console. int compareTo(LinkedList other) will compare the measured lengths of two LinkedLists. It should return 0 if they are equal, a negative value if this LinkedList is shorter than the other LinkedList, and a positive value if this LinkedList is longer then the other LinkedList. You can use the totalLength() method for this calculation. Side note: Keep in mind we could have alternatively chosen to write the compareTo method to compare some other factors (size() for example) so this really depends on the needs of the project. public LinkedList deepCopy() returns a deep copy of