Deques

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

Learning Goals

• Identify flaws in a program using the debugging cycle.

  1. Develop a hypothesis based on what we know about the problem.
  2. Gather information about the program to identify the root cause.
  3. Make productive changes based on the root cause.
  4. If the bug is not fixed, return to step 1.

  Learning how to apply this process to identify flaws in a program will save a lot of our time in the future. When a TA is assisting a student in office hours, they typically use exactly this process but they bring to bear more experience about where and how flaws tend to develop in a program.

• Understand the difference between implementing an ADT and using an ADT.

  The first part of the assignment involves fixing and developing two different data structures that both implement the Deque ADT. The second part of the assignment involves using these ADT implementations to solve the problem of identifying palindromes.

• Apply your understanding of invariants towards testing programs.

  Unit tests are code. Writing code for unit tests is a skill, just as writing code for programs is a skill. In several of the following homework assignments, you will be expected to verify the correctness of the programs you write, and the most convenient way to do this in an automated manner is to write tests to verify it for us.

Table of contents

1. Getting Started
2. Deque API
3. Debugging ArrayDeque
4. Implementing LinkedDeque
   1. Testing LinkedDeque
5. Palindromes
   1. Implementing wordToDeque
   2. Testing isPalindrome
   3. Implementing isPalindrome
   4. Generalizing isPalindrome
   5. Implementing randomPalindrome
6. Submission

Getting Started

To get the skeleton (starter) code for the homework, open IntelliJ. IntelliJ should automatically open your most recently used project containing the contents of your personal repository. In the menu bar, tap on the VCS item, then hover over the Git drilldown 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.

Then, right click the data folder in the Project Tool Window. In the Git submenu, choose Repository… and then Pull to get the new data files for this assignment.

Deque API

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 exactly the following operations.

• public void addFirst(T item): Adds an item of type T to the front of the deque.
• public void addLast(T item): Adds an item of type T to the back of the deque.
• public boolean isEmpty(): Returns true if deque is empty, false otherwise.
• public int size(): Returns the number of items in the deque.
• public T removeFirst(): Removes and returns the item at the front of the deque. If no such item exists, returns null.
• public T removeLast(): Removes and returns the item at the back of the deque. If no such item exists, returns null.
• public T get(int index): Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth. If no such item exists, returns null. Must not alter the deque!

Unlike lists, we do not allow users to add items to the middle of a deque.

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 ArrayDeque.java, along with a failing test in ArrayDequeTest.java. Your task is to fix the flaw in the implementation. To the best of our understanding, there is only one bug in this class. Our fix involves changing no more than 5 lines of code.

Follow the debugging cycle. Use the IntelliJ debugger and the Java Visualizer to aid in gathering information.

1. Develop a hypothesis based on what we know about the problem.
2. Gather information about the program to identify the root cause.
3. Make productive changes based on the root cause.
4. If the bug is not fixed, return to step 1.

As we learned in lecture, we can also gather information from the test itself. We recommend reading the code by first skimming all of ArrayDeque.java to learn the layout of methods and variables and then analyzing ArrayDequeTest.testTricky.

Do not spend more than an hour debugging! Drop-by office hours and remember to take breaks. This course is designed to help you learn efficiently and the course staff are here to help you along the way. But spending too much time debugging is not the most efficient way to learn. This guideline applies to all assignments in this course.

Implementing LinkedDeque

There are many ways to implement LinkedDeque. Part of this section is to give you an opportunity to explore implementation design decisions. 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 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 represent an empty deque.
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.

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 size should be more like a deque with 1 item than 10,000. Do not maintain references to items that are no longer in the deque.

Testing LinkedDeque

Two starter tests are provided in the LinkedDequeTest class. While LinkedDequeTest is not graded, it is to your benefit to write more comprehensive tests. One place to start is to adapt ArrayDequeTest.testTricky for LinkedDeque by copying the unit test into the LinkedDequeTest class and making a few changes. But it’s also important to write simpler unit tests that check to make sure that inserting one item works, for example.

Two larger-scale tests are provided in the LargeScaleLinkedDequeTest class. These tests compare the output of the reference model ArrayDeque against the testing implementation LinkedDeque. (This relies on a correct ArrayDeque implementation.) If a test fails for whatever reason, the sequence of operations will be printed out so that you can create a new test with the exact sequence of operations for debugging purposes.

Tips

• If you’re not sure how to get started, look back at LinkedIntList. You’re also welcome to refer to LinkedStack.java and LinkedQueue.java from the 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.
• Take things a little at a time. Writing tons of code all at once is going to lead to misery and only misery. If you wrote too much stuff and feel overwhelmed, comment out whatever is unnecessary.
• 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.)
• 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.
• If you’ve been stuck debugging for more than an hour, take a break and work on the next part first which only requires one of either ArrayDeque or LinkedDeque working.
• Use the Java Visualizer to aid in debugging!

Palindromes

In this part of the homework, we will write a few methods using our deque implementations and write tests for them. The tests you write for this part are graded.

Warning

