Idiomatic way to use for-each loop given an iterator?

Question

When the enhanced for loop (foreach loop) was added to Java, it was made to work with a target of either an array or Iterable.

for ( T item : /*T[] or Iterable<? extends T>*/ ) {
    //use item
}

That works great for Collection classes that only implement one type of iteration, and thus have a single iterator() method.

But I find myself incredibly frustrated the odd time I want to use a non-standard iterator from a Collection class. For example, I was recently trying to help somebody use a Deque as a LIFO/stack but then print the elements in FIFO order. I was forced to do this:

for (Iterator<T> it = myDeque.descendingIterator(); it.hasNext(); ) {
   T item = it.next();
   //use item
}

I lose the advantages of the for-each loop. It's not just about keystrokes. I don't like exposing the iterator if I don't have to, since it's easy to make the mistake of calling it.next() twice, etc.

Now ideally I think the for-each loop should have accepted an Iterator as well. But it doesn't. So is there an idiomatic way of using the for-each loop in these circumstances? I'd also love to hear suggestions that use common collections libraries like Guava.

The best I can come up with in absense of a helper method/class is:

for ( T item : new Iterable<T>() { public Iterator<T> iterator() { return myDeque.descendingIterator(); } } ) {
    //use item
}

Which isn't worth using.

I'd love to see Guava have something like Iterables.wrap to make this idiomatic, but didn't find anything like that. Obviously I could roll my own Iterator wrapper via a class or helper method. Any other ideas?

Edit: As a side-note, can anybody give a valid reason for why the enhanced for-loop shouldn't have been able to just accept an Iterator? It would probably go a long way to making me live with the current design.

Alcestis

note: Guava is opposed to any utility to view an Iterator as an Iterable. The Iterable returned would be an accident waiting to happen, and looping over it wouldn't really leave your code any shorter. – Defenestration

@Kevin: can you cite an example of that (feature request comments or something?) – Alcestis

Oh, @Kevin, I guess you can just cite yourself. Profile read. – Alcestis

For the record, I found this idea in the "Idea Graveyard" of Guava: code.google.com/p/guava-libraries/wiki/IdeaGraveyard. – Alcestis

For the lazy, Guava users can do ImmutableList.copyOf(Iterator) to safely convert an Iterator into an Iterable. See the above link for more on why. – Piddle

@Piddle IMHO you should really convert your comment to an answer! I think it is succinct and explicit enough. – Rodrigues

Answer 1

What I'd probably do is just make a utility class called Deques which could support this, along with other utilities if desired.

public class Deques {
  private Deques() {}

  public static <T> Iterable<T> asDescendingIterable(final Deque<T> deque) {
    return new Iterable<T>() {
      public Iterator<T> iterator() {
        return deque.descendingIterator();
      }
    }
  }
}

This is another case where it's really too bad we don't have lambdas and method references yet. In Java 8, you'll be able to write something like this given that the method reference descendingIterator() matches the signature of Iterable:

Deque<String> deque = ...
for (String s : (Iterable<String>) deque::descendingIterator) { ... }

Altheaalthee

The Java 8 approach works, with the unfortunate requirement that a cast (Iterable<String>) is necessary to provide a target type for the method reference. – Metternich

Answer 2

Why doesn't the enhanced for loop just accept an iterator?

I want to gather a few of the potential reasons from the various answers as to why the for-each loop doesn't simply accept an iterator.

1. Convenience: The for-each loop was created partly for convenience for the common operation of performing an action given each element of a collection. It has no obligation or intention of replacing the explicit use of iterators (obviously if you want to remove elements, you need an explicit reference to the iterator).
2. Readability: The for-each loop for ( Row r : table ) is meant to be extremely readable as "for each row "r" in table...". Seeing for ( Row r : table.backwardsIterator() ) breaks that readability.
3. Transparency: If an object is both an Iterable and an Iterator, what will be the behaviour? Though it's easy to make a consistent rule (e.g. Iterable before Iterator) the behaviour will be less transparent to developers. Furthermore, this will have to be checked at compile time.
4. Encapsulation/Scope: This is (in my opinion) the most important reason. The for-each loop is designed to encapsulate the Iterator and limits its scope to the loop. This makes the loop "read-only" in two ways: it doesn't expose the iterator, meaning there is nothing (easily) tangible that has its state altered by the loop, nor can you alter the state of the operand in the loop (as you can by interfacing directly with an Iterator via remove()). Passing the Iterator yourself necessarily means the Iterator is exposed, making you lose both of those "read-only" attributes of the loop.

Alcestis

It would be confusing that the for statement would appear like just a read operation but would be modifying the state of its operand. Today you might "foreach" through a list of Strings once to find the longest length, then do it again to find all Strings of that length. But if you changed that code to act on an Iterator instead and foreach still worked, you'd be majorly obscuring the fact that the code is now terribly broken. – Defenestration

