Assignment 7
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 7 |
// 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)
There will be a separate submission for each problem - it makes it easier to grade each problem, and to provide you with the feedback for each problem wou work on.
The two submissions will be organized as follows:
Submission HW7P1: The log file and the solution to the buddies problem from the lab in one .zip file
Submission HW7P2: The file Dequeue.java with all classes, interfaces, methods, and tests. If you wish to keep the examples and tests in a separate Java files, you may do so.
Due Date: Wednesday, February 26th, 11: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 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 7 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: Dequeue for Strings
Create a project with the name HW07Problem2.
We would like to build a list (of Strings) 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.