Should Iterator.hasNext() be idempotent?

[Mike Noel]

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:

class Main {
 
    public static void main(String args[]) {
List l = new ArrayList();
l.add(new Integer(1));
l.add(new Integer(2));
l.add(new Integer(3));
 
Iterator itor = l.iterator();
while (itor.hasNext()) {
    //    Integer i = (Integer) itor.next();
}
    }
}

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_

[Greg Charles]

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().

[Jim Yingst]

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:

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("A");
        list.add("B");
        list.add("C");
 
        Iterator iter = list.iterator();
        System.out.println("should be A: " + iter.next());
 
        System.out.println("should be true: " + iter.hasNext());
        System.out.println("should be true: " + iter.hasNext());
        System.out.println("should be true: " + iter.hasNext());
        System.out.println("should be true: " + iter.hasNext());
        System.out.println("should be true: " + iter.hasNext());
 
        System.out.println("should be B: " + iter.next());
        System.out.println("should be C: " + iter.next());
 
        try {
            iter.next();
            System.out.println("should have trown exception, but didn't");
        } catch (NoSuchElementException e) {
            System.out.println("correctly threw exception");
        }
 
        try {
            iter.next();
            System.out.println("should have trown exception, but didn't");
        } catch (NoSuchElementException e) {
            System.out.println("correctly threw exception");
        }
    }

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):

    public static String join(Collection coll, String delim) {
        StringBuffer sb = new StringBuffer();
        for (Iterator it = coll.iterator(); it.hasNext(); ) {
            sb.append(it.next());
            if (it.hasNext())
                sb.append(delim);
        }
        return sb.toString();
    }

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 ]

[Ilja Preuss]

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]

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]

Ah, I forgot to check the earlier versions of the docs. Yes, I was looking at the JDK 5 docs specifically.