@Kevin: I think that goes along with encapsulation and scope. It's not really a read operation in that you can still obtain the iterator it uses and mess with it as much as you want. The current foreach loop just makes doing that more difficult. – Alcestis

@Kevin What about an overloaded version of Iterables.reverse() which takes a Deque? – Rogatory

@Willi: If ColinD's right, Guava hasn't made an attempt to cover things added in 1.6 yet. I would expect there might be a few things to add. See also ColinD's answer. – Alcestis

It doesn't seem likely to happen soon. – Defenestration

Actually part 3 is IMHO not that easy. Because it is compile time vs. runtime. An object that looks like an Iterator at compile time can turn out to be an Iterable at runtime, and suddenly it behaves unexpectedly. – Streamliner

@Anony: That's a great point. I think the only choice would be to base it on the static type of the expression/variable, since the decision needs to be made before compilation (after compilation, there's really nothing distinguishing a for-each loop from a for-loop that explicitly uses an iterator; it's a language feature, not a bytecode feature). – Alcestis

I have been considering this, too. But even then it may be irritating, for Generics, when the type is even somewhat dynamic at compile-time. – Streamliner

Answer 3

Rather than create a descendingIterator, it would be better to write a descendingIterable() method to return a descending iterable based on a deque- which basically takes the place of your anonymous class. That seems pretty reasonable to me. As per Colin's suggestion, the iterable implementation returned by this method would call descendingIterator on the original deque each time its own iterator() method was called.

If you've only got an iterator and want to keep it that way, you'd have to write an implementation of Iterable<T> which wrapped the iterator and returned it exactly once, throwing an exception if iterator() is called more than once. That would work, but it would clearly be pretty ugly.

Servility

@JonSkeet: That's a good point about descendingIterable(), and that's kind of how you get by with Maps: you can just do for ( Entry e : myMap.entrySet() ). Unfortunately Deque is a standard library class, not my class. – Alcestis

Can you expand why you need that condition that if iterator() is called more than once it should throw an error? I'm assuming you're saying that so that if you leak references to the Iterable, you don't provide out of date iterators? – Alcestis

Agreed... you could make a utility class of your own called, say, Deques and have a method like <T> Iterable<T> asDescendingIterable(Deque<? extends T> deque). This seems most reasonable, as you get an actual correct (reusable) implementation of Iterable. I feel like Guava could probably have something like this if it was able to support Java 1.6. – Altheaalthee

@Mark: An Iterable should return a valid, fresh Iterator each time... if it can't do that, its iterator() method should not be allowed to be called more than once, since it could otherwise give out multiple references to the same Iterator. This could lead to something expecting that it was iterating over all the elements the Iterable represents while in reality the single Iterator is completely spent and has nothing to read, or worse. In general, I think it's best not to try to represent a single Iterator as an Iterable. – Altheaalthee

@ColinD: you're right, that's the other important point. Either way it's about preventing the effects of leaking a reference to the iterable. Man, it's becoming increasingly apparent (to me anyway) that they should have just designed the damned loop to accept an iterator. – Alcestis

+1 for touching on why a wrapper isn't as nice as it seems to be. – Alcestis

@ColinD: I think your first comment is the best answer so far (it differs from Jon's suggestion). Consider adding it as an answer. – Alcestis

@Mark: Colin's suggestion is what I was aiming at; I clearly didn't express it clearly enough :) – Servility

@Mark Peters: I've added it as an answer, though it's very similar to Bozho's answer... just a bit nicer syntax and doesn't expose the implementation class. – Altheaalthee

Answer 4

The idiomatic way in Java 8 (being a verbose language) is this:

for (T t : (Iterable<T>) () -> myDeque.descendingIterator()) {
  // use item
}

I.e. wrap the Iterator in an Iterable lambda. This is pretty much what you did yourself using an anonymous class, but it's a bit nicer with the lambda.

Of course, you could always just resort to using Iterator.forEachRemaining():

myDeque.descendingIterator().forEachRemaining(t -> {
  // use item
});

Remedial

Or for (T t : (Iterable<T>)myDeque::descendingIterator) { … } – Micahmicawber

Answer 5

Guava users can do ImmutableList.copyOf(Iterator) to safely convert an Iterator into an Iterable. Despite the seeming simplicity of looping over an Iterator, there are concerns that foreach hides, and the safest option is to create a stable data structure like a list.

This is also discussed in the Idea Graveyard:

The biggest concern is that Iterable is generally assumed to be able to produce multiple independent iterators. The doc doesn't say this, but the Collection doc doesn't say this, either, and yet we assume it of its iterators. We have had breakages in Google when this assumption was violated.

