9
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ There's so many things you could improve here if you would use Java 8... \$\endgroup\$ – Simon Forsberg Nov 28 '15 at 10:18
9
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ The issue with using null as the "no more values" value is that if anything in the iterator is null and it passes through the filter, hasNext will return false, even if there's still elements in the iterator. \$\endgroup\$ – Jack Wilsdon Nov 28 '15 at 11:59
  • \$\begingroup\$ @oliverpool Oversight, corrected. \$\endgroup\$ – Eric Stein Nov 28 '15 at 13:45
  • \$\begingroup\$ @JackWilsdon True, I dropped the ball on that. Corrected. \$\endgroup\$ – Eric Stein Nov 28 '15 at 13:45
  • \$\begingroup\$ I don't the the usage of this at all. It makes to code almost illegible for no reason. I would recommend only using this when there is an ambiguity that needs to be resolved. \$\endgroup\$ – Boris the Spider Nov 28 '15 at 16:13
  • 1
    \$\begingroup\$ @BoristheSpider i feel the opposite way, I prefer using this even when it's redundant \$\endgroup\$ – Alexander Mills Mar 1 at 8:57
6
\$\begingroup\$

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) {
\$\endgroup\$
  • 1
    \$\begingroup\$ I should have specified this in the original question, but when filter is null I want all items to pass. With my current code this works fine, however when the filter is null in your code, iteratorHasNext is never set to false, and iteratorNext is never set, leading to an infinite loop when trying to consume the iterator. \$\endgroup\$ – Jack Wilsdon Nov 28 '15 at 3:50
  • \$\begingroup\$ Using final will not significantly speed up his code. It should be used to clarify intent to later readers. iterator should also be final, as the reference should not be reassigned. \$\endgroup\$ – Eric Stein Nov 28 '15 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.