Java 8 stream reverse order

Question

General question: What's the proper way to reverse a stream? Assuming that we don't know what type of elements that stream consists of, what's the generic way to reverse any stream?

Specific question:

IntStream provides range method to generate Integers in specific range IntStream.range(-range, 0), now that I want to reverse it switching range from 0 to negative won't work, also I can't use Integer::compare

List<Integer> list = Arrays.asList(1,2,3,4);
list.stream().sorted(Integer::compare).forEach(System.out::println);

with IntStream I'll get this compiler error

Error:(191, 0) ajc: The method sorted() in the type IntStream is not applicable for the arguments (Integer::compare)

what am I missing here?

Solution 1

For the specific question of generating a reverse IntStream, try something like this:

static IntStream revRange(int from, int to) {
    return IntStream.range(from, to)
                    .map(i -> to - i + from - 1);
}

This avoids boxing and sorting.

For the general question of how to reverse a stream of any type, I don't know of there's a "proper" way. There are a couple ways I can think of. Both end up storing the stream elements. I don't know of a way to reverse a stream without storing the elements.

This first way stores the elements into an array and reads them out to a stream in reverse order. Note that since we don't know the runtime type of the stream elements, we can't type the array properly, requiring an unchecked cast.

@SuppressWarnings("unchecked")
static <T> Stream<T> reverse(Stream<T> input) {
    Object[] temp = input.toArray();
    return (Stream<T>) IntStream.range(0, temp.length)
                                .mapToObj(i -> temp[temp.length - i - 1]);
}

Another technique uses collectors to accumulate the items into a reversed list. This does lots of insertions at the front of ArrayList objects, so there's lots of copying going on.

Stream<T> input = ... ;
List<T> output =
    input.collect(ArrayList::new,
                  (list, e) -> list.add(0, e),
                  (list1, list2) -> list1.addAll(0, list2));

It's probably possible to write a much more efficient reversing collector using some kind of customized data structure.

UPDATE 2016-01-29

Since this question has gotten a bit of attention recently, I figure I should update my answer to solve the problem with inserting at the front of ArrayList. This will be horribly inefficient with a large number of elements, requiring O(N^2) copying.

It's preferable to use an ArrayDeque instead, which efficiently supports insertion at the front. A small wrinkle is that we can't use the three-arg form of Stream.collect(); it requires the contents of the second arg be merged into the first arg, and there's no "add-all-at-front" bulk operation on Deque. Instead, we use addAll() to append the contents of the first arg to the end of the second, and then we return the second. This requires using the Collector.of() factory method.

The complete code is this:

Deque<String> output =
    input.collect(Collector.of(
        ArrayDeque::new,
        (deq, t) -> deq.addFirst(t),
        (d1, d2) -> { d2.addAll(d1); return d2; }));

The result is a Deque instead of a List, but that shouldn't be much of an issue, as it can easily be iterated or streamed in the now-reversed order.

Solution 2

Elegant solution

List<Integer> list = Arrays.asList(1,2,3,4);
list.stream()
    .sorted(Collections.reverseOrder()) // Method on Stream<Integer>
    .forEach(System.out::println);

Solution 3

General Question:

Stream does not store any elements.

So iterating elements in the reverse order is not possible without storing the elements in some intermediate collection.

Stream.of("1", "2", "20", "3")
      .collect(Collectors.toCollection(ArrayDeque::new)) // or LinkedList
      .descendingIterator()
      .forEachRemaining(System.out::println);

Update: Changed LinkedList to ArrayDeque (better) see here for details

Prints:

3

20

2

1

By the way, using sort method is not correct as it sorts, NOT reverses (assuming stream may have unordered elements)

Specific Question:

I found this simple, easier and intuitive(Copied @Holger comment)

IntStream.iterate(to - 1, i -> i - 1).limit(to - from)

Solution 4

Many of the solutions here sort or reverse the IntStream, but that unnecessarily requires intermediate storage. Stuart Marks's solution is the way to go:

static IntStream revRange(int from, int to) {
    return IntStream.range(from, to).map(i -> to - i + from - 1);
}

It correctly handles overflow as well, passing this test:

