Class Iteration<T>

java.lang.Object
com.google.mu.util.stream.Iteration<T>
public class Iteration<T> extends Object
Transforms eager, recursive algorithms into lazy streams. emit() is used to emit a sequence of values; and lazily() is used to lazily generate elements.

Iteration can be used to adapt iterative or recursive algorithms to lazy streams. The size of the stack is O(1) and execution is deferred.

For example, if you have a list API with pagination support, the following code retrieves all pages eagerly: 


 ImmutableList<Foo> listAllFoos() {
   ImmutableList.Builder<Foo> builder = ImmutableList.builder();
   ListFooRequest.Builder request = ListFooRequest.newBuilder()...;
     do {
       ListFooResponse response = service.listFoos(request.build());
       builder.addAll(response.getFoos());
       request.setPageToken(response.getNextPageToken());
     } while (!request.getPageToken().isEmpty());
   return builder.build();
 }
To turn the above code into a lazy stream using Iteration, the key is to wrap the recursive calls into a lambda and pass it to lazily(() -> recursiveCall()). This allows callers to short-circuit when they need to: 

 Stream<Foo> listAllFoos() {
   class Pagination extends new Iteration<Foo>() {
     Pagination paginate(ListFooRequest request) {
       ListFooResponse response = service.listFoos(request);
       emit(response.getFoos());
       String nextPage = response.getNextPageToken();
       if (!nextPage.isEmpty()) {
         lazily(() -> paginate(request.toBuilder().setNextPageToken(nextPage).build()));
       }
       return this;
     }
   }
   return new Pagination()
       .paginate(ListFooRequest.newBuilder()...build())
       .iterate();
 }

Another common use case is to traverse recursive data structures lazily. Imagine if you have a recursive binary tree traversal algorithm: 


 void inOrder(Tree<T> tree) {
   if (tree == null) return;
   inOrder(tree.left);
   System.out.println(tree.value);
   inOrder(tree.right);
 }
Instead of traversing eagerly and hard coding System.out.println(), it can be intuitively transformed to a lazy stream, again, by wrapping the recursive inOrder() calls in a lambda and passing it to lazily(): 

 class DepthFirst<T> extends Iteration<T> {
   DepthFirst<T> inOrder(Tree<T> tree) {
     if (tree == null) return this;
     lazily(() -> inOrder(tree.left));
     emit(tree.value);
     lazily(() -> inOrder(tree.right));
   }
 }

 new DepthFirst<>().inOrder(root).iterate().forEachOrdered(System.out::println);

One may ask why not use flatMap() like the following? 


 <T> Stream<T> inOrder(Tree<T> tree) {
  if (tree == null) return Stream.empty();
  return Stream.of(inOrder(tree.left), Stream.of(tree.value), inOrder(tree.right))
      .flatMap(identity());
 }
This unfortunately doesn't scale, for two reasons:
  1. The code will recursively call inOrder() all the way from the root node to the leaf node. If the tree is deep, you may run into stack overflow error.
  2. flatMap() was not lazy in JDK 8. While it was later fixed in JDK 10 and backported to JDK 8, the JDK 8 you use may not carry the fix.

Similarly, the following recursive graph post-order traversal code: 


 class DepthFirst<N> {
   private final Set<N> visited = new HashSet<>();

   void postOrder(N node) {
     if (visited.add(node)) {
       for (N successor : node.getSuccessors()) {
          postOrder(successor);
       }
       System.out.println("node: " + node);
     }
   }
 }
can be transformed to an iterative stream using: 

 class DepthFirst<N> extends Iteration<N> {
   private final Set<N> visited = new HashSet<>();

   DepthFirst<N> postOrder(N node) {
     if (visited.add(node)) {
       for (N successor : node.getSuccessors()) {
         lazily(() -> postOrder(successor));
       }
       emit(node);
     }
     return this;
   }
 }

 new DepthFirst<>().postOrder(startNode).iterate().forEachOrdered(System.out::println);

If transforming tail-recursive algorithms, the space requirement is O(1) and execution is deferred.

While not required, users are encouraged to create a subclass because you need a class to define recursive methods anyways.

Keep in mind that, unlike return or System.out.println(), lazily() is lazy and does not evaluate until the stream iterates over it. So it's critical that all side effects should be wrapped inside Continuation objects passed to lazily() or forEachLazily().

Unlike Python's yield statement or C#'s yield return, the lazily() is a normal Java method. It doesn't "return" execution to the caller. Laziness is achieved by wrapping code block inside the Continuation lambda.

Like most manual iterative adaptation of recursive algorithms, laziness is implemented using a stack. No threads or synchronization is used.

This class is not threadsafe.

Nulls are not allowed.

Since:
4.4

  • Constructor Details

    • Iteration

      public Iteration()

  • Method Details

    • emit

      public final void emit(T element)
      Emits element to the result stream.
      Since:
      0.6

    • emit

      public final void emit(Iterable<? extends T> elements)
      Emits all of elements to the result stream.
      Since:
      9.6

    • lazily

      public final void lazily(Iteration.Continuation continuation)
      Lazily generate into the stream a recursive iteration or lazy side-effect wrapped in continuation.
      Since:
      9.6

    • forEachLazily

      public final <V> void forEachLazily(Iterable<V> iterable, Consumer<? super V> consumer)
      Applies consumer lazily on each element in iterable. An element is only iterated when consumed by the result stream.

      Note that if you have a small iterable of elements to be emitted, using emit(Iterable) is more efficient. Only use this method if it's critical that the iterable elements must be lazily consumed (for example it's a large list).

      Upon return, you shouldn't add or remove from iterable any more or else ConcurrentModificationException may be thrown while streaming.

      Since:
      9.6

    • forEachLazily

      public final <V> void forEachLazily(Stream<V> stream, Consumer<? super V> consumer)
      Applies consumer lazily on each element from stream. An element is only iterated when consumed by the result stream.
      Since:
      9.6

    • forEachLazily

      public final <V> void forEachLazily(IntStream stream, IntConsumer consumer)
      Applies consumer lazily on each int element from stream. An element is only iterated when consumed by the result stream.
      Since:
      9.6

    • forEachLazily

      public final <K,V> void forEachLazily(Map<K,V> map, BiConsumer<? super K, ? super V> consumer)
      Applies consumer lazily on each entry from map. An entry is only iterated when consumed by the result stream.

      Upon return, you shouldn't add or remove from map any more or else ConcurrentModificationException may be thrown while streaming.

      Since:
      9.6

    • iterate

      public final Stream<T> iterate()
      Starts iteration over the emitted elements.

      Because an Iteration instance is stateful and mutable, iterate() can be called at most once per instance.

      Throws:
      IllegalStateException - if iterate() has already been called.
      Since:
      4.5