Iteration Explained

The Iteration class converts recursive algorithms into iterative streams.

Have you ever needed to create iterators (or streams) for recursive algorithms such as in-order, post-order traversal of binary trees, maybe to make the algorithm lazy, flexible, or to avoid stackoverflow error when the tree depth can be large?

If you have, you'll know that it's feasible but requires some careful stack manipulation to get it right. The code tends to be less than intuitive.

The Iteration class attempts to solve this kind of problem in a generic way.

For example, if you have a post-order binary tree traversal code that looks like this:

void printNodesInPostOrder(Tree<N> tree) {
  if (tree.left != null) {
    printNodesInPostOrder(tree.left);
  }
  if (tree.right != null) {
    printNodesInPostOrder(tree.right);
  }
  println(tree.node);
}

It's simple but not very flexible. Using the Iteration class, you can trivially turn it into a Stream of nodes. All you need is to wrap the recursion calls in a yield(), and also replace the println() with yield():

class PostOrder extends Iteration<N> {
  static <N> Stream<N> postOrderFrom(Tree<N> tree) {
    rerturn new PostOrder<N>().visit(tree).iterate();
  }

  PostOrder visit(Tree<N> tree) {
    if (tree.left != null) {
      yield(() -> visit(tree.left);
    }
    if (tree.right != null) {
      yield(() -> visit(tree.right);
    }
    yield(tree.node);
    return this;
  }
}

The generated postOrder stream is fully lazy.