How to create an infinite Stream<E> out of an Iterator<E>?

Question

Looking at the following class I've made:

public class FibonacciSupplier implements Iterator<Integer> {
    private final IntPredicate hasNextPredicate;

    private int beforePrevious = 0;
    private int previous = 1;

    private FibonacciSupplier(final IntPredicate hasNextPredicate) {
        this.hasNextPredicate = hasNextPredicate;
    }

    @Override
    public boolean hasNext() {
        return hasNextPredicate.test(previous);
    }

    @Override
    public Integer next() {
        int result = beforePrevious + previous;
        beforePrevious = previous;
        previous = result;
        return result;
    }

    public static FibonacciSupplier infinite() {
        return new FibonacciSupplier(i -> true);
    }

    public static FibonacciSupplier finite(final IntPredicate predicate) {
        return new FibonacciSupplier(predicate);
    }
} 

And the usage of it in:

public class Problem2 extends Problem<Integer> {
    @Override
    public void run() {
        result = toList(FibonacciSupplier.finite(i -> (i <= 4_000_000)))
                .stream()
                .filter(i -> (i % 2 == 0))
                .mapToInt(i -> i)
                .sum();
    }

    @Override
    public String getName() {
        return "Problem 2";
    }

    private static <E> List<E> toList(final Iterator<E> iterator) {
        List<E> list = new ArrayList<>();
        while (iterator.hasNext()) {
            list.add(iterator.next());
        }
        return list;
    }
}

How would I be able to create an infinite Stream<E>?

If I were to use Stream<Integer> infiniteStream = toList(FibonacciSupplier.infinite()).stream(), I would, possibly surprisingly, never get an infinite stream.
Instead the code would loop forever in the creation of the list in an underlying method.

This so far is purely theoretical, but I can definately understand the need for it if I would want to first skip the first x numbers from an infinite stream, and then limit it by the last y numbers, something like:

int x = MAGIC_NUMBER_X;
int y = MAGIC_NUMBER_y;
int sum = toList(FibonacciSupplier.infinite())
    .stream()
    .skip(x)
    .limit(y)
    .mapToInt(i -> i)
    .sum();

The code would not ever return a result, how should it be done?

Answer 1

Your mistake is to think that you need an Iterator or a Collection to create a Stream. For creating an infinite stream, a single method providing one value after another is enough. So for your class FibonacciSupplier the simplest use is:

IntStream s=IntStream.generate(FibonacciSupplier.infinite()::next);

or, if you prefer boxed values:

Stream<Integer> s=Stream.generate(FibonacciSupplier.infinite()::next);

Note that in this case the method does not have to be named next nor fulfill the Iterator interface. But it doesn’t matter if it does as with your class. Further, as we just told the stream to use the next method as a Supplier, the hasNext method will never be called. It’s just infinite.

Creating a finite stream using your Iterator is a bit more complicated:

Stream<Integer> s=StreamSupport.stream(
  Spliterators.spliteratorUnknownSize(
    FibonacciSupplier.finite(intPredicate), Spliterator.ORDERED),
  false);

In this case if you want a finite IntStream with unboxed int values your FibonacciSupplier should implement PrimitiveIterator.OfInt.

Answer 2

In Java 8 there are no public, concrete classes implementing the interface Stream. However, there are some static factory methods. One of the most important is StreamSupport.stream. In particular, it is used in the default method Collection.stream –inherited by most collection classes:

default Stream<E> stream() {
    return StreamSupport.stream(spliterator(), false);
}

The default implementation of this method creates a Spliterator by invoking spliterator(), and passes the created object to the factory method. Spliterator is a new interface introduced with Java 8 to support parallel streams. It is similar to Iterator, but in contrast to the latter, a Spliterator can be divided into parts, that can be processed independently. See Spliterator.trySplit for details.

The default method Iterable.spliterator was also added in Java 8, so that every Iterable class automatically supports Spliterators. The implementation looks as follows:

default Spliterator<T> spliterator() {
    return Spliterators.spliteratorUnknownSize(iterator(), 0);
}

