• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Should Iterator.hasNext() be idempotent?

 
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The Iterator interface hasNext() method is supposed to return true if the collection being iterated has additional elements. The next() method returns that next element. At what point does the "next pointer" move to the next element? The API docs don't make it clear. I tried the following code:

As I half-expected this created an infinite loop. The hasNext() method kept returning true but I never called the next() method. So with an ArrayList the pointer advances when the next() method is called. Are all collections the same (I guess I could try all of the standard ones)? I don't see anything in the docs that indicate that this needs to be the case.

By now you might be wondering why I would want an iterator that behaved this way. In some code I'm working on with a specialized itor I don't know if there are more elements to return until I find the next element. Think of it this way, suppose I have a PrimeNumberIterator that takes a list of numbers and returns the next prime number on each call to next(). The hasNext() method would have to find the next prime number in the list in order to know if there were more. Since hasNext() would already be doing the work to find the next value it makes sense to remember that value so that the next call to next() would return it. But what if there's another call to hasNext() before the call to next()? Should it find the next prime number or not?

I hope I didn't make this too confusing of a question.

_M_
 
Sheriff
Posts: 3063
12
Mac IntelliJ IDE Python VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, as far as I know, hasNext() will keep returning true until next() is called. If you have to do a significant amount of work for hasNext(), like in your PrimeNumberIterator example, I would just save the result in a private field, which could be cleared on the call to next().
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think it's perfectly reasonable to have an iterator which, internally, may fetch the next element when hasNext() is called. However, as far as what it looks like from outside the API (i.e. to people using it), you need to make sure it looks like hasNext() does not have any side effects, and only next() advances the pointer. This means you'll have to remember if hasNext() is called multiple times without next() - you don't keep fetching new elements; you have to wait until next() is called to move on. Furthermore even if hasNext() has never been called, next() should be able to return the next element if there is one (and throw NoSuchElementException otherwise). Consider this code:

Now this is a pretty silly way to use an iterator, but it shows off the special cases you need to consider. I think the API does make it clear enough that next() should return the next element, period (even if hasNext() is not called). And the ability to actually advance though the data structure is stipulated under next(), not hasNext(). It's not stated as clearly as we might like, but I think it's clear enough.

The above code was extremely contrived, of course. But I have seen, and even occasionally written, code that calls hasNext() more than once on a given iteration. For exampls, here's a method to convert a collection of objects to a string in which the objects are separated by a delimiter (e.g. a comma):

There are other ways this could be done - but the point is, this is a perfectly reasonable thing to do, and I would expect to get each element in the collection exactly once. Even though hasNext() is being called twice on each iteration.

Hope that helps...
[ January 10, 2006: Message edited by: Jim Yingst ]
 
author
Posts: 14112
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Mike Noel:
The API docs don't make it clear.



I think since Java 5 it does, as the following was added to the description of the next() method:


Calling this method repeatedly until the hasNext() method returns false will return each element in the underlying collection exactly once.



As this leaves totally open how often hasNext() gets called between calls to next(), it requires that hasNext() behaves as if it doesn't change the state of the iterator.
 
Mike Noel
Ranch Hand
Posts: 108
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for your comments guys. It made sense to me that hasNext() wouldn't alter the state of the object but since it wasn't explicit (at least I didn't think so) I wasn't sure if it was a requirement or not. It looks like they made the docs more specific for java 5.

_M_
 
Jim Yingst
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ah, I forgot to check the earlier versions of the docs. Yes, I was looking at the JDK 5 docs specifically.
 
What are your superhero powers? Go ahead and try them on this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic