Deques

Debugging, implementing, and testing double-ended queues.¹

Learning Goals

• Understand the difference between an ADT and a data structure.

  Many students find it easier to understand these concepts by exploring a working codebase, and in this assignment, we have one with multiple ADTs and data structures.

• Practice debugging code using tests.

  Learning how to write and use tests to identify and fix flaws in a program will save us a lot of time in the future. Following the debugging cycle allows us to do so effectively and systematically.

  1. Develop a hypothesis based on what we know about the problem.
  2. Reproduce the issue in a minimal working example.
  3. Make productive changes based on the root cause discovered.
  4. If there are more issues, return to step 1.

• Apply your understanding of invariants towards testing programs.

  Data structures can be difficult to test, since simply calling the methods provided by their ADTs may not always reveal issues hidden in the remainder of the data structure’s internal state. Instead of relying only on values returned by the ADT’s methods, it can sometimes be easier to check the validity of this state directly by determining whether it violates the data structure’s invariants.

Table of contents

1. Getting Started
2. Deque ADT
3. Debugging ArrayDeque
4. Implementing LinkedDeque
5. Submission

Getting Started

To get the skeleton (starter) code for the homework, first open IntelliJ. IntelliJ should automatically open your most-recently-used project, which will likely be your personal repository for this class. In the menu bar, tap on the VCS item, then hover over the Git dropdown and tap the Pull… menu item when it’s revealed.

In the window that appears, change the “Remote” to skeleton and select skeleton/master in the “Branches to merge”. If there are no branches to merge, try tapping the refresh icon next to the remote to update the list of branches. Then, tap the blue Pull button to get the homework skeleton code.

If the deques folder that you just pulled isn’t bolded in the file explorer like intlist, and you can’t seem to run any tests, it is likely that IntelliJ didn’t react to the change in time. We can manually ask it to reimport your project.

On the far right hand side of IntelliJ, there’s a Gradle menu that you can bring up. Click on “Reimport All Gradle Projects” (refresh button):

Deque ADT

Deque (usually pronounced like “deck”) is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).²

Deques can do everything that both stacks and queues can do. Specifically, any deque implementation must have the following operations:

Unlike lists, we do not allow clients to add items to the middle of a deque. We do, however, allow clients to access elements in the deque—this method primarily exists to make it easier for us to test the implementations.

Open the Deque.java file using IntelliJ to explore the interface in more detail. There are a few important things to note here:

• The interface methods defined there include comments with extra notes on edge cases and preconditions.
• Note that this Deque interface extends Java’s Queue interface: this means that it inherits all the methods defined by Java’s Queue interface, and any implementations of this interface must define those methods as well. This is reasonable, since a deque—a double-ended queue—should have strictly more functionality than a queue.
  • In AbstractDeque.java, we define the relationships between our Deque interface and Java’s Queue; this means that subclasses of AbstractDeque can implement the functionality of a deque using our Deque interface, but also provide the functionality of a queue through Java’s Queue interface for free. (Unfortunately, Java does not have a particular interface for stacks, otherwise we would’ve implemented that as well.)
• The rest of this assignment will involve two data structures implementing the deque ADT through our Deque interface. To a client using this code, both implementations should behave the same way, even though the implementations will look drastically different—in fact, this assignment uses essentially the same tests for both implementations.

Debugging ArrayDeque

Explore the Circular ArrayDeque Demo³ below to see how the ArrayDeque works: it uses the same invariants as the ArrayQueue class presented in lecture.

We’ve provided a nearly-working implementation in src/deques/ArrayDeque.java that is intentionally buggy, along with a failing test in test/deques/AbstractDequeTests.java that causes the bug to emerge. Your task is to fix the flaw in the implementation. To the best of our understanding, there is only one problem with this class and it involves changing at most 5 lines of code.

Follow the debugging cycle:

1. Develop a hypothesis based on what we know about the problem.
   • Skim through the code in ArrayDeque.java to learn the layout of its methods and fields.
   • Run the provided tests. The tests are defined in AbstractDequeTests.java, but the actual runnable file is ArrayDequeTests.java. (Alternatively, you can run tests from AbstractDequeTests.java and select ArrayDequeTests.java when IntelliJ prompts you for which implementation to run.)
2. Reproduce the issue in a minimal working example.
   • Write and run additional unit tests to help determine what exactly is going wrong. The failing test that we provide isn’t very useful for debugging since it calls many methods—it’s difficult to figure out which of these actually contribute to the test failing. You’ll want to write some simpler tests to figure out what exactly is going wrong.
   • If you’re having trouble isolating the issue, try using the debugger on your tests to gather additional information that might be difficult or tedious to expose through testing alone.
3. Make productive changes based on the root cause discovered.
   • Make sure that the unit tests you’ve written pass after you’ve fixed the issue.
4. If there are more issues, return to step 1.

Tips

