Created
April 2, 2019 04:55
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Run it online at https://jdoodle.com/a/172K