How can I reverse a Java 8 stream and generate a decrementing IntStream of values?

java, java-8, java-stream, list, sorting

Solution

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.

Problem

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?

Original source

Related problems