How to write Iterators really REALLY fast

Recently I had to write an Iterator implementation for a TreeModel. I had used only the TreeModel interface, so I'll post the code (which is not long) in my next post for the benefit of anyone who wants to do the same. Some warning: I'm going to discuss a feature of dotNet here, but be patient - It's both interesting and I'll get to the Java bit very quickly! While writing the iterator, I remembered one of the (only) features I really liked about dotNet 2.0 - the "yield" feature. This allowed a developer to write an iterator implementation without worrying about state. Read more about it on MSDN's "yield" article. I'll provide a short example. Suppose you wanted to write an iterator which would iterate a Collection and return only the items matching a certain Predicate. The code would be something like:

public class PredicateIterable implements Iterable {
  private final Collection coll;
  private final Predicate pred;

  public PredicateIterable(Collection coll, Predicate pred) {
    this.coll = coll;
    this.pred = pred;
  }

  public Iterator iterator() {
    return new PredicateIterator(coll, pred);
  }
}

class PredicateIterator implements Iterator {
  private final Iterator state;
  private final Predicate pred;
  private boolean hasNextItem = false;
  private Object nextItem = null;

  public PredicateIterator(Collection coll, Predicate predicate) {
    this.state = coll.iterator();
    this.pred = predicate;
    calcNext();
  }
  
  public boolean hasNext() {
    return hasNextItem;
  }

  public Object next() {
    Object ret = nextItem;
    calcNext();
    return ret;
  }

  public void calcNext() {
    hasNextItem = false;
    while (!hasNextItem && state.hasNext()) {
      Object temp = state.next();
      if (pred.evaluate(temp)) {
        nextItem = temp;
        hasNextItem = true;
      }
  }
}

If you think this is bad enough, imagine having to traverse tree structures and keeping state for those using a Stack to keep traversal state. This is really simplified using the "yield" keyword. To give the same example, this time using it:

public class PredicateIterable implements Iterable {
  private final Collection coll;
  private final Predicate pred;

  public PredicateIterable(Collection coll, Predicate pred) {
    this.coll = coll;
    this.pred = pred;
  }

  public Iterator iterator() {
    for (Object nextItem : coll) {
      if (pred.evaluate(nextItem)) {
        yield return nextItem;
      }
    }
}

And that's it! This works because in dotNet, the compiler notices usages of "yield return" and compiles an entire Iterator class (Enumerator in dotNet, to be truthful). This class does a lot of magic in the background and creates a state machine which will make it seem as if whenever the code reaches the next() method of the returned iterator, the method will be pointed at the line following the previous "yield return". That's why it won't return the first element all the time, and why the method returns a single element when it's expected to return an Iterable instance of them. Back to Java. I really missed that feature when I was writing my TreeModelIterator. That's why I've recreated it, in Java - working in Java 5 and up. I had some restrictions for my design:

I wanted the code to compile using any normal Java compiler - No pre-compilers allowed.

I couldn't override the return keyword, as the compiler checks for unreachable code and it might invoke compilation errors in some cases.

I had to make it dead simple, simple enough for me to want to use it.

With these restrictions, I came up with the following design:

An abstract class called Yielder.

The class is Iterable, so it can be used anywhere.

An abstract method called yieldNext which the user implements using the same style he would use to implement a dotNet "yielding" method.

From the method, the developer could call yieldReturn(Object) in order to return an item, or yieldBreak() to break the iteration loop.

So, the above example would be implemented as:

public class PredicateIterable implements Iterable {
  private final Collection coll;
  private final Predicate pred;

  public PredicateIterable(Collection coll, Predicate pred) {
    this.coll = coll;
    this.pred = pred;
  }

  public Iterator iterator() {
    return new Yielder() {
      public void yieldNextCore() {
        for (Object nextItem : coll) {
          if (pred.evaluate(nextItem)) {
            yieldReturn(nextItem);
          }
        }
      }
    };
  }
}

The difference from dotNet is mainly due to the creation of the anonymous class. Not that different, is it? In the next post I'll post the implementation details of this. On the other hand, if you're excited and want to download it, please go to the project's site.