Project 1b: Data Structures Part 2

Introduction

In project 1B, you will:

In the skeleton, we have provided the following files for Phase I:

And for Phase II:

In phase I, you will create at least one Java file TestArrayDeque1B.java that acts as an ArrayDeque autograder.

In phase II, you will create four files that allow analysis of Deques of English words: Deque.java, Palindrome.java, OffByOne.java, and OffByN.java.

Unlike Project 1A, this project will be more highly scaffolded to reduce the workload in anticipation of the midterm.

Important tip: As you probably learned from Project 1A, jumping right in before you know what you're doing can cause a lot of trouble. It's OK to jump right in and start programming to clarify your thoughts and approach, but when you start feeling that creeping feeling of "hmmm... this is getting messy", you should take a step back and really think about what you're doing.

For Project 1B, if you hit this point, make sure to re-read the spec for the task you're working on! Especially for Phase I, we've provided a number of useful hints that will save you tons of time.

Getting the Skeleton Files

As before, pull the skeleton using the command git pull skeleton master.

Phase I: Randomized Testing

Here's a fun secret: The autograder project 1A largely relies on randomized tests. For example, our JUnit tests on gradescope simply call random methods of your LinkedListDeque class and our correct implementation LinkedListDequeSolution and as soon as we see any disagreement, the test fails and prints out a sequence of operations that caused the failure. In this part of the project, you'll pretend you're writing the autograder for the class using these same ideas.

There will be two new ideas:

To start off this project, you should start by making sure your IntelliJ has properly imported the project. To do this try running the StudentArrayDequeLauncher.java file. If it works you should see numbers printed by 0 and 9.

Task I:

Next, create a JUnit test file called TestArrayDeque1B.java. Start your file with the needed import statements:

import static org.junit.Assert.*;
import org.junit.Test;

In this file, write a single JUnit test marked with the @Test annotation in lab3. The name of your test method does not matter. Your test should randomly call StudentArrayDeque and ArrayDequeSolution methods until they disagree on an output. You can generate random numbers using the StdRandom library (Documentation). Use StudentArrayDequeLauncher as a guide, and if you copy and paste code from StudentArrayDequeLauncher, make sure to cite your source.

For this project, you must use Integer as your type for the Deque, i.e. StudentArrayDeque<Integer>. You should be able to find an error using only the addFirst, addLast, removeFirst, and removeLast methods, though you're welcome to try out the other methods as well.

Your test should NOT cause a NullPointerException. Make sure that you never try to remove from an empty ArrayDeque, since Integer x = ad.removeFirst() will cause a NullPointerException. Additionally, for this project always use Integer instead of int when you are retrieving values from the deques, i.e. do not do int x = ad.removeFirst(). For an explanation of why this causes problems, please read the "Frequently Asked Questions" below.

Task II:

Once you've managed to get the test consistently failing, the trickier part begins. Simply telling the student that their code fails is only going to lead to tears, sadness, confusion and late night Piazza posts. Thus, you're going to modify your autograder so that it tells the student something useful.

To do this, we'll take advantage of the assertEquals(message, expected, actual) method, which outputs a helpful message to the user.

For an example of how this method works, see AssertEqualsStringDemo.java in the examples folder.

Modify your TestArrayDeque1B.java so that the message parameter to assertEquals contains a list of operations that cause the StudentArrayDeque to output the wrong answer.

The string message provided to assertEquals must be a series of method calls, where the last call in the sequence yields an incorrect return value. For example, if adding 5 to the front, then 3 to the front, then removing from the front yields an incorrect value, then the String message passed to assertEquals should be exactly the following:

addFirst(5) 
addFirst(3)
removeFirst()

You do not need to supply the expected and actual values as part of the String message, since those are passed separately to the assertEquals statement as the expected and actual parameters. In other words, your message should NOT look like:

addFirst(5) 
addFirst(3)
removeFirst(), student was 3, correct was 7

To make your life easier, we've provided optional helper classes DequeOperation.java and OperationSequence.java. You are not required to use these files, and you're free to modify them however you wish. However, if you DO use them, you should make sure to submit them to gradescope. For examples of how to use these classes, see OperationSequenceDemo.java. Learning how to adapt existing helper classes to your own task an important skill, so we've been deliberately vague about how you should use these.

Phase I: Tips

Phase I: Frequently Asked Questions

How would I write a test for printDeque()?

It would be rather involved, and our autograder autograder isn't quite smart enough to be able to read your output anyway. Stick with the other methods. If you're really truly curious, google "redirect standard output".

I'm getting a "reference to assertEquals is ambiguous" error.

Always try searching the web for mysterious error messages. Recall that self-sufficiency as a programmer is a major goal of 61B. I think the first hit on Google should be enough, but certainly post to Piazza if you're still stuck.

I keep getting NullPointerExceptions

First, make sure you're not trying to get from somewhere beyond the size of the list. Second, if you're writing code like int result = deque.removeFirst(), instead write Integer result = deque.removeFirst().

This error happens because Java will freely convert from Integer (boxed type) to int (primitive type). This is called unboxing. However, only reference types can be null, so if you try to automatically convert a null Integer to an int, you'll get a NullPointerException in your own code. The StudentArrayDeque is buggy and may return a null (incorrectly), which can trigger this problem in your code.

The autograder is complaining about my failure sequences.

As you might imagine, the autograder for project 1B is a weirdly complex beast, as it is has to autograde autograder output. To keep things simple the String argument to a failing assert must contain a failure sequence and ONLY a failure sequence, and all tests must fail due to a failing assert. There should be no failures due to null pointer exceptions. The String argument to your assert statement must contain no extraneous information.

The autograder is still complaining about my failure sequences.

