Testing the Iterator

Iterating is now part of the Set contract, so the iterator tests go in the abstract SetTest from the Set chapter’s code. It follows the ListTest pattern from the testing chapter, so the tests run against both ArraySet and LinkedSet. The fixture gives each test a fresh, empty set:

public abstract class SetTest {

  protected Set<Integer> set;

  protected abstract Set<Integer> createSet();

  @BeforeEach
  public void setup() {
    set = createSet();
  }

  // ... the add/remove/contains/size tests, plus the iterator tests below ...
}

The main thing we want to check is that an iterator returns exactly the elements of the set. We add a few elements, collect what the loop produces into a list, and check that we got those elements and no others:

@Test
public void iteratorVisitsEveryElement() {
  set.add(1);
  set.add(2);
  set.add(3);
  List<Integer> seen = new ArrayList<>();
  for (Integer x : set) {
    seen.add(x);
  }
  assertEquals(3, seen.size());
  assertTrue(seen.contains(1));
  assertTrue(seen.contains(2));
  assertTrue(seen.contains(3));
}

We check size and membership rather than position, because ArraySet and LinkedSet make no promise about the order in which their iterators return the elements. The list has three elements, and each value we added is in it, so the list holds exactly the values we added.

On an empty set there is nothing to visit, so hasNext() is false from the start and an enhanced for loop runs its body zero times:

@Test
public void iteratorOnEmptySetHasNoElements() {
  assertFalse(set.iterator().hasNext());
}

Once an iterator has returned its last element, calling next() again is not allowed, and the iterator must throw NoSuchElementException. We test that with the same try / fail / catch pattern we used to test other exceptions:

@Test
public void nextPastEndThrows() {
  set.add(1);
  Iterator<Integer> it = set.iterator();
  it.next();
  try {
    it.next();
    fail("expected NoSuchElementException after the last element");
  } catch (NoSuchElementException e) {
    return;
  }
}

hasNext() only tells you whether there are elements left. It must not move the iterator forward. Calling it twice in a row should not skip past the first element:

@Test
public void hasNextDoesNotAdvance() {
  set.add(42);
  Iterator<Integer> it = set.iterator();
  it.hasNext();
  it.hasNext();
  assertEquals(42, it.next());
}

Finally, two iterators over the same set must not affect each other. The nested loops that compared every element with every other one depended on that. We run one iterator to the end and check that the other still has elements left:

@Test
public void twoIteratorsAreIndependent() {
  set.add(1);
  set.add(2);
  Iterator<Integer> first = set.iterator();
  Iterator<Integer> second = set.iterator();
  first.next();
  first.next();
  assertTrue(second.hasNext());
}

You can add a few more tests the same way. The iterator of a one-element set should return that element. After it does, hasNext() should be false. Calling next() once per element should work without ever calling hasNext(). A full iteration should leave the size unchanged, and it should leave every element in the set. Each of these is its own test. We are leaving out one case on purpose: what happens when the set is modified while an iteration is in progress.