How should I check whether a Stream<T> 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...