iterators

[Stefan Ram]

An iterator object, according to me, has the following three
atomic operations:

V - deliver the current value
A - deliver the current availability
(that is, whether there still is a value available)
I - attempt to increment the state to the next value

How does

http://download.java.net/jdk7/docs/api/java/util/Iterator.html

make these operations available? It has:

next = V + I and
hasNext = A

. How do I prefer to write code for iterators?

class Example
implements de.dclj.ram.Value<T>, de.dclj.ram.Advanceable
{ public T value(){ ... }
public boolean advance(){ ... }}

, where »advance« returns »true« iff the increment operation
was possible. So, I prefer two operations as follows:

value = V and
advance = A + I

(the »I« now has moved from »V« to »A«).

This allows to »peek« at the current value as often as seen
fit without risking to change the state of the iterator
inadvertently. Also, it seems to be natural to me to
/try to advance/ to the next state /and then return/
whether this was a success in one operation.

So, this style for me is both easier and more natural to code
and easier and more natural to use than the »Iterator«
interface of Java SE. Of course, I can't use these objects
directly with Java SE classes that expect an Iterator,
I need to wrap them into an adapter object for this.
Still, I really consider to go this way than to code
directly in the Java Iterator style.

I have no question, but feel free to comment.

 

[Stefan Ram]

class Example
implements de.dclj.ram.Value<T>, de.dclj.ram.Advanceable
{ public T value(){ ... }
public boolean advance(){ ... }}

I made a design error:

If there is not even one first value available,
the client can not detect this. So now, I prefer:

class ExampleIterator
implements
de.dclj.ram.IsAvailable,
de.dclj.ram.Value<T>,
de.dclj.ram.Advanceable,
{ public boolean IsAvailable(){ ... }
public T value() { ... }
public void advance() { ... }}

 

[Mike Schilling]

I made a design error:

If there is not even one first value available,
the client can not detect this. So now, I prefer:

class ExampleIterator
implements
de.dclj.ram.IsAvailable,
de.dclj.ram.Value<T>,
de.dclj.ram.Advanceable,
{ public boolean IsAvailable(){ ... }
public T value() { ... }
public void advance() { ... }}

I'd call this a "cursor", and propbably call the boolean method
isValid()". Note that C# presents things more the way you like. Its
IEnumerator interface has:

1. The property Current, like your method value().
2. The boolean method MoveNext(), which is like your advance() plus
your isAvailable() put together.

 

[Andreas Leitgeb]

I made a design error:

Not really, if you considered the initial position of the
iterator to be *before* the first element.
while (ramIt.advance()) { ... ramIt.value() ... }

There would have been perhaps a dozen different but equally
consistent approaches for iterators. Each has its pros and
cons, being better in some situations and worse in others.

hasNext/next fits well into loops that save the return-value of
next() into a local variable (or use it just once), and thus have
no need for redoable value-retrieval. Your iterator does an
additional job, namely that of keeping the value available until
next advance. Maybe that was the reason for the Java-guys to
choose their more barebone abstraction.

 

[Lew]

class Example
implements de.dclj.ram.Value<T>, de.dclj.ram.Advanceable
{ public T value(){ ... }
public boolean advance(){ ... }}

I made a design error:

If there is not even one first value available,
the client can not detect this. So now, I prefer:

class ExampleIterator
implements
de.dclj.ram.IsAvailable,
de.dclj.ram.Value<T>,
de.dclj.ram.Advanceable,
{ public boolean IsAvailable(){ ... } [sic]
public T value() { ... }
public void advance() { ... }}

I'd call this a "cursor", and propbably call the boolean method
isValid()". Note that C# presents things more the way you like. Its
IEnumerator interface has:

1. The property Current, like your method value().
2. The boolean method MoveNext(), which is like your advance() plus
your isAvailable() put together.

You could build one from a ListIterator.
<http://java.sun.com/javase/6/docs/api/java/util/ListIterator.html>

public interface Advancer <E> extends java.util.ListIterator <E>
{
public E value();
}

You would simply use 'hasNext()' instead of 'isAvailable()'.

'next()' is already like 'MoveNext()', but uses an exception instead of a
boolean return. I suspect this is to obviate a test-and-branch in both the
source and the runtime for the usual case of having a next element.

A simple implementation of 'value()' could be put together from a combination
of 'hasNext()', 'hasPrevious()', 'next()' and 'previous()' or use a local
'current' and a little bit of state.

 