@Test
public void testRevRange() {
    assertArrayEquals(revRange(0, 5).toArray(), new int[]{4, 3, 2, 1, 0});
    assertArrayEquals(revRange(-5, 0).toArray(), new int[]{-1, -2, -3, -4, -5});
    assertArrayEquals(revRange(1, 4).toArray(), new int[]{3, 2, 1});
    assertArrayEquals(revRange(0, 0).toArray(), new int[0]);
    assertArrayEquals(revRange(0, -1).toArray(), new int[0]);
    assertArrayEquals(revRange(MIN_VALUE, MIN_VALUE).toArray(), new int[0]);
    assertArrayEquals(revRange(MAX_VALUE, MAX_VALUE).toArray(), new int[0]);
    assertArrayEquals(revRange(MIN_VALUE, MIN_VALUE + 1).toArray(), new int[]{MIN_VALUE});
    assertArrayEquals(revRange(MAX_VALUE - 1, MAX_VALUE).toArray(), new int[]{MAX_VALUE - 1});
}

Solution 5

without external lib...

import java.util.List;
import java.util.Collections;
import java.util.stream.Collector;

public class MyCollectors {

    public static <T> Collector<T, ?, List<T>> toListReversed() {
        return Collectors.collectingAndThen(Collectors.toList(), l -> {
            Collections.reverse(l);
            return l;
        });
    }

}

View more solutions

Comments

[fge]

An IntStream has no .sorted(Comparator) method; you have to go through a Stream<Integer> first and reverse there before yielding an IntStream

[vach]

Ok, I've found it, you need to use .boxed() and then .sorted()

[Stuart Marks]

To generate an IntStream.range(0, n) in reverse order, do something like map(i -> n - i - 1). No need to do boxing and sorting.

[chiccodoro]

Your gerneral question and your specific question read like two completele different questions to me. The general speaks of reversing the stream, while the specific speaks of ordering numbers in descending order. If the stream produces the numbers in an unordered manner like 1, 3, 2, what is your expected outcome? Do you want the reversed stream like 2, 3, 1 or the sorted stream like 3, 2, 1?

[assylias]

You can't reverse a stream in general - for example a stream may be inifinite.

[chiccodoro]

To "reverse the stream" you will first need to collect all items. You might try to use a stack because its LIFO nature will reverse the items after pushing and pulling back, something like: stream.collect(Collectors.toCollection(Stack::new)).stream()‌​. (As assylias commented, you can't do that on an infinite stream. But that holds for sorting, too.

[vach]

Yes I've come up with this, but I tought there will be a "cleaner" way to do that. I think you can put it as an answer, and guys above are right my questions are different indeed, one about reversing the other one about ordering. Anyway I think others who might search and navigate to this question will looking for reversing part of this discussion. So please post it as an answer.

[Manu Manjunath]

You may want to rephrase the question as "Iterate a collection in reverse order in Java 8 way". Answer may be beyond streams. Below answer from @venkata-raju solves the problem, but takes extra space. I'm still waiting to see a good answer on this question.

[JAAAY]

@assylias This doesn't make sense. For the same reason there is no point on collecting a stream or using loops in general (cause we may run into the halting problem), but we can do both.

[bjmi]

IntStream.rangeClosed(-n, 0).map(i -> -i) will produce elements in reversed order i.e. n, n-1, n-2, ... , 0.

[chiccodoro]

This is only an answer to your "specific question" but not to your "general question".

[Holger]

Collections.reverseOrder() exists since Java 1.2 and works with Integer…

[Holger]

Alternatively: IntStream.iterate(to-1, i->i-1).limit(to-from)

[Lii]

Some stream operation, such as sorted and distinct actually store an intermediate result. See the package API docs for some information about that.

[vach]

Nice didnt know about this project

[John McClean]

cyclops now also comes with Spliterators for efficient Stream reversal (currently for Ranges, arrays and Lists). Creating cyclops SequenceM Stream extension with SequenceM.of, SequenceM.range or SequenceM.fromList will automatically take advantage of efficiently reversible spliterators.

[Venkata Raju]

@Lii I see No storage in the same page. Even it stores we can't get access to that storage (so No storage is fine i guess)

[Tagir Valeev]

You violate the contract of Comparator. As a result nobody can guarantee you that this "trick" will work in any future Java version with any sorting algorithm. The same trick does not work for parallel stream, for example, as parallel sorting algorithm uses Comparator in different way. For sequential sort it works purely by chance. I would not recommend anybody to use this solution.

[Tagir Valeev]

Also it doesn't work when you set System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

[parmeshwor11]

I thought it was about just printing things in reverse order not in sorted order (ie. descending order), and it works with parallel stream too : public static <T> void reverseHelper(List<T> li){ li.parallelStream() .sorted((x,y)->-1) .collect(Collectors.toList()) .forEach(System.out::println); }

[Tagir Valeev]

Try reverseHelper(IntStream.range(0, 8193).boxed().collect(Collectors.toList())) (result may depend on number of cores though).

[Manu Manjunath]

Good answer. But since extra space is used, it many not be a great idea for programmers to use your approach on very large collection.

[vach]

awesome and simple. Is this from some opensource utilty? (the Estreams thing) or some piece of your code?

[Brandon]

Thanks! Unfortunately, I didn't intend to leak the Estreams name (I'm going to remove it from the post). It's one of our company's internal utility classes, which we use to supplement java.util.stream.Stream's static methods.

[Holger]

Okay…“awesome and simple”… Is there any case that this solution handles, which Stuart Marks’ even simpler solution didn’t already handle more than one and a half year ago?

[Brandon]

I just tested his solution with my test method above; it passes. I was unnecessarily avoiding overflow instead of embracing it as he did. I agree that his is better. I'll edit mine to reflect that.

[Brandon]

I encourage @vach to accept his instead of mine. Once my suggested edit of his post is accepted, I'll delete my answer altogether.

[Brandon]

@Holger Unfortunately, that solution doesn't handle overflow correctly.

[Tagir Valeev]

@vach, you may use by StreamEx specifying step: IntStreamEx.rangeClosed(from-1, to, -1)

[Holger]

@Brandon Mintern: indeed, you would have to use .limit(endExcl-(long)startIncl) instead, but for such large streams, it is very discouraged anyway as it’s much less efficient than the range based solution. At the time I wrote the comment, I wasn’t aware about the efficiency difference.

[vach]

@TagirValeev thanks, i've seen this lib few places, on habrahabr also, i'm gonna check it out for sure, seems like a good tool

[Jochen Bedersdorfer]

This is sorting in reverse order, not reverting a list.

[Krzysztof Wolny]

It is elegant but not fully working as it seems as elements of the list are required to be Comparable...

[Beezer]

I like the simplicity of the solution from an understandability perspective and leveraging an existing method on an existing data structure...the solution previous with a map implementation is harder to understand but for sure Manu is right, for large collections I would not use this intuitive, and would opt for the map one above.

[neXus]

What about IntStream.range(-to, -from).map(i -> -i-1) or IntStream.rangeClosed(-to, -from).map(i -> -i)?

[Brandon]

@neXus: Both of your proposals fail on the second to last test above: assertArrayEquals(revRange(MIN_VALUE, MIN_VALUE + 1).toArray(), new int[]{MIN_VALUE});.

[Dillon Ryan Redding]

That's assuming we want elements to be sorted in reverse order. The question is about reversing the order of a stream.

[andrebrait]

It's worth adding that Stream.generate() generates in infinite stream, so the call to limit() is very important here.

[Cubic]

This is one of the few correct answers here. Most of the other ones don't actually reverse the stream, they try to avoid doing it somehow (which only works under peculiar sets of circumstances under which you normally wouldn't need to reverse in the first place). If you try to reverse a stream that doesn't fit into memory you're doing it wrong anyway. Dump it into a DB and get a reversed stream using regular SQL.

[wilmol]

This doesn't reverse the stream. It sorts the stream in reverse order. So if you had Stream.of(1,3,2) the result would be Stream.of(3,2,1) NOT Stream.of(2,3,1)

[vitrums]

I like this solution a lot. Most answers split into two categories: (1) Reverse the collection and .stream() it, (2) Appeal to custom collectors. Both are absolutely unnecessary. Otherwise, it would've testified about some serious language expressiveness issue in JDK 8 itself. And your answer proves the opposite :)

[Dávid Leblay]

@KrzysztofWolny you can pass a comparator function to reverseOrder(), so that shouldn't be too much of a bother

[yankee]

(a, b) -> -1 breaks the contract for Comparator. Whether this works depends on the implementation of the sort algorithm. The next release of the JVM might break this. Actually I can already break this reproduciblly on my machine using IntStream.range(0, 10000).parallel().boxed().sorted((a, b) -> -1).forEachOrdered(System.out::println);

[luke]

@yankee Yes you are right. It breaks Comparator contract and is kind of misuse of Comparator. It works fine for single thread, but even if you don't use .parallel() you can't rely on it, because you don't know how virtual machine will run this and you don't know which sorting algorithm will be used (maybe even sorting algorithm working on single thread might break with this implementation). Thank you for your comment. I will revise my answer in my free time.

[luke]

I revised my answer according to yankee comment. Now the answer should be correct.

[greybeard]

Or IntStream.rangeClosed(1, to - from).map(i -> to-i) (see bjmi's comment, too).

[greybeard]

(see Adrian's May '19 answer, too.)