cloning Iterators?

[Andreas Leitgeb]

Mostly out of curiosity, and not so much out of any current real
need, I wonder, why Iterators are not cloneable.

I can't think of any reason, how this cloning could ever be non-
trivial to implement for any type of collection/iterator, but
perhaps someone else knows of some ferro concrete strong reasons
why this could be a bad idea, and cares to let me know?

By googling I found (from more than two years ago):
http://www.velocityreviews.com/foru...terator-or-an-equivalent-solution-needed.html
where two "solutions" (*) were suggested (by Patricia and Eric),
which both do not appear like satisfactory abstract solutions,
but rather workarounds for current non-cloneability.

* namely toArray() being one, and the other was: iterating the inner
loop from 0 to current element, rather than from current to end -
but how can I even detect, when two iterators sit on the the same
spot, if the collection had no uniqueness constraint in the first
place?

 

[Owen Jacobson]

Mostly out of curiosity, and not so much out of any current real
need, I wonder, why Iterators are not cloneable.

I can't think of any reason, how this cloning could ever be non-
trivial to implement for any type of collection/iterator, but
perhaps someone else knows of some ferro concrete strong reasons
why this could be a bad idea, and cares to let me know?

By googling I found (from more than two years ago):
 http://www.velocityreviews.com/forums/t140911-clone-an-iterator-or-an....
where two "solutions" (*) were suggested (by Patricia and Eric),
which both do not appear like satisfactory abstract solutions,
but rather workarounds for current non-cloneability.

* namely toArray() being one, and the other was: iterating the inner
loop from 0 to current element, rather than from current to end -
but how can I even detect, when two iterators sit on the the same
spot, if the collection had no uniqueness constraint in the first
place?

As it stands, I can write (and have written) iterators over some input
source such as a stream or ResultSet. Forcing all Iterators to be
Clonable would make them unusable for that (and I'd basically end up
writing my own Iterator interface, sans Clonable).

-o

 

[Mike Schilling]

Mostly out of curiosity, and not so much out of any current real
need, I wonder, why Iterators are not cloneable.

I can't think of any reason, how this cloning could ever be non-
trivial to implement for any type of collection/iterator, but
perhaps someone else knows of some ferro concrete strong reasons
why this could be a bad idea, and cares to let me know?

It seems safe enough to clone readonly iterators. Cloning iterators
that can modify the underlying Collection is asking for trouble; as
soon as one does, the others start throwing
ConcurrentModificationExceptions.

 

[Andreas Leitgeb]

As it stands, I can write (and have written) iterators over some input
source such as a stream or ResultSet. Forcing all Iterators to be
Clonable would make them unusable for that (and I'd basically end up
writing my own Iterator interface, sans Clonable).

Thanks! That's exactly the ferro concrete reason, that didn't occur
to me. I didn't think of iterable ressources, that are consumed during
iteration.

If anything was to be done, it would be subclassing Iterator to a
CloneableIterator, for which the standard collections could be
retrofitted to actually return that, but this is another story...

 

[Andreas Leitgeb]

It seems safe enough to clone readonly iterators. Cloning iterators
that can modify the underlying Collection is asking for trouble; as
soon as one does, the others start throwing
ConcurrentModificationExceptions.

Owen hit the Nail on its head in his followup.
Anyway, there can *usually* be more than one iterator for
the same structure (except for those pointed out by Owen),
so it shouldn't make a difference to reading iterators,
whether a *cloned* iterator writes, or if a *normally obtained*
iterator writes.

At least, wherever more than one iterator can be created,
it would theoretically be also safe to clone them.

Anyone, who can falsify even this weakened thesis?

 

[Owen Jacobson]

Thanks! That's exactly the ferro concrete reason, that didn't occur
to me. I didn't think of iterable ressources, that are consumed during
iteration.

If anything was to be done, it would be subclassing Iterator to a
CloneableIterator, for which the standard collections could be
retrofitted to actually return that, but this is another story...

