MY ASSIGNMENT IS HALF WAY DONE, JUST WANT TO SEE IF MY I SHOULD REVISE OR ADD A FEW THINGS, THERE ARE TWO METHODS THAT I HAVING ISSUES WITH. THE VOID SETCURRENT AND VOID INSERT
CS 351/751: Data Structures & Algorithms Homework #4 Homework #4 due Monday, October 3, 10:00 PM In this assignment we continue our investigation of implementing a “sorted sequence” ADT. This week, it will be re-implemented using a linked-list. Read Chapter 4 carefully and especially make sure that you read Section 4.5, pages 232–238 (225–231, 3rd ed.) which specifically say how to implement Sequence with linked lists. We will be implementing ApptBook with its different interface, and with a change in the data structure too. Use this link to accept the assignment: https://classroom.github.com/a/MSlyiVCN 1 Concerning New Implementation of ApptBook The ApptBook class will have the same public declarations as the ApptBook you implemented before (except no way to specify an initial capacity), but the data structure (private fields) will be completely different. Declare a node class as a “private static class” inside the ApptBook class. Such a class (one declared inside another class) is called a “nested” class. The node class should have two fields: the data (of type Appointment) and the next node. It should have a constructor that takes initial values for both fields, but no other methods. Despite what it says in the textbook, do not write methods in the “Node” class. The design in the textbook starting on page 232 (225, 3rd ed.). We make the data structure smaller by omitting a “tail” field. The tail is not needed for any of our methods, so the burden of keeping it consistent outweighs the non-existent benefit. We still have a precursor and a cursor (which implies some redundancy) but represent the “no current element” condition differently: We represent “no current element” by having the curor be null and the precursor be the last node of the list (if there is one). For example: cursor head 1 2 3 precursor (The textbook has both precursor and cursor be null in this case which requires more special cases in the code.) Your wellFormed method will need to check the data structure (as always). And also as usual, you are given a number of invariant tests to make sure that this is done. If you don’t understand the test, and you have read the explanation of the fields in the textbook, please post a question on Piazza about the test. Fall 2022 page 1 of 3 https://classroom.github.com/a/MSlyiVCN CS 351/751: Data Structures & Algorithms Homework #4 The redundancy makes certain operations easier (especially ones that do not change anything, such as isCurrent), but complicates the work of those which make changes (such as removeCurrent). Unlike in the past assignment, clone requires some (difficult!) work for you to do: the list must be copied, cell by cell, and pointers of the clone made to point to the appropriate copied nodes. 1.1 The Invariant The invariant is more complex than in the previous implementation. It has the following parts: 1. The list may not include a cycle, where the next link of some node points back to some earlier node. 2. No data in the list may be null, and they must be in non-decreasing natural order. (As before, duplicates are permitted.) 3. The precursor field is either null or points to a node in the list. It cannot point to a node that is no longer in the list—the node must be reachable from the head of the list. 4. The cursor must be the first node if the precursor is null, and otherwise must be the node after the precursor. 5. The field manyNodes should accurately represent the number of nodes in the list. We have implemented the first part for you; you should implement the other parts yourself. You should do this early on in developing the implementation—it will help you catch bugs as quickly as possible. We provide code to test the invariant checker. Be very careful that you never change any fields in the invariant checker, wellFormed. It is ONLY supposed to check the invariant and return true or false (with a report). It should never change things. It will need to define its own local variabloes of course, which may be modified during the execution of the method. Local variables have no effect on any stored objects. 2 Files The repository homework4.git includes the following files: src/TestApptBook.java Updated functionality tests. src/TestInvariant.java Call out to the invariant checker tests. src/edu/uwm/cs351/ApptBook.java Skeleton file. lib/homework4.jar JAR file containing the other ADTs, and random testing. Fall 2022 page 2 of 3 CS 351/751: Data Structures & Algorithms Homework #4 This project also has random testing. It is implemented without change from Homework #2 because the public interface (and meaning of the methods) of the ApptBook class is unchanged. There are no efficency tests for thie assignment. Fall 2022 page 3 of 3 Concerning New Implementation of ApptBook The Invariant Files