PA 2: 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 work stealing algorithm.

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 ⅔ of the required memory is "wasted" overhead.

The project stages below should be completed in order. Each part builds on the work completed in the earlier stages.

Hybrid Deque Data Structure

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:

Starter 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.

Note

The provided start code related to this PA have the package declaration package pas.hybriddeque;. This means that the files should be placed in a directory named hybriddeque inside a directory named pas inside your source/project directory.

Drawing Pictures

This assignment will be impossible if you don't develop a good mental model of how the data structure is organized. The readiness quiz will require that you take some time to draw the memory layout for some sample HybridDeque objects before you start coding. You will be asked to draw a HybridDeque at each of the indicated points in the sample code below.

HybridDeque.setBlockSize(8);
HybridDeque<String> deque = new HybridDeque<>();

// Draw the deque now... (This one is done for you.)

deque.offerLast("A");

// Draw the deque now...

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

// Draw the deque now...

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

// Draw the deque now...

Here is an example of what the correct memory diagram would look like for the initial step above:

Hint

Where would "A" be stored in the diagram above? It's not at index 0 in the block. Think about the Cursor class and what it represents. The leftCursor should be pointing to the left-most item and the rightCursor should be pointing to right-most item.

If you call offerLast(), should the item be placed at the current position of rightCursor? Would that make sense? Or should it be the next position? Does that ensure both cursors are valid?

Updated 2/19: In addition, when all items are removed from a block, that block needs to be deleted. In Java, this is done by making sure there are no remaining references pointing to that object. This way, the Hybrid Deque doesn't waste any space that it doesn't need.

Part A: Hybrid Deque Readiness Quiz in Gradescope

(10% of the final grade)

Before you start coding, carefully read this document and review the provided starter code, especially HybridDeque.java. Ensure you fully understand the assignment expectations. Then, go to Gradescope and complete the Readiness Quiz.

The quiz is an assessment of your understanding, and you can submit your solution an unlimited number of times before the deadline.

Important

The comments in the provided starter code can assist you in answering some questions on the Readiness Quiz.

No late submissions will be accepted for the readiness quiz.

Part B: Hybrid Deque

Part B of the assignment involves implementing all HybridDeque methods that do not involve removing elements from the middle of the collection.

You should look through HybridDeque.java to see which methods you need to implement.

Most of these methods should have a \(\Theta(1)\) time complexity, with the exception of .equals().

Implementation Advice

Equality

Note that the equals method doesn't care about how elements are stored in the HybridDeque, only that the elements are the same and in the same order. You can have two HybridDeque objects with different numbers of blocks and different head/tail references, but they should still be considered equal if they contain the same elements in the same order.

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. The implementation may be 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 provided inner Cursor class if you would like to take this approach.

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.

We suggest hardcoding the block size to 4 or 8 while you work on your implementation. You should switch back to 64 when you submit.

We have also provided a setBlockSize method that allows you to change the block size, which should only be used for testing, and only after you have a working implementation. Here is an example of how you might use it:

@Test
public void testOfferLastLargeBlockSize() {
  HybridDeque.setBlockSize(128);

  Deque<Integer> deque = new HybridDeque<>();

  for (int i = 0; i < 500; i++) {
    deque.offerLast(i);
  }

  for (int i = 0; i < 500; i++) {
    assertEquals(i, deque.pollFirst());
  }
}

Debugging

If you are failing one of your own tests, but can't figure out why, use the debugger: First, create the simplest/smallest possible test that fails. Second, set a breakpoint at the beginning of the test. Then step through your code using the debugger to determine why the error is occurring.

Read these if you are unfamiliar with the debugger in your IDE:

• VS Code Debugging
• Eclipse Debugging
• IntelliJ Debugging

Debugging is the Key to Success

It's not enough to just write code and run tests (and maybe print things out in main).

Successful programmers use the debugger all the time. You should focus on learning how to set breakpoints, step through code, and inspect variables.

Student Tests Required

Note that we will not be providing copies of our Gradescope 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 line coverage of the HybridDeque class. Your tests should be in a separate file named TestHybridDeque.java.

