Project 1B: Applying and Testing Data Structures version 1.0

Introduction

In most of your prior programming assignments, you’ve relied on some external source of truth to tell you that your code was correct.

In this project, you’ll use your one of your deques from project 1A to solve a real world problem. Specifically, you will write a class with methods that decide if a given a word is a palindrome, a word that can be read the same forward and backward. For example, the words “noon”, “racecar”, and “mom” are palindromes. You will then expand the functionality of this class by giving it the ability to find generalized palindromes. For example, the word “flake” is an off-by-one palindrome. If we forgive differences between characters that are 1 away in the alphabet, it reads the same when read forward and backward (‘f’ and ‘e’, and ‘k’ and ‘l’ are one away from each other).

Along the way in this project, you’ll also write tests of your application to convince yourself that everything works correctly.

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

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

Set Up

Snaps Backups

The snaps repository you set up in lab 2 saves frequent backups of your work to your local computer. To make these backups available on Github, you can push them by following the directions below. If you’re OK with staff taking an early look at your snaps repo fill out this form. Otherwise, we won’t look at your snaps repo as described in Josh’s post.

To push your snaps backups to Github, open a new terminal window (Git Bash on Windows), and run the following commands, one by one:

cd $SNAPS_DIR
git push

That’s it! You can close the terminal window and continue working on this project!

Skeleton Files

Pull the skeleton using the command git pull skeleton master.

In the skeleton, we have provided the following files:

We also made a file for you, words.txt, with tens of thousands of English words that will help you test your program. To get it, run the following when in your fa20-s*** repo:

cd library-fa20
git pull origin master

If git pull origin master didn’t work, try git submodule update --recursive --remote from your fa20-s*** repo.

Note: We’ve set up your git repository so that it will reject words.txt by default, since it is too large to upload to the grader. So, don’t try to move it outside of the library-fa20 folder. Please don’t use the -f command to force this large file into your repo. It will slow down the autograder.

For this assignment, you’ll also need a correct Deque implementation. You are welcome to use your LinkedListDeque or your ArrayDeque from Project 1A. To do this,
simply copy over one of your implementations to the proj1b folder. This can be done by running the following command, when you are in your fa20-s*** repo:

cp proj1a/ArrayDeque.java proj1b/

You can replace ArrayDeque.java with LinkedListDeque.java if you prefer to use that implementation.

If you’re not sure if your solution to Project 1A is correct, or you just didn’t finish, you may download a correct implementation of LinkedListDeque by left clicking on this link. In your proj1b folder make a new file called LinkedListDeque.java and manually copy and paste the displayed code.

Setting up via Intellij

You can open the proj1b folder in Intellij as normal. However, we’ve seen a few issues with students’ Intellij not recognizing the code as Java because most of it is commented out. If it seems ilke your class files have red circles near them, there are a few fixes to this issue:

  1. Mark the source directory (proj1b) as “Sources Root”. You can right click the proj1b directory in Intellij → Mark Directory as → Sources Root.
  2. Uncomment TestPalindrome.java and TestOffByOne.java, and try reimporting again.

Task 1: Deque Interface

In this project you will find palindromes using a Double Ended Queue structure. Recall that we defined the Deque API, or behavior, by the following methods:

public void addFirst(T item)
public void addLast(T item)
public boolean isEmpty()
public int size()
public void printDeque()
public T removeFirst()
public T removeLast()
public T get(int index)

Since your program will rely on this behavior, it shouldn’t matter to it what Deque implementation it is provided, ArrayDeque or LinkedListDeque, and should work for both. To achieve this, we will use the power of interfaces.

This first task is going to be a little tedious, but it won’t take long.

Create an interface in a new file named Deque.java that contains all of the methods above. In IntelliJ, use “New → Java Class”. IntelliJ will assume you want a class, so make sure to replace the class keyword with interface.

Modify your LinkedListDeque and/or ArrayDeque so that they implement the Deque interface by adding implements Deque<T> to the line declaring the existence of the class. If you used something other than T for your generic type parameter, use that instead. Add @Override tags to each method that overrides a Deque method.