[Mike Schilling]

(e-mail address removed)-berlin.de (Stefan Ram) writes:
class Example
implements de.dclj.ram.Value<T>, de.dclj.ram.Advanceable
{ public T value(){ ... }
public boolean advance(){ ... }}
I made a design error:

If there is not even one first value available,
the client can not detect this. So now, I prefer:

class ExampleIterator
implements
de.dclj.ram.IsAvailable,
de.dclj.ram.Value<T>,
de.dclj.ram.Advanceable,
{ public boolean IsAvailable(){ ... } [sic]
public T value() { ... }
public void advance() { ... }}

I'd call this a "cursor", and propbably call the boolean method
isValid()". Note that C# presents things more the way you like.
Its
IEnumerator interface has:

1. The property Current, like your method value().
2. The boolean method MoveNext(), which is like your advance() plus
your isAvailable() put together.

You could build one from a ListIterator.
<http://java.sun.com/javase/6/docs/api/java/util/ListIterator.html>

public interface Advancer <E> extends java.util.ListIterator <E>
{
public E value();
}

You would simply use 'hasNext()' instead of 'isAvailable()'.

'next()' is already like 'MoveNext()', but uses an exception instead
of a boolean return. I suspect this is to obviate a test-and-branch
in both the source and the runtime for the usual case of having a
next element.

It's becausee Java assumes you've called hasNext() first, so next()
failing really is exceptional. C# can't assume anything analogous,
since no "test-only" method exists. That is, the standard Java loop
looks like

for (Iterator iter = ...; iter.hasNext(); )
{
value = iter.next();
}

while the C# equivalent is

for (Iterator iter = ...; iter.MoveNext()
{
value = iter.Current;
}

The same amount of work, just divided up differently.

 

[Tom Anderson]

An iterator object, according to me, has the following three
atomic operations:

V - deliver the current value
A - deliver the current availability
(that is, whether there still is a value available)
I - attempt to increment the state to the next value

How does

http://download.java.net/jdk7/docs/api/java/util/Iterator.html

make these operations available? It has:

next = V + I and
hasNext = A

. How do I prefer to write code for iterators?

class Example
implements de.dclj.ram.Value<T>, de.dclj.ram.Advanceable
{ public T value(){ ... }
public boolean advance(){ ... }}

, where ?advance? returns ?true? iff the increment operation
was possible. So, I prefer two operations as follows:

value = V and
advance = A + I

(the ?I? now has moved from ?V? to ?A?).

This allows to ?peek? at the current value as often as seen
fit without risking to change the state of the iterator
inadvertently. Also, it seems to be natural to me to
/try to advance/ to the next state /and then return/
whether this was a success in one operation.

So, this style for me is both easier and more natural to code
and easier and more natural to use than the ?Iterator?
interface of Java SE. Of course, I can't use these objects
directly with Java SE classes that expect an Iterator,
I need to wrap them into an adapter object for this.
Still, I really consider to go this way than to code
directly in the Java Iterator style.

I have no question, but feel free to comment.

ISTR that this is exactly how Bertrand Meyer says iterators should work -
separate methods for inspecting the state and altering it.

I don't object to that at all; i also don't really feel the pain of having
it the way we do in java. I very rarely use iterators in anything other
than the stereotypical loops, where both styles of iterator work fine.

tom

 

[Daniel Pitts]

I made a design error:

If there is not even one first value available,
the client can not detect this. So now, I prefer:

class ExampleIterator
implements
de.dclj.ram.IsAvailable,
de.dclj.ram.Value<T>,
de.dclj.ram.Advanceable,
{ public boolean IsAvailable(){ ... }
public T value() { ... }
public void advance() { ... }}

It gets more complicated than that if you consider different classes of
iterators (ListIterators in Java for example, or Random Access Iterators
in C++)

ListIterators actually keep track of the location "between" elements.
isAvailable doesn't make sense in that case.

One thing that I miss in Java is reversible iterators. Actually, there
are a lot of things I'd like to rework in the Java collections library,
but unfortunately there aren't any ways of doing so without breaking
everything or creating ugly bridge code.

What I would *love* is an iterator that can be made smart enough to not
throw ConcurrentModificationException if the modification can be proven
to be non-conflicting (such as appending to a list, or removing a node
from a linked-list, which is not any node being pointed to by the iterator.)

 

[Andreas Leitgeb]

[...]
What I would *love* is an iterator that can be made smart enough to not
throw ConcurrentModificationException if the modification can be proven
to be non-conflicting (such as appending to a list, or removing a node
from a linked-list, which is not any node being pointed to by the
iterator.)

Can you give some examples of situations where you've wished you
had such a thing?

Iterate a list, and for certain elements, just throw them back to the end
of the list (in the expectation to run over them later again, when time is
hopefully mature for these elements) and the others either leave or remove.

Current workaround is to append them to a temp list instead, and after
the first list is through, append to it the elements of the temp list,
and redo the first list's iteration (not before expensively positioning
the cursor to its previous position, of course).

