Work out as the following exercises from the textbook. Do not add them to your assignment submission, though you should keep them in your electronic portfolio in your own svn repository.
Problem: Designing Mutable Lists
Start a new project for this portfolio and import the files from Lists.zip available from the assignment page. You should have three files: Node.java, LoS.java, and LinkedListExamples.java.
In the last lab we used a wrapper class (Bank) to implement a mutable list of accounts. This is because we cannot simply change an empty list into a nonempty list (it's just not possible). The example files show a similar technique to maintaining a mutable list, but instead of replacing the original list with a new list in our wrapper, we directly change the structure of the list (inserting or removing elements) by modifying/mutating the Nodes involved.
The LoS and Node classes represent a collection of Strings organized as a list. Instead of having two different classes for the empty list and for nonempty list, we have a class that represents a Node in a list (similar to our Cons class that contained the data and a link to the next item), and a subclass that represents the end of the list (a sentinel). An LoS list always contains one Node. If the list is empty, the Node is our special sentinel node.
The following pictures illustrate the structure of an empty linked list and a linked list after we added three Strings, "abc", "def", and "ghi":
+------+
| LoS |
+------+ +----------+
| node |->| Sentinel |
+------+ +----------+
| "" |
| null |
+----------+
+------+
| LoS |
+------+ +-------+ +-------+ +-------+ +----------+
| node |->| Node | +->| Node | +->| Node | +->| Sentinel |
+------+ +-------+ | +-------+ | +-------+ | +----------+
| "abc" | | | "def" | | | "ghi" | | | "" |
| next |-+ | next |-+ | next |-+ | null |
+-------+ +-------+ +-------+ +----------+
Study the code and classes. Make sure you understand what is going on. Add an example to each test method defined in the LinkedListExamples class.
Add tests for the methods that are not tested.
Design the method removeNode for the LoS class that removes the Node that contains given String.
Design the method size that counts the number of nodes in a list (LoS), not including the sentinel node.
These problems should be checked into your pair's SVN repository by the due date.
Project naming requirements
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.
Every file you submit must have a header that identifies you and the problem it solves. So, for the first problem the header should look like this:
// Assignment 7 Problem 1 // Partner Name1 // partner1username // Partner Name2 // partner2username // 28 February 2012
In this problem we will model one part of a social network system.
Create a project with the name HW07Problem1. Define the classes and interfaces that implement the class diagram shown. Notice, that we will need to break the circularity of this class diagram.
+------------------------------------------------+
| +------------------+ |
| | | |
| v | v
| +------+ | +------+
| | ALoP |<------------+ | | ALoG |<-----------+
| +------+ | | +------+ |
| +------+ | | +------+ |
| / \ | | / \ |
| --- | | --- |
| | | | | |
| ---------------- | | ---------------- |
| | | | | | | |
| +-------+ +--------------+ | | +-------+ +-------------+ |
| | MTLoP | | ConsLoP | | | | MTLoG | | ConsLoG | |
| +-------+ +--------------+ | | +-------+ +-------------+ |
| +-------+ +-| Person first | | | +-------+ +-| Group first | |
| | | ALoP rest |-+ | | | ALoG rest |-+
| | +--------------+ | | +-------------+
| | | |
| v | v
| +-------------+ | +--------------+
| | Person | | | Group |
| +-------------+ | +--------------+
| | String name | | | String name |
| | int age | | | int limit |
+----| ALoG groups | +-----| ALoP members |
+-------------+ +---------------+
The classes represent people signed up for a social network site. Each person can choose to join one or more groups. Each group keeps track of the people who signed up for it. Some groups limit the age of people who can sign up for the group (for example to keep children from signing up for adult-oriented groups).
Define examples of at least three Persons and eight Groups, with every person signed up for at least two groups.
Design the method join in the class Person that lets the person join the given group. Throw an exception if the person is already a member of the group, or if the person is too young to join the group.
Design the method dropGroup that removes the person from the given group. Throw an exception if the person is not a member of the group.
You meet an interesting person at a party. When you get home you wonder whether or not this person may be signed up for one of the groups you participate in. Design the method canMeet that determines whether the given person has joined one of the groups this person has joined.
You now want to help the manager of this social network by writing the programs that will manage the network. Design the class MeetingPlace that will keep track of the list of people signed up for the network, the list of the groups, and will manage these lists. Include your original examples of people and groups in the examples you design.
Design the method join> that consumes the name of a person, the person's age, and a group name, and makes the person a new member of the desired group. The same restrictions on joining groups apply as before. Additionally, the method should throw an exception if any of the information given does not exist (no person with the given name and age, or no group with the given name).
Design the method remove that consumes the name of a person, the person's age, and a group name, and removes the given person from the given group. The same restrictions apply as above.
Note 1: Most of these methods require several helper methods. At least half of the grade for this homework will be assessing the design of these helpers -- whether you truly follow the rule one task = one method.
Note 2: All of these methods (except canMeet), are defined only to affect a change in the registrar system. Design your tests carefully. At least one half of the grade for this homework will be assessing the design and implementation your tests for these methods.
Note 3: Did you notice that the above two criteria cover two halves of the grade for the homework? Well, there is some wiggle room, but we really want you to understand how important these two issues are (i.e., helpers and testing).
Create a project with the name HW07Problem2.
Here we extend what we learned in the portfolio problem. 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 |
+-------+
+--| head |
| | tail |--+
| +-------+ |
| |
v v
+----------+ +----------+
| Head | | Tail |
+----------+ +----------+
| "" | | "" |
| next |-->| null |
| null |<--| prev |
+----------+ +----------+
+-------+
| Deque |
+-------+
+--| head |
| | tail |---------------------------------+
| +-------+ |
| |
v v
+----------+ +----------+ +----------+ +----------+
| Head | | Node | | Node | | Tail |
+----------+ +----------+ +----------+ +----------+
| "" | | "abc" | | "def" | | "" |
| abcnode |-->| pqrnode |-->| tailnode |-->| null |
| null |<--| headnode |<--| abcnode |<--| pqrnode |
+----------+ +----------+ +----------+ +----------+
Instead of one sentinel node, we have two of them: one marking the head of the queue and the other marking the tail of the queue. Additionally, we have a new field in each node, a reference to the previous item in the list.
The class diagram for modeling this data would then be:
+------------+
| Deque |
+------------+
+--| Node head |
| | Node tail |--+
| +------------+ |
| |
+-------+ +--------+
| |
+----------+ | | +-----------+
| +--+ | | | | +--+ |
| | | | | | | | | |
| | v v v v v v | |
| | +-------------+ | |
| | | Node | | |
| | +-------------+ | |
| | | String data | | |
| +-| Node next | | |
| | Node prev |-+ |
| +-+---------+-+ |
| / \ / \ |
| +---+ +---+ |
| | | |
| +-----------+ +-----------+ |
| | Head | | Tail | |
| +-----------+ +-----------+ |
| | "" | | "" | |
+-| Node next | | null | |
| null | | Node prev |-+
+-----------+ +-----------+
Define the classes Node, Head, Tail, and Deque that implement doubly-linked lists of Strings. Use the code from the portfolio problems as your model.
Make examples of three lists: the empty list, a list with two values ("abc" and "def") shown in the drawing at the beginning of this problem, and a list with three values, ordered lexicographically from the head to the tail.
Design the method size that counts the number of nodes in a list (Deque), not including the two sentinel nodes (the head and the tail).
Design the method addAtHead for the class Deque that consumes a String and inserts it at the head of this 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. Beside the obvious effect, it should produce the String that was removed.
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. Beside the obvious effect, it should produce the String that was removed.
Throw an exception, if an attempt is made to remove from an empty list.
Design the method insertSorted for the class Deque that consumes a String and inserts it into this sorted list in the correct order.
Design the method removeSorted for the class Deque that removes the node that contains the given String from this Deque.
Throw an exception, if the there is no such String.
Design the method toLowerCase for the class Deque that changes all the Strings to lower case.
The class String defines the method
toLowerCase that produces a new String with all letters changed to lower case.
Note:
Do not use this method with special characters without looking up the formal documentation for the method.