Iterator performance contract (and use on non-collections)

Question

If all that you're doing is a simple one-pass iteration (i.e. only hasNext() and next(), no remove()), are you guaranteed linear time performance and/or amortized constant cost per operation?

Is this specified in the Iterator contract anywhere?

Are there data structures/Java Collection which cannot be iterated in linear time?

java.util.Scanner implements Iterator<String>. A Scanner is hardly a data structure (e.g. remove() makes absolutely no sense). Is this considered a design blunder?

Is something like PrimeGenerator implements Iterator<Integer> considered bad design, or is this exactly what Iterator is for? (hasNext() always returns true, next() computes the next number on demand, remove() makes no sense).

Similarly, would it have made sense for java.util.Random implements Iterator<Double>?

Should a type really implement Iterator if it's effectively only using one-third of its API? (i.e. no remove(), always hasNext())

Answer 1

There is no such guarantee. As you point out, anyone can model anything as Iterator. Individual producers of iterators would have to specify their individual performance.

Answer 2

Nothing in the Iterator documentaton mentions any kind of performance guarantee, so there is no guarantee.

It also wouldn't make sense to require this constraint on such a universal tool.

A much more useful constraint would be document a iterator() method to specify the time constraints that this Iterator instance fulfills (for example an Iterator over a general-purpose Collection will most likely be able to guarantee linear time operation).

Similarly, nothing in the documentation requires hasNext() to ever return false, so an endless Iterator would be perfectly valid.

However, there is a general assumption that all Iterator instances behave like "normal" Iterator instances as returned by Collection.iterator() in that they return some number of values and end at some point. This is not required by the documentation and, strictly speaking, any code depending on that fact would be subtly broken.

Answer 3

All of your proposals sound reasonable for Iterator. The API docs explicitly say remove need not be supported, and suggests that one not use the older Enumeration that works just like Iterator except without remove.

Also, infinite-length streams are a very useful concept in functional programming, and can be implemented with an Iterator that always hasNext. It's a feature that it can handle either case.

Answer 4

I can imagine a use case for this.. And it seems intuitive enough. Personally I think it's fine.

for(long prime : new PrimeGenerator()){
    //do stuff
    if(condition){
        break;
    }
}

Answer 5

It sounds like you're thinking of iterators in the sense of a list or set traversal. I think a more useful mental model is a discrete object stream, aything that you want to handle one-at-a-time that can be streamed from a source in terms of discrete instances.

In that sense a stream of prime numbers or of list objects both makes sense, and the model doesn't imply anything about the finite-ness of the data source.