Solution: The getMax Tests

Every getMax test goes into MaxListTest, using the maxList field shown earlier. We build the suite from the ADT’s specification, one scenario at a time.

Start with one element

Add one value. The maximum up to index 0 is that value:

@Test
public void getMaxOfSingleElement() {
  maxList.add(5);
  assertEquals(5, maxList.getMax(0));
}

The cumulative maximum

getMax reports the maximum of a prefix, positions 0 through index, not the whole list. The example from the problem description gives us the test. With [5, 7, 3, 8], the maximum at each position is 5, 7, 7, 8. This is one behavior, so it is one test:

@Test
public void getMaxIsMaximumOfPrefix() {
  maxList.add(5);
  maxList.add(7);
  maxList.add(3);
  maxList.add(8);
  assertEquals(5, maxList.getMax(0));
  assertEquals(7, maxList.getMax(1));
  assertEquals(7, maxList.getMax(2));
  assertEquals(8, maxList.getMax(3));
}

The important assertion is getMax(2). It returns 7, not 8. The 8 is at index 3, outside the prefix 0 through 2, so it does not affect getMax(2). That assertion catches an implementation that just returns the largest element in the whole list.

A few more cases

When the largest value comes first and the rest are smaller, the maximum is the first value, and it stays the same at every later position:

@Test
public void getMaxStaysWhenLaterElementsAreSmaller() {
  maxList.add(8);
  maxList.add(5);
  maxList.add(3);
  assertEquals(8, maxList.getMax(2));
}

When the maximum is duplicated, the result is just that value. This is not really a special case, but it confirms that duplicate values are treated as ordinary list elements:

@Test
public void getMaxWithDuplicateMaximum() {
  maxList.add(7);
  maxList.add(7);
  assertEquals(7, maxList.getMax(1));
}

Changes after mutation

Because MaxList is still a List, operations like set and remove can change the values that getMax reads. The inherited ListTest already checks that those operations satisfy the List contract. These tests check that the prefix maximum is still correct afterward.

If a new value becomes the largest value in a prefix, getMax should return it:

@Test
public void getMaxUpdatesAfterSetToLargerValue() {
  maxList.add(2);
  maxList.add(3);
  maxList.add(1);
  maxList.set(2, 5);
  assertEquals(5, maxList.getMax(2));
}

If set replaces the old maximum with a smaller value, the maxima for later prefixes may change. Starting from [5, 4, 3] and setting index 0 to 1 gives [1, 4, 3], whose prefix maxima are 1, 4, 4:

@Test
public void getMaxAfterLoweringOldMaximum() {
  maxList.add(5);
  maxList.add(4);
  maxList.add(3);
  maxList.set(0, 1);
  assertEquals(1, maxList.getMax(0));
  assertEquals(4, maxList.getMax(1));
  assertEquals(4, maxList.getMax(2));
}

The same happens after remove. If we remove the value that used to be the maximum, the prefix maxima need to be recomputed. remove on the List contract takes an element, not an index, so remove(5) removes the value 5, which happens to sit at index 0. After that the list is [4, 3], and both prefix maxima are 4:

@Test
public void getMaxAfterRemovingOldMaximum() {
  maxList.add(5);
  maxList.add(4);
  maxList.add(3);
  maxList.remove(5);
  assertEquals(4, maxList.getMax(0));
  assertEquals(4, maxList.getMax(1));
}

Out-of-range indices throw

The contract says getMax throws IndexOutOfBoundsException when index < 0 or index >= size(), the same as get. We test that with the try / fail / catch idiom.

Below the range:

@Test
public void getMaxBelowRangeThrows() {
  maxList.add(1);
  try {
    maxList.getMax(-1);
    fail("expected IndexOutOfBoundsException for index -1");
  } catch (IndexOutOfBoundsException e) {
    return;
  }
}

At or above the range. Index size() is one past the last valid position:

@Test
public void getMaxAboveRangeThrows() {
  maxList.add(1);
  try {
    maxList.getMax(1);  // size is 1, so index 1 is out of range
    fail("expected IndexOutOfBoundsException for index == size()");
  } catch (IndexOutOfBoundsException e) {
    return;
  }
}

On an empty list, every index is out of range, so getMax(0) throws:

@Test
public void getMaxOnEmptyListThrows() {
  try {
    maxList.getMax(0);
    fail("expected IndexOutOfBoundsException on an empty list");
  } catch (IndexOutOfBoundsException e) {
    return;
  }
}