22

Is there a sane way to get an ordered stream from a list (array list specifically, but it shouldn't matter) that streams elements in reverse of how they are in the original list?

I'm looking for a solution that doesn't involve buffering data in anything (collector, another list, array, etc, because they copy the container which is wasteful), or uses Collections.reverse (because it modifies the list).

So far, the cleanest ways that I see here is to implement my own version of Spliterator that's ORDERED and advances through the list in reverse, or implement an Iterator that iterates in reverse, and use Spliterators.spliteratorUnknownSize(iterator,ORDERED) on it.

Note this question is different from Java 8 stream reverse order : that other question asks on how to reverse a stream (which is impossible in general case), and answers offer to reverse the source somehow (which I don't want to do), and then stream that reversed source. The cost of reversing the source is O(N), and I want to avoid it at all if possible.

Improve this question
1

6 Answers 6

Reset to default
23

If your List is a random access list, you may simply use

int num=list.size()-1;
IntStream.rangeClosed(0, num).mapToObj(i->list.get(num-i))

to create a Stream which has the characteristics ORDERED | SIZED | SUBSIZED and offers full splitting support.

For a non-random access list like LinkedList it would be a performance disaster, however, who uses LinkedList anyway?

You may also check via list instanceofRandomAccess first…

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Heh, I should have thought of this first. +1. I guess I was too enamored with the idea of writing a reversing spliterator.
Or IntStream.rangeClosed(1, list.size()).mapToObj(i -> list.get(list.size() - i)).
8

NOTE: If you have an ArrayList or other list that allows random-access retrieval by index (get(i)) then Holger's approach is preferable. The approach below is only necessary if you have a data structure that allows reverse traversal but not indexed access.

Unfortunately there doesn't seem to be a really simple (i.e., a one-liner) way to do this. But getting a reversed stream using AbstractSpliterator isn't too difficult, given that List already has the ability to iterate in reverse. Here's a utility method to do that:

static <T> Stream<T> reversedStream(List<? extends T> input) {
    ListIterator<? extends T> li = input.listIterator(input.size());
    return StreamSupport.stream(
        new Spliterators.AbstractSpliterator<T>(input.size(), Spliterator.ORDERED) {
            @Override public boolean tryAdvance(Consumer<? super T> action) {
                if (li.hasPrevious()) {
                    action.accept(li.previous());
                    return true;
                } else {
                    return false;
                }
            }
        },
        false);
}

(I suppose the Spliterator could be SIZED, but that's mostly pointless because this is an unsplittable spliterator.)

As it stands, this can afford a limited degree of parallelism, as AbstractSpliterator will call tryAdvance multiple times and batch up work to hand off to fork-join tasks. But it's not as efficient as being able to split.

If parallel efficiency is a great concern, one could write a spliterator that can actually split, where the splits are traversed in reverse order.

Improve this answer

6 Comments

So, using AbstractSpliterator is somehow better than IteratorSpliterator?
I don’t think that SIZED is pointless. SUBSIZED would be pointless though.
@PawelVeselov I think that AbstractSpliterator is a bit easier than writing your own iterator. But if you already have an iterator, then using Spliterators.spliteratorUnknownSize(iterator, ...) -- which uses IteratorSpliterator underneath -- is certainly easier to code.
@Holger Yes, SIZED might allow the stream to do better buffering, but I'm not sure. Well, in JDK 9 it would allow count() to short-circuit.
@PawelVeselov (I think you mean AbstractSpliterator?) There are some tradeoffs. The IteratorSpliterator doesn't need a HoldingConsumer but it does require an extra method call (hasNext+next) for each element. But that might be offset by the Consumer.accept call... hmmm. Well I think the only real way to find out is to measure. (And yes, it's been a while!) :-)
|
7

Starting with Java 21, the reversed() method can be used to return a reversed view on the list, which can then be streamed over:

Stream<Object> reversedStream = list.reversed().stream();

As requested, this doesn't buffer or copy the data, as this is merely a reversed view of the original list.

Improve this answer

Comments

5

Google's Guava library provides a reverse view of a list (Lists#reverse(List)). There's a ReverseListIterator in the Apache Commons Collection library, too.

Improve this answer

Comments

5

I found this solution quite recently.

public <T> Stream<T> toReverseStream(List<T> list) {
    ListIterator<T> listIterator = list.listIterator(list.size());
    return Stream.generate(listIterator::previous)
            .limit(list.size());
}
Improve this answer

1 Comment

Not a good idea. Stream.generate(…) creates an unordered stream. Further, a Stream stage should not rely on the effect of a subsequent stage. In other words, there is no guaranty that the supplier is only evaluated as often as specified by the limit. It may happen to do the desired thing in sequential contexts but may fail with parallel execution in practice. But on the formal level, it’s wrong in either case.
2

I tend to like @teppic's answer of using a third-party library to do this. However, it's an interesting exercise to try to come up with a solution using only the Java 8 APIs. Delegating to a ListIterator is the cleanest thing I could come up with, but it's not really much cleaner than implementing your own Iterator from scratch.

public static void main(String[] args){
    List<String> l = Arrays.asList("first", "second", "third");

    StreamSupport.stream(Spliterators.spliterator(revit(l), l.size(), 0), false)
                 .forEachOrdered(System.out::println);
}

private static final <T> Iterator<T> revit(List<T> l){
    ListIterator<T> li = l.listIterator(l.size());

    return new Iterator<T>(){
        @Override
        public boolean hasNext(){
            return li.hasPrevious();
        }

        @Override
        public T next(){
            return li.previous();
        }
    };
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.