Sliding Window Spliterator in Java

Question

I implemented a custom Sliding Window Spliterator in Java. Do you have any ideas how this could be improved?

Thinking if replacing the buffer with a plain array could have a positive impact on the performance side of things if done correctly.

I'm not going to use that code in any production system, just exercising.

public class WindowSpliterator<T> implements Spliterator<Stream<T>> {

    static <T> Stream<Stream<T>> windowed(Collection<T> stream, int windowSize) {
        return StreamSupport.stream(new WindowSpliterator<>(stream, windowSize), false);
    }

    private final Queue<T> buffer;

    private final Iterator<T> sourceIterator;
    private final int windowSize;

    private WindowSpliterator(Collection<T> collection, int windowSize) {
        this.buffer = new ArrayDeque<>(windowSize);
        this.sourceIterator = Objects.requireNonNull(collection).iterator();
        this.windowSize = windowSize;
    }

    @Override
    public boolean tryAdvance(Consumer<? super Stream<T>> action) {
        if (windowSize < 1) {
            return false;
        }

        while (sourceIterator.hasNext()) {
            buffer.add(sourceIterator.next());

            if (buffer.size() == windowSize) {
                action.accept(Arrays.stream((T[]) buffer.toArray(new Object[0])));
                buffer.poll();
                return sourceIterator.hasNext();
            }
         }

        if (!buffer.isEmpty()) {
            action.accept(buffer.stream());
        }

        return false;
    }

    @Override
    public Spliterator<Stream<T>> trySplit() {
        return null;
    }

    @Override
    public long estimateSize() {
        return Long.MAX_VALUE;
    }

    @Override
    public int characteristics() {
        return ORDERED | NONNULL;
    }
}

Answer 1

I'm curious why you are using:

action.accept(Arrays.stream((T[]) buffer.toArray(new Object[0])));

It seems to me that action.accept(buffer.stream()) would work here, as long as the action.accept() fully processes the produced stream before returning.

---

Given the stream 1, 2, 3, 4 and the window size 3, the code looks like it will produce [1,2,3], [2,3,4], and then due to the code outside the while loop, it looks like it wants to produce [3,4] as one last hurrah!

Except, tryAdvance has already returned false from return sourceIterator.hasNext(), so tryAdvance should not be called again. So the code after the while loop looks effectively unreachable.

But it can be reached ... if the window never fill up completely in the first case, in which case it will produce exactly one stream of less than the full window size. Is this intended behaviour? If so, you really need to add comments explaining how that code is reached, and why it is possible not to reach it.

If less than a full window of output is possible, then shouldn't the Spliterator produce [1], [1,2], [1,2,3], [2,3,4], [3,4], [4] ... building up to the full window size and then tapering off once the end of the source stream has been reached? Wouldn't that be more consistent?

---

An ArrayDeque will (based on its name) internally use an array, probably with head and tail indices. I'm not sure how much you can improve it by implementing it with your own "plain array". Sounds like you'd be reinventing the wheel. Although using an array of windowSize*2-1 to avoid the wrap-around might give you a slight speedup.

---

estimateSize() could query the collection for its size, compute the number of windows it will be producing and return an actual value, instead of simply returning MAX_VALUE.