Note: If you’re using the provided solution for LinkedListDeque, which relies on some inheritance black magic, your class definition should look like

public class LinkedListDeque<Item> extends LinkedList<Item> implements Deque<Item>

Now, in the Deque interface,give isEmpty() a default implementation, which returns true if the size() is 0. Since your LinkedListDeque and/or ArrayDeque implement the Deque interface, given the default isEmpty() implementation, you can remove that method from the LinkedListDeque and/or ArrayDeque that you copied over to the proj1b folder.

Task 2: wordToDeque

Create a new file called Palindrome.java. In our final program, we will use a Palindrome object to help us decide whether certain English words are palindromes (or generalized palindromes). But first, we will add a helper function that given a String, wordToDeque should return a Deque where the characters appear in the same order as in the String. For example, if the word is “persiflage”, then the returned Deque should have ‘p’ at the front, followed by ‘e’, and so forth.

In Palindrome.java, add a method with the signature shown below:

public Deque<Character> wordToDeque(String word)

Don’t write any code yet for this method.

For now, just have it return null so that Palindrome.java can compile.

Uncomment the code in TestPalindrome and run the test contained in the file. You should fail the provided test. This makes sense. The JUnit test in this class checks that your
wordToDeque implementation is correct, but you have not written it yet.

While it may seem strange, this is the recommended way to go about writing code. Especially when writing big programs. You should first write a test that checks
that your implementation is correct, carefully thinking about all edge cases you need to check for. This will help you organize your thoughts and be aware of cases you need to account for when you actually get to writing your method.

Notice line 7 in this class:

static Palindrome palindrome = new Palindrome();

Make sure to not alter this line. If you do, the autograder may not work for you.

The first thing that may seem strange is that this code compiles even though we never defined a Palindrome constructor. Turns out that all classes in Java have a default constructor. Thinking about our beloved environment diagrams, this constructor will make an empty “object box” of type Palindrome and save a reference to it in the static variable palindrome. The Palindrome class is not going to define any instance variables, and we really only need Palindrome instances to call the instance methods you will define in this class (one of which is wordToDeque). So, the default constructor suffices here.

You’d notice that this static variable is missing an access modifier, such as public or private. When no access modifiers are specified Java gives the variable or method the default “package private” modifier. It means that any class in the same package will have access to these components. We will learn more about packages soon, and will even work with them in HW1. For now, you can assume that any class in the proj1b folder will have access to this static variable.

Throughout this project, the testing classes will follow the same layout of this one. Do not instantiate objects (using new) in your JUnit test methods. Instead, instantiate objects are instantiated in static variables of the testing class. This will ensure you can use them across all your testing methods. This is mostly to allow our grader to test your tests. When you write JUnit tests in the future you can definitely instantiate objects inside your JUnit tests.

Your goal is to now pass this test by correctly implementing wordToDeque. Once you’ve passed the test, move on to the next part of this assignment.

Tips

Task 3: isPalindrome

Now that you’re passing the test and getting to enjoy the nice green glow of the success bar, let’s break things again.

Modify your Palindrome.java so that it now has a second method with the signature below.

public boolean isPalindrome(String word)

For now, have it return a dummy value, some arbitrary thing you select, i.e. either true or false, that will allow the code to compile. Before we write the method itself, we’re going to write a test. Let’s start by discussing what isPalindrome is supposed to do.

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 forward or backward. 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. If the argument word is null, the method should return false.

‘A’ and ‘a’ should not be considered equal. However, you can assume we will only be working with lower case characters in this project.

isPalindrome Testing

Add JUnit tests to TestPalindrome, testing 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. It’s ok to have multiple asserts in one test, though don’t go too wild. Make sure to annotate your tests with @Test, otherwise JUnit won’t run your tests.

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.

When you run TestPalindrome again, your code should fail your tests.

Tips

Writing isPalindrome

Now that you have a failing test, implement the isPalindrome method. Use your wordToDeque method to make this task easier for yourself. While you can technically not use a Deque at all to solve this problem, we hope that this exercise will demonstrate how your choice of data structures (in this case, Deque) will have a profound effect on how you write your code.

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 you can feel good about your code.

