DEV Community

Allen D. Ball
Allen D. Ball

Posted on • Updated on • Originally published at blog.hcf.dev

Java Stream Tree Walker

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 Spliterators.

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)
    ...
}
Enter fullscreen mode Exit fullscreen mode

The Function provides the subordinate ("children") nodes of the argument node. For example, for Java Classes to obtain inner (declared) Classes:

    t -> Stream.of(t.getDeclaredClasses()
Enter fullscreen mode Exit fullscreen mode

or for Files:

    t -> t.isDirectory() ? Stream.of(t.listFiles()) : Stream.empty()
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
    ...
}
Enter fullscreen mode Exit fullscreen mode

A Stream of Spliterator Suppliers 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);
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

Yields:

.
./src
./src/main
./src/main/resources
./target
Enter fullscreen mode Exit fullscreen mode

This presents a flexible solution and can be extended with disparate objects. For example, a method to walk XML Nodes might be:

    public static Stream<Node> childrenOf(Node node) {
        NodeList list = node.getChildNodes();

        return IntStream.range(0, list.getLength()).mapToObj(list::item);
    }
Enter fullscreen mode Exit fullscreen mode

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);
    }
    ...
}
Enter fullscreen mode Exit fullscreen mode

Summary

Streams 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)