Iterator in reverse - for reduceRight functionality

Question

Trying to implement some reduceRight functionality. For performance would be nice to iterate from right to left, without reversing everything first, and then going left to right. Normally we do:

Iteratable iterable ...;
Iterator iterator = iterable.iterator();
iterator.next();

but I am looking for something like:

Iteratable iterable ...;
Iterator iterator = iterable.reverseIterator();
iterator.next();

I see this solution: Iterating through a list in reverse order in java

The current accepted answer says that this works:

ArrayList<...> a = new ArrayList<...>();

// Add elements to list.

// Generate an iterator. Start just after the last element.
ListIterator li = a.listIterator(a.size());

// Iterate in reverse.
while(li.hasPrevious()) {
  System.out.println(li.previous());
}

Anyone know how to implement reverse iteration given only an Iterable in hand? I don't have an ArrayList or List in hand, I have an Iterable in hand. I suppose I can convert the Iterable to an ArrayList, reverse the list, then get an iterator, but that would be no fun :)

You cannot. Iterator only supports traversal in a single direction. You'd have to copy the elements to a stack and pop them. Given you are trying to achieve performance, I wouldn't do this - see if you can repexpress your reduce in the other direction. — Boris the Spider, Feb 17 '19 at 07:51
@BoristheSpider yeah that's what I figured, given the info in OP can you give best possible solution? thanks — Alexander Mills, Feb 17 '19 at 07:51
Remember, an `Iterable` can be theoretically infinite. That's why this can't be supported at the API level. You should use a data structure that supports reverse traversals. — Joe C, Feb 17 '19 at 07:55
@JoeC it's for a library so trying to support as many data types as possible by using `Iterable` — Alexander Mills, Feb 17 '19 at 08:00
https://github.com/google/guava/issues/980 if you have time, otherwise just use guava's Lists.newArrayList(iterable).reverse() — Satyendra Kumar, Feb 17 '19 at 08:06
@JoeC's point is a good one to bear in mind - both `Stream` and `Iterator` are able to be infinite; take [Guava's `Iterators.cycle`](https://google.github.io/guava/releases/15.0/api/docs/com/google/common/collect/Iterators.html#cycle(java.lang.Iterable)) for example. I would avoid exposing an API that allows for things that you cannot support. — Boris the Spider, Feb 17 '19 at 11:07

score 2 · Answer 1 · answered Feb 17 '19 at 08:03

Simple answer: not possible in a generic performant way.

The essence of iterator is to get you one direction, not both. And imagine a singlely linked list. That thing really has "only one direction"!

So the question how you can reverse an iterable thingy really requires you to look at the exact implementation. Without that possibility, you have to use an intermediate data structure to fetch all entries before reversing.

score 1 · Answer 2 · answered Feb 17 '19 at 08:01

You'll have to iterate over the original Iterator once in order to construct a reversed Iterator (assuming your original Iterator is finite).

For example:

static <T> Iterator<T> getReversedIterator(Iterable<T> iterable) {
    Iterator<T> iter = iterable.iterator();
    List<T> rev = new ArrayList<>();
    while (iter.hasNext()) {
        rev.add (0, iter.next());
    }
    return rev.iterator();
}

score 1 · Answer 3 · answered Feb 17 '19 at 08:05

1

If you have an Iterable in hand, as you wrote in your question, then someone provided you with it. I would suggest asking the provider to supply an Iterable that supports reverse iteration.

answered Feb 17 '19 at 08:05

Abra

19,142
7
29
41

That or just implement reduce and don't implement reduceRight and expect them to have the list in the right order. But I think it's nice to do the work for the user of the lib. – Alexander Mills Feb 17 '19 at 08:07

score 0 · Answer 4 · answered Sep 07 '21 at 14:39

Here is how I do it. If you are using a for loop, this will cause the original Iterator to be completely consumed and a new linked list to be created before the first iteration. This can obviously be an issue with large iterables, but it is predictable and easy to use. It has the advantage of working with anything that implements Iterable vs. some solutions that only work with specific types.

import java.util.Iterator;

public class Reversible<E> implements Iterable<E> {
    private Iterable<E> source;

    public Reversible(Iterable<E> source) {
        this.source = source;
    }

    public Iterator<E> iterator() {
        return new Reverserator<>(source.iterator());
    }

    public static class Reverserator<E> implements Iterator<E> {
        private Entry<E> next = null;

        private Reverserator(Iterator<E> source) {
            while (source.hasNext()) {
                next = new Entry<>(source.next(), next);
            }
        }

        public boolean hasNext() {
            return next != null;
        }

        public E next() {
            Entry<E> curr = next;
            next = curr.next;
            return curr.obj;
        }

        private static class Entry<E> {
            private E obj;
            private Entry<E> next;

            private Entry(E obj, Entry<E> next) {
                this.obj = obj;
                this.next = next;
            }
        }
    }
}

It is quite simple to use:

List<String> names = new ArrayList<>();
names.add("George");
names.add("Fred");
names.add("Harry");
for (String name:new Reversible<>(names)) {
    System.out.println(name);
}

Returns:

Harry
Fred
George

Iterator in reverse - for reduceRight functionality

4 Answers4