The CS Wiki has a helpful guide on writing JUnit tests. Use this to help you!

Here are some additional guidelines for tests:

• Your code must pass your tests for Gradescope to run.
  • You must submit tests to Gradescope in order to receive any points.
• Tests do not need to conform to the style guide, meaning you do not need to provide JavaDoc comments for your tests.
• Updated 3/2: You do not need to test any methods from Part C. Gradescope will display them as missed, but you can ignore them.
  • However, any other methods included in the HybridDeque.java file must be tested, including Cursor methods!
  • If there are methods you don't ever use, then you should either test them or remove them. (Or think about if you should use them!)
• You do not need to worry about branch coverage. Gradescope will display branch coverage, but will not deduct points.
• You can check coverage using your IDE:
  • VS Code Coverage
  • Eclipse Coverage
  • IntelliJ Coverage

Just because you have 100% line coverage doesn't mean your tests are good OR your code is correct. You will need to write tests that cover all possible cases, including edge cases. Gradescope tests will be the final say on whether your code is correct. If your tests pass, but Gradescope says your code is incorrect, you are probably not testing thoroughly enough.

Part B Submission

Submit both HybridDeque.java and TestHybridDeque.java to Gradescope after you complete these methods. Failure to submit tests will result in a 0% for the entire assignment.

Updated 3/3: You will need to have all methods in the HybridDeque class defined in order for the autograder to run. You do not need to implement methods from Part C, but they should exist in your code. You may just have them throw an UnsupportedOperationException if you wish.

Gradescope will run multiple tests against each of the methods you implement. You will receive points based on each method/component you fully implement. Gradescope will also check to see if your methods work with different block sizes and also evaluate the efficiency of your code.

The error messages from Gradescope will typically not be very helpful, but they will indicate which method is failing. See the tips below for more info.

Part C: 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 removeLastOccurrence, removeFirstOccurrence 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 either the left or right.
• Updated 2/19: What do you do if after a removal, a block is empty? You should remove all references to that block (aka make all those references null), unless it is the only block left.

Part C Submission

Submit HybridDeque.java with to Gradescope after you complete all required methods. You do not need to submit tests for this submission.

Note: Gradescope will also check certain tests from Part B to ensure that they still pass. If your HybridDeque is not fully functional, you may receive a reduced grade for Part C.

Note that your implementation will also be manually graded for style and efficiency. You should ensure that your code is well-documented and that you have followed the style guidelines provided in the course syllabus.

Submission and Grading

The project will be graded as follows:

Component	Weight
Gradescope Readiness Quiz	10%
Part B Functionality	45%
Part C Functionality	20%
Student JUnit Tests	10%
Gradescope Style Checks	5%
Instructor Style Points	10%

Gradescope Tips

If you are failing one of our tests, carefully read the name of the test to determine what is being tested.  Create your own test that covers the same cases.

As much as possible, our tests check the entire state of the Deque after each modification (even "unrelated" parts): is the size correct? do peekLeft and peekRight return the expected elements? Make sure that your tests are doing the same.

Limited Submissions

For this project, you will be limited to 10 free Gradescope submissions each for parts B & C. Your grade will be reduced by 1% for each submission beyond 10.

You should make sure you are properly testing your code locally and fixing any style issues before submitting to Gradescope. At the same time, do not assume that because your tests pass, your code is correct. Try to submit early and regularly, but not so often that you run out of submissions.

Efficiency Checks

The Gradescope submission tests will include checks for efficiency as well as correctness. In other words, if you code a \(\Theta(1)\) operation in such a way that it requires \(\Theta(n)\) time to execute, your implementation will be considered incorrect even if it produces the expected result.

Updated 2/28: The efficiency tests can sometimes be inaccurate. If you are receiving an efficiency error on Gradescope, please double-check your implementation. If you are sure that your implementation is correct, please reach out to your instructor. They can re-run the autograder for FREE without costing an additional submission.

---

1. https://github.com/python/cpython/blob/v3.11.2/Modules/_collectionsmodule.c (https://docs.python.org/3.11/license.html)

   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 ideas. ↩