How should I check whether a Stream is sorted?

Question

With an Iterable<T>, it's easy:

T last = null;
for (T t : iterable) {
    if (last != null && last.compareTo(t) > 0) {
        return false;
    }
    last = t;
}
return true;

But I can't think of a clean way to do the same thing for a Stream<T> that avoids consuming all the elements when it doesn't have to.

Answer 1

There are several methods to iterate over the successive pairs of the stream. For example, you can check this question. Of course my favourite method is to use the library I wrote:

boolean unsorted = StreamEx.of(sourceStream)
                           .pairMap((a, b) -> a.compareTo(b) > 0)
                           .has(true);

It's short-circuit operation: it will finish as soon as it find the misorder. Also it works fine with parallel streams.

Answer 2

You can grab the Stream's underlying spliterator and check it it has the SORTED characteristic. Since it's a terminal operation, you can't use the Stream after (but you can create another one from this spliterator, see also Convert Iterable to Stream using Java 8 JDK).

For example:

Stream<Integer> st = Stream.of(1, 2, 3);
//false
boolean isSorted = st.spliterator().hasCharacteristics(Spliterator.SORTED);

Stream<Integer> st = Stream.of(1, 2, 3).sorted();
//true
boolean isSorted = st.spliterator().hasCharacteristics(Spliterator.SORTED);

My example shows that the SORTED characteristic appears only if you get the Stream from a source's that reports the SORTED characteristic or you call sorted() at a point on the pipeline.

One could argue that Stream.iterate(0, x -> x + 1); creates a SORTED stream, but there is no knowledge about the semantic of the function applied iteratively. The same applies for Stream.of(...).

If the pipeline is infinite then it's the only way to know. If not, and that the spliterator does not report this characteristic, you'd need to go through the elements and see if it does not satisfy the sorted characteristic you are looking for.

This is what you already done with your iterator approach but then you need to consume some elements of the Stream (in the worst case, all elements). You can make the task parallelizable with some extra code, then it's up to you to see if it's worth it or not...

Answer 3

This is a sequential, state holding solution:

IntStream stream = IntStream.of(3, 3, 5, 6, 6, 9, 10);
final AtomicInteger max = new AtomicInteger(Integer.MIN_VALUE);
boolean sorted = stream.allMatch(n -> n >= max.getAndSet(n));

Parallelizing would need to introduce ranges. The state, max might be dealt with otherwise, but the above seems most simple.

Answer 4

You could hijack a reduction operation to save the last value and compare it to the current value and throw an exception if it isn't sorted:

.stream().reduce((last, curr) -> {
   if (((Comparable)curr).compareTo(last) < 0) {
       throw new Exception();
    }

    return curr;
});

EDIT: I forked another answer's example and replaced it with my code to show it only does the requisite number of checks.

http://ideone.com/ZMGnVW

Answer 5

You could use allMatch with a multi-line lambda, checking the current value against the previous one. You'll have to wrap the last value into an array, though, so the lambda can modify it.

// infinite stream with one pair of unsorted numbers
IntStream s = IntStream.iterate(0, x -> x != 1000 ? x + 2 : x - 1);
// terminates as soon as the first unsorted pair is found
int[] last = {Integer.MIN_VALUE};
boolean sorted = s.allMatch(x -> {
    boolean b = x >= last[0]; last[0] = x; return b; 
});

Alternatively, just get the iterator from the stream and use a simple loop.

Answer 6

A naive solution uses the stream's Iterator:

public static <T extends Comparable<T>> boolean isSorted(Stream<T> stream) {
    Iterator<T> i = stream.iterator();
    if(!i.hasNext()) return true;
    T current = i.next();
    while(i.hasNext()) {
        T next = i.next();
        if(current == null || current.compareTo(next) > 0) return false;
        current = next;
    }
    return true;
}

Edit: It would also be possible to use a spliterator to parallelize the task, but the gains would be questionable and the increase in complexity is probably not worth it.

Answer 7

I don't know how good it is , but i have just got an idea:

1. Make a list out of your Stream , Integer or Strings or anything.
2. i have written this for a List<String> listOfStream:

        long countSorted = IntStream.range(1, listOfStream.size())
                .map(
                        index -> {
                            if (listOfStream.get(index).compareTo(listOfStream.get(index-1)) > 0) {
                                return 0;
                            }
                            return index;
                        })
                .sum();