Solution: A Seeded Constructor

If an implementation uses randomness, we can design that implementation so its randomness is repeatable during a test.

A seeded constructor

For testing, we can add a second constructor that accepts a seed:

public class ArrayBag {

  private BallColor[] balls;
  private int size;
  private Random rng;

  public ArrayBag() {
    balls = new BallColor[10];
    size = 0;
    rng = new Random();
  }

  public ArrayBag(long seed) {
    balls = new BallColor[10];
    size = 0;
    rng = new Random(seed);
  }

  // add, remove, size, grow...
}

A Random built with the same seed produces the same sequence every time. That means a test can now know which index the implementation will draw first, as long as the test also knows this implementation’s removal algorithm. Note we are doing white-box testing here: the test knows that ArrayBag uses rng.nextInt(size) to choose an index, and that it fills the gap with the last ball.

This is not a contract test

A shared BagTest should not require a seeded constructor, because the Bag ADT does not promise one. Some other correct implementation might use a different source of randomness, or a different internal structure or implementation, and still keep the Bag contract.

So the seed-based test belongs in the concrete implementation’s test class:

public class ArrayBagTest extends BagTest {
  // tests specific to ArrayBag
}

A repeatable draw

The test can build its own Random with the same seed, replay it, and write down which index each call to remove will draw.

The indexes never change between tests, so there is no reason to recompute them for each one. This is a good place for @BeforeAll. It runs once, before any test in the class, and it must be static. Compare that with @BeforeEach, which runs before every test and is the right choice for the bag itself, because each test modifies its bag.

public class ArrayBagTest extends BagTest {

  private static final long SEED = 226;
  private static final int BALLS = 5;

  // drawnIndex[i] is the index that the i-th call to remove will draw
  private static int[] drawnIndex;

  @BeforeAll
  public static void computeDraws() {
    Random reference = new Random(SEED);
    drawnIndex = new int[BALLS];
    for (int i = 0; i < BALLS; i++) {
      drawnIndex[i] = reference.nextInt(BALLS - i);  // the bag has one fewer ball each draw
    }
  }

  // tests specific to ArrayBag
}

Notice the bound of nextInt. The bag has five balls at the first draw, four at the second, and so on, and remove calls rng.nextInt(size) with the current size. The replay has to use the same bounds, otherwise it produces different numbers.

A test that follows the draws

Now we know the index of every draw, but we still need to know which ball is at that index. We keep a plain List next to the bag and apply the same removal rule to it: take the ball at the drawn index, fill the gap with the last ball, and shrink.

@Test
public void seededRemoveFollowsTheKnownDraws() {
  ArrayBag bag = new ArrayBag(SEED);
  List<BallColor> expected = new ArrayList<>();
  BallColor[] balls = {BLACK, BLUE, BLUE, BLACK, BLUE};
  for (BallColor ball : balls) {
    bag.add(ball);
    expected.add(ball);
  }

  for (int i = 0; i < BALLS; i++) {
    int index = drawnIndex[i];
    BallColor want = expected.get(index);
    expected.set(index, expected.get(expected.size() - 1));  // fill the gap with the last ball
    expected.remove(expected.size() - 1);

    assertEquals(want, bag.remove());
    assertEquals(BALLS - i - 1, bag.size());
  }
}

The colors are mixed on purpose, and in an order where the gap-filling matters. If every ball had the same color, a remove that filled the gap wrongly would still pass.

Every assertion here is exact, and the test never fails by chance. If it fails, ArrayBag is not doing what we said it does.

What this test does and does not show

This test copies the removal rule of ArrayBag. That is what white-box testing means. It checks that this implementation follows its own algorithm, and it breaks if someone changes the algorithm, even to another correct one. That is why it does not belong in BagTest, and why this is the one place where we allow a test to depend on the implementation.

The contract tests from the previous solution ask whether an object behaves like a Bag, whichever implementation we use. The seeded test asks whether ArrayBag behaves correctly on a known sequence of random choices. Keep them separate, so the contract tests still run against any implementation.