• Do not spend more than an hour debugging! It’s easy to lose track of time and get stuck in a really deep hole when debugging. Please come to drop-in times, and remember to take breaks! This course is designed to help you learn, but spending too long debugging is not the most efficient way to learn.
• Java’s own stack trace is usually pretty informative. A stack trace shows the history of an exception with the latest method calls on top. For example, the following stack trace shows that an addLast() call is responsible for a NullPointerException:

java.lang.NullPointerException
    at deques.LinkedDeque.addLast(LinkedDeque.java:44)
    at deques.AbstractDequeTests$Asymmetrical.sizeAfter_addToOppositeEnds(AbstractDequeTests.java:100)

Implementing LinkedDeque

There are many ways to implement LinkedDeque. Part of this section is to give you an opportunity to explore the kinds of decisions that go into designing a data structure. We’ll present two recommended approaches, each with their own set of invariants, to aid you in developing the data structure, but you’re welcome to solve the problem however you prefer.

1. The first approach is to use two sentinel nodes: one at the front of the deque and the other at the back.⁴ A sentinel node is a node that is always present in a linked data structure, even when the data structure is empty. The item field of the sentinel node is not used and doesn’t actually represent an item in the data structure. Using a sentinel node differs from what we saw in lecture but allows us to simplify the way that we handle empty deques.
2. The second approach is to use a single sentinel node with links wrapping around to create a circular, linked data structure.⁴

Your implementation is subject to a few additional requirements not specified by the Deque interface:

• add and remove operations must not involve any looping or recursion. A single such operation must take constant time, i.e., execution time should not depend on the size of the deque.
• get must use iteration, not recursion.
• size must take constant time. This is already done for you.

Even though you are choosing your own invariants (such as whether if you want to use sentinel nodes), our autograder does have certain baseline invariants that we expect all LinkedDeque implementations to adhere to:

• The individual nodes in your deque maintain the doubly-linked list invariant. For example, if a node curr has a curr.next, we expect to see curr.next.prev = curr.
• You are using sentinel nodes in ways that make sense. For example, if your front and back sentinels do not point to each other when the deque is empty, notice how difficult it is to insert new items.

In addition, the amount of memory that your program uses at any given time must be proportional to the number of items. For example, if you add 10,000 items to the deque, and then remove 9,999 items, the resulting data structure should use memory similar to a deque with 1 item rather than 10,000. Do not maintain references to items that are no longer in the deque.

A template for the LinkedDeque class is provided for you in LinkedDeque.java. We’ve provided some tests in the LinkedDequeTests class, but we’ll be using additional tests to grade your submission. While LinkedDequeTests is not graded, it is to your benefit to write more comprehensive tests.

Implementation Tips

• If you’re still not sure how to get started, look back at LinkedIntList. You’re also welcome to refer to LinkedStack.java and LinkedQueue.java from the Algorithms, 4e textbook as case studies. We don’t recommend copying any code from these examples since our approaches aren’t compatible, but the ideas contained within them can be helpful to study.
• Work out what your LinkedDeque will look like on paper before you try implementing them in code! If you can find a willing friend, have them give commands, while you attempt to draw everything out. Try to come up with operations that might reveal problems with your implementation.
• Make sure you think carefully about what happens if the data structure goes from empty, to some non-zero size (e.g. 4 items) back down to zero again, and then back to some non-zero size. This is a common oversight.
• Take things a little at a time. Writing tons of code all at once is going to lead to misery and only misery.

Testing and Debugging Tips

• “Get that repro”. If you find your code failing the tests on Gradescope, you should try to recreate the test locally so that you can run and debug it.
  • From the root of your repo, there is a file called test/AssertJIntro.java that walks you through testing with JUnit 5.
• We’ve also included an unimplemented getErrorMessageIfInvalid method with in LinkedDequeAssert.java. Once you implement this method, you can easily use assertThat(deque).isValid() in your tests. You can implement the method to check whether your LinkedDeque satisfies any invariants you come up with (such as whether if your single sentinel node wraps around, if the doubly linked list invariants are maintained). This code won’t be graded, though. (We’ll be running a similar check on our grader tests rather than using your implementation.)
  • We’ve provided some tests for this method as well, to demonstrate the kinds of issues you might try to detect. Note that these tests may include some cases that do not align with your particular invariants, so feel free to remove tests that don’t apply, or replace them with your own.
• Use the Java Visualizer to aid in debugging! It’s very useful for showing the current state of small programs, so write a small unit test that causes the bug to emerge, then use the debugger to access the Java Visualizer view.
• If your first try goes badly, don’t be afraid to scrap your code and start over. The amount of code for this part isn’t actually that much. (Our solution adds about 40 lines of code to the skeleton.)
• If you’ve been stuck debugging for more than an hour, take a break and work on something else. It might be particularly helpful to come back later with another perspective.

Submission

Commit and push your changes to GitLab before submitting your homework to Gradescope.