The simplest workaround is ImmutableList.copyOf(Iterator), which is pretty fast, safe, and provides many other advantages besides.

Piddle

Answer 6

public class DescendingIterableDequeAdapter<T> implements Iterable<T> {
    private Deque<T> original;

    public DescendingIterableDequeAdapter(Deque<T> original) {
        this.original = original;
    }

    public Iterator<T> iterator() {
         return original.descendingIterator();
    }
}

And then

for (T item : new DescendingIterableDequeAdapter(deque)) {

}

So, for each such case, you'd need a special adapter. I don't think it is theoretically possible to do what you want, because the facility has to know what iterator-returning methods exist, so that it can call them.

As for your additional question - I believe because the for-each loop was actually meant to make things shorter for general-purpose scenarios. And calling an additional method makes the syntax more verbose. It could've supported both Iterable and Iterator, but what if the object passed implemented both? (would be odd, but still possible).

Vento

Definitely works, but hardly idiomatic if I have to write a new class for each type of iterator I want to use it for. I was hoping for something that would work given an arbitrary iterator. – Alcestis

@Mark Peters - there can't be such a thing. At best it would hide all these concrete adapters behind a static utility method, which would use at least some reflection, or will have an enum to choose your desired type. – Vento

@Bozho: there can't be such a thing to return a valid, reusable Iterable, that much is true. But I just want to shove my iterator into a for loop, valid Iterable or not. – Alcestis

@Mark Peters: It's very simple to do that, so I'd recommend just making a method to do it yourself. I don't think any library, at least not a high-quality one like Guava, would put in a feature like this that encourages people to do potentially bad things. – Altheaalthee

@Vento or anybody: I haven't followed the whole closures issue closely. It would be possible to do this quite easily with a function pointer to any no-arg function that returns an Iterator. Anyone know if Project Lambda, assuming it makes it into Java 7, would support this kind of thing? – Alcestis

@Mark Peters: I actually addressed this in my answer... it should be very easy! However, Project Lambda has officially slipped to JDK 8 in 2012. – Altheaalthee

Thanks @Vento for answering the side question. Wish I could give you another +1. I worked that into an answer to try to collect a few of the potential reasons. – Alcestis

Answer 7

The Apache Commons Collections API has a class called IteratorIterable to do exactly this:

Iterator<X> iter;
for (X item : new IteratorIterable(iter)) {
    ...
}

Cunnilingus

Answer 8

Guava does of course have a solution for the reverse iterable scenario, but unfortunately you need two Steps. Iterables.reverse() takes a List as parameter, not an Iterable.

final Iterable<String> it = Arrays.asList("a", "b", "c");
for(final String item : Iterables.reverse(Lists.newArrayList(it))){
    System.out.println(item);
}

Output:

c
b
a

Lollard

descendingIterator is just used as an example. Maybe you have a Tree collection where iterator() performs a depth-first search and breadthFirstIterator() performs a BFS. – Alcestis

There could be an overloaded version of Iterables.reverse() which takes a Deque instead of a List. Would be a nice addition. – Rogatory

Guava only supports Java 1.5, but Deque is a 1.6 addition – Lollard

Answer 9

I suggest to create a helper class with factory methods that you can use like this:

import static Iter.*;

for( Element i : iter(elements) ) {
}

for( Element i : iter(o, Element.class) ) {
}

As a next step, the return type of iter() could be a fluent interface so you can do:

for( Element i : iter(elements).reverse() ) {
}

or maybe

for( Element i : reverse(elements) ) {
}

You should also have a look at op4j which solves many of these problems with a very nice API.

Desirae

How would you reverse an arbitrary Iterator or Iterable? Some don't even have an end that you could start from. – Altheaalthee

@ColinD: Why would I want to reverse an arbitrary iterator? 100% of all iterators in my code terminate eventually and 95% of them even quickly. That leaves 5% for which I need a special case but that doesn't make the code useless for the other 95% (like when some old class returns an Enumeration or a List without a generic type). – Desirae

Your methods suggest the ability to reverse any iterator, though of course I suppose you could document that it should only be used with bounded iterators. But then to actually do it, you'd have to first copy the contents of the iterator and then iterate through that copy in reverse, which seems wasteful. – Altheaalthee

@ColinD: The default Java API just doesn't offer enough information to create a reverse iterator which always works. So what I do is the next best thing. If you don't like it, use ListIterator instead. – Desirae

Answer 10

I'm not sure why people are reluctant to solve this using two separate lines of code. This avoids the need to do any casting.

Iterable<T> elements = myDeque::descendingIterator;
for (T element: elements)
{
  ...
}

This is the same answer as Lukas but easier to read.

Savannasavannah