It should be possible to express the union using type bounds, which
would be marginally more flexible than requiring a specific joint
interface ClonableInterator:

import java.util.Iterator;

public class JointType {
public <E, T extends Iterator<E> & Cloneable> void
takesCloneableIterator (T iterator) {
T copy = iterator.clone ();

/* use copy and original */
}
}

However, this doesn't work for two reasons:
- you need to cast the return from clone.
- the Cloneable interface doesn't actually declare the clone()
method.

To use cloneable you actually need a reference of a type implementing
Cloneable that has a public clone method, rather than of Cloneable.

 

[Andreas Leitgeb]

To use cloneable you actually need a reference of a type implementing
Cloneable that has a public clone method, rather than of Cloneable.

I'd even be happy, if all the standard collections in java.util had
a method, that took an apt Iterator (i.e. one belonging to that
collection), and returned a new one initially sitting on the same spot.
Appropriate collections could even return a new ListIterator
when given only a plain one.

 

[Lew]

Owen hit the Nail on its head in his followup.
Anyway, there can *usually* be more than one iterator for
the same structure (except for those pointed out by Owen),
so it shouldn't make a difference to reading iterators,
whether a *cloned* iterator writes, or if a *normally obtained*
iterator writes.

At least, wherever more than one iterator can be created,
it would theoretically be also safe to clone them.

Anyone, who can falsify even this weakened thesis?

Even Iterators that have not modified their underlying Iterable can throw
ConcurrentModificationException if another iterator, or anything else,
modifies the Iterable.

The iterators returned by this class's iterator and listIterator methods are fail-fast:
if the list is structurally modified at any time after the iterator is created,
in any way except through the iterator's own remove or add methods, the iterator will
throw a ConcurrentModificationException. Thus, in the face of concurrent modification,
the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic
behavior at an undetermined time in the future.

from <http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html>
but it applies to others, too.

So if you cloned an Iterator and the clone modified the underlying Iterable,
the original Iterator will throw a ConcurrentModificationException.

This suggests that CloneableIterators must not be "fail-fast". It also
suggests that classes such as ArrayList that do have fail-fast Iterators
cannot be retrofitted with CloneableIterators, or they will break documented
behavior.

 

[Mike Schilling]

Even Iterators that have not modified their underlying Iterable can
throw ConcurrentModificationException if another iterator, or
anything else, modifies the Iterable.

from
<http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html>
but it applies to others, too.

So if you cloned an Iterator and the clone modified the underlying
Iterable, the original Iterator will throw a
ConcurrentModificationException.

As it should. The alternative is that the iterator silently returns
garbage.

This suggests that CloneableIterators must not be "fail-fast".

To me it suggests that a set of cloned iterators should all be used in
read-only fashion. In fact, make that part of the contract of
CloneableIterator -- that remove() and the other methods that modify
the underlying Iterable throw UnsupportedOperationException.

 

[Lew]

To me it suggests that a set of cloned iterators should all be used in
read-only fashion. In fact, make that part of the contract of
CloneableIterator -- that remove() and the other methods that modify
the underlying Iterable throw UnsupportedOperationException.

Good point, but removing remove(), et al., still precludes replacing with
CloneableIterator the Iterators for existing classes that contract to support
those methods.

 

[Mike Schilling]

Good point, but removing remove(), et al., still precludes replacing
with CloneableIterator the Iterators for existing classes that
contract to support those methods.

True. You'd need a new method to return ClonableIterators, and the
problem with adding a method to a heavily used interface like List is
that you can't.

 

[Daniele Futtorovic]

I'd even be happy, if all the standard collections in java.util had
a method, that took an apt Iterator (i.e. one belonging to that
collection), and returned a new one initially sitting on the same spot.
Appropriate collections could even return a new ListIterator
when given only a plain one.

Without further support for this assertion, I would suspect that if you
end up needing such iterators you're using a wrong data structure. Not
sure, though -- it's just that I can't recall ever having had this need.