Yes, it would require some logic to not run into a busy loop moving always
the same element cyclically, but that task is on the programmer. We don't
stop him from "while(true) {...}", either, even if the body has no break in
it.

"fail late" and "fail early" lack another alternative:
"just don't fail at all"

(yes, of course, not *all* collections would necessarily support it.)

Daniels request was probably not very precise. It's not "Iterator"'s
business to allow such uses, but the collection that implements any
such iterator. He could easily create his own collection and make his
own iterator for it never fail with concurrent modifications, but I
understood him as saying: Some of these standard collections really
could be a bit less touchy in this regard.

 

[markspace]

[...]
What I would *love* is an iterator that can be made smart enough to
not throw ConcurrentModificationException if the modification can be
proven to be non-conflicting (such as appending to a list, or removing
a node from a linked-list, which is not any node being pointed to by
the iterator.)

Can you give some examples of situations where you've wished you
had such a thing?

I seem to recall that some of the concurrent collections in Java have a
similar behavior. That is they don't fail, but they might not return
"consistent" or intuitive results either. A queue might found to have
size() > 0 for example, but the next instant to contain no elements at all.

I don't believe these concurrent classes provide an Iterator either,
although it might be possible to make one.

 

[markspace]

I don't believe these concurrent classes provide an Iterator either,
although it might be possible to make one.

Oops, and I had the page open to the docs too, which clearly state that
an Iterator is provided. Silly me. Here's the docs on it:

"The returned iterator is a "weakly consistent" iterator that will
never throw ConcurrentModificationException, and guarantees to traverse
elements as they existed upon construction of the iterator, and may (but
is not guaranteed to) reflect any modifications subsequent to construction."


Interesting....

 

[Roedy Green]

What I would *love* is an iterator that can be made smart enough to not
throw ConcurrentModificationException if the modification can be proven
to be non-conflicting (such as appending to a list, or removing a node
from a linked-list, which is not any node being pointed to by the iterator.)

Since Iterator is an interface, and since below-average programmers
are expected to implement it, I think it important that Iterator be
kept as simple as possible. It also needs to be speedy since it is at
the core of loops. If you want to add fancy features, use a new
interface, perhaps a sub-interface of Iterator with a superset of
methods.

--
Roedy Green Canadian Mind Products
http://mindprod.com

"Let us pray it is not so, or if it is, that it will not become widely known."
~ Wife of the Bishop of Exeter on hearing of Darwin's theory of the common descent of humans and apes.

 

[Daniel Pitts]

[...]
What I would *love* is an iterator that can be made smart enough to
not throw ConcurrentModificationException if the modification can be
proven to be non-conflicting (such as appending to a list, or removing
a node from a linked-list, which is not any node being pointed to by
the iterator.)

Can you give some examples of situations where you've wished you
had such a thing?

I have a simulation involving robots which can shoot at each other.
Once a robot is destroyed, it is removed from the list. At the time
that damage is dealt, I am already iterating through that list.

This means that I must go through the list afterward and remove the dead
robots, instead of removing them as they die.

This is a simplified example. The list itself may contain other objects
(such as missiles, mines, etc...) each of which may cease to exist
and/or inflict damage at any time.

 

[Daniel Pitts]

Since Iterator is an interface, and since below-average programmers
are expected to implement it, I think it important that Iterator be
kept as simple as possible. It also needs to be speedy since it is at
the core of loops. If you want to add fancy features, use a new
interface, perhaps a sub-interface of Iterator with a superset of
methods.

Uh, what I was requesting wasn't an addition to the behavior or an
Iterator, but a modification of existing behavior.

Besides, have you ever tried to create a fail-fast iterator? Look at
source-code provided for existing implementation, and you will see that
they go through a lot of hoops to *prevent* the use-case I would like,
even when it is possible (and even easy) to implement correctly.

I doubt many below-average programmers are creating Iterator
implementations (well, then again, below-average programmers do tend to
do things the hard way).

 