The autograder output for this part is going to be terse and unhelpful. This is because we want you to use your tests to build confidence in your code. You will not be able to rely on the autograder for correctness.

Implementing wordToDeque

Implement Palindrome.wordToDeque(String word). Given a string word, wordToDeque should return a Deque<Character> where the characters appear in the same order as in the word. For example, if the word is “persiflage”, then the returned deque should have ‘p’ at the front, followed by ‘e’, and so forth.

Don’t implement wordToDeque yet! Instead, run the unit test provided in PalindromeTest first which should fail since we haven’t implemented the method. Your goal is to now pass this test by correctly implementing wordToDeque, running the test and using the debugger to gather more information about the state of the deque that you’re creating.

Testing isPalindrome

The Palindrome.isPalindrome(String word) method should return true if the given word is a palindrome, and false otherwise.

However, because there are no tests for this method, we have no way of telling if our implementation will work. Before we implement isPalindrome, let’s write some tests. Add at least one test to the PalindromeTest class that tests the isPalindrome method.

You’ll probably find the assertTrue and assertFalse methods to be useful. You’re also welcome to use any other methods in the JUnit documentation. Ideally, you should write several tests, and not just one, but it’s up to you how to divide the methods as long as PalindromeTest provides good overall coverage of the different possible inputs to isPalindrome. It’s OK to have multiple asserts in one test, though don’t go too wild. IntelliJ can help you create test methods.

When you run PalindromeTest, your code should fail all of the tests because we have not yet implemented isPalindrome.

Implementing isPalindrome

Now that you have a failing test, implement the Palindrome.isPalindrome(String word) method. Use your wordToDeque method to simplify the implementation.

While you can technically not use a deque at all, we strongly encourage you to do so. It’s a good exercise in understanding how your choice of abstract data types and data representation (in this case, deque) will have a profound effect on how you write your code. However, don’t use the get method of your deque. Abstract data types likes deques are useful as a way of organizing data and access patterns by restricting the ways in which we access items. The restriction of only being able to add or remove items from the front and the back of a deque affects the way we design algorithms for solving problems like isPalindrome.

Once you’ve passed your own tests, you’re ready to move on. Keep in mind that our autograder is going to be very quiet, so you’ll want to make sure your tests are thorough so that you feel good about your code. At the very least, you should have at least one test that checks that some word is a palindrome, and one that checks that some word is not a palindrome, as well as two interesting corner cases.

Tip

Consider recursion. There’s a really elegant solution that uses recursion. You’ll need to create a private static helper method for this to work.

Tip

If you’re failing your own test and can’t figure out why, remember that you can use the debugger and the Java Visualizer.

Once you have a functioning implementation of isPalindrome, you can run the PalindromeFinder to get a list of all English palindromes of length 4 or more.

Generalizing isPalindrome

There is a second Palindrome.isPalindrome method that accepts a CharacterComparator in addition to a word. For the purposes of palindrome detection, CharacterComparator allows us to define what it means for two characters to be considered equal to each other by implementing the equalChars method. OffByOne is a class that implements CharactorComparator such that equalChars returns true for characters that are different by exactly one, i.e. characters that are exactly one (letter) away from each other, rather than the exact same character.

OffByOne obo = new OffByOne();

obo.equalChars('a', 'b');  // true
obo.equalChars('r', 'q');  // true

obo.equalChars('a', 'e');  // false
obo.equalChars('z', 'a');  // false
obo.equalChars('a', 'a');  // false

1. Write tests in OffByOneTest for OffByOne.equalChars. Use the provided static offByOne. The autograder will replace this instance with various buggy implementations to run “meta-tests” that test the thoroughness of your tests.
2. Write tests in PalindromeTest for the second Palindrome.isPalindrome method. Use new OffByOne() to instantiate a CharacterComparator.
3. Implement the isPalindrome method and verify that it works.

Note

To allow for odd length palindromes, we do not check the middle character for equality with itself. So “flake” is an off-by-one palindrome, even though ‘a’ is not one character off from itself.

As with our earlier isPalindrome method, any zero or one character word is considered a palindrome. Even though a good solution for Palindrome and OffByOne should not explicitly worry about non-alphabetical characters or uppercase letters, your tests could hypothetically be run on a poor solution, and thus in that case should try to cause errors that only apply to non-alphabetical characters.

Once you have a functioning implementation of isPalindrome, you can modify PalindromeFinder to use your new isPalindrome method and OffByOne class to list all English off-by-one palindromes of length 4 or more.

Implementing randomPalindrome

In addition to OffByOne, we have provided starter code for the DNABasePair class that also implements CharacterComparator. DNA bases are one of either A, T, C, or G. A palindromic sequence is a DNA palindrome where equalChars is defined by the DNABasePair.complement.

Implement the DNABasePair.randomPalindrome method to generate a DNA palindromic sequence of the given length using the provided random instance. Your implementation should repeatedly call random.nextInt(4) to compute random DNA bases from left to right for the first half of the palindrome (including the middle item in odd-length palindromes). Then, use the complement method to fill in the second half of the palindrome. You don’t need to use your deque implementation for this part.

Submission

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