Assignment 7
Goals: Practice designing methods in the presence of mutation. Learn to abstract over the data types (using parametrized types).
Instructions
The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit.
Make sure you follow the style guidelines for code indentation.
You will submit this assignment by the deadline using the Web-CAT submission system.
With each homework you will also submit your log file named pairxxx.txt where you replace xxx with your pair number.
On top of every file you submit you will have the names of both partners, and the pair number.
The .txt file will be the log of your work on this assignment. Each log entry will have data and time, who was present (one or both of the partners) and a short comment decribing what you were working on.
Due Date: Friday, October 26th, 9:59 pm.
Practice Problems
Work out these problems on your own. Save them in an electronic portfolio, so you can show them to your instructor, review them before the exam, use them as a reference when working on the homework assignments.
Review the problem 2 from last week’s assignment
Review the lab problems and finish them.
Read the older lecture notes on function objects and on parametrized types.
Problem 1
Problem 2 from the previous assignment introduced a mutable linked list data structure.
Create a project with the name HW07Problem1.
Here we extend what we learned in the the last lab and the last homework. We would like to build a list in such a way that we can start either at the front, or at the back, and move through the list in either direction. In order to do so, we have decided on the structures to represent the following scenarios:
+-------+ |
| Deque | |
+-------+ |
| node |--+ |
+-------+ | |
+------+ |
| |
v |
+----------+ |
| Sentinel | |
+----------+ |
| "" | |
+---| next | |
| | prev |-----------------------------+ |
| +----------+ | |
| | |
v v |
+----------+ +----------+ +----------+ +----------+ |
| Node | | Node | | Node | | Node | |
+----------+ +----------+ +----------+ +----------+ |
| "abc" | | "bcd" | | "cde" | | "def" | |
| bcdnode |-->| cdenode |-->| defnode |-->| sentinel | |
| sentinel |<--| abcnode |<--| bcdnode |<--| cdenode | |
+----------+ +----------+ +----------+ +----------+ |
Each node now has two links, one to the next item in the list and one to the previous node in the list.
The Sentinel node is always present. It does not contain any useful data, i.e. the data field may be either null, or for the list of Strings the empty String. Its role is to provide the link to the head of the list and to the tail of the list.
The Deque is a wrapper class that contains one field, the Sentinel node for this list. So an empty list would have the following class diagram:
+-------+ |
| Deque | |
+-------+ |
| node |--+ |
+-------+ | |
+----+ +------+ |
| | | +----+ |
| | | | | |
| v v v | |
| +----------+ | |
| | Sentinel | | |
| +----------+ | |
| | "" | | |
+--| next | | |
| prev |--+ |
+----------+ |
Define the class Node, the class Sentinel that extends the class Node as before, and the class Deque that implement doubly-linked lists of Strings. Use the code from the previous problems as your model.
Make examples of three lists: the empty list, a list with the values ("abc", "bcd", "cde", and "def") shown in the drawing at the beginning of this problem, and a list with four values, that are not ordered lexicographically.
(Make more examples as needed to test the methods you define.)
Name your examples class ExamplesDeque.
Design the method size that counts the number of nodes in a list Deque, not including the sentinel node.
Design the method addAtHead for the class Deque that consumes a String and inserts it at the front of the list. Be sure to fix up all the links correctly!
Design the method addAtTail for the class Deque that consumes a String and inserts it at the tail of this list. Again, be sure to fix up all the links correctly!
Design the method removeFromHead for the class Deque that removes the first node from this Deque. Throw an exception, if an attempt is made to remove from an empty list.
Design the method removeFromTail for the class Deque that removes the last node from this Deque. Throw an exception, if an attempt is made to remove from an empty list.
Design the method getFirst for the class Deque that produces the data in the first node of this Deque. Throw an exception, if an attempt is made to retrieve data from an empty list.
Design the method getLast for the class Deque that produces the data in the last node of this Deque. Throw an exception, if an attempt is made to retrieve data from an empty list.
Design the method insertSorted for the class Deque that consumes a String and inserts it into a sorted list in the correct order. This method should never be used with an unsorted list. It is not your responsibility to worry whether the client for your code observes this constraint.
Design the method removeSorted for the class Deque that removes the node that contains the given String from the sorted Deque.
Throw an exception, if the there is no such String.
This method should never be used with an unsorted list. It is not your responsibility to worry whether the client for your code observes this constraint.
Problem 2
The data structure you have built in the previous problem is very useful, except for the fact that the data in the list can only be of the type String.
Create a project with the name HW07Problem2.
Import into it your solution to the previous problem.
Comment out as a block comment all methods you have defined. Now change the classes Node, Sentinel, and Deque so that they are parametrized over the type of data each Node contains.
Comment out all tests for the methods in your ExamplesDeque class and modify the examples of data so they would work with the new class definitions. Rename the class to be ExamplesDequeT.
Define a new class of data of your choice (books, pets, persons, ...) and make examples of lists of the items of this type.
Uncomment all but the last two methods for the class Deque (and all helper methods they refer to in the class Node or the class Sentinel) and adjust them so that they work with the parametrized class definitions. Adjust all tests as needed.
Add tests for all methods but use now the lists of the items of the new type of data you have defined.
To make the insertSorted work with the parametrized types, the method needs to consume a function object that will provide the method for comparing two data items.
Java in the libraries provided with the language defines the following interface:
interface Comparator<T>{
// compare two items of the type T
// return <0 if t1 < t2
// return 0 if t1 equals t2
// return >0 if t1 > t2
int compare{T t1, T t2};
}
You need to add import java.util.*; at the beginning of your program if your wants to use this interface (or define classes that implement it).
Define three new classes that implement the Comparator interface. The first one compares two Strings lexicographically, the second one compares two Strings by their length, the third one compares two objects of the type you have defined (and you decide what does the ordering represent).
Now rewrite the insertSorted method so that it would consume an instance of a Comparator<T> and use it to determine the ordering of the items in the list.
Modify your tests for the insertSorted method for lists of Strings so that they would work with the parametrized data definitions.
Add tests that use the other two Comparators.
Finally, modify the method removeSorted to work with the Comparator object and adjust and extend the test suite in the manner similar to what you have done for the insertSorted method.