Assignment 8
Goals: Practice working paramtrized types and using the ArrayList
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.
Submission Details:
Make sure the class that defines the binary search method is named ExamplesAlgorithms and that the method signature is:
<T> int binSearch(T item, ArrayList<T> alist, Comparator<T> comp)
If you have defined the binSearch method in the Algorithms class as specified in the assignment originally, add the following to your ExamplesAlgorithms class:
Algorithms algo = new Algorithms();
<T> int binSearch(T item, ArrayList<T> alist, Coparator<T> comp){
return this.algo.binSearch(item, alist, comp, 0, alist.size());
}
For the dequeue problem for Strings make sure there are public default constructors for the classes Deque and Sentinel
Make sure that when the getFirst method throws a RuntimeException when invoked on an empty queue, the message is
"Cannot get the first of an empty list"
Make sure that when the getLast method throws a RuntimeException when invoked on an empty queue, the message is
"Cannot get the last of an empty list"
For the parametrized Deque change the names of all classes so that they end with T, i.e. DequeT, NodeT, SentinelT, etc. so that the names do not conflict with the solutions to the previous problem.
Due Date: Friday, March 15th, 10:00 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.
Finish all of the problems from the Lab 8 that deal with ILo<T> lists.
Finish the problems from the Lab 8 that deals with the methods for ArrayLists.
Problem 1: Binary Search
Start with a new project HW08Problem1 and create two files: Algorithms.java and ExamplesAlgorithms.java.
In the class ExamplesAlgorithms make examples of sorted ArrayLists of Strings and Integers. Of course, there is no constructor that creates an ArrayList filled with values. You need to define a method initData that adds the values to the initially empty ArrayLists one at a time.
Next, design two classes that implement the Comparator interface in Java Collections Framework —
one that compares Strings by lexicographical ordering, one that compares Integers by their magnitude. Now, design the method binarySearch in the class Algorithms that consumes the lower index (inclusive), the upper index (exclusive), an ArrayList of data of the type T a Comparator of the type T, and an object of the type T and produces the index for this object in the given ArrayList or -1 if the object is not found.
Problem 2: Dequeue for Strings
Create a project with the name HW08Problem2.
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 structure 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 | |
+----------+ +----------+ +----------+ +----------+ |
Every list has a header that consists of the Sentinel node. This node does not change, only its fields that provide the links to the first and the last item in the list can change.
Each node 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 empty list has just one node, the Sentinel that contains no useful data, and its links to the first and to the last item just reference the Sentinel node itself.
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 3: Parametrized Dequeue
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 HW08Problem3.
Import into it your solution to Problem 2.
Rename all classes by adding T at the end. So you should now have NodeT, SentinelT, DequeT, and ExamplesDequeT classes in your project.
Hint: Use the Eclipse Rename choice in the Refactor menu.
Now change the classes NodeT, SentinelT, and DequeT so that they are parametrized over the type of data each NodeT contains.
Comment out all tests for the methods in your ExamplesDequeT class and modify the examples of data so they would work with the new class definitions..
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 DequeT (and all helper methods they refer to in the class NodeT or the class SentinelT) 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.