On this page:
Instructions
Problem 1: Who’s On Deque?
8.1 Data definitions and examples
8.2 Methods
Problem 2: Secret Code
7.7

Assignment 8: Mutation and ArrayLists

Goals:Design a double-ended queue, or deque (pronounced "deck"); Use ArrayLists and loops to solve interesting problems

Instructions

As always, be very careful with your naming conventions.

The submissions will be organized as follows:

Problem 1: Who’s On Deque?

We would like to build a generic 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. Here is an example of such a list (shown here with Strings), drawn as an object diagram:

              +---------------+
              | Deque<String> |
              +---------------+
              | header ----------+
              +---------------+  |
                  +--------------+
                  |
                  v
            +------------------+
+---------->| Sentinel<String> |<-------------------------------------------+
|           +------------------+                                            |
|       +---- next             |                                            |
|       |   | prev ------------------------------------------------+        |
|       |   +------------------+                                   |        |
|       |                                                          |        |
|       v                                                          v        |
| +--------------+   +--------------+   +--------------+   +--------------+ |
| | Node<String> |   | Node<String> |   | Node<String> |   | Node<String> | |
| +--------------+   +--------------+   +--------------+   +--------------+ |
| | "abc"        |   | "bcd"        |   | "cde"        |   | "def"        | |
| | next ----------->| next ----------->| next ----------->| next ----------+
+-- prev         |<--- prev         |<--- prev         |<--- prev         |
  +--------------+   +--------------+   +--------------+   +--------------+

Every Deque has a header that consists of the Sentinel node. This header field does not change, but the fields within the Sentinel node (that provide the links to the first and the last item in the Deque) can and will change.

Each data Node has two links, one to the next item in the list and one to the previous item in the list.

The Sentinel node is always present. It also has next and prev fields, which are consistently updated to link to the head of the list and to the tail of the list, respectively.

The Sentinel and Node classes both inherit from a common superclass (shown below), because the next or prev item after any given node may be either a data-carrying Node or the Sentinel marking the end of the list.

The list shown above has four data-carrying nodes and the lone sentinel. The empty list has just the Sentinel, and its links to the first and to the last item just reference the Sentinel node itself. So an empty list would have the following object diagram:

     +---------------+
     | Deque<String> |
     +---------------+
     | header ---------+
     +---------------+ |
                       |
              +--------+
+----+        |     +----+
|    |        |     |    |
|    V        V     V    |
|  +------------------+  |
|  | Sentinel<String> |  |
|  +------------------+  |
+--- next             |  |
   | prev ---------------+
   +------------------+

The class diagram for these classes is as follows:
        +--------------------+
        | Deque<T>           |
        +--------------------+
        | Sentinel<T> header |-+
        +--------------------+ |
                               |
    +--------------------------+
    |
    |
    |      +---------------+
    |      | ANode<T>      |
    |      +---------------+
    |      | ANode<T> next |
    |      | ANode<T> prev |
    |      +---------------+
    |         /_\     /_\
    |          |       |
    |     +----+       |
    V     |            |
+-------------+      +---------+
| Sentinel<T> |      | Node<T> |
+-------------+      +---------+
+-------------+      | T data  |
                     +---------+

We have an abstract class ANode<T>, which can be either a Sentinel<T> node or an actual Node<T> containing data. We use an abstract class here instead of an interface because we need to share the next and prev fields. Moreover, because all ANodes are contained and hidden within the Deque, no external code needs to know about it: they are implementation details rather than a publicly visibly datatype definition.

8.1 Data definitions and examples
8.2 Methods

Problem 2: Secret Code

Related files:
  PermutationCode.java  

Your goal is to write a program that will encode and decode secret messages using a simple mapping of letters to a permutation of all letters. So if our alphabet had only five letters (a, b, c, d, and e) we could choose to encode them as (b, e, a, c, and d). Then the received message abeedc would be decoded as cabbed and the message badace would be sent encoded as ebcbad.

Download the file PermutationCode.java. It is a skeleton for your program. Your job is to design the three methods for which the purpose statements and the headers are already provided. You may need additional helper methods. For all methods, you are expected to follow the design recipe.

The class PermutationCode contains the key for the encoding and decoding of the messages, as well as the methods that perform these tasks. There are two constructors. One allows you to specify explicitly what will be your encoding permutation. This allows you to test your methods that encode and decode the messages. The second constructor generates a new encoding permutation that may be given to the parties that wish to communicate in secret; you may assume the list given to this constructor will always be a proper permutation of the alphabet field.

Be sure to abstract if and when appropriate.