Mini-Project 1A: Deques and Tests

Lectures needed for this project:

  • Lecture 5 (Testing).

Partner policy: No partners. Discussing ideas with other students is allowed, but code sharing is not allowed, and the solutions you submit should be your own work! More details on the policies page.

In this assignment, we will be practicing Test-Driven-Development with Deques, or a double-ended queue. This means that rather than writing our implementation first, we will be writing the test cases to better understand the requirements and edges cases involved in implementing a Deque.

Setup

Follow the Assignment Workflow Guide to get started with this assignment. This starter code is in the proj1 folder.

Please ensure that Provenance is recording before writing any code. Any submission without Provenance recording the entire time for this project and any future assignments will receive no credit.

Task 1: Read the Deque61B ADT and API

What is a Deque?

A Deque, or double ended queue, is a list-like data structure where elements are inserted/removed from the front and the back of the list, rather than just anywhere.

Here is a definition of the double ended queue from the Java standard library.

A linear collection that supports element insertion and removal at both ends. The name deque is short for “double ended queue” and is usually pronounced “deck”. Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

We don’t need all the methods defined in Java’s Deque, and have defined our own interface, which can be found in src/Deque61B.java.

For example, the get method is described as follows, in something called a Javadoc comment:

/** ...
 * @param index index to get
 * @return element at {@code index} in the deque
 */
T get(int index);

Here, @param indicates a parameter to the method, and @return indicates the return value of the method. The @code tag is used to format as code.

If you hover over the method name in IntelliJ, you’ll see a popup that looks like this, which is useful if you want to know what a method does:

Hover over method name to see JavaDoc

Open the Deque61B.java file and read the documentation in it. This spec doesn’t have all the information you need to complete the project, so it’s important that you read through all of Deque61B.java!

Seriously. Do not skip this. You will spend hours confused if you skip this step. Please save yourself the time and stress!

You should not edit Deque61B.java.

Writing Tests

We’ve provided tests that verify that addFirst and toList works. However, you’ll see that there are many more methods you’ll need to test.

You will need to write your own unit tests! Note: Our grader will test your tests to see if they are good enough. More on this below.

Sharing tests on projects will be considered academic misconduct (cheating).

To write tests, we will use Google’s Truth assertions library. We love it because it’s easy to use and generates useful error messages.

We often write tests using the Arrange-Act-Assert pattern:

  1. Arrange the test case, such as instantiating the data structure or filling it with elements.
  2. Act by performing the behavior you want to test.
  3. Assert the result of the action in (2).

We will often have multiple “act” and “assert” steps in a single test method to reduce the amount of boilerplate (repeated) code.

Truth Assertions

A Truth assertion takes the following format:

assertThat(actual).isEqualTo(expected);

To add a message to the assertion, we can instead use:

assertWithMessage("actual is not expected")
    .that(actual)
    .isEqualTo(expected);

We can use things other than isEqualTo, depending on the type of actual. For example, if actual is a List, we could do the following to check its contents without constructing a new List:

assertThat(actualList)
    .containsExactly(0, 1, 2, 3)
    .inOrder();

If we had a List or other reference object, we could use:

assertThat(actualList)
    .containsExactlyElementsIn(expected)  // `expected` is a List
    .inOrder();

Truth has many assertions, including isNull and isNotNull; and isTrue and isFalse for booleans. IntelliJ’s autocomplete will often give you suggestions for which assertion you can use.

If you do not assert anything, you will pass your own tests, even if your implementation is incorrect! For example, the following test will pass, even if addFirst does nothing:

@Test
public void noAssertionTest() {
    Deque61B<String> lld = new LinkedListDeque61B<>();
    lld.addFirst("front");
}

You also must remember to use .isTrue() or .isFalse() when asserting boolean statements. For example, the following test will always pass, even if isEmpty always returns false.

@Test
public void isEmptyTest() {
    Deque61B<String> lld = new LinkedListDeque61B<>();
    assertThat(lld.isEmpty());
}

The last line of the above test should instead be assertThat(lld.isEmpty()).isTrue();.

Example Test

Let’s break down the provided addLastTestBasic:

@Test
/** In this test, we use only one assertThat statement.
    *  Sometimes, the tedious work of adding the extra assertion statements isn't worth it. */
