Guava: Flattening tree-like structure

[Lysergid]

I was looking for functionality to make my tree-like structure flat and didn't find anything
_( Maybe just missed, if so please disregard all below =] )_
I'm wondering if this is something that might be useful for other.

Let's say I have this model:

public class Node {
    private String value;
    private Collection<Node> children;
    ...
}

Taking example I have this structure.

                /             \
            L1N1               L1N2
          /       \                 
    L1L2N1         L1L2N2

Naming might be better but just for sake of example :

Node node =
                new Node("root",
                        new Node("L1N1",
                                new Node("L1L2N1"),
                                new Node("L1L2N2")),
                        new Node("L1N2"));
Stream<Node> flat = Flatten.flatten(node, Node::getChildren);

Resulting to stream of:
root, L1N1, L1L2N1, L1L2N2, L1N2

Also Flatten.flatten should check for cycles.

Signature with options for array and stream(IDK if really needed) would look like:

public static <N> Stream<N> flatten(N root, Function<N, Collection<N>> childrenGetter)
public static <N> Stream<N> flattenArray(N root, Function<N, N[]> childrenGetter)
public static <N> Stream<N> flattenStream(N root, Function<N, Stream<N>> childrenGetter)

[jbduncan]

@Lysergid I think you'll be glad to know that Guava actually does have something for this!

It looks to me what you effectively want is a depth-first traversal of your tree starting from your tree's root node, which can be achieved with the following code (or something to the effect of it; I've not checked it with a compiler).

Node tree = ...
Traverser<Node> traverser = Traverser.forTree(Node::getChildren);
Iterable<Node> flat = traverser.depthFirstPreOrder(node);
Stream<Node> flatAsStream = Streams.stream(flat);

I hope this helps.

[Lysergid]

Thank you @jbduncan!

[jbduncan]

If you want your code to check for cycles though, it's a bit more complicated. You can use Traverser::forGraph, but then you'd need to ensure that your Node class has an equals()and hashCode() that doesn't recursively call the equals()/hashCode() of the node's children.

See the Javadoc for Traverser for more information.

[jbduncan]

And you're very welcome! :)