Code Monkeyism

Programming is hard by Stephan Schmidt

August 8, 2008

Response to the critique for my last post and OneElementIterator

I’ve wrote an update to the post where someone suggested in a trackback to use the JDK for an one element iterator.

I got interested in aa OneElementIterator, which optimized - not sure how fast try is - could look like this:

public class OneElementIterator[T] implements Iterator[T] {
  private T element;

  public OneElementIterator(T element) {
    this.element = element;
  }

  public boolean hasNext() {
    return element != null;
  }

  public T next() {
    try {
      return element;
    } finally {
      element = null;
    }
  }

Faster and shorter ideas?

Update: Remove got lost during cut & paste:

  public void remove() {
    // not supported, throw exception
    throw new UnsupportedOperationException("Remove not supported in OneElementIterator");
  }

And as Eugene noted next() should throw NoSuchElementException .

About the author: Stephan Schmidt is currently a team manager at ImmobilienScout24 in Berlin. Stephan has been working as a head of development and CTO. He has used a lot of different technologies in the last 20 years including Java, Rails and Python. Stephans main field of interest is maintainablity and productivity in software development. Want to know more? All views are only his own.

If you did like this article but you don't want to subscribe to new articles with your reader, you can follow me on Twitter or subscribe to new posts with your email:

Comments

Daniel Spiewak

Much faster to avoid the try (which as you implied, can be quite slow) and instead use a local temporary:

public T next() {
  T e = element;
  element = null;
  return e;
}

It’s not concurrency safe, but then, neither is yours. :-)

August 8th, 2008
stephan

Yes, thought about that, but was intrigued by the beauty of the finally solution. In production I would introduce the e reference though.

But I’m not sure about performance, because there is no Exception being thrown or catched.

August 8th, 2008
Eugene Kulesov

According to the Iterator class javadoc, next() method is supposed to throw NoSuchElementException when iteration has no more elements. Also, there is a remove() method, which should throw an UnsupportedOperationException if the remove operation is not supported by Iterator.

August 8th, 2008
stephan

@Eugene: You’re right of course.

The remove got lost with cut&paste (see missing } for class :-)

I’ll add the method.

August 8th, 2008
Erik Mogensen

What if you want to return an iterator that contains a _null_ :-)

And of course you have the while(true) System.out.println(e.next()); which relies on the exception to be thrown. It’s not good code, but it is valid. Violating the javadoc requirement of throwing the exception would put some unlucky user into a tight loop…

I’d go with Collections.singletonList(whatever).iterator(). The less code you write, the fewer bugs you write.

August 8th, 2008
stephan

@Erik: The whole point was not to return null ;-)

“@Eugene: You’re right of course.”

So I added to my version

  public T next() {
    if (!hasNext()) {
      throw new NoSuchElementException("No more elements in OneElementIterator");
    }
    try {
      return element;
    } finally {
      element = null;
    }
  }

“I’d go with Collections.singletonList(whatever).iterator(). The less code you write, the fewer bugs you write.”

Normally I would agree. There are some posts on this topic on this blog, for example the String.reverse issue (JDK versus write-your-own).

In this case, because Option[T] is potentially used a lot, I’d go for an optimization.

August 8th, 2008
Eugene Kuleshov

Stephan, it seem to me that you created a problem that does not actually exist. Basically, if you are always using iterator, just for the sake of syntactic sugar with the foreach loop, according to my microbenchmark you got yourself about 60% overhead (even with your optimized OneItemIterator class) comparing to simply returning a Null object. It is actually unlikely something like that ever going to be a bottle neck in the real application, but number of iterations and tiny mistakes you made while implementing such simple class is really scare. So, it would have been safer to simply use existing JRE classes.

August 8th, 2008
lqd

Nice :)

I guess we could rename OneElementIterator to Some, extend Option[T] and return this in iterator() to realign with the last post concepts.

August 8th, 2008
stephan

@Eugene: I’m not sure what’s more important, less bugs or performance. You decide. Otherwise I fear there is only Scala left for me.

@lqd: Hmm :-)

August 9th, 2008
James Iry

If you don’t care about performance, Collections.singleton(value).iterator. :-)

If you want performance and null handling, add a mutable “hasNext” boolean flag to your implementation.

It’s important to mention that, unlike Java style external iterators, the Scala solution based on map and flatMap or the Haskell solution based on bind and “return” (not the same thing as Java style return) require no mutation. E.g., here’s a complete Option monad in Scala - it’s even covariant, which is a pain in the arse in Java

sealed abstract class MyOption[ A] {
def map[B](f:A=>B):MyOption[B] = flatMap(x => MySome(f(x)))
def flatMap[B](f:A=>MyOption[B]):MyOption[B] = this match {
case MySome(x) => f(x)
case _ => MyNone
}
}
case class MySome[ A](value:A) extends MyOption[A]
case object MyNone extends MyOption[Nothing]

println(for {x <- MySome(3);y <- MySome(4);} yield x y)

The Haskell option monad is even tighter with less syntactic noise (although, I know this will get totally borked by word press, I hope something makes it through)

data MyOption a = MySome a | MyNone deriving Show

instance Monad MyOption where
(MySome x) >>= k = k x
MyNone >>= k = MyNone
return = MySome
fail s = MyNone

main = print $ do x <- MySome 3; y <- MySome 4; return (x y)

August 9th, 2008

Leave a Reply