You need to include the operation that caused the failure. For example, if size() returns the wrong value, you need to include size() in your failure sequence, since you're required to provide "a series of method calls, where the last call in the sequence yields an incorrect return value". Also make sure your failure sequence only appears once!

I tried all that and the autograder is still complaining about my failure sequences.

Copy the reported failure sequence from the online autograder, and write a simple file Quick.java which generates a studentDeque, applies the operations listed, and prints the result of the final step. Chances are you'll find that the result is not the same as your test reported in the AG. Most likely you forgot to include an operation, or possibly added operations you didn't actually make.

Phase II: Word Manipulation

Before starting this part, download a list of English words from this link.

For this assignment, you'll need a correct Deque implementation. You are welcome to use your LinkedListDeque, your ArrayDeque, or the provided ArrayDequeSolution.java. You should probably not use StudentArrayDeque since you proved it's broken in Phase I, and fixing it is probably next to impossible. If you're not sure if your solution to project 1a is correct, feel free to use the provided ArrayDequeSolution.java instead.

Create an interface in Deque.java that contains all of the methods that appear in both ArrayDeque and LinkedListDeque. See the project 1a spec for a concise list.

After creating this interface, modify any Deque implementation you intend to use for later parts of this project (LinkedListDeque, ArrayDeque, or ArrayDequeSolution) so that they implement the Deque interface. Add @Override tags to each method that overrides a Deque method.

Note: If you're using ArrayDequeSolution, which relies on some inheritance black magic, your class definition should look like public class ArrayDequeSolution<Item> extends LinkedList<Item> implements Deque<Item>.

Task 1: Basic Palindrome

Create a class Palindrome, and implement the two methods shown below:

The wordToDeque method should be straightforward. You will simply build a Deque where the characters in the deque appear in the same order as in the word.

The isPalindrome method should return true if the given word is a palindrome, and false otherwise. A palindrome is defined as a word that is the same whether it is read forwards or backwards. For example "a", "racecar", and "noon" are all palindromes. "horse", "rancor", and "aaaaab" are not palindromes. Any word of length 1 or 0 is a palindrome.

'A' and 'a' should not be considered equal. You don't need to do anything special for capital letters to work properly. In fact, if you forgot that they exist, your code will work fine.

Tip: Search the web to see how to get the ith character in a String.

Tip: Inserting chars into a Deque<Character> is just like inserting ints into a LinkedListDeque<Integer>.

Tip: I do not recommend writing JUnit tests for wordToDeque. Instead, use the printDeque method to make sure things look correct.

Tip: Consider recursion. It's a more beautiful approach to this problem IMO.

Just for fun: Uncomment the main method in the provided PalindromeFinder.java class and you'll get a list of all palindromes of length 4 or more in English (assuming you also downloaded the provided words file).

Task 2: Generalized Palindrome

In this part, you will generalize your isPalindrome method by adding a new method:

The method will return true if the word is a palindrome according to the character comparison test provided by the CharacterComparator passed in as argument cc. A character comparator is defined as shown below:

    /** This interface defines a method for determining equality of characters. */
    public interface CharacterComparator {
        /** Returns true if characters are equal by the rules of the implementing class. */
        boolean equalChars(char x, char y);
    }

In addition to adding the method above to Palindrome.java, you should also create a class called OffByOne.java, which should implement CharacterComparator such that equalChars returns true for letters that are different by exactly one letter. For example the following calls to obo should return true. Note that characters are delineated in Java by single quotes, in contrast to Strings, which use double quotes.

	OffByOne obo = new OffByOne();
	obo.equalChars('a', 'b')
	obo.equalChars('r', 'q')

However, the three calls below should return false:

	obo.equalChars('a', 'e')
	obo.equalChars('z', 'a')
	obo.equalChars('a', 'a')

A palindrome is a word that is the same when read forwards and backwards. To allow for odd length palindromes, we do not check the middle character for equality with itself. So "flake" is an off-by-1 palindrome, even though 'a' is not one character off from itself.

Tip: Make sure to include @Override when implementing equalChars. While it has no effect on the function of your program, it's a good habit for the reasons detailed in lecture.

Tip: To calculate the difference between two chars, simply compute their difference. For example 'd' - 'a' would return -3.

Just for fun: Try printing out all off-by-one palindromes of length 4 or more in English (assuming you also downloaded the provided dictionary) by modifying PalindromeFinder.java. For example "flake" is an off-by-1 palindrome since f and e are one letter apart, and k and l are one letter apart.

Task 3: OffByN

In this final phase of the project, you will implement a class OffByN, which should implement the CharacterComparator interface, as well as a single argument constructor which takes an integer. In other words, the callable methods and constructors will be:

The OffBYN constructor should return an object whose equalChars method returns true for characters that are off by N. For example the call to equal chars below should return true, since a and f are off by 5 letters, but the second call would return false since f and h are off by 4 letters.

	OffByN offby5 = new OffByN(5);
	offBy5.equalChars('a', 'f')  // true
	offBy5.equalChars('f', 'h')  // false

Just-for-fun: Try modifying PalindromeFinder so that it outputs a list of offByN palindromes for the N of your choosing.

Just-for-more-fun: For what N are there the most palindromes in English? What is the longest offByN palindrome for any N?

Phase II: Frequently Asked Questions

ArrayDequeSolution won't compile.

Make sure your class definition is public class ArrayDequeSolution<Item> extends LinkedList<Item> implements Deque<Item>.

My implementation of LinkedListDeque or ArrayDeque won't compile.

Make sure your class definition ends with implements Deque<Item>.

The style checker complains that catching Exception is not OK in some of the skeleton files.

That's fine, since the autograder won't actually check these files.