Making an efficient Java 8 sorted Spliterator from an array

Question

In Java 8, a variety of convenient utilities are provided to build efficient Spliterators from arrays. However, no factory methods are provided there to build a Spliterator with a comparator. Clearly Spliterators are allowed to have attached comparators; they have a getComparator() method and a SORTED property.

How are library authors supposed to build SORTED Spliterators?

Answer 1

It seems that it is not foreseen to have such a Spliterator with an order other than natural. But implementing it is not that hard. It could look like this:

class MyArraySpliterator implements Spliterator.OfInt {
    final int[] intArray;
    int pos;
    final int end;
    final Comparator<? super Integer> comp;

    MyArraySpliterator(int[] array, Comparator<? super Integer> c) {
        this(array, 0, array.length, c);
    }
    MyArraySpliterator(int[] array, int s, int e, Comparator<? super Integer> c) {
        intArray=array;
        pos=s;
        end=e;
        comp=c;
    }
    @Override
    public OfInt trySplit() {
        if(end-pos<64) return null;
        int mid=(pos+end)>>>1;
        return new MyArraySpliterator(intArray, pos, pos=mid, comp);
    }
    @Override
    public boolean tryAdvance(IntConsumer action) {
        Objects.requireNonNull(action);
        if(pos<end) {
            action.accept(intArray[pos++]);
            return true;
        }
        return false;
    }
    @Override
    public boolean tryAdvance(Consumer<? super Integer> action) {
        Objects.requireNonNull(action);
        if(pos<end) {
            action.accept(intArray[pos++]);
            return true;
        }
        return false;
    }
    @Override
    public long estimateSize() {
        return end-pos;
    }
    @Override
    public int characteristics() {
        return SIZED|SUBSIZED|SORTED|ORDERED|NONNULL;
    }
    @Override
    public Comparator<? super Integer> getComparator() {
        return comp;
    }
}

But Java 8 is not entirely fixed yet. Maybe there will be a JRE-provided solution in the final.

Answer 2

You can create an ORDERED Spliterator:

• by starting from a Collection with an appropriate iterator():

  A Collection has an encounter order if the corresponding Collection.iterator() documents an order. If so, the encounter order is the same as the documented order. Otherwise, a collection does not have an encounter order.

  Typically, TreeSet.spliterator#getComparator returns the TreeSet's Comparator, but ArrayList.spliterator#getComparator returns null: the order is by incrementing index.

• or, if you have an array, by using the new convenience methods provided in the Arrays helper class, such as Arrays.spliterator(double[]):

  The spliterator reports Spliterator.SIZED, Spliterator.SUBSIZED, Spliterator.ORDERED, and Spliterator.IMMUTABLE.

• or (which is what Arrays.spliterator does) by explicitly providing characteristics, such as: Spliterators.spliterator(array, Spliterator.ORDERED);

When the collection is not associated with a particular comparator (or with arrays), it would make sense to sort before "spliterating".