Authoring Iterators Using Google’s Collections Library

By | June 23, 2008

Let’s implement an iterator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Removes duplicates from the elements returned by provided iterator.
 * The provided iterator must return the elements in the order elements in the order defined by the comparator.
 * The first element of a series of duplicates is returned by this iterator.
 * @param  Type of element returned by the iterator.
 */
public final class DedupingOrderedCollectionIterator<E> implements Iterator<E> {
    private final PeekingIterator<E> iterator;
    private final Comparator<? super E> comparator;
 
    /**
     * @param iterator iterates over an ordered collection
     * @param comparator implements the same comparison used to order the collection
     */
    public DedupingOrderedCollectionIterator(final Iterator<? extends E> iterator, final Comparator<? super E> comparator) {
        this.iterator = Iterators.peekingIterator(iterator);
        this.comparator = comparator;
    }
 
    public boolean hasNext() {
        return iterator.hasNext();
    }
 
    public E next() {
        final E next = iterator.next();
        while (iterator.hasNext() && comparator.compare(next, iterator.peek()) == 0) {
            iterator.next();
        }
        return next;
    }
 
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

First, if you’re confused about the generic wildcards, watch Josh Bloch’s presentation entitled Effective Java Reloaded and watch for the reference of “producer extends, consumer super” (aka PECS) or reference Josh Bloch’s second edition of Effective Java.

Second, using Google’s PeekingIterator often reduces the code you need to deal with iterators.

Third, when implementing an iterator, you usually have to worry about what happens when next() is called when hasNext() would return false. What exception are you supposed to throw? And I keep coding the same implementation for remove() and always forget what exception it’s supposed to throw. Google’s AbstractIterator to the rescue!

Here’s the same iterator written with com.google.common.collect.AbstractIterator<T>:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Removes duplicates from the elements returned by provided iterator.
 * The provided iterator must return the elements in the order elements in the order defined by the comparator.
 * The first element of a series of duplicates is returned by this iterator.
 * @param  Type of element returned by the iterator.
 */
public final class DedupingOrderedCollectionIterator<E> extends AbstractIterator<E> {
    private final PeekingIterator<E> iterator;
    private final Comparator<? super E> comparator;
 
    /**
     * @param iterator iterates over an ordered collection
     * @param comparator implements the same comparison used to order the collection
     */
    public DedupingOrderedCollectionIterator(final Iterator<? extends E> iterator, final Comparator<? super E> comparator) {
        this.iterator = Iterators.peekingIterator(iterator);
        this.comparator = comparator;
    }
 
    protected E computeNext() {
        if (iterator.hasNext()) {
            final E next = iterator.next();
            while (iterator.hasNext() && comparator.compare(next, iterator.peek()) == 0) {
                iterator.next();
            }
            return next;
        }
        return endOfData();
    }
}

AbstractIterator allows you to write concise iterators with consistent behavior.