Proj1B Notes

CS61B UCBerkeley

Introduction

In project 1B, you will:

• Phase I: Build a rudimentary autograder for project 1A.
• Phase II: Create a Deque interface and use it to solve some problems with words.

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.

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.

Phase I

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().

my codes are like the following, and I got a test failed in line 30.

public class TestArrayDeque1B {
    @Test
    public void testArrayDeque() {
        StudentArrayDeque<Integer> student = new StudentArrayDeque<>();
        ArrayDequeSolution<Integer> solution = new ArrayDequeSolution<>();
        //source from StudentArrayDequeLauncher.java
        for (int i = 0; i < 10; i += 1) {
            double numberBetweenZeroAndOne = StdRandom.uniform();
            if (numberBetweenZeroAndOne < 0.5) {
                student.addLast(i);
                solution.addLast(i);
            } else {
                student.addFirst(i);
                solution.addFirst(i);
            }
        }
        Integer a = solution.removeFirst();
        Integer b = student.removeFirst();
        assertEquals(a,b);
        Integer c = solution.removeLast();
        Integer d = student.removeLast();
        assertEquals(c,d);
        Integer e = solution.removeFirst();
        Integer f = student.removeFirst();
        assertEquals(e,f);
        Integer g = solution.removeLast();
        Integer h = student.removeLast();
        assertEquals(g,h);
        Integer i = solution.removeFirst();
        Integer j = student.removeFirst();
        assertEquals(i,j);
        Integer k = solution.removeLast();
        Integer l = student.removeLast();
        assertEquals(k,l);
        Integer m = solution.removeFirst();
        Integer n = student.removeFirst();
        assertEquals(m,n);
    }
}

Task II:

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, For examples of how to use these classes, see OperationSequenceDemo.java. Learning how to adapt existing helper classes to your own task is an important skill, so we've been deliberately vague about how you should use these.

my codes were as follows:

public class TestArrayDeque1B {
    @Test
    public void testArrayDeque() {
        StudentArrayDeque<Integer> student = new StudentArrayDeque<>();
        ArrayDequeSolution<Integer> solution = new ArrayDequeSolution<>();
        OperationSequence fs = new OperationSequence();
        //source from StudentArrayDequeLauncher.java
        for (int i = 0; i < 10; i += 1) {
            double numberBetweenZeroAndOne = StdRandom.uniform();
            if (numberBetweenZeroAndOne < 0.5) {
                student.addLast(i);
                solution.addLast(i);
                DequeOperation randomAddLast = new DequeOperation("addLast", i);
                fs.addOperation(randomAddLast);
            }else {
                student.addFirst(i);
                solution.addFirst(i);
                DequeOperation randomAddFirst = new DequeOperation("addFirst", i);
                fs.addOperation(randomAddFirst);
            }
        }
        Integer a = solution.removeFirst();
        Integer b = student.removeFirst();
        DequeOperation dequeOp1 = new DequeOperation("RemoveFirst");
        fs.addOperation(dequeOp1);
        assertEquals(fs.toString(),a,b);
        Integer c = solution.removeLast();
        Integer d = student.removeLast();
        DequeOperation dequeOp2 = new DequeOperation("RemoveLast");
        fs.addOperation(dequeOp2);
        assertEquals(fs.toString(),c,d);
        Integer e = solution.removeFirst();
        Integer f = student.removeFirst();
        DequeOperation dequeOp3 = new DequeOperation("RemoveFirst");
        fs.addOperation(dequeOp3);
        assertEquals(fs.toString(),e,f);
        Integer g = solution.removeLast();
        Integer h = student.removeLast();
        DequeOperation dequeOp4 = new DequeOperation("RemoveLast");
        fs.addOperation(dequeOp4);
        assertEquals(fs.toString(),g,h);
        Integer i = solution.removeFirst();
        Integer j = student.removeFirst();
        DequeOperation dequeOp5 = new DequeOperation("RemoveFirst");
        fs.addOperation(dequeOp5);
        assertEquals(fs.toString(),i,j);
        Integer k = solution.removeLast();
        Integer l = student.removeLast();
        DequeOperation dequeOp6 = new DequeOperation("RemoveLast");
        fs.addOperation(dequeOp6);
        assertEquals(fs.toString(),k,l);
        Integer m = solution.removeFirst();
        Integer n = student.removeFirst();
        DequeOperation dequeOp7 = new DequeOperation("RemoveFirst");
        fs.addOperation(dequeOp7);
        assertEquals(fs.toString(),m,n);
    }
}

And I got the expected test result:

Phase II: Word Manipulation

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

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

Here's how to creat an Interface: basiacally, you creat an Interface Deque in Deque.java file, and you write all methods the Interface hava, but end the methods with an; and no contents of the methods is needed to write.

public interface Deque<Item>{
    //Adds an item to the front of the Deque.
    public void addFirst(Item item);
    //Adds an item to the back of the Deque.
    public void addLast(Item item);
    //Returns true if deque is empty, false otherwise.
    public boolean isEmpty();
    //Returns the number of items in the Deque.
    public int size();
    //Prints the items in the Deque from first to last, separated by a space.
    public void printDeque();
    //Removes and returns the item at the front of the Deque. If no such item exists, returns null.
    public Item removeFirst();
    //Removes and returns the item at the back of the Deque. If no such item exists, returns null.
    public Item removeLast();
    //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!
    public Item get(int index);
}

Task 1: Basic Palindrome

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

public static Deque<Character> wordToDeque(String word)
public static boolean isPalindrome(String word)
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).

When checking if a word is palimdrome, I got some problems. Even two strings are exactly the same, the isPalimdrome method returned false.

Later I realized that when compare two strings are equal to each other or not, use string1.equals(string2), don't use string1 == string2,

Things then went on just fine：

Task 2: Generalized Palindrome
In this part, you will generalize your isPalindrome method by adding a new method:

public static 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 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.

Here's how to implement an Interface:

My CharacterComparator Interface:

/** 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);
}

I want to implement this interface in my Palindrome.java, I just need to write implements CharacterComparator after the class name Palindrome, and override the methods in the Interface for your class's use.

public class Palindrome implements CharacterComparator {
 @Override
    public boolean equalChars(char x, char y) {
        return x == y;
    }