At any rate, you could always use a class like this one:

public class CloneableIterator<E>
implements Iterator<E>, Cloneable
{
final Iterator<E>
backing
;
Node<E>
firstHead,
mainHead,
mainTail
;

public CloneableIterator(Iterator<E> it) {
backing = it;
}

public CloneableIterator(Iterable<E> it){
this( it.iterator() );
}

public boolean hasNext() {
if( mainTail == null || mainHead == mainTail ){
return backing.hasNext();
}
else{
return true;
}
}

public void remove() {
throw new UnsupportedOperationException();
}

public E next()
throws NoSuchElementException
{
if( mainTail == null || mainHead == mainTail ){
poll();
}

mainHead = mainHead.next;
return mainHead.object;
}

void poll()
throws NoSuchElementException
{
E o = backing.next(); //throws NSE
Node<E> n = new Node<E>(o);

if( mainTail != null ){
mainTail.next = n;
}

mainTail = n;

if( mainHead == null ){
mainHead = new Node<E>(null);
mainHead.next = mainTail;

firstHead = mainHead;
}
}

public Iterator<E> clone(){
return new ClonedIterator();
}

private static class Node<K> {
final K object;
Node<K> next;

public Node(K o){
object = o;
}
}

private class ClonedIterator
implements Iterator<E>
{
Node<E> myHead = CloneableIterator.this.mainHead;

public void remove() {
throw new UnsupportedOperationException();
}

public E next()
throws NoSuchElementException
{
if( myHead == null ){
if( CloneableIterator.this.firstHead == null ){
CloneableIterator.this.poll(); // throws NSE
}

myHead = CloneableIterator.this.firstHead;
}

if( myHead == CloneableIterator.this.mainTail ){
CloneableIterator.this.poll(); // throws NSE
}

myHead = myHead.next;
return myHead.object;
}

public boolean hasNext() {
if( myHead == null ){
return CloneableIterator.this.firstHead != null ||
CloneableIterator.this.backing.hasNext();
}
else if( myHead != mainTail ){
return true;
}
else{
return CloneableIterator.this.backing.hasNext();
}
}
}
}

 

[Andreas Leitgeb]

It seems I goofed in decribing a few postings upthread, and brought
this subthread completely off-track. :-(

I meant: There is no need to worry *more* about cloned
iterators, if you already can *have* multiple iterators.

Situation 1: you obtain two iterators from a collection,
and use one for remove/insert, then the other will throw
an exception (ConcurrentWhateverException)

Situation 2: you obtain one iterator from a collection,
clone it, and use one for ... exactly the same as above.

It's exactly the same thing, not less not worse. The only
difference is, that the cloned iterators would start somewhere
in the middle, without ever having to traverse the part which
they effectively skipped.

 

[Andreas Leitgeb]

Without further support for this assertion, I would suspect that if you
end up needing such iterators you're using a wrong data structure.

The only data-structure that would effectively and instantly support
de-facto cloning of iterators are those which can be O(1)-indexed.
Arrays, Vector and ArrayList come to mind. If I need something else,
my only choice now seems to be copying the element-refs in some way -
either .toArray(), or the single-linked list you contributed below.

Not sure, though -- it's just that I can't recall ever having had this need.

I for myself do recall having had that wish, to implement a subset-iterator
based on a set's iterator and cloning that. In the url I mentioned at
thread-start, someone also had such a wish, but was told a specific
workaround that seemed to have done it for him.

At any rate, you could always use a class like this one:
public class CloneableIterator<E> implements Iterator<E>, Cloneable
{
private static class Node<K> { ... }
private class ClonedIterator implements Iterator<E>
{ ... }
}

As it seems to me, a new hand-made Collection is built up from the
elements that the backend-iterator has already visited, but any of
the existing instances of CloneableIterator/ClonedIterators has not.

By building up a shadow-list, it's still nearer (though likely a
bit better) to .toArray(), than to re-create-able Iterators.