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 typeIntStream
is not applicable for the arguments (Integer::compare
)
what am I missing here?
This question is related to
java
list
sorting
java-8
java-stream
Based on @stuart-marks's answer, but without casting, function returning stream of list elements starting from end:
public static <T> Stream<T> reversedStream(List<T> tList) {
final int size = tList.size();
return IntStream.range(0, size)
.mapToObj(i -> tList.get(size - 1 - i));
}
// usage
reversedStream(list).forEach(System.out::println);
One could write a collector that collects elements in reversed order:
public static <T> Collector<T, ?, Stream<T>> reversed() {
return Collectors.collectingAndThen(Collectors.toList(), list -> {
Collections.reverse(list);
return list.stream();
});
}
And use it like this:
Stream.of(1, 2, 3, 4, 5).collect(reversed()).forEach(System.out::println);
Original answer (contains a bug - it does not work correctly for parallel streams):
A general purpose stream reverse method could look like:
public static <T> Stream<T> reverse(Stream<T> stream) {
LinkedList<T> stack = new LinkedList<>();
stream.forEach(stack::push);
return stack.stream();
}
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});
}
Elegant solution
List<Integer> list = Arrays.asList(1,2,3,4);
list.stream()
.boxed() // Converts Intstream to Stream<Integer>
.sorted(Collections.reverseOrder()) // Method on Stream<Integer>
.forEach(System.out::println);
I would suggest using jOO?, it's a great library that adds lots of useful functionality to Java 8 streams and lambdas.
You can then do the following:
List<Integer> list = Arrays.asList(1,2,3,4);
Seq.seq(list).reverse().forEach(System.out::println)
Simple as that. It's a pretty lightweight library, and well worth adding to any Java 8 project.
For reference I was looking at the same problem, I wanted to join the string value of stream elements in the reverse order.
itemList = { last, middle, first } => first,middle,last
I started to use an intermediate collection with collectingAndThen
from comonad or the ArrayDeque
collector of Stuart Marks, although I wasn't happy with intermediate collection, and streaming again
itemList.stream()
.map(TheObject::toString)
.collect(Collectors.collectingAndThen(Collectors.toList(),
strings -> {
Collections.reverse(strings);
return strings;
}))
.stream()
.collect(Collector.joining());
So I iterated over Stuart Marks answer that was using the Collector.of
factory, that has the interesting finisher lambda.
itemList.stream()
.collect(Collector.of(StringBuilder::new,
(sb, o) -> sb.insert(0, o),
(r1, r2) -> { r1.insert(0, r2); return r1; },
StringBuilder::toString));
Since in this case the stream is not parallel, the combiner is not relevant that much, I'm using insert
anyway for the sake of code consistency but it does not matter as it would depend of which stringbuilder is built first.
I looked at the StringJoiner, however it does not have an insert
method.
Answering specific question of reversing with IntStream, below worked for me:
IntStream.range(0, 10)
.map(x -> x * -1)
.sorted()
.map(Math::abs)
.forEach(System.out::println);
the simplest solution is using List::listIterator
and Stream::generate
List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
ListIterator<Integer> listIterator = list.listIterator(list.size());
Stream.generate(listIterator::previous)
.limit(list.size())
.forEach(System.out::println);
This method works with any Stream and is Java 8 compliant:
Stream<Integer> myStream = Stream.of(1, 2, 3, 4, 5);
myStream.reduce(Stream.empty(),
(Stream<Integer> a, Integer b) -> Stream.concat(Stream.of(b), a),
(a, b) -> Stream.concat(b, a))
.forEach(System.out::println);
In all this I don't see the answer I would go to first.
This isn't exactly a direct answer to the question, but it's a potential solution to the problem.
Just build the list backwards in the first place. If you can, use a LinkedList instead of an ArrayList and when you add items use "Push" instead of add. The list will be built in the reverse order and will then stream correctly without any manipulation.
This won't fit cases where you are dealing with primitive arrays or lists that are already used in various ways but does work well in a surprising number of cases.
The most generic and the easiest way to reverse a list will be :
public static <T> void reverseHelper(List<T> li){
li.stream()
.sorted((x,y)-> -1)
.collect(Collectors.toList())
.forEach(System.out::println);
}
You could define your own collector that collects the elements in reverse order:
public static <T> Collector<T, List<T>, List<T>> inReverse() {
return Collector.of(
ArrayList::new,
(l, t) -> l.add(t),
(l, r) -> {l.addAll(r); return l;},
Lists::<T>reverse);
}
And use it like:
stream.collect(inReverse()).forEach(t -> ...)
I use an ArrayList in forward order to efficiently insert collect the items (at the end of the list), and Guava Lists.reverse to efficiently give a reversed view of the list without making another copy of it.
Here are some test cases for the custom collector:
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.*;
import java.util.ArrayList;
import java.util.List;
import java.util.function.BiConsumer;
import java.util.function.BinaryOperator;
import java.util.function.Function;
import java.util.function.Supplier;
import java.util.stream.Collector;
import org.hamcrest.Matchers;
import org.junit.Test;
import com.google.common.collect.Lists;
public class TestReverseCollector {
private final Object t1 = new Object();
private final Object t2 = new Object();
private final Object t3 = new Object();
private final Object t4 = new Object();
private final Collector<Object, List<Object>, List<Object>> inReverse = inReverse();
private final Supplier<List<Object>> supplier = inReverse.supplier();
private final BiConsumer<List<Object>, Object> accumulator = inReverse.accumulator();
private final Function<List<Object>, List<Object>> finisher = inReverse.finisher();
private final BinaryOperator<List<Object>> combiner = inReverse.combiner();
@Test public void associative() {
final List<Object> a1 = supplier.get();
accumulator.accept(a1, t1);
accumulator.accept(a1, t2);
final List<Object> r1 = finisher.apply(a1);
final List<Object> a2 = supplier.get();
accumulator.accept(a2, t1);
final List<Object> a3 = supplier.get();
accumulator.accept(a3, t2);
final List<Object> r2 = finisher.apply(combiner.apply(a2, a3));
assertThat(r1, Matchers.equalTo(r2));
}
@Test public void identity() {
final List<Object> a1 = supplier.get();
accumulator.accept(a1, t1);
accumulator.accept(a1, t2);
final List<Object> r1 = finisher.apply(a1);
final List<Object> a2 = supplier.get();
accumulator.accept(a2, t1);
accumulator.accept(a2, t2);
final List<Object> r2 = finisher.apply(combiner.apply(a2, supplier.get()));
assertThat(r1, equalTo(r2));
}
@Test public void reversing() throws Exception {
final List<Object> a2 = supplier.get();
accumulator.accept(a2, t1);
accumulator.accept(a2, t2);
final List<Object> a3 = supplier.get();
accumulator.accept(a3, t3);
accumulator.accept(a3, t4);
final List<Object> r2 = finisher.apply(combiner.apply(a2, a3));
assertThat(r2, contains(t4, t3, t2, t1));
}
public static <T> Collector<T, List<T>, List<T>> inReverse() {
return Collector.of(
ArrayList::new,
(l, t) -> l.add(t),
(l, r) -> {l.addAll(r); return l;},
Lists::<T>reverse);
}
}
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)
How NOT to do it:
.sorted(Comparator.reverseOrder())
or .sorted(Collections.reverseOrder())
, because it will just sort elements in the descending order.[1, 4, 2, 5, 3]
[5, 4, 3, 2, 1]
["A", "D", "B", "E", "C"]
[E, D, C, B, A]
.sorted((a, b) -> -1)
(explanation at the end)The easiest way to do it properly:
List<Integer> list = Arrays.asList(1, 4, 2, 5, 3);
Collections.reverse(list);
System.out.println(list);
Output:
[3, 5, 2, 4, 1]
The same for String
:
List<String> stringList = Arrays.asList("A", "D", "B", "E", "C");
Collections.reverse(stringList);
System.out.println(stringList);
Output:
[C, E, B, D, A]
Don't use .sorted((a, b) -> -1)
!
It breaks comparator contract and might work only for some cases ie. only on single thread but not in parallel.
yankee explanation:
(a, b) -> -1
breaks the contract forComparator
. 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 usingIntStream.range(0, 10000).parallel().boxed().sorted((a, b) -> -1).forEachOrdered(System.out::println);
//Don't use this!!!
List<Integer> list = Arrays.asList(1, 4, 2, 5, 3);
List<Integer> reversedList = list.stream()
.sorted((a, b) -> -1)
.collect(Collectors.toList());
System.out.println(reversedList);
Output in positive case:
[3, 5, 2, 4, 1]
Possible output in parallel stream or with other JVM implementation:
[4, 1, 2, 3, 5]
The same for String
:
//Don't use this!!!
List<String> stringList = Arrays.asList("A", "D", "B", "E", "C");
List<String> reversedStringList = stringList.stream()
.sorted((a, b) -> -1)
.collect(Collectors.toList());
System.out.println(reversedStringList);
Output in positive case:
[C, E, B, D, A]
Possible output in parallel stream or with other JVM implementation:
[A, E, B, D, C]
List newStream = list.stream().sorted(Collections.reverseOrder()).collect(Collectors.toList());
newStream.forEach(System.out::println);
If implemented Comparable<T>
(ex. Integer
, String
, Date
), you can do it using Comparator.reverseOrder()
.
List<Integer> list = Arrays.asList(1, 2, 3, 4);
list.stream()
.sorted(Comparator.reverseOrder())
.forEach(System.out::println);
Java 8 way to do this:
List<Integer> list = Arrays.asList(1,2,3,4);
Comparator<Integer> comparator = Integer::compare;
list.stream().sorted(comparator.reversed()).forEach(System.out::println);
Not purely Java8 but if you use guava's Lists.reverse() method in conjunction, you can easily achieve this:
List<Integer> list = Arrays.asList(1,2,3,4);
Lists.reverse(list).stream().forEach(System.out::println);
ArrayDeque
are faster in the stack than a Stack or LinkedList. "push()" inserts elements at the front of the Deque
protected <T> Stream<T> reverse(Stream<T> stream) {
ArrayDeque<T> stack = new ArrayDeque<>();
stream.forEach(stack::push);
return stack.stream();
}
Reversing string or any Array
(Stream.of("abcdefghijklm 1234567".split("")).collect(Collectors.collectingAndThen(Collectors.toList(),list -> {Collections.reverse(list);return list;}))).stream().forEach(System.out::println);
split can be modified based on the delimiter or space
How about reversing the Collection backing the stream prior?
import java.util.Collections;
import java.util.List;
public void reverseTest(List<Integer> sampleCollection) {
Collections.reverse(sampleCollection); // remember this reverses the elements in the list, so if you want the original input collection to remain untouched clone it first.
sampleCollection.stream().forEach(item -> {
// you op here
});
}
This is how I do it.
I don't like the idea of creating a new collection and reverse iterating it.
The IntStream#map idea is pretty neat, but I prefer the IntStream#iterate method, for I think the idea of a countdown to Zero better expressed with the iterate method and easier to understand in terms of walking the array from back to front.
import static java.lang.Math.max;
private static final double EXACT_MATCH = 0d;
public static IntStream reverseStream(final int[] array) {
return countdownFrom(array.length - 1).map(index -> array[index]);
}
public static DoubleStream reverseStream(final double[] array) {
return countdownFrom(array.length - 1).mapToDouble(index -> array[index]);
}
public static <T> Stream<T> reverseStream(final T[] array) {
return countdownFrom(array.length - 1).mapToObj(index -> array[index]);
}
public static IntStream countdownFrom(final int top) {
return IntStream.iterate(top, t -> t - 1).limit(max(0, (long) top + 1));
}
Here are some tests to prove it works:
import static java.lang.Integer.MAX_VALUE;
import static org.junit.Assert.*;
@Test
public void testReverseStream_emptyArrayCreatesEmptyStream() {
Assert.assertEquals(0, reverseStream(new double[0]).count());
}
@Test
public void testReverseStream_singleElementCreatesSingleElementStream() {
Assert.assertEquals(1, reverseStream(new double[1]).count());
final double[] singleElementArray = new double[] { 123.4 };
assertArrayEquals(singleElementArray, reverseStream(singleElementArray).toArray(), EXACT_MATCH);
}
@Test
public void testReverseStream_multipleElementsAreStreamedInReversedOrder() {
final double[] arr = new double[] { 1d, 2d, 3d };
final double[] revArr = new double[] { 3d, 2d, 1d };
Assert.assertEquals(arr.length, reverseStream(arr).count());
Assert.assertArrayEquals(revArr, reverseStream(arr).toArray(), EXACT_MATCH);
}
@Test
public void testCountdownFrom_returnsAllElementsFromTopToZeroInReverseOrder() {
assertArrayEquals(new int[] { 4, 3, 2, 1, 0 }, countdownFrom(4).toArray());
}
@Test
public void testCountdownFrom_countingDownStartingWithZeroOutputsTheNumberZero() {
assertArrayEquals(new int[] { 0 }, countdownFrom(0).toArray());
}
@Test
public void testCountdownFrom_doesNotChokeOnIntegerMaxValue() {
assertEquals(true, countdownFrom(MAX_VALUE).anyMatch(x -> x == MAX_VALUE));
}
@Test
public void testCountdownFrom_givesZeroLengthCountForNegativeValues() {
assertArrayEquals(new int[0], countdownFrom(-1).toArray());
assertArrayEquals(new int[0], countdownFrom(-4).toArray());
}
Simplest way (simple collect - supports parallel streams):
public static <T> Stream<T> reverse(Stream<T> stream) {
return stream
.collect(Collector.of(
() -> new ArrayDeque<T>(),
ArrayDeque::addFirst,
(q1, q2) -> { q2.addAll(q1); return q2; })
)
.stream();
}
Advanced way (supports parallel streams in an ongoing way):
public static <T> Stream<T> reverse(Stream<T> stream) {
Objects.requireNonNull(stream, "stream");
class ReverseSpliterator implements Spliterator<T> {
private Spliterator<T> spliterator;
private final Deque<T> deque = new ArrayDeque<>();
private ReverseSpliterator(Spliterator<T> spliterator) {
this.spliterator = spliterator;
}
@Override
@SuppressWarnings({"StatementWithEmptyBody"})
public boolean tryAdvance(Consumer<? super T> action) {
while(spliterator.tryAdvance(deque::addFirst));
if(!deque.isEmpty()) {
action.accept(deque.remove());
return true;
}
return false;
}
@Override
public Spliterator<T> trySplit() {
// After traveling started the spliterator don't contain elements!
Spliterator<T> prev = spliterator.trySplit();
if(prev == null) {
return null;
}
Spliterator<T> me = spliterator;
spliterator = prev;
return new ReverseSpliterator(me);
}
@Override
public long estimateSize() {
return spliterator.estimateSize();
}
@Override
public int characteristics() {
return spliterator.characteristics();
}
@Override
public Comparator<? super T> getComparator() {
Comparator<? super T> comparator = spliterator.getComparator();
return (comparator != null) ? comparator.reversed() : null;
}
@Override
public void forEachRemaining(Consumer<? super T> action) {
// Ensure that tryAdvance is called at least once
if(!deque.isEmpty() || tryAdvance(action)) {
deque.forEach(action);
}
}
}
return StreamSupport.stream(new ReverseSpliterator(stream.spliterator()), stream.isParallel());
}
Note you can quickly extends to other type of streams (IntStream, ...).
Testing:
// Use parallel if you wish only
revert(Stream.of("One", "Two", "Three", "Four", "Five", "Six").parallel())
.forEachOrdered(System.out::println);
Results:
Six
Five
Four
Three
Two
One
Additional notes: The simplest way
it isn't so useful when used with other stream operations (the collect join breaks the parallelism). The advance way
doesn't have that issue, and it keeps also the initial characteristics of the stream, for example SORTED
, and so, it's the way to go to use with other stream operations after the reverse.
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;
});
}
}
Here's the solution I've come up with:
private static final Comparator<Integer> BY_ASCENDING_ORDER = Integer::compare;
private static final Comparator<Integer> BY_DESCENDING_ORDER = BY_ASCENDING_ORDER.reversed();
then using those comparators:
IntStream.range(-range, 0).boxed().sorted(BY_DESCENDING_ORDER).forEach(// etc...
With regard to the specific question of generating a reverse IntStream
:
starting from Java 9 you can use the three-argument version of the IntStream.iterate(...)
:
IntStream.iterate(10, x -> x >= 0, x -> x - 1).forEach(System.out::println);
// Out: 10 9 8 7 6 5 4 3 2 1 0
where:
IntStream.iterate?(int seed, IntPredicate hasNext, IntUnaryOperator next);
seed
- the initial element;hasNext
- a predicate to apply to elements to determine when the
stream must terminate;next
- a function to be applied to the previous element to produce a
new element.cyclops-react StreamUtils has a reverse Stream method (javadoc).
StreamUtils.reverse(Stream.of("1", "2", "20", "3"))
.forEach(System.out::println);
It works by collecting to an ArrayList and then making use of the ListIterator class which can iterate in either direction, to iterate backwards over the list.
If you already have a List, it will be more efficient
StreamUtils.reversedStream(Arrays.asList("1", "2", "20", "3"))
.forEach(System.out::println);
How about this utility method?
public static <T> Stream<T> getReverseStream(List<T> list) {
final ListIterator<T> listIt = list.listIterator(list.size());
final Iterator<T> reverseIterator = new Iterator<T>() {
@Override
public boolean hasNext() {
return listIt.hasPrevious();
}
@Override
public T next() {
return listIt.previous();
}
};
return StreamSupport.stream(Spliterators.spliteratorUnknownSize(
reverseIterator,
Spliterator.ORDERED | Spliterator.IMMUTABLE), false);
}
Seems to work with all cases without duplication.
Source: Stackoverflow.com