Class Iteration<T>
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: - 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. 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
-
Nested Class Summary
Modifier and TypeClassDescriptionstatic interface
Encapsulates recursive iteration or a lazy block of code with side-effect. -
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptioniterate()
Starts iteration over theyielded
elements.yield
(Iteration.Continuation continuation) Yields to the stream a recursive iteration or lazy side-effect wrapped incontinuation
.Yields to the stream the result ofcomputation
.Yieldselement
to the result stream.Yields all ofelements
to the result stream.
-
Constructor Details
-
Iteration
public Iteration()
-
-
Method Details
-
yield
Yieldselement
to the result stream. -
yield
Yields to the stream a recursive iteration or lazy side-effect wrapped incontinuation
. -
yield
Yields to the stream the result ofcomputation
. Upon evaluation, also passes the computation result toconsumer
. 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:
It can be transformed to iterative stream as in:int sumNodeValues(Tree tree) { if (tree == null) return 0; return tree.value + sumNodeValues(tree.left) + sumNodeValues(tree.right); }
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
Yields all ofelements
to the result stream.- Since:
- 5.4
-
iterate
Starts iteration over theyielded
elements.Because an
Iteration
instance is stateful and mutable,iterate()
can be called at most once per instance.- Throws:
IllegalStateException
- ifiterate()
has already been called.- Since:
- 4.5
-