Goals of this activity:
Here's what you'll be doing in each of the seven steps of this activity:
This is a pair activity; find somebody to work with, design your tests collaboratively on one sheet of paper, and write your code through pair programming. Remember to switch who's driving!
DummyListImplementation.New→JUnit Test Case. Call it ListTest, and leave everything else with the default. If Eclipse asks you whether you want to add JUnit 4 to the build path, say yes.In this step, you'll add empty methods to the DummyListImplementation class. First, create a no-args constructor with an empty body. Then read through all the methods declared in the List interface and make stub implementations of them in your implementation class. Add a stub for toString() too. Note that you'll have to import java.util.Iterator, but you should have no other import statements. There should also be no Javadoc comments, except on the class itself and the constructors.
A stub method is one that does just enough work to make it compile: in a void method, the body should be empty; in a method that has a return value, the body should simply return a dummy value of the correct type. Every stub method should have a “TODO” comment in it.
Here are the first few lines, to get you started:
// In-class activity: List implementation.
// By Christine Cagney and Mary Beth Lacey
// For Data Structures: Comp 630, 10th period, with Dr. Miles
// S'16 at Phillips Academy
import java.util.Iterator;
/**
* A dummy implementation of the List ADT.
*
* @param <T> The type of data that the list stores.
*
* @author Christine Cagney, Mary Beth Lacey
*/
public class DummyListImplementation<T> implements List<T> {
/** Default constructor. */
public DummyListImplementation() {
// TODO: fill me in!
}
public void add(T newItem) {
// TODO: fill me in!
}
public void add(int newPosition, T newItem) {
// TODO: fill me in!
}
public T remove(int position) {
// TODO: fill me in!
return null;
}
// ...
}
In this step, you and your partner will design, on paper, at least 20 test cases for the List ADT (and the additional capabilities provided by the implementation, like constructors and toString()).
A single test case for a software artifact (like an ADT implementation) is a pair of things: an input (or setup, or situation) and a corresponding expected output (or behavior, or modified state). Test-driven development is the idea that we can express, through test cases, what the correct behavior of our software artifact is before we even figure out how to write the code to embody that correct behavior. By expressing our tests first, we can double-check our implementation work later — or catch somebody else messing up!
Here are a few example test cases. Notice that the documentation in List.java is all I need to know in order to define the correct behavior of a list.
Notice that test cases are simple and very granular. Often, multiple test cases will address different aspects of the correct behavior under the same setup. However, no test is redundant with another. For example, it wouldn't make sense for me to write another test that says “After adding four items at the end of a list, the length of the list should be 4.” That doesn't uncover any new ideas.
(A distinct idea would be this: “After adding 1,000 items at the end of a list, the length of the list should be 1,000.” This is describing the behavior of the List implementation when dealing with a large number of items, which you'll learn can be an error-prone situation. Having tested 1,000, though, there's no reason to test 2,000 or 10,000 or even 1,000,000.)
The expectation in a test is usually just one fact. Note, however, that that doesn't necessarily mean that it regards only a single value returned from a single call. In our fourth test case above, “the list should contain only those items, in order” is a single fact, but verifying it requires several calls: getting the value at each index. This is just fine. (Note we wouldn't have to check the length, because that's covered by a different test case.)
The central tenet of designing good tests is this: You are trying to prove the software wrong, not prove it right. The point is not to demonstrate that your implementation is correct, but instead to be as devious as possible, to think of as many different tricky edge cases as possible, in order to catch mistakes.
Try to design things that an implementor might screw up. Remember that what makes a situation tricky for a program is not usually the same as what makes it tricky for a person doing the work by hand. You want to expose programmer mistakes: off-by-one-errors, failure to clean up old state, misuse of constants, failure to properly handle invalid input, etc. Gigantic inputs are usually not tricky, unless what you're testing is: “does this thing properly handle gigantic input?” Most tests should be simple and small, but devious.
An adversarial mindset helps you do a good job when writing tests — you should really want to prove the implementor wrong. Fortunately, for this assignment, we've got a little gambit: you're going to test my list implementation before you write and test your own. And if you find a bug in my implementation, then you'll get mad bragging rights (plus a bonus point on this assignment). However, I wrote a suite of 105 tests to really put my implementation through the wringer, so good luck finding something that I missed!
Now get out a sheet of paper and write down test cases with your partner. There are three requirements:
You may need to look up the documentation for the Iterator interface to know what that's supposed to do.
Now translate all of your tests into JUnit. Copy the following code into ListTest.java:
// In-class activity: Tests for a list implementation.
// By Christine Cagney and Mary Beth Lacey
// For Data Structures: Comp 630, 10th period, with Dr. Miles
// S'16 at Phillips Academy
import java.util.Iterator;
import org.junit.Before;
import org.junit.Test;
import org.junit.Rule;
import org.junit.rules.ExpectedException;
import static org.junit.Assert.*;
public class ListTest {
private List<String> L;
@Rule public ExpectedException thrown = ExpectedException.none();
@Before public void initialize() {
L = new DummyListImplementation<String>();
}
@Test public void lengthOfNewListShouldBeZero() {
assertEquals(0, L.length());
}
@Test public void newListShouldBeEmpty() {
assertTrue(L.isEmpty());
}
@Test public void indexingAt0InNewListShouldThrow() {
thrown.expect(IndexOutOfBoundsException.class);
String s = L.at(0);
}
// ...
}
You should be able to translate most of your tests just by investigating my example code. You may also need to look into some of JUnit's more exotic assertions, like assertArrayEquals().
As you work to express your tests in JUnit, try compiling and running your test class. At this stage, almost all of your tests should fail, since your dummy implementation class doesn't do anything. (A handful of tests might pass by coincidence.)
Right-click on the ListTest file/class in the Package Explorer pane and select Run As→JUnit Test.
Use the following command to compile your test class:
javac -cp .:./* ListTest.java
The -cp flag stands for “class path”, which is the set of paths that Java should look in to find class definitions. The argument to the flag says that the compiler should search for class definitions in this directory (.) as well as any .jar files in this directory (./*); the colon separates this list of two paths.
Now, as for running: the main method to run your tests doesn't live in your test class. Instead it's in a standard JUnit “test runner” class called JUnitCore. So you run it as follows:
java -cp .:./* org.junit.runner.JUnitCore ListTest
Here's where you get to prove me wrong. Load the two class files for my mystery List implementation (implementation; iterator) into your project (if you're in Eclipse) or working directory (if you're using the command line). Modify your test file so that it uses the MysteryListImplementation instead of your DummyListImplementation. Then run it. All the tests should pass; if a test fails, there's either a bug in the test or a bug in my implementation. Check carefully!
Now that you've done this much of the activity, it's time to learn more about the implementation that you'll be writing. We'll talk about that in class. Once you've got a handle on this, go back and write more tests that directly address tricky situations for this implementation. (Do them on paper first, then express them in JUnit, then verify your tests with the oracle.) By the end of this step, the total number of tests should be at least 30.
Now that you've verified that your tests are correct, it's time to write your own implementation of the List ADT. Rename DummyListImplementation as specified in class. Change your ListTest class to use your new implementation class, rather than my mystery implementation.
Then start writing your implementation! As you work, keep re-running your test suite. As you fill in more and more methods correctly, more and more of your tests should pass!
It's best, of course, to have a complete test suite written before you begin writing the thing being tested. However, if you think of new edge cases as you code, go ahead and add them to your test suite. As long as you're not writing redundant tests, more is always merrier!