Problem: Testing a MaxList

Let’s define a new ADT and use test-first development to implement it.

The problem

Suppose we want a list of integers that, in addition to the usual operations, can answer one more kind of question: what is the largest value from the start of the list up to position i? Call it the cumulative maximum at i.

list:        [5, 7, 3, 8]
getMax(0) -> 5     (max of [5])
getMax(1) -> 7     (max of [5, 7])
getMax(2) -> 7     (max of [5, 7, 3])
getMax(3) -> 8     (max of [5, 7, 3, 8])

Everything else behaves like an ordinary list.

A new ADT, by extension

We could write a brand-new interface but the thing we want is a list. It has everything a List has, plus one extra operation. An interface can extend another interface, which means it inherits all of the other interface’s operations and adds new ones:

public interface MaxList extends List<Integer> {

  /**
   * Return the maximum value among the elements at positions 0 through index,
   * inclusive.
   *
   * @param index the position to compute the cumulative maximum up to.
   * @return the largest value in positions 0..index.
   * @throws IndexOutOfBoundsException if index < 0 or index >= size().
   */
  int getMax(int index);
}

MaxList extends List<Integer> means a MaxList promises everything a List<Integer> promises (add, remove, set, get, contains, indexOf, size), and also getMax. A MaxList is a List. Anywhere a List<Integer> is expected, a MaxList may be used. It is the same type substitution that let an ArrayList stand in for a List. This time both sides are interfaces.

We are adding an operation, not removing one. Adding new promises to a contract is always allowed. A subtype has to keep every promise its supertype makes, so extension can never remove an operation.

The test class

A MaxList is-a List, so every test in ListTest applies to it too. We do not want to copy those tests into a new file. ListTest already holds the shared tests, with a factory method each implementation fills in, so MaxListTest extends it and every inherited test runs against each MaxList implementation.

There is one problem. The ListTest field is a private List<Integer> list. If we were to write more tests in MaxListTest, we would need to access list. But list is private. A subclass cannot see the private fields. We have to change the field visibility modifier to protected, so MaxListTest can see it. But even then, list is typed List<Integer>, and List has no getMax. So if we were to use that field to call list.getMax(0) for example, it would not compile.

The fix is to give MaxListTest its own field, typed MaxList, and fill it in its own @BeforeEach. I can override createList and narrow its return type from List<Integer> to MaxList. Java allows this. It is called a covariant return type, and it is legal because a MaxList is-a List<Integer>. Now I can use the same factory method to fill both fields.

public abstract class MaxListTest extends ListTest {

  private MaxList maxList;

  @Override
  protected abstract MaxList createList();

  @BeforeEach
  public void setupMax() {
    maxList = createList();
  }

  // getMax tests go here, using `maxList`
}

Note that this design has a cost. Every test now builds two objects. JUnit runs the inherited setup() first, which creates list, and then setupMax(), which creates maxList. Any one test uses only one of the two. We accept that cost, because Java does not give us a better option. A field cannot be re-typed in a subclass, so the choice is a second variable or a cast in every getMax test. A cast cannot be verified at compile time, it happens (and fails) at runtime. I prefer that in the tests we let the compiler check as much as it can. So I will go with the second variable.

Each implementation then gets a small subclass that says which MaxList to build:

public class MaxArrayListTest extends MaxListTest {
  @Override
  protected MaxList createList() {
    return new MaxArrayList();
  }
}

I assumed we will implement MaxList with an array-backed list, so I called it MaxArrayList. (I could also call it ArrayMaxList.) The point here is that whatever implementation we choose, we need to create a subclass of MaxListTest that builds it. The tests are written once, and run against every implementation.

The task

Assume we have the MaxList interface and the MaxListTest abstract class as shown above. Write the getMax tests following the best practices of unit testing as described in the chapter.

Once you have written the tests, you will implement MaxList.