Skip to content

Instantly share code, notes, and snippets.

@Genzer
Created April 2, 2019 04:55
Show Gist options
  • Save Genzer/cb9b1cc5e11cbf36baa7894ba494ed93 to your computer and use it in GitHub Desktop.
Save Genzer/cb9b1cc5e11cbf36baa7894ba494ed93 to your computer and use it in GitHub Desktop.
This gist explores how to use `Stream` with a tree-like data structure
import java.util.*;
import java.util.function.*;
import java.util.stream.*;
/**
* This class is a test to see if we can use `Stream`
* to walk/explore a tree-like data structure.
*/
public class StreamingWithRecursion {
public static void main(String args[]) {
Node root = new Node("root");
Node one = new Node("1");
Node two = new Node("2");
Node three = new Node("3");
Node four = new Node("4");
Node five = new Node("5");
Node a = new Node("a");
Node b = new Node("b");
Node c = new Node("c");
Node d = new Node("d");
root
.add(one)
.add(two)
.add(three)
.add(four)
.add(five);
root.add(a)
.add(b)
.add(c);
a.add(b)
.add(d);
System.out.println("HHH - Use recursiveStream:");
recursiveStream(root)
.forEach(n -> System.out.println(n.value));
System.out.println("HHH - Use iteratingStream:");
iteratingStream(root)
.forEach(n -> System.out.println(n.value));
}
/**
* This method builds a `Stream<Node>` which is a concatenation
* of smaller `Stream`s. Each of them is in turn a concatenated
* `Stream<Node>` of the childrens.
*
* This method uses recursion.
*/
public static Stream<Node> recursiveStream(Node node) {
if (node.children.isEmpty()) {
return Stream.of(node);
}
return Stream.concat(
Stream.of(node),
node.children.stream()
.map(StreamingWithRecursion::recursiveStream)
.reduce(Stream.empty(), Stream::concat)
);
}
/**
* This method builds a `Stream<Node>` backed by an `Iterator` which in turn
* is backed by a `Deque` (as a stack).
*
* This method does not use recursion.
*/
public static Stream<Node> iteratingStream(Node node) {
return StreamSupport.stream(
Spliterators.spliteratorUnknownSize(new NodeIterator(node), Spliterator.ORDERED), false);
}
static class NodeIterator implements Iterator<Node> {
private final Deque<Node> nodes = new java.util.ArrayDeque<>();
public NodeIterator(Node node) {
this.nodes.addFirst(node);
}
@Override
public boolean hasNext() {
return !nodes.isEmpty();
}
@Override
public Node next() {
// IMPLEMENTATION NOTE:
// ----
// Use stack operations for depth-first.
Node next = nodes.pop();
for (Node child : next.children) {
nodes.addFirst(child);
}
return next;
}
}
/**
* A simple Node (as in Tree) for testing
*/
static class Node {
final String value;
final List<Node> children = new java.util.ArrayList<>();
public Node(String value) {
this.value = value;
}
public Node add(Node node) {
this.children.add(node);
return node;
}
}
}
@Genzer
Copy link
Author

Genzer commented Apr 2, 2019

Run it online at https://jdoodle.com/a/172K

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment