This article discusses walking a tree or graph of nodes with a Java 8 Stream
implementation. The implementation is codified in a Spliterator
The strategy described herein can be a useful alternative to implementing a class-hierarchy specific visitor because only a single per-type method need be defined (often as a Java lambda).
Please refer to this article for an in-depth discussion of creating Spliterator
s.
API Definition
The implementaion provides the following API:
public class Walker<T> ... {
...
public static <T> Stream<T> walk(T root, Function<? super T,Stream<? extends T>> childrenOf)
...
}
The Function
provides the subordinate ("children") nodes of the argument node. For example, for Java Class
es to obtain inner (declared) Class
es:
t -> Stream.of(t.getDeclaredClasses()
or for File
s:
t -> t.isDirectory() ? Stream.of(t.listFiles()) : Stream.empty()
Implementation
The API provides a static method to create a Stream
from the implemented Spliterator
:
public static <T> Stream<T> walk(T root, Function<? super T,Stream<? extends T>> childrenOf) {
return StreamSupport.stream(new Walker<>(root, childrenOf), false);
}
The complete Spliterator
implementation is:
public class Walker<T> extends Spliterators.AbstractSpliterator<T> {
private final Stream<Supplier<Spliterator<T>>> stream;
private Iterator<Supplier<Spliterator<T>>> iterator = null;
private Spliterator<? extends T> spliterator = null;
private Walker(T node, Function<? super T,Stream<? extends T>> childrenOf) {
super(Long.MAX_VALUE, IMMUTABLE | NONNULL);
stream =
Stream.of(node)
.filter(Objects::nonNull)
.flatMap(childrenOf)
.filter(Objects::nonNull)
.map(t -> (() -> new Walker<T>(t, childrenOf)));
spliterator = Stream.of(node).spliterator();
}
@Override
public Spliterator<T> trySplit() {
if (iterator == null) {
iterator = stream.iterator();
}
return iterator.hasNext() ? iterator.next().get() : null;
}
@Override
public boolean tryAdvance(Consumer<? super T> consumer) {
boolean accepted = false;
while (! accepted) {
if (spliterator == null) {
spliterator = trySplit();
}
if (spliterator != null) {
accepted = spliterator.tryAdvance(consumer);
if (! accepted) {
spliterator = null;
}
} else {
break;
}
}
return accepted;
}
...
}
A Stream
of Spliterator
Supplier
s is created at instantiation (and the Supplier
will supply another Walker
). The first time trySplit()
is called the Stream
is converted to an Iterator
and the next Spliterator
is generated. The tryAdvance(Consumer)
will exhaust the last created Spliterator
before calling tryAdvance()
to obtain another. The first Spliterator
consists solely of the root node.
Examples
To print the inner defined classes of Collections
:
Walker.<Class<?>>walk(java.util.Collections.class,
t -> Stream.of(t.getDeclaredClasses()))
.limit(10)
.forEach(System.out::println);
Yields:
class java.util.Collections
class java.util.Collections$UnmodifiableCollection
class java.util.Collections$UnmodifiableSet
class java.util.Collections$UnmodifiableSortedSet
class java.util.Collections$UnmodifiableNavigableSet
class java.util.Collections$UnmodifiableNavigableSet$EmptyNavigableSet
class java.util.Collections$UnmodifiableRandomAccessList
class java.util.Collections$UnmodifiableList
class java.util.Collections$UnmodifiableMap
class java.util.Collections$UnmodifiableMap$UnmodifiableEntrySet
And to print the directory structure (sorted):
Walker.walk(new File("."),
t -> t.isDirectory() ? Stream.of(t.listFiles()) : Stream.empty())
.filter(File::isDirectory)
.sorted()
.forEach(System.out::println);
Yields:
.
./src
./src/main
./src/main/resources
./target
This presents a flexible solution and can be extended with disparate objects. For example, a method to walk XML Node
s might be:
public static Stream<Node> childrenOf(Node node) {
NodeList list = node.getChildNodes();
return IntStream.range(0, list.getLength()).mapToObj(list::item);
}
Alternate Entry Point
It is straightforward to offer an alternate entry point where multiple root nodes are supplied by defining a corresponding constructor:
public class Walker<T> extends Spliterators.AbstractSpliterator<T> {
...
private Walker(Stream<T> nodes, Function<? super T,Stream<? extends T>> childrenOf) {
super(Long.MAX_VALUE, IMMUTABLE | NONNULL);
stream = nodes.map(t -> (() -> new Walker<T>(t, childrenOf)));
}
...
public static <T> Stream<T> walk(Stream<T> roots, Function<? super T,Stream<? extends T>> childrenOf) {
return StreamSupport.stream(new Walker<>(roots, childrenOf), false);
}
...
}
Summary
Stream
s created from the Spliterator
implementation described herein provide a versatile means for walking any tree with a minimum per-type implementation while offering all the filtering and processing power of the Stream
API.
Top comments (0)