James Madison University, Fall 2017

Hybrid Deque

Introduction

The Deque (pronounced "deck") is an abstract data type that allows elements to be appended and removed from either end of a sequence. The Java collections framework includes a Deque Interface along with several implementing classes. These include the ArrayDeque, (implemented using a circular dynamic array), and LinkedList (implemented using a doubly-linked list).

Note that the Deque is not a widely used abstract data type. In most cases it makes more sense to use either a Stack or a Queue, depending on the application. The most commonly cited example of an application that does require a Deque is the A-Steal job scheduling algorithm. In practice, the Java Deque interface is most frequently used in place of a Stack, since there is no pure Stack interface in the Java collections framework.

The goal of this assignment is to develop a new Deque implementation that satisfies the following design requirements:

Worst case \(\Theta(1)\) append and remove operations at either end.
Efficient use of space for large collections.

Neither ArrayDeque nor LinkedList satisfy both of these requirements. While the ArrayDeque provides amortized \(\Theta(1)\) append and remove operations, the need to resize the underlying array means that appending will occasionally require \(\Theta(n)\) steps. The LinkedList does provide \(\Theta(1)\) append and remove in the worst case, but it is quite inefficient in terms of space. The need to store backward and forward references for each item stored means that as much as 2/3 of the required memory is "wasted" overhead.

Part 1: Hybrid Deque

For this project we will develop a HybridDeque class that combines some of the advantages of contiguous and linked data structures. Our implementation is inspired by the Python deque collection. The following description is taken from the internal documentation for that class:

Data for deque objects is stored in a doubly-linked list of fixed length blocks. This assures that appends or pops never move any other data elements besides the one being appended or popped.

Textbook implementations of doubly-linked lists store one datum per link, but that gives them a 200% memory overhead (a prev and next link for each datum) and it costs one malloc() call per data element. By using fixed-length blocks, the link to data ratio is significantly improved and there are proportionally fewer calls to malloc() and free(). The data blocks of consecutive pointers also improve cache locality.*

Basically, our class will be a doubly-linked list where each list node will contain multiple data elements.

Part 2: Palindrome Check

As a simple application to test your Deque data structure, you will use it to determine if a provided string is a palindrome (a word or phrase that is spelled the same forward and backwards). Note that the string provided may included spaces, punctuation, and a mix of upper- and lower-case letters; your palindrome check needs to ignore these. For instance, the following phrase is a valid palindrome and your check must return true:

"A man, a plan, a cat, a ham, a yak, a yam, a hat, a canal-Panama!"

A Deque provides an elegant solution to this check, as it can determine if a string is a palindrome without storing external information. Specifically, you can traverse through the string, appending each letter to the end of the Deque. Once all of the letters have been added, you can pull the first and last letters ("A" and "a" in this case) and compare. If they match, pull the first and last again. Repeat this process until either the letters don't match (not a palindrome), the Deque is empty, or there is only a single letter.

The provided code includes a Palindrome class. In the constructor, you should create the Deque and fill it with the letters from the string. There is also a check method that will return true if the string is a palindrome.

Part 3 Mid-Deque Removal

While the Deque interface is primarily designed to allow access to elements at the ends of the sequence, there are a few methods that allow an item to be removed from the middle. These are removeLastOccurance, removeFirstOccurance and the remove methods of the two iterators. These methods are relatively challenging to implement because removing an element from middle of the sequence requires shifting all subsequent elements left to fill the vacated space.

Some issues to keep in mind while implementing removal:

Don't code the removal logic four times! You should create a helper method to handle removal and use it as needed in your other methods.
The most efficient implementation would first determine whether the item to be removed is nearer to the beginning or the end of the sequence. Elements near the beginning would be removed by shifting preceding elements to the right while elements near the end would be removed by shifting subsequent elements to the left. YOUR CODE DOESN'T NEED TO HANDLE THESE TWO CASES DIFFERENTLY. For the sake of simplicity, we suggest that you always shift elements to the left to handle removal.
Removing the last element may need to be handled as a special case. It is the only case that doesn't require shifting elements to the left.
The case where rightIndex is 0 is also a special case. Once the final element is removed from a block, the entire block should be removed from the data structure.

Provided Code

The following files are provided:

AbstractDeque.java - The Deque interface has three super-interfaces: Collection, Iterable and Queue. Any class that implements the Deque interface must provide concrete versions of the methods declared in Deque as well as all of it's super-interfaces. In all, this is around 40 methods. The AbstractDeque class facilitates the creation of new Deque implementations by providing default implementations for many of these methods. YOU SHOULD NOT NEED TO MODIFY THIS CLASS.
HybridDeque.java - This is the starter code for your Deque implementation. Your implementation must conform to the implementation notes included in the comments for this file.
Palindrome.java - This class uses your Deque to determine if a string is a palindrome.

Implementation Advice

Existing Implementation

As we mentioned above, the design of the HybridDeque class is based on the C implementation of Python's deque collection. You are welcome to examine to the existing C implementation as you work on your code. It probably isn't a good idea to attempt a line-for-line translation from C to Java, but the C code should provide some helpful pointers.

Submission and Grading

There will be two Web-CAT submissions for this project. Submit HybridDeque.java, Palindrome.java and JUnit tests for both. The first submission will test Parts 1 and 2 (i.e., no tests for removing items from the middle or with the iterators). The second submission will test your removal implementation. The project will be graded as follows:

The project will be graded as follows:

Web-CAT Functionality Parts 1 and 2	40%
Web-CAT Functionality Part 3	20%
Student JUnit Tests	10%
Web-CAT Style Checks	10%
Instructor Style Points	20%

Note that we will not be providing copies of our Web-CAT submission tests for this assignment. In order to get full credit for the testing portion of the grade, you must submit JUnit tests that provide full method coverage of the HybridDeque class. Recall that method coverage is a low bar for testing. It only requires that each method be executed by at least one of your tests. Our intention is to give you the responsibility for testing and debugging your own code without requiring you to submit a comprehensive test suite.

You will be limited to 10 free Web-CAT submissions for this assignment. Your project grade will be reduced by 1% for each submission beyond 10.

Any submission that doesn't pass all of the instructor unit tests will receive at most 50% of the points for that component of the grade.

* https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c
https://docs.python.org/3.5/license.html