The method creates the Spliterator from an arbitrary Iterator. If you combine these two steps, you can create a Stream from an arbitrary Iterator:

<T> Stream<T> stream(Iterator<T> iterator) {
    Spliterator<T> spliterator
        = Spliterators.spliteratorUnknownSize(iterator, 0);
    return StreamSupport.stream(spliterator, false);
}

---

To get an impression of Spliterators, here is a very simple example without using collections. The following class implements Spliterator to iterate over a half-open interval of integers:

public final class IntRange implements Spliterator.OfInt {
    private int first, last;
    public IntRange(int first, int last) {
        this.first = first;
        this.last = last;
    }
    public boolean tryAdvance(IntConsumer action) {
        if (first < last) {
            action.accept(first++);
            return true;
        } else {
            return false;
        }
    }
    public OfInt trySplit() {
        int size = last - first;
        if (size >= 10) {
            int temp = first;
            first += size / 2;
            return new IntRange(temp, first);
        } else {
            return null;
        }
    }
    public long estimateSize() {
        return Math.max(last - first, 0);
    }
    public int characteristics() {
        return ORDERED | DISTINCT | SIZED | NONNULL
            | IMMUTABLE | CONCURRENT | SUBSIZED;
    }
}

Answer 3

To add another answer, perhaps AbstractSpliterator is a better choice, especially given the example code. Generate is inflexible as there is no [good] way to give a stop condition except by using limit. Limit only accepts a number of items rather than a predicate, so we have to know how many items we want to generate - which might not be possible, and what if the generator is a black box passed to us?

AbstractSpliterator is a halfway house between having to write a whole spliterator, and using Iterator/Iterable. AbstractSpliterator lacks just the tryAdvance method where we first check our predicate for being done, and if not pass the generated value to an action. Here's an example of a Fibonacci sequence using AbstractIntSpliterator:

public class Fibonacci {
    private static class FibonacciGenerator extends Spliterators.AbstractIntSpliterator
    {
        private IntPredicate hasNextPredicate;
        private int beforePrevious = 0;
        private int previous = 0;

        protected FibonacciGenerator(IntPredicate hasNextPredicate)
        {
            super(Long.MAX_VALUE, 0);
            this.hasNextPredicate = hasNextPredicate;
        }

        @Override
        public boolean tryAdvance(IntConsumer action)
        {
            if (action == null)
            {
                throw new NullPointerException();
            }

            int next = Math.max(1, beforePrevious + previous);
            beforePrevious = previous;
            previous = next;

            if (!hasNextPredicate.test(next))
            {
                return false;
            }

            action.accept(next);

            return true;
        }

        @Override
        public boolean tryAdvance(Consumer<? super Integer> action)
        {
            if (action == null)
            {
                throw new NullPointerException();
            }

            int next = Math.max(1, beforePrevious + previous);
            beforePrevious = previous;
            previous = next;

            if (!hasNextPredicate.test(next))
            {
                return false;
            }

            action.accept(next);

            return true;
        }
    }

    public static void main(String args[])
    {
        Stream<Integer> infiniteStream = StreamSupport.stream(
                new FibonacciGenerator(i -> true), false);

        Stream<Integer> finiteStream = StreamSupport.stream(
                new FibonacciGenerator(i -> i < 100), false);

        // Print with a side-effect for the demo
        infiniteStream.limit(10).forEach(System.out::println);
        finiteStream.forEach(System.out::println);
    }
} 

For more details I've covered generators in Java 8 in my blog http://thecannycoder.wordpress.com/

Answer 4

You can use the low level stream support primitives and the Spliterators library to make a stream out of an Iterator.

The last parameter to StreamSupport.stream() says that the stream is not parallel. Be sure to let it like that because your Fibonacci iterator depends on previous iterations.

return StreamSupport.stream( Spliterators.spliteratorUnknownSize( new Iterator<Node>()
{
    @Override
    public boolean hasNext()
    {
        // to implement
        return ...;
    }

    @Override
    public ContentVersion next()
    {
        // to implement
        return ...;
    }
}, Spliterator.ORDERED ), false );