Writing the ArraySet Iterator

The borrowed iterator did not show us how an iterator works. To see how it works, we write our own. First, what does an iterator have to do? The Iterator<T> interface, which is the return type of iterator(), asks for two methods:

public interface Iterator<T> {
  boolean hasNext();
  T next();
}

hasNext() tells us whether there are more elements, and next() returns the next element and advances past it. The enhanced for loop uses these two together: as long as hasNext() returns true, it calls next() and runs the loop body with the result. In fact, when you write an enhanced for loop like this:

for (String email : subscribers) {
  sendNewsletter(email);
}

The compiler turns it into this:

Iterator<String> it = subscribers.iterator();
while (it.hasNext()) {
  String email = it.next();
  sendNewsletter(email);
}

You can write the second version yourself if you like, but the first is shorter and easier to read.

Earlier, we borrowed an iterator:

@Override
public Iterator<T> iterator() {
  return Arrays.stream(arr, 0, size).iterator();
}

Let’s replace that with this:

@Override
public Iterator<T> iterator() {
  return new ArraySetIterator();
}

What is ArraySetIterator? It is a new class that we write ourselves. It implements Iterator<T> and iterates through the elements of an ArraySet. We will write it as an inner class inside ArraySet, so it can read the set’s private fields directly. Here is the skeleton:

public class ArraySet<T> implements Set<T> {
  // ... other methods implemented as before ...

  private class ArraySetIterator implements Iterator<T> {
    @Override
    public boolean hasNext() {
      return false;  // TODO: implement this
    }

    @Override
    public T next() {
      return null;  // TODO: implement this
    }
  }
}

Now to implement the two methods, I am going to show you how I usually think about writing an iterator. I start by thinking about how I would iterate through the elements if I were doing it with a regular loop. I typically go for a while loop because that breaks the looping logic into several parts that map nicely to the iterator methods. For example, I might write this:

int cursor = 0;
while (cursor < size) {
  T element = arr[cursor];
  // do something with element
  cursor++;
}

Here, cursor holds the index of the next element to process. The loop condition cursor < size checks whether there are more elements to process, and the body of the loop retrieves the current element and advances the cursor. Now let’s map each part of this loop onto ArraySetIterator:

• The cursor variable will become a field in the ArraySetIterator class, so that it keeps its value between calls to hasNext() and next().
• The condition cursor < size will be the logic for hasNext().
• The body of the loop will be the logic for next().

Here is all of that put together:

private class ArraySetIterator implements Iterator<T> {
  private int cursor = 0;  // index of the next element to return

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public T next() {
    T element = arr[cursor];
    cursor++;
    return element;
  }
}

Technically, a client is not required to call hasNext() before calling next(). If they call next() when there are no more elements, we should throw a NoSuchElementException to signal that the iteration has finished. So here is the final version of next() with that check:

@Override
public T next() {
  if (!hasNext()) {
    throw new NoSuchElementException();
  }
  return arr[cursor++];
}

You need to import java.util.NoSuchElementException for this.

I also read the element and incremented the cursor in one line to keep it short.