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:
return keyword, as the compiler checks for unreachable code and it might invoke compilation errors in some cases.With these restrictions, I came up with the following design:
Yielder.Iterable, so it can be used anywhere.yieldNext which the user implements using the same style he would use to implement a dotNet “yielding” method.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);
}
}
}
};
}
}
Difference from dotNet is bolded. 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.
July 14th, 2007 at 5:52 pm
By the way, as you might have noticed I’ve changed the theme of the blog to a different one, so let me know whether you like it or not, and if not - what about it.
Also, I didn’t place the ads. I’ll be getting rid of them slowly, unless you have some (weird) objection for it.
July 15th, 2007 at 4:49 am
Thanks for the idea. Side comment: Looks like you forgot the yieldNext method declaration in your final example. Gotta love Java verbosity.
July 15th, 2007 at 5:44 am
Oops! I knew it was too short.. Fixed!
PS, stay tuned and I’m also talking about how it was implemented…
If there’s a an interest, I’ll put the source up somewhere, too.
July 15th, 2007 at 2:06 pm
I’m definitely interested in more information on this. Very interesting!
July 18th, 2007 at 6:33 am
[…] In the third in the “yielder series” (1, 2>), I will describe the differences I’ve seen between Jakarta’s BCEL and ObjectWeb’s ASM frameworks for bytecode manipulation. […]
July 23rd, 2007 at 8:49 am
[…] Until the project’s site is made clearer, please take a look at the blog’s posts for explanations. Specifically, the post about the concept, the one about the implementation, about the library used, and about hooking into the class loader. Also, take a look at this example on the blog and many other examples in the proof-of-concept collections library built on top of the yielder feature, in the repository. […]
July 30th, 2007 at 6:17 pm
[repost; the backing database crashed on my last attempt]
As an aside, you can also easily write yield-style iterators in (interpreted) Rhino Javascript, as for example is included in JDK 6+.
July 30th, 2007 at 9:11 pm
However, my implementation doesn’t require you to learn an additional language - Rhino, in your case, and is also implemented in pure Java, which means all the HotSpot benefits known today.
August 6th, 2007 at 2:42 pm
Alternatively you could write an anonymous iterator that works with JDK 1.2+ like this.
return new Iterator() {
ListIterator iter = new LinkedList(coll).listIterator();
public boolean hasNext() {
while (iter.hasNext()) {
if (pred.evaluate(iter.next())) {
iter.previous();
return true;
}
}
return false;
}
public Object next() {
return iter.next();
}
public void remove() {
return iter.remove();
}
};
August 6th, 2007 at 3:37 pm
Your suggestion will work great, but only for a collection - as I said in my post, this is the simple case. When it gets more complex, it’s harder and you need to save more state. More-over, this is not intuitive code.
Take a look at the examples I have in the project’s site; there are some iterators that traverse a graph, a tree, transform a list - All with very simple and intuitive code.
Check it out!
August 6th, 2007 at 11:52 pm
Is the purpose of this to filter out items that are not included in the predicate ? If so, it will just stop when it reaches the first “non-predicate”. You really need to put the calcNext bit in a loop to do it properly.
August 7th, 2007 at 5:08 am
Burnley - Yes, the calcNext is in a loop externally as the iterator is used in a loop - a foreach loop, preferably.
August 7th, 2007 at 6:55 pm
August 7th, 2007 at 11:47 pm
In that case, the Iterator interface is being misused. An interator shouldn’t have hasNext return false then return true.
August 8th, 2007 at 12:47 am
Burley - It doesn’t…
August 8th, 2007 at 4:03 pm
Elementary Java Solutions
I recently found a great article at Chaotic Java on coding iterators that introduced a solution for iterating over varying types of object collections and only returning those that satisfy given conditions or predicates. I’m a big fan of ..
…
August 31st, 2007 at 7:30 am
[…] A week ago, Michael Barker wrote a use case for yielder, where he uses the yielding ability to implement “Mini-Axon”, the Kamaelia learning experience usually done in Python, where generators are a built-in feature of the language. I thought it was good to mention it here, to show how yielder can be used for more than just an easy way to implement iterators - for example, to yield results of processing requests as soon as they arrive at the processing box, in the case of Mini-Axon. […]
April 6th, 2008 at 6:42 am
[…] or post your comments here on the blog. If you haven’t experienced the yielder feature yet, read some about it or download it and give it a […]