Assignment 5 Solution

Goals: Learn to program with mutation and resolve circularity in data.
Instructions
The names of the classes must be exactly the same as specified. The same is the case for the names and types of the fields within the class, as well as the order in which they are defined and listed as the constructor arguments. This allows us to design our own Examples class that tests your program.
Make sure you follow the style guidelines that WebCAT enforces. For now the most important ones are: using spaces instead of tabs, indenting by 4 characters, following the naming conventions (data type names start with a capital letter, names of fields and methods start with a lower case letter), and having spaces before curly braces.
You will submit this assignment by the deadline using the Web-CAT submission system. You may submit as many times as you wish. Be aware of the fact that close to the deadline the WebCAT system may slow down to handle many submissions - so try to finish early.
With each homework you will also submit your log file named pair-user1-user2.txt where you replace user1 and user2 with the usernames of the two partners.
On top of both files you will have five lines of comments as follows:
// assignment 5
// partner1-last-name partner1-first-name
// partner1-username
// partner2-last-name partner2-first-name
// partner2-username
(In the text file you do not need the two slashes)
Your submission sould consist of the following files:
    • pair-user1-user2.txt – your log file
    • Buddies.java.java – the solution for Problem 1
    • ExamplesBuddies.java – the examples and tests for Problem 1
    • Algorithms.java – the solution and examples for Problem 2
    • Deque.java – the solution and examples for Problem 4
all combined into one HW5.zip file.
You will not submit the solution for Problem 3: the Deque designed to work only with the String data.
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 lecture notes on Books and Authors with circularly referential data and actually run the programs.
Add new examples of books, define the method that checks whether two books are the same.
Pair Programming Problems
Problem 1: Circular data
Finish all work in the Lab 6 and hand it in.
Specifically:
    • Design the method addBuddy and then make example of the circle of buddies as given in the lab.
    • Design the method hasDirectBuddy
    • Design the method countCommonBuddies
    • Design the method hasDistantBuddy
    • Design the method partyCount that counts the number of people who will be invited to a party given by this person if all buddies and all buddies of all buddies (including the distant ones) come to the party.
Submission for Problem 1:
    • The instructor’s test program will assume that you have made examples of all people listed and the object that represents each person has the same name as that person, but in all lower-case letters.
So, you should define ann, bob, etc.
    • The instructor’s test program assumes that the headers of all methods are the same as given in the lab document.
    • If you cannot design these methods, include at least the method header and a stub code within that produces some value of the expected type.
So, for example, if the method produces a boolean value, just write return true;, if it produces a String, write return "s";, etc.
This will make your program compile and will run all instructor’s tests, even though they will probably fail. The methods of this type are called stubs. Developers use them as placeholders for the methods in their wish lists.
What will be tested on submission:
    • Name your examples class for Problem 1 ExamplesBuddies.
    • You must have a method void initBuddies() is the ExamplesBuddies class that initializes all person’s buddy lists. Make sure the method can be called repeatedly.
    • The test program will test the methods hasDirectBuddy, hasDistantBuddy, countCommonBuddies, and partyCount.
Make sure you have at least the stubs for these methods defined in the appropriate classes and interfaces.
    • Make sure the ExamplesBuddies class is defined in its own file named ExamplesBuddies.java
Problem 2: Binary Search
Start with a new project HW05Problem2 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 five arguments:
        ◦ the lower index (inclusive)
        ◦ the upper index (exclusive)
        ◦ an ArrayList of data of the type T (and sorted by the given Comparator
        ◦ the Comparator of the type T that determines the sorting order
        ◦ the object of the type T that we are looking for
The method produces the index at which the given object is located in the given ArrayLis. If the object is does not appear in the given ArrayList the method returns -1.
Problem 3: Dequeue for Strings
Create a project with the name HW05Problem3.
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 find for the class Deque that consumes a String and produces the node in this Deque that contains the given String.
If the String does not appear in the Deque it returns the Sentinel node in this Deque.
    • Design the method removeNode for the class Deque that removes the given Node from this Deque. If the given node is the Sentinel, the method does nothing.
Problem 4: 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 HW05Problem4.
Import into it your solution to Problem 3.
    • 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.
    • When testing the method find make sure that the object you are looking for is identical to the one that has been inserted into the Deque, as it relies on the Java pre-defined equals method.