PeekingIterator and AbstractIterator from Google Guava

Introduction

In this post we will learn about the PeekingIterator and AbstractIterator from Google Guava.

Peeking Iterator - An Iterator that can peek

A PeekingIterator is an Iterator that can do one-element peek (lookahead) when we are iterating. As I have explained in other Iterator posts, an Iterator has the hasNext() methods to check if the iterator has more elements to iterate on and the next() method to get the next element. Calling the next() method would internally move the pointer/reference to the next element, and the retrieved element cannot be put back into the iterator.

The PeekingIterator interface in Google Guava extends the Java Iterator interface and provides a peek() method. The peek() method returns the next element from the iterator, but doesn’t advance the iteration process, i.e., we can call peek any number of times, and unless we call next(), the iteration wouldn’t advance to the next element.

Let us now look at a code example.

PeekingIterator - A Simple example

Let us start with a list of string and create an iterator out of it. To turn any existing iterator to a Peeking Iterator, we have to call Google Guava’s peekingIterator static method on the Iterators utility class.

List<String> elements = List.of("Learning", "About", "Useful", "Utilities", "From", "Google", "Guava");

PeekingIterator<String> peekingIterator = Iterators.peekingIterator(elements.iterator());

Note: I’m using the Java 9 List.of method here. Refer to the Convenience Factory Methods for Collections post to learn more.

Once we have a peeking iterator, we can call the peek method.

while (peekingIterator.hasNext()) {
    System.out.println(peekingIterator.peek());
    System.out.println(peekingIterator.next());
}

Prints,

Learning
Learning
About
About
Useful
Useful
Utilities
Utilities
From
From
Google
Google
Guava
Guava

Note that we can call peek() any number of times and calling next() will guarantee to return the same element as returned by the peek(). Like the next(), if we call peek() when the iterator is empty (has no more elements), it will throw a NoSuchElementException.

Creating an iterator for iterating over even numbers

Let’s say we want to create an iterator out of a list of integers. But the iterator will serve as an even numbers iterator. It will keep returning back values as long as they are even. When it encounters any odd numbers, it will ignore them.

Without capability to peek, we cannot implement such an iterator. Because to know if we have any more elements left to iterate on, we need to know if we still have any even numbers left in the original iterator. For this, we have to call the next() on the underlying iterator. But where should we store the consumed integer (if that is an even number). This is actually what the Peeking Iterator does behind the scenes.

Note: If this example seems contrived, imaging the source of iterator as infinite or unknown.

public class EvenNumbersIterator implements Iterator<Integer> {
    private final PeekingIterator<Integer> peekIterator;

    private EvenNumbersIterator(List<Integer> nums) {
        this.peekIterator = Iterators.peekingIterator(nums.iterator());
    }

    @Override
    public boolean hasNext() {
        // Consume (remove) the odd numbers
        while (peekIterator.hasNext() && peekIterator.peek() % 2 == 1) {
            peekIterator.next();
        }
        return peekIterator.hasNext();
    }

    @Override
    public Integer next() {
        if (!hasNext()) {
            throw new NoSuchElementException("No more elements");
        }
        return peekIterator.next();
    }
}

The EvenNumbersIterator class implements an Iterator<Integer> and creates a Google Guava PeekingIterator from the iterator created from the passed list. The hasNext() method is the key.

It checks if the underlying (peeking) iterator has more elements and checks if the next element is odd/even by peeking into it. By doing this in a loop, it basically removes all the odd numbers from it. So, the next call to the underlying peeking iterator (next()) will return an even number provided it is not empty.

EvenNumbersIterator evenNumbersIterator = new EvenNumbersIterator(List.of(2, 4, 6, 8, 1, 5, 10, 12, 7, 9));
while (evenNumbersIterator.hasNext()) {
    System.out.println(evenNumbersIterator.next());
}

We pass a list of integers having a mix of odd and even numbers. Iterating over our iterator prints,

This works even if the list has only even or odd numbers.

EvenNumbersIterator evenNumbersIterator = new EvenNumbersIterator(List.of(2, 4, 6, 8));
while (evenNumbersIterator.hasNext()) {
    System.out.println(evenNumbersIterator.next());
}

EvenNumbersIterator evenNumbersIterator = new EvenNumbersIterator(List.of(3, 5, 7));
System.out.println("Is empty: " + !evenNumbersIterator.hasNext());

Is empty: true

Removing from a peeking iterator

Remember that an iterator has a remove method which will remove the last element the next() method returned from the underlying source (collection). Hence we can call it once per call to next(). It will throw an IllegalStateException if we call remove() without a call to next() or call it more than once per call to next().

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
PeekingIterator<Integer> peekingIterator = Iterators.peekingIterator(list.iterator());

while (peekingIterator.hasNext()) {
    Integer element = peekingIterator.next();
    if (element % 2 == 1) {
        peekingIterator.remove();
    } else {
        System.out.println(element);
    }
}
System.out.println(list);

We have a peeking iterator (or could have been any iterator) and we get the element by using the next() method. If the retrieved element is odd, we remove it; otherwise we print it. Result is:

2
4
6
[2, 4, 6]

