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:
Submission Homework 8 Problem 1: The Deque.java file with all its classes, interfaces, methods and tests.
Submission Homework 8 Problem 2: The Permutation.java file with all its classes, interfaces, methods and tests.
Due Date: March 23rd at 9:00pm
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 ---------------+
+------------------+ +--------------------+
| 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
Define the classes ANode<T>, Node<T>, Sentinel<T>, and Deque<T>.
For Sentinel<T>, define a constructor that takes zero arguments, and initializes the next and prev fields of the Sentinel to the Sentinel itself.
For Node<T>, define two constructors: the first one takes just a value of type T, initializes the data field. The next and prev fields would be null. The second convenience constructor should take a value of type T and two ANode<T> nodes, initialize the data field to the given value, initialize the next and prev fields to the given nodes, and also update the given nodes to refer back to this node. Throw an IllegalArgumentException in this constructor if either of the given nodes is null. (You can use if (theNode == null) { ... } to test for null-ness.) Note carefully the order of the arguments in this constructor! The order should match the class diagram above; getting the order wrong will result in oddly “backwards” lists.
For Deque<T>, define two constructors: one which takes zero arguments and initializes the header to a new Sentinel<T>, and another convenience constructor which takes a particular Sentinel value to use.
Make examples of three lists: the empty list, a list of Strings with the values ("abc", "bcd", "cde", and "def") shown in the drawing at the beginning of this problem, and a list with (at least) four values that are not ordered lexicographically. (Hint: If you’ve defined your constructors correctly, you shouldn’t need to use any explicit assignment statements in your examples class!)
(Make more examples as needed to test the methods you define.)
Name your examples class ExamplesDeque, and your first three examples deque1, deque2 and deque3.
8.2 Methods
Design the method size that counts the number of nodes in a list Deque, not including the header node. (I.e., just count the Nodes and not the Sentinel.)
Design the method addAtHead for the class Deque that consumes a value of type T 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 value of type T 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 a RuntimeException if an attempt is made to remove from an empty list. Be sure to fix up all the links correctly! As with ArrayList’s remove method, return the item that’s been removed from the list.
Design the method removeFromTail for the class Deque that removes the last node from this Deque, analogous to removeFromHead above. Again, be sure to fix up all the links correctly!
Design the method find for the class Deque that takes an Predicate<T> and produces the first node in this Deque for which the given predicate returns true.
If the predicate never returns true for any value in the Deque, then the find method should return the header node in this Deque. (Hint: think carefully about the return type for find!)
Problem 2: Secret Code
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.
Design the method decode that will consume the encoded message and use the ArrayList code to decipher the message, one character at a time. Look up methods you may use with the data of the type String in the Java documentation. You may assume all the characters in the string can be found in the alphabet field (and therefore, the code field as well).
Design the method encode that will consume the message we wish to encode and use the ArrayList code to produce the encoded message, —
again — one character at a time. You may assume all the characters in the string can be found in the alphabet field (and therefore, the code field as well). Design the method initEncoder that produces a random permutation of the 26 letters of the alphabet and returns it as an ArrayList of Characters.
Hint: Make a copy of the alphabet list, then remove one character at random and add it to the encoder list, until all letters have been consumed.
Be sure to abstract if and when appropriate.
Problem 3: Vigenere Cipher (Extra Credit)
This problem is extra credit to be done individually. You can do it if you choose, but it will not negatively affect your grade if you choose not to. Your code must compile and be a good attempt in order to earn any extra credit.
Your goal is to write a program that will encode and decode secret messages using the Vigenère cipher. The Vigenère Cipher encrypts alphabetic text by using a simple form of polyalphabetic substitution, which uses multiple substitution alphabets. The encryption of the original text is done using the Vigenère table (unlike the table below, we will use lower case letters for our alphabet):
The table has 26 rows of the alphabet where each row is shifted to the left compared to the previous row. The cipher uses a different alphabet from one of the rows at different points in the process. The alphabet used at each point depends on a repeating keyword.
For example, the message we want to encrypt is "thanksgiving" and the keyword is "happy". To generate the key, we repeat the keyword until it is the length of the plain text. So the key would be "happyhappyha".
To encrypt, we do the following. Take the first letter of the message, ’t’, and pair it with ’h’, the first letter of the key. So we use row ’t’ and column ’h’ of the Vigenère square, getting ’a’. For the second letter of the message, we use the second letter of the key: the intersection of row ’h’ and column ’a’ gives us the second letter of the encrypted message, ’h’. The rest of the message is encoded in this way. Encoding the message "thanksgiving" would produce "ahpcizgxkgug".
To decode a message, we go to the row in the table corresponding to the first letter of the key. In this row, we find the position of the first letter of the encoded message, and use the column’s label as the first letter of the message. For example, in row ’h’, the first letter of the encoded message ’a’ appears in column ’t’, which is the first letter of the message. Next, we go to row ’a’, locate the ’h’ which is found in column ’h’, so ’h’ is the second letter of the message. The rest of the message is decoded in this way.
Your job is to design the Vigenere class which has two fields and three methods. The first field is named alphabet which is an ArrayList<Character> and it holds all 26 letters of the alphabet similar to the PermutationCode class from Problem 2. The second field is named table which is an ArrayList<ArrayList<Character>> (described above). The Vigenere class has the three methods below. The constructor of the class should generate the Vigenère table. You may need additional helper methods. For all methods, you are expected to follow the design recipe.
Design the method initVigenere that produces the Vigenère table as an ArrayList<ArrayList<Character>>.
Design the method decode that will consume the encoded message and the keyword and use the Vigenère table to decipher the message, one character at a time. You will need to produce the key from the keyword first. You may assume all the characters in the string can be found in the alphabet (and therefore, the code field as well).
Design the method encode that will consume the message we wish to encode and the keyword and use the Vigenère table to produce the encoded message, —
again — one character at a time. You will need to produce the key from the keyword first. You may assume all the characters in the string can be found in the alphabet (and therefore, the code field as well).