Package com.google.mu.util.stream

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. yield() is used to generate a sequence that computes each value on-demand.

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 yield(() -> 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);
       yieldAll(response.getFoos());
       String nextPage = response.getNextPageToken();
       if (!nextPage.isEmpty()) {
         yield(() -> 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 yeidl(): 

 class DepthFirst<T> extends Iteration<T> {
   DepthFirst<T> inOrder(Tree<T> tree) {
     if (tree == null) return this;
     yield(() -> inOrder(tree.left));
     yield(tree.value);
     yield(() -> 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()) {
         yield(() -> postOrder(successor));
       }
       yield(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 and then be able to call yield() as if it were a keyword.

Keep in mind that, unlike return or System.out.println(), yield() 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 yield().

Unlike Python's yield statement or C#'s yield return, this yield() 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, yielding 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

    • yield

      public final Iteration<T> yield(T element)
      Yields element to the result stream.

    • yield

      public final Iteration<T> yield(Iteration.Continuation continuation)
      Yields to the stream a recursive iteration or lazy side-effect wrapped in continuation.

    • yield

      public final Iteration<T> yield(Supplier<? extends T> computation, Consumer<? super T> consumer)
      Yields to the stream the result of computation. Upon evaluation, also passes the computation result to consumer. Useful when the computation result of a recursive call is needed. For example, if you have a recursive algorithm to sum all node values of a tree: 
      
 int sumNodeValues(Tree tree) {
   if (tree == null) return 0;
   return tree.value + sumNodeValues(tree.left) + sumNodeValues(tree.right);
 }
      It can be transformed to iterative stream as in: 
      
 class SumNodeValues extends Iteration<Integer> {
   SumNodeValues sum(Tree tree, AtomicInteger result) {
     if (tree == null) return this;
     AtomicInteger leftSum = new AtomicInteger();
     AtomicInteger rightSum = new AtomicInteger();
     yield(() -> sum(tree.left, leftSum));
     yield(() -> sum(tree.right, rightSum));
     yield(() -> tree.value + leftSum.get() + rightSum.get(), result::set);
     return this;
   }
 }

 Stream<Integer> sums =
     new SumNodeValues()
         .sum((root: 1, left: 2, right: 3), new AtomicInteger())
         .iterate();

     => [2, 3, 6]
      Since:
      4.5

    • yieldAll

      public final Iteration<T> yieldAll(Iterable<? extends T> elements)
      Yields all of elements to the result stream.
      Since:
      5.4

    • iterate

      public final Stream<T> iterate()
      Starts iteration over the yielded 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