Problem: Testing the Bag

Back in the practice problems of the first chapter we built a Bag: an unordered collection of colored balls. You add balls to it, and you draw one out. Here is the whole class.

public class Bag {
  private BallColor[] balls;   // the underlying fixed-size storage
  private int size;            // how many balls are in the bag right now
  private Random rng;          // source of randomness for drawing a ball

  public Bag() {
    balls = new BallColor[10];  // start with room for 10 balls
    size = 0;
    rng = new Random();
  }

  public void add(BallColor ball) {
    if (size == balls.length) {
      grow();              // out of room — make the backing array bigger first
    }
    balls[size] = ball;
    size++;
  }

  public BallColor remove() {
    if (size == 0) {
      throw new IllegalStateException("the bag is empty");
    }
    int i = rng.nextInt(size);    // pick a slot uniformly at random in [0, size)
    BallColor drawn = balls[i];
    balls[i] = balls[size - 1];   // fill the gap with the last ball and shrink
    size--;
    balls[size] = null;
    return drawn;
  }

  public int size() {
    return size;
  }

  // grow() doubles the backing array when it fills up
}

BallColor is a small enum with two values, BLACK and BLUE.

A new bag is empty. add puts a ball in and grows the backing array when it fills. size reports how many balls are in the bag. And remove draws one ball out uniformly at random, returns it, and moves the last ball into the drawn ball’s slot. On an empty bag it throws IllegalStateException.

The Challenge with Randomness

With a List you could write assertEquals(42, list.get(0)) because the answer is fixed. But what should you assert about bag.remove()? You add a black ball and a blue ball, you draw one out, and you do not know which color you will get. Write assertEquals(BallColor.BLACK, bag.remove()) and the test passes on some runs and fails on others, with no bug anywhere. A test like that is flaky, and a flaky test is worse than no test, because it reports a failure when nothing is wrong.

So the challenge is to write a JUnit suite for Bag that is never flaky, using only the tools this chapter gave you: @BeforeEach, assertEquals, the try / fail / catch idiom, and a fresh bag per test.