9 3/17: Cyclic and Mutable Structures

Due: 3/17 at 11:59 PM.

Language: Java

9.1 Lab Completion

Finish the 3/10: Party invitations lab. Hand in sufficient code (and tests!) so that we can run and grade exercises 7 and 8.

9.2 Mutable Deques

We’re going to implement a mutable, direct-access list, that implements the following interface:

interface IMutableList<T> {

// Get the (zero-based) nth element from the front of the list

// Throw an error if the index is out of bounds

T get(int n);

// Set the (zero-based) nth element of the list to the new value

// and return the old value at that index.  Throw an error if the

// index is out of bounds

T set(int n, T newT);

// Insert a new element at the given (zero-based) index.  Throw

// an error if the index is less than zero or greater than length()

void insert(int n, T t);

// Remove an element at the given (zero-based) index and return it.

// Throw an error if the index is out of bounds

T remove(int n);

// Add given element on to the front of this list.

void addAtFront(T t);

// Add given element on to the end of this list.

void addAtEnd(T t);

// Compute the number of elements in this list

int length();

// Reverses the list

void reverse();

// Computes whether this list is the same as that one,

// using the provided IComparator to compare elements

bool sameList(IMutableList<T> that, ISameTest<T> areSame);

}

interface ISameTest<T> {

// Returns true if first is the same as second

bool check(T first, T second);

}

The object diagram below illustrates a Deque<String> containing four strings:

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 is null. Its role is to provide the link to the head of the list and to the tail of the list — and we let it have a data field as a convenience.

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. (This is the point of having the Sentinel: it is always the case that there is a next node after the current one; it just might be the Sentinel. So for at least some of your operations, you don’t need any special-case behavior for the end or front of the list...)

Design the classes Deque, Node and Sentinel. Make sure that Deque implements IMutableList<T>, and implement whatever helper methods are needed to make the interface work.

Test your methods carefully.