The PeekingIterator will not allow us to call remove() after a call to peek(). If we replace the call to next() with a peek(), we will get a IllegalStateException.

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
PeekingIterator<Integer> peekingIterator = Iterators.peekingIterator(list.iterator());
while (peekingIterator.hasNext()) {
    Integer element = peekingIterator.peek();
    if (element % 2 == 1) {
        peekingIterator.remove(); //Throws IllegalStateException if we had peeked before this call
    } else {
        System.out.println(peekingIterator.next());
    }
}

Throws

java.lang.IllegalStateException: Can't remove after you've peeked at next

Note that the behaviour is unspecified if the underlying collection is modified when the iteration is in progress (other than calling the remove() method).

Google Guava AbstractIterator

The Google Guava AbstractIterator class simplifies writing Iterators by providing a skeletal implementation. Remember that we need to implement two methods to have an Iterator (hasNext and next). There are certain types of data sources for which we cannot know if there is more elements left until we read the next element. Hence, it is difficult (or impossible) to implement the hasNext method (i.e., querying the end-of-data status).

Example: Let’s say we have a stream of some source which returns one element at a time and a special element (marker) when it has run out of elements. And we want to write an iterator for it. When the stream doesn’t support peeking, the only way to see if there are more elements, it to actually attempt to read from it. Then what do we do with the read element? We have to store it and return it when the caller calls the next() on our Iterator.

The AbstractIterator from Google Guava helps us do this. We have to implement only one method called computeNext(). We have to return the next element and call a method named endOfData() (a protected method in the AbstractIterator class) when we have no more elements left.

AbstractIterator - Example

Let us write the same EvenNumbersIterator using the Google Guava AbstractIterator this time.

public class EvenNumbersIterator extends AbstractIterator<Integer> {
    private final Iterator<Integer> iterator;

    private EvenNumbersIterator(List<Integer> nums) {
        this.iterator = nums.iterator();
    }

    @Override
    protected Integer computeNext() {
        // Consume (remove) the odd numbers
        while (iterator.hasNext()) {
            Integer element = iterator.next();
            if (element % 2 == 0) { // found an even number
                return element;
            }
        }
        return endOfData();
    }
}

We extend the AbstractIterator class, whose type parameter is same as the type parameter of our Iterator. We implement the computeNext method and it has the logic to return the next element. Here, we have a normal Iterator over integers and we keep checking (consuming elements) till we get an even number. If we get one, we return it. Otherwise, we call the endOfData method (a protected method in the AbstractIterator class) to denote there are no more elements left.

Using the same data/example, used earlier, it gives the same result.

EvenNumbersIterator evenNumbersIterator = new EvenNumbersIterator(List.of(2, 4, 6, 8, 1, 5, 10, 12, 7, 9));
while (evenNumbersIterator.hasNext()) {
    System.out.println(evenNumbersIterator.next());
}

Prints,

When the source has only even/odd elements,

EvenNumbersIterator evenNumbersIterator = new EvenNumbersIterator(List.of(2, 4, 6, 8));
while (evenNumbersIterator.hasNext()) {
    System.out.println(evenNumbersIterator.next());
}

EvenNumbersIterator evenNumbersIterator = new EvenNumbersIterator(List.of(3, 5, 7));
System.out.println("Is empty: " + !evenNumbersIterator.hasNext());

//Prints
Is empty: true

The only downside of using the AbstractIterator is the inheritance involved (we have to extend AbstractIterator). This means that our iterator cannot extend any other class. Usually there would be no reason to do so though and so the AbstractIterator is a very useful utility to have.

The computeNext method invocation

The implementation in the AbstractIterator will call the computeNext method from its hasNext() or the next() method. It gets the next element and stores it (as an instance variable) and returns it when next() is called. Once we call endOfData(), it never calls computeNext() thereafter.

If we throw an exception from the computeNext(), it propagates it to the caller calling the iterator’s hasNext() or the next().

From the implementation of the computeNext(), we cannot call hasNext(), next() or peek() (yes, even the AbstractIterator has a peek method). Because doing so will result in an infinite loop (as the iterator’s hasNext/next/peek calls computeNext in the first place). If we do so, it will throw an IllegalStateException.

AbstractIterator#peek

Since an AbstractIterator has a peek method and our Iterator extends it, we can peek at our Iterator.

EvenNumbersIterator evenNumbersIterator = new EvenNumbersIterator(List.of(2, 4, 6, 8));
while (evenNumbersIterator.hasNext()) {
   //Does not consume the next element and can call peek any number of times
    System.out.println(evenNumbersIterator.peek());
    System.out.println(evenNumbersIterator.next()); //This call moves the iteration forward
}

Conclusion

In this post, we learnt about the PeekingIterator and AbstractIterator from Google Guava. We use the Peeking Iterator to enable peeking into an Iterator without progressing the iteration. And the AbstractIterator enables us to write an Iterator for cases where we have to actually get/consume an element from the underlying source to determine the end-of-data status.

And check out the other google-guava utilities.

Introduction#

Peeking Iterator - An Iterator that can peek#

PeekingIterator - A Simple example#

Creating an iterator for iterating over even numbers#

Removing from a peeking iterator#

Google Guava AbstractIterator#

AbstractIterator - Example#

The computeNext method invocation#

AbstractIterator#peek#

Conclusion#