Filtered Iterator

Question

I have written a wrapper for Java's Iterator class using Java 7, which is designed to only iterate items that match a certain filter.

When the filter is null, all items should be iterated.

Filter.java

public interface Filter<T> {
    boolean apply(T type);
}

FilteredIterator.java

import java.util.Iterator;

public class FilteredIterator<E> implements Iterator<E> {
    private Iterator<E> iterator;
    private Filter<E> filter;

    private E iteratorNext;
    private boolean iteratorHasNext;

    public FilteredIterator(Iterator<E> iterator, Filter<E> filter) {
        this.iterator = iterator;
        this.filter = filter;

        findNextValid();
    }

    private void findNextValid() {
        iteratorHasNext = iterator.hasNext();

        while (iterator.hasNext()) {
            iteratorNext = iterator.next();

            if (filter == null || filter.apply(iteratorNext)) {
                iteratorHasNext = true;
                break;
            }
        }
    }

    @Override
    public boolean hasNext() {
        return iteratorHasNext;
    }

    @Override
    public E next() {
        E nextValue = iteratorNext;
        findNextValid();
        return nextValue;
    }

    @Override
    public void remove() {
        iterator.remove();
    }
}

Is there anything I can improve on here? I'm not all that fond of findNextValid's implementation but I don't know what I can do to improve it.

Answer 1

Correctness

You can't support remove() because your iterator must always be at least one step behind the iterator being wrapped.

Design

You twist the code to make a null filter equal to a filter that accepts everything. Don't do that. Write a filter that accepts everything and use that instead.

Your class should be final. It's not designed to be extended.

You really need to document the Filter#apply(). That's not an intuitive method name. I'd rather see something like #accept(). When I apply a filter, I expect to pass in a collection and get back a filtered collection. You're asking the filter if a specific element is acceptable. That naming would also be more consistent with the JDK classes named XXXFilter, which use the accept name.

EDIT: I'm not a big fan of using null to indicate a default behavior. If they don't have to specify a filter, give them another constructor that doesn't ask for one. It can chain to the two-arg filter with a new Accept All filter. If they call a constructor asking for a filter and don't give one, I'd throw an NPE back at them.

EDIT: You can/should also move the Accept All filter to its own top-level class and make it public. You need it anyway .. may as well let clients specify it directly.

Implementation

You don't need iteratorHasNext at all. Just keep the next value. If there is none, set it to null. Your hasNext() implementation can check for null and return correctly.

With all these changes, your code might look more like:

public final class FilteredIterator<E> implements Iterator<E> {
    private final Iterator<E> iterator;
    private final Filter<E> filter;

    private boolean hasNext = true;
    private E next;

    public FilteredIterator(final Iterator<E> iterator, final Filter<E> filter) {
        this.iterator = iterator;
        Objects.requireNonNull(iterator);
        
        if (filter == null) {
            this.filter = new AcceptAllFilter<E>();
        } else {
            this.filter = filter;
        }
        
        this.findNext();
    }

    @Override
    public boolean hasNext() {
        return this.next != null;
    }

    @Override
    public E next() {
        E returnValue = this.next;
        this.findNext();
        return returnValue;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException();
    }
    
    private void findNext() {
        while (this.iterator.hasNext()) {
            this.next = iterator.next();
            if (this.filter.accept(this.next)) {
                return;
            }
        }
        this.next = null;
        this.hasNext = false;
    }
    
    private static final class AcceptAllFilter<T> implements Filter<T> {
        public boolean accept(final T type) {
            return true;
        }
    }
}

Answer 2

As scwagner has pointed out, your implementation of findNextValid has a bug.

Your implementation of findNextValid() has a bug. If you implement a filter that always returns false, you will still get the last element of the collection output. This is because you are caching the value of iterator.hasNext() when findNextValid() is entered, and not resetting it to false if you run off the end of the original iterator.

Do you understand why?

Imagine you have an iterator that is reading an array that looks like this:

{1,2,3}

Now, imagine that the iterator is on this conditional line:

if (filter == null || filter.apply(iteratorNext)) {

with the number 2. Well, the filter is not null so that is false, and the filter is always going to say no to any input, so that is also false. This conditional does not, and we loop again to the last element: 3.

iteratorNext now holds 3 because of:

iteratorNext = iterator.next();

And, just like with 2, the conditional will fail with 3. The problem here is that iteratorNext still holds 3.

This can be easily fixed by only setting iteratorNext if the conditional passes:

iteratorHasNext = iterator.hasNext();

while (iterator.hasNext()) {
    E tempNext = iterator.next();
    if (filter == null || filter.apply(tempNext)) {
        iteratorNext = tempNext
        iteratorHasNext = true;
        break;
    }
}

Note that this was not tested (I did not have time), but I believe that it should work.

---

public class FilteredIterator<E> implements Iterator<E> {
    private Iterator<E> iterator;
    private Filter<E> filter;

    private E iteratorNext;
    private boolean iteratorHasNext;

    public FilteredIterator(Iterator<E> iterator, Filter<E> filter) {

As far as I can tell filter isn't going to be changing much at all, right? If this is the case, then you should make them final. This will speed up your code:

public class FilteredIterator<E> implements Iterator<E> {
    private Iterator<E> iterator;
    private final Filter<E> filter;

    private E iteratorNext;
    private boolean iteratorHasNext;

    public FilteredIterator(Iterator<E> iterator, final Filter<E> filter) {