16560

Iterator performance contract (and use on non-collections)

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

Answer1:

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.

Answer2:

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.

Answer3:

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.

Answer4:

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.

Answer5:

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; } }

Recommend

  • How can I ensure Realm schema is identical across Android and iOS?
  • How can I do a 301 redirect from http to https in Wildfly 8.2?
  • Putting incomplete nested lists in a rectangular ndarray
  • shutdown and update job in Google Dataflow with PubSubIO + message guarantees
  • What I have to do to guarantee that ccc.jar is loaded before aaa.jar?
  • mapping between two ontologies
  • Is there a way to call library thread-local init/cleanup on thread creation/destruction?
  • Cannot invoke my method on the array type int[]
  • Lua: Line breaks in strings
  • Iron Router: How do I send data to the layout?
  • Two Tables Serving as one Model in Rails
  • Django simple Captcha “No module named fields” error
  • How to attach a node.js readable stream to a Sendgrid email?
  • Use of this Javascript
  • The plugin 'org.apache.maven.plugins:maven-jboss-as-plugin' does not exist or no valid ver
  • Linq Objects Group By & Sum
  • Android screen density dpi vs ppi
  • C# - Serializing and deserializing static member
  • Bug in WPF DataGrid
  • How would I use PHP exceptions to define a redirect?
  • Incrementing object id automatically JS constructor (static method and variable)
  • How to extract text from Word files using C#?
  • Hazelcast - OperationTimeoutException
  • RestKit - RKRequestDelegate does not exist
  • How to format a variable of double type
  • Revoking OAuth Access Token Results in 404 Not Found
  • Buffer size for converting unsigned long to string
  • log4net write single file for each call to log.info
  • How can I get HTML syntax highlighting in my editor for CakePHP?
  • How do I configure my settings file to work with unit tests?
  • How to stop GridView from loading again when I press back button?
  • need help with bizarre java.net.HttpURLConnection behavior
  • IndexOutOfRangeException on multidimensional array despite using GetLength check
  • Bitwise OR returns boolean when one of operands is nil
  • sending mail using smtp is too slow
  • MATLAB: Piecewise function in curve fitting toolbox using fittype
  • Busy indicator not showing up in wpf window [duplicate]
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • Binding checkboxes to object values in AngularJs
  • How can I use `wmic` in a Windows PE script?