Hybrid Deque

Introduction

The Double Ended Queue, or 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.*

Essentially, our Deque implementation will be a doubly-linked list where each list node contains multiple data elements.

Part 2 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.

Implementation Advice

Drawing Pictures

This assignment will be impossible if you don't develop a good mental model of how the data structure is organized. I strongly suggest that you take some time to draw the memory layout for some sample HybridDeque objects before you start coding. As a start, try drawing the HybridDeque at each of the indicated points in the sample code below.

HybridDeque.setBlockSize(8);
HybridDeque<String> deque = new HybridDeque<>();
// Draw the deque now...

deque.offerLast("A");
deque.offerLast("B");
deque.offerLast("C");
deque.offerLast("D");

// Draw the deque now...

deque.offerLast("E");

// Draw the deque now...

deque.pollFirst();
deque.pollFirst();
deque.pollFirst();
deque.pollFirst();

// Draw the deque now...

Cursor Class

One of the challenges in implementing the HybridDeque class is that it requires two pieces of information to specify a location in the Deque: a block reference and an index into that block. I found that the implementation was simplified by creating a private inner class that encapsulates both pieces of information and handles the logic of stepping forward and backward. Feel free to make use of the following class skeleton if you would like to take this approach.

  private class Cursor {
    private final Block block;
    private final int index;

    public Cursor(Block block, int index) {
      this.block = block;
      this.index = index;
    }

    /**
     * Increment the cursor, crossing a block boundary if necessary.
     * 
     * @return A new cursor at the next position
     */
    private Cursor next() {

    }

    /**
     * Decrement the cursor, crossing a block boundary if necessary.
     * 
     * @return A new cursor at the previous position
     */
    private Cursor prev() {

    }

    /**
     * Two cursors are equal if they refer to the same index in the same block.
     */
    public boolean equals(Object other) {

    }

    /**
     * Return the element stored at this cursor.
     */
    public E get() {

    }

    /**
     * Set the element at this cursor.
     */
    public void set(E item) {

    }

  }

Smaller Block Sizes

The default block size in the provided code is 64. This follows the original Python implementation and represents a trade-off: A large block size will waste a significant amount of space for small collections that don't fill an entire block. A small block size will increase the overhead required for forward and backward references when storing large collections.

While 64 represents a good block size in terms of space efficiency, it probably isn't ideal for tracing and debugging your code during the implementation stage. Bugs are likely to pop up at block boundaries, and it is inconvenient if you need to step through dozens of operations before reaching a boundary. I suggest changing the block size to 4 or 8 while you work on your implementation. You should switch back to 64 when you submit.

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 might provide some helpful pointers.

Submission and Grading

There will be two Autolab submissions for this project. Submit HybridDeque.java, and your JUnit tests for both. The first submission will test Part 1 (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:

Note that we will not be providing copies of our Autolab submission tests for this assignment. In order to get full credit for the testing portion of the grade, you must submit JUnit 5 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 Autolab 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.7/Modules/_collectionsmodule.c
https://docs.python.org/3.7/license.html