Lab 15: Mutable Lists
Intro
You’ll work in this lab with your ad-hoc partner.
The two of you will work as a team to solve problems. At any time, one of you will be the Head and the other will be the Hands. The Head does the thinking and the Hands does the typing. Hands type only what the Head tells them to, but you’re free to discuss any issues that pop up. You should switch off during the lab to make sure each of you get practice problem solving, dealing with syntax, and getting finger exercises on the keyboard.
You can start this lab with this project skeleton. (Yes, the file is named lab 17, but this is the right lab material.)
Recall
In Lab 14: Cyclic Lists we learned how to handle cycles with specialized helper methods that keep track of the head of a list. Unfortunately, the normally elegant list operations grew a bit of cruft in the process; our interface was littered with helper methods that we did not want to expose.
In this lab, we’ll see a similar problem crop up with mutable lists, and we’ll learn a new technique that will help hide these kinds of implementation details.
A List of Contacts
Your phone’s contacts can be modeled as a mutable list of objects with names and phone numbers. Each contact itself is quite simple:
class Contact { |
String name; |
Integer phone; |
Contact(String name, Integer phone) { |
this.name = name; |
this.phone = phone; |
} |
} |
We’ve provided you a basic List implementation in Contacts.java. Here’s a three-contact list that we’ll use as our running example.
+----------------------+ |
| first: Nick 555-1234 | |
| rest: ---+ | |
+--------- | ----------+ |
v |
+----------------------+ |
| first: DVH 555-0000 | |
| rest: ---+ | |
+--------- | --------- + |
v |
+----------------------+ |
| first: Sam 555-3141 | |
| rest: ---+ | |
+--------- | --------- + |
v |
+-------+ |
+-------+ |
The new feature we need is the ability to remove old contacts from this list (as we burn bridges over time), so let’s get started!
Removing from Lists
Removing a contact from the list is a bit tricky. We need to search through the contact list until we find the Contact to remove, but what do we do then?
// In Cons: |
public void removeContact(String name) { |
if (this.first.name.equals(name)) { |
// How do we remove the contact?! |
} else { |
this.rest.removeContact(name); |
} |
} |
Let’s look at what we want to happen to our contact list. If we want to remove our DVH contact, we need the rest of the Cons cell with the Nick contact to point to the Cons cell Sam contact.
+----------------------+ |
| first: Nick 555-1234 | |
| rest: | |
+-- | -----------------+ |
| |
| +----------------------+ |
| | first: DVH 555-0000 | |
| | rest: ---+ | |
| +--------- | --------- + |
| v |
| +----------------------+ |
+---------->| first: Sam 555-3141 | |
| rest: ---+ | |
+--------- | --------- + |
v |
+-------+ |
+-------+ |
So, when we identify the Cons cell that holds the contact we want to remove, we need to mutate the previous Cons cell’s rest field. We can’t do that with removeContact as it is currently written: we need to pass along the previous Cons cell as well.
Ex 3: Design the helper method void removeHelper(Cons prev, String name) that removes a contact from the list by mutating the previous Cons cell to point to the rest of the contact list. The argument prev should always point to the previous Cons cell so its rest field can be modified.
Ex 4: There is a contact in the list that can’t be removed with this design: which is it?
A New Start
As you noticed in Ex 4, it’s not possible to remove the first contact in the list because there is no previous Cons cell to modify.
The solution: create a special cell at the head of the list with no contact. This special cell is known as a Sentinel. It is similar to a Cons cell, in that it has a rest field that points to a ListofContact.
+-------+ |
| rest: | |
+--- | -+ |
v |
+----------------------+ |
| first: Nick 555-1234 | |
| rest: ---+ | |
+--------- | ----------+ |
v |
+----------------------+ |
| first: DVH 555-0000 | |
| rest: ---+ | |
+--------- | --------- + |
v |
+----------------------+ |
| first: Sam 555-3141 | |
| rest: ---+ | |
+--------- | --------- + |
v |
+-------+ |
+-------+ |
This allows our removeHelper to accept either the Sentinel or a Cons as the previous cell to mutate. To get keep Java’s type system happy, we need to modify our class hierarchy so Cons and Sentinel extend a shared abstract class Cell.
Ex 5: Add the following classes to your Contacts.java:
abstract class Cell implements IListofContact { |
IListofContact rest; |
Cell(IListofContact rest) { |
this.rest = rest; |
} |
} |
|
class Sentinel extends Cell { |
Sentinel(IListofContact rest) { super(rest); } |
|
public Optional<Integer> findPhoneNumber(String name) { |
return this.rest.findPhoneNumber(name); |
} |
|
public void removeContact(String name) { |
this.rest.removeHelper(this, name); |
} |
|
public void removeHelper(Cell prev, String name) { |
throw new RuntimeException("This will never be called!"); |
} |
} |
Ex 6: Modify the IListofContact.removeHelper signature to accept a Cell as the previous node to modify. Update your Mt and Cons removeHelper signatures to follow suit.
Ex 7: Change the Cons class to extend Cell. Remove the Cons.rest field and place a call to super(rest) as the first line in the Cons constructor.
At this point, the same tests should pass/fail. But we can modify the Main.initData method to create a list with a Sentinel at the head to get all our tests to pass!
void initData() { |
this.contacts = |
new Sentinel(new Cons(nick, new Cons(dvh, new Cons(sam, new Mt())))); |
} |
Wrapping Up
It’s great that our tests pass, but a few issues remain.
First, users of our mutable lists will now need to create instances of Sentinel to wrap around their underlying Cons or Mt instances.
Second, the API presented by the interface includes removeHelper, which is an implementation detail that should not be used external to the implementation of the classes.
Ex 8: Design a wrapper class MutableList to encapsulate the Sentinel class. It should accepts either an Mt or Cons IListofContact in its constructor and have a single field where it stores that list after placing a Sentinel at its head.
Once you’ve done this, the MutableList class can expose the proper methods: removeContact and findPhoneNumber without exposing the implementation details of the Sentinel or removeHelper.
Ex 9: Fix up the tests to operate on your new MutableList.
Submission
Submit a zip file of your work at the end of lab.