Class Iteration<T>
generate()
is used to generate
a sequence of values; and yield()
is used to yield control
back to the stream, with elements lazily generated 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);
generate(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
yield()
:
class DepthFirst<T> extends Iteration<T> {
DepthFirst<T> inOrder(Tree<T> tree) {
if (tree == null) return this;
yield(() -> inOrder(tree.left));
generate(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));
}
generate(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 TypeMethodDescriptionGenerates all ofelements
to the result stream.Generateselement
to the result stream.iterate()
Starts iteration over thegenerated
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
.Deprecated.Deprecated.usegenerate(Iterable)
instead
-
Constructor Details
-
Iteration
public Iteration()
-
-
Method Details
-
generate
Generateselement
to the result stream.- Since:
- 8.1
-
generate
Generates all ofelements
to the result stream.- Since:
- 8.1
-
yield
Deprecated.usegenerate(T)
insteadYieldselement
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: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
Deprecated.usegenerate(Iterable)
insteadYields all ofelements
to the result stream.- Since:
- 5.4
-
iterate
Starts iteration over thegenerated
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
-
generate(T)
instead