Java Streams - Filtering on previously filtered values

Question

I am experimenting with Java's Streams and trying to figure out what is possible as well as their strengths and weaknesses. Currently I am trying to implement the Sieve of Eratosthenes using a stream, but cannot seem to find a good way to loop through previously filtered values without storing them in a separate collection.

I am wanting to accomplish something like this:

IntStream myStream = IntStream.range(0,3);
myStream.filter(s -> {
    System.out.print("[filtering "+s+"] ");
    myStream.forEach(q -> System.out.print(q+", "));
    System.out.println();
    return true; //eventually respond to values observed on the line above
});

With a desired output of:

[filtering 0] 
[filtering 1] 0, 
[filtering 2] 0, 1, 
[filtering 3] 0, 1, 2, 

Note that while filtering each new value all previously filtered values are observed. This would allow an easy implementation of the Sieve of Eratosthenes because I could filter out all non-prime values and for each new value check for divisibility against all numbers that have previously passed the prime filter.

However, the above example gives me an error in NetBeans:

local variables referenced from a lambda expression must be final or effectively final

This appears to be because I am referencing myStream within a filter that is already acting on myStream. Is there any good way of working around this error (ie. making a final copy of the stream containing only the values that have been filtered so far), or is there a better approach to this sort of problem without using a separate collection to store values?

Answer 1

I managed to create an infinite Stream of prime numbers using the Sieve of Eratosthenes, but it actually does not use past values. Instead, it removes the multiples of a prime in the tail (in a lazy way, because the tail is infinite), like the original Sieve of Eratosthenes algorithm. For that, I used an Iterator as auxiliary (because the Stream can only be used once) and implemented a lazyConcat for streams.

class StreamUtils {
    public static IntStream fromIterator(PrimitiveIterator.OfInt it) {
        return StreamSupport.intStream(
                Spliterators.spliteratorUnknownSize(it, Spliterator.ORDERED), false);
    }

    public static IntStream lazyConcat(Supplier<IntStream> a, Supplier<IntStream> b) {
        return StreamSupport.intStream(new Spliterator.OfInt() {
            boolean beforeSplit = true;
            Spliterator.OfInt spliterator;

            @Override
            public OfInt trySplit() {
                return null;
            }

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

            @Override
            public int characteristics() {
                return Spliterator.ORDERED;
            }

            @Override
            public boolean tryAdvance(IntConsumer action) {
                boolean hasNext;
                if (spliterator == null) {
                    spliterator = a.get().spliterator();
                }
                hasNext = spliterator.tryAdvance(action);
                if (!hasNext && beforeSplit) {
                    beforeSplit = false;
                    spliterator = b.get().spliterator();
                    hasNext = spliterator.tryAdvance(action);
                }
                return hasNext;
            }
        }, false);
    }
}

My Sieve of Eratosthenes stream looks like this:

class Primes {
    public static IntStream stream() {
        return sieve(IntStream.iterate(2, n -> n + 1));
    }

    private static IntStream sieve(IntStream s) {
        PrimitiveIterator.OfInt it = s.iterator();
        int head = it.nextInt();
        IntStream tail = StreamUtils.fromIterator(it);
        return StreamUtils.lazyConcat(
                () -> IntStream.of(head),
                () -> sieve(tail.filter(n -> n % head != 0)));
    }
}

Then we can use it this way:

System.out.println(Primes.stream().limit(20).boxed().collect(Collectors.toList()));

Output:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]

I think it was a good exercise, but it seems it is quite inefficient and not stack-friendly at all.

Answer 2

You can't process a Stream more than once, therefore calling myStream.forEach inside the filter method is not possible.

You could create a new IntStream inside the filter.

Note that you will have to add some terminal operation to the outer Stream pipeline in order for it to be processed :

IntStream myStream = IntStream.range(0,4);
myStream.filter(s -> {
    System.out.print("[filtering "+s+"] ");
    IntStream.range(0,s).forEach(q -> System.out.print(q+", "));
    System.out.println();
    return true; //eventually respond to values observed on the line above
}).forEach(i->{});

This produces :

[filtering 0] 
[filtering 1] 0, 
[filtering 2] 0, 1, 
[filtering 3] 0, 1, 2,