Tips

Task 4: Generalized Palindrome and OffByOne

However, you’re welcome to do them in any order you choose. For this task, rather than carefully enumerating everything you’re supposed to do, as in the tasks above, we will simply give a general description of your goal.

In this task, your ultimate goal is to add a third public method to your Palindrome class with the following signature:

public boolean isPalindrome(String word, CharacterComparator cc)

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

public interface CharacterComparator {

    /** Returns true if characters are equal by the rules of the implementing class. */
    public boolean equalChars(char x, char y);
}

For this task, you’ll create a class called OffByOne.java, which should implement CharacterComparator such that equalChars returns true for characters that are off by one from each other. For example, the following calls to equalChars should return true. Note that characters are delineated in Java by single quotes, in contrast to Strings, which are delineated by double quotes.

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

However, the three calls below should return false:

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

Note: Every char in Java has an associated integer. For example, “under the hood” 'a' is 97. Convince yourself that this is true by running variants of the following (either in a main method in a class of your choosing, or the Java Visualizer)

int x = `a`;
System.out.println(x);

For this reason, you can perform arithmetic operations on characters, so 'b'-'a' will evaluate to 1.

Characters in Java include non-alphabetical characters. These also have integer values associated with them. For example, '%'' is 37 and '&'' is 38. So, '%'' and '&'' are off by one, and the following should reutrn true:

OffByOne obo = new OffByOne();
obo.equalChars('&', '%');

You should add the method signature to OffByOne and have it return a dummy value. Then only proceed to completing it after you have written tests in TestOffByOne.

After you are done writing your OffByOne class, implement the overloading isPalindrome in your Palindrome class and have it return a dummy value for now.

public boolean isPalindrome(String word, CharacterComparator cc)

In your TestPalindrome add a JUnit test for this method, sending in an OffByOne object as the CharacterComparator argument. You are allowed to instantiate new OffByOne objects in JUnit tests in TestPalindrome. Once you feel you have a high quality test, you can complete the method and verify that it is correct using your test.

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.

As with our earlier isPalindrome method, any zero or 1 character word is considered an off-by-one palindrome. Additionally, if word is null, the method should return false. If no CharacterComparator is provided (cc is null) but word is provided, the method should resort to the behavior of isPalindrome(String word).

Tips

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.

Task 5: OffByN

In this last part, you will add another class, OffByN, that implements CharacterComparator. The equalChars(char x, char y) method of OffByN objects, will say that x and y are equal if they are off by N from each other. Each OffByN object may have a different N. Thus, this class should define a constructor that takes in an N as an argument and saves it as an instance variable of the object.

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

You are not required to write tests for this class, but hopefully by now you are convinced that you should! If you choose to write tests, you’ll need to make your own test file. Make sure to include the appropriate import statements, which you can copy and paste from our two provided test files.

Just-for-fun: Try modifying PalindromeFinder.java so that it outputs a list of off-by-N 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 off-by-N palindrome for any N?

Frequently Asked Questions

I can’t get the provided LinkedListDeque solution to compile.

Make sure your class definition is
public class LinkedListDeque<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>, or if your code doesn’t use Item, replace this with whatever generic parameter type variable you used.

My code passes all my tests, but fails some autograder tests.

Try to think about corner cases that you may not be covering. Re-read the corresponding section of the spec carefully to identify them. Then write your own tests that check these corner cases, and ensure your code passes them.

The Autograder doesn’t like my tests.

Make sure that you’re not using words.txt anywhere in your tests. The autograder does not have access to this file.

Only my tests are failing. What tests am I missing?

Probably corner cases.

I’m failing the TestPalindrome or TestOffByOne tests but I feel like my tests are good.

Make sure your TestPalindrome does not say new Palindrome anywhere other than the lines we provided. Similarly, make sure your TestOffByOne does not say new OffByOne anywhere.

What’s with the weird static Palindrome palindrome = new Palindrome(); stuff?

In order to create JUnit tests for your JUnit tests, we had to resort to some clever hacks, and the easiest way involved this weird stuff. Sorry. Luckily in TestOffByN you don’t have to worry about it.

Deliverables