public void addFirstTestBasic() {
    Deque61B<String> lld1 = new LinkedListDeque61B<>();

    lld1.addFirst("back"); // after this call we expect: ["back"]
    lld1.addFirst("middle"); // after this call we expect: ["middle", "back"]
    lld1.addFirst("front"); // after this call we expect: ["front", "middle", "back"]

    assertThat(lld1.toList()).containsExactly("front", "middle", "back").inOrder();
}
  • @Test tells Java that this is method is a test, and should be run when we run tests.
  • Arrange: We construct a new Deque61B, and add 3 elements to it using addLast.
  • Act: We call toList on Deque61B. This implicitly depends on the earlier addLast calls.
  • Assert: We use a Truth assertion to check that the toList contains specific elements in a specific order.

You must call toList() if you want to check the contents of a Deque61B. For example, assertThat(lld1).containsExactly("front", "middle", "back").inOrder(); will not work, because Google Truth doesn’t know how to iterate over lld1 to see its contents. In a later lecture, we will see how to make our Deques iterable so that Google Truth will know how to check their contents. assertThat(lld1).isEqualTo(...) will also not work.

Task 2: Testing tests

Our autograder will actually test your tests to make sure that they have sufficient “coverage”. That is, we will essentially be taking your test file (LinkedListDeque61BTest.java) and using it to “test” our staff solution for a LinkedListDeque61B, which you will be implementing in Project 1B.

Using some autograder magic, we’re able to determine which edge cases your tests are able to hit, thus telling us the “coverage” of your test suite. In order to get a full score on the testing component, you’ll need to think about interesting corner cases.

Unlike the autograder for the rest of Project 1, the autograder for Project 1A has no token limit, so check your test quality as often as you’d like!

Since you are creating LinkedListDeque.java in Project 1B, you will be getting compiler errors. You can ignore this and use Gradescope to test your code!

Add tests to LinkedListDeque61BTest.java, covering all the flags listed below.

Flags for add tests

  • “add_first_from_empty”: Check that you can call addFirst on an empty deque.
  • “add_last_from_empty”: Check that you can call addLast on an empty deque.
  • “add_first_nonempty”: Check that you can call addFirst on a non-empty deque.
  • “add_last_nonempty”: Check you can call addLast on a non-empty deque.

Flags for toList tests

  • “to_list_empty”: Check that toList still works with empty LinkedListDeque61B.
  • “to_list_nonempty”: Check that toList works with non-empty LinkedListDeque61B.

Flags for add after remove tests

  • “add_first_after_remove_to_empty”: Add elements to a deque and remove them all, then check that addFirst still works.
  • “add_last_after_remove_to_empty”: Add elements to a deque and remove them all, then check that addLast still works.

Flags for remove tests

  • “remove_first”: Basic check that removeFirst works. Ensure your deque has at least three elements before removing.
  • “remove_last”: Basic check that removeLast works. Ensure your deque has at least three elements before removing.
  • “remove_first_to_empty”: Add some elements to a deque and remove all of them except one. Check that removeFirst works.
  • “remove_last_to_empty”: Add some elements to a deque and remove all of them except one. Check that removeLast works.
  • “remove_first_to_one”: Add some elements to a deque and remove all of them except two. Check that removeFirst works.
  • “remove_last_to_one”: Add some elements to a deque and remove all of them except two. Check that removeLast works.

Flags for get tests

  • “get_first_empty”: Check that getFirst works on an empty deque.
  • “get_last_empty”: Check that getLast works on an empty deque.
  • “get_first_valid”: Check that getFirst returns the first element on a non-empty deque.
  • “get_last_valid”: Check that getLast returns the last element on a non-empty deque.
  • “get_valid”: Check that get works on a valid index.
  • “get_oob_large”: Check for get intended behavior on a large, out of bounds index.
  • “get_oob_neg”: Check for get intended behavior on a negative index.
  • “get_recursive_valid”: Check that getRecursive works on a valid index.
  • “get_recursive_oob_large”: Check for getRecursive intended behavior on a large, out of bounds index.
  • “get_recursive_oob_neg”: Check for getRecursive intended behavior on a negative index.

Hint: For the get_recursive tests, copy paste your get tests, but replace get with getRecursive.

(oob stands for “out of bounds”)

Flags for size tests

  • “size”: Check that size works.
  • “size_after_remove_to_empty”: Add elements to a deque and remove them all, then check that size still works.
  • “size_after_remove_from_empty”: Remove from an empty deque, then check for size intended output.

Flags for isEmpty tests

  • “is_empty_true”: Check that isEmpty works on an empty deque.
  • “is_empty_false”: Check that isEmpty works on a non-empty deque.

Submission

Once you’ve written local tests for every method, follow the Assignment Workflow Guide to submit to the autograder.

Scoring

Project 1A is worth 60 points