[Tom Anderson]

[...]
What I would *love* is an iterator that can be made smart enough to not
throw ConcurrentModificationException if the modification can be proven to
be non-conflicting (such as appending to a list, or removing a node from a
linked-list, which is not any node being pointed to by the iterator.)

Can you give some examples of situations where you've wished you
had such a thing?

I have a simulation involving robots which can shoot at each other. Once a
robot is destroyed, it is removed from the list. At the time that damage is
dealt, I am already iterating through that list.

This means that I must go through the list afterward and remove the dead
robots, instead of removing them as they die.

This is a simplified example. The list itself may contain other objects (such
as missiles, mines, etc...) each of which may cease to exist and/or inflict
damage at any time.

I had exactly that problem many years ago, only it was spaceships instead
of robots.

How about something like:

Collection<Thing> things; // robots, missiles, mines, etc

void carryOutATurn() {
List thingsToDo = new LinkedList(things);
while (!thingsToDo.isEmpty()) {
Thing next = thingsToDo.remove(0);
Collection<Thing> casualties = next.takeTurn();
if (!casualties.isEmpty()) {
things.removeAll(casualties);
thingsToDo.removeAll(casualties);
}
}
}

This does involve creating and throwing away a linked list of everything
in the universe on every turn, and potentially a lot of little casualty
lists too - although these can be emptySet or singleton sets from
Collections, which are very cheap.

It would be straightforward to extend this to handle new things (a
newly-fired missile, etc) as well.

An alternative to the casualty list would be to create and pass in a
little callback object for deleting things:

class Undertaker {
public void kill(Thing t) {
things.remove(t);
thingsToDo.remove(t);
}
}

tom

 

[Lew]

I have a simulation involving robots which can shoot at each other. Once
a robot is destroyed, it is removed from the list. At the time that
damage is dealt, I am already iterating through that list.

This means that I must go through the list afterward and remove the dead
robots, instead of removing them as they die.

This is a simplified example. The list itself may contain other objects
(such as missiles, mines, etc...) each of which may cease to exist
and/or inflict damage at any time.

So when, say, a robot dies, the iterator is no longer pointing to it but has
already moved on?

If the iterator hasn't moved on, then iterator.remove() would help.

 

[Daniel Pitts]

Daniel Pitts wrote:
[...]
What I would *love* is an iterator that can be made smart enough to
not throw ConcurrentModificationException if the modification can be
proven to be non-conflicting (such as appending to a list, or
removing a node from a linked-list, which is not any node being
pointed to by the iterator.)

Can you give some examples of situations where you've wished you
had such a thing?

I have a simulation involving robots which can shoot at each other.
Once a robot is destroyed, it is removed from the list. At the time
that damage is dealt, I am already iterating through that list.

This means that I must go through the list afterward and remove the
dead robots, instead of removing them as they die.

This is a simplified example. The list itself may contain other
objects (such as missiles, mines, etc...) each of which may cease to
exist and/or inflict damage at any time.

I had exactly that problem many years ago, only it was spaceships
instead of robots.

How about something like:

Collection<Thing> things; // robots, missiles, mines, etc

void carryOutATurn() {
List thingsToDo = new LinkedList(things);
while (!thingsToDo.isEmpty()) {
Thing next = thingsToDo.remove(0);
Collection<Thing> casualties = next.takeTurn();
if (!casualties.isEmpty()) {
things.removeAll(casualties);
thingsToDo.removeAll(casualties);
}
}
}

This does involve creating and throwing away a linked list of everything
in the universe on every turn, and potentially a lot of little casualty
lists too - although these can be emptySet or singleton sets from
Collections, which are very cheap.

It would be straightforward to extend this to handle new things (a
newly-fired missile, etc) as well.

This is similar to what I did, but instead of copying things, used this
approach:

public void doTurn() {
Collection<Thing> current = allThings;
do {
// clean up
allThings.addAll(thingsToAdd);
allThings.removeAll(thingsToRemove);

handleTurns(current);

// things not yet processed
current = thingsToAdd;

// reset
thingsToAdd = new ArrayList<Thing>();
thingsToRemove.clear();
} while (!current.isEmpty())
}

public void handleTurns(Collection<Thing> toHandle) {
for (Thing thing: toHandle) {
if (!thingsToRemove.contains(thing)) {
thing.handleTurn();
}
}
}

This is still somewhat annoying to deal with, however.