CODEWITHSUNDEEP
javajava-8treejava-stream
Sam
Sam

Reputation: 5731

How to unflatten a flattened hierarchy with Streams API

If I have a hierarchical structure that is still sorted, but flattened - how can I create a parent/child structure with Java Streams API? An example: How do I go from

-,A,Foo
A,A1,Alpha1
A,A2,Alpha2
-,B,Bar
B,B1,Bravo1
B,B2,Bravo2

to

-
  A
    A1,Alpha1
    A2,Alpha2
  B
    B1,Bravo1
    B2,Bravo2

A simple non-stream way would be to keep track of the parent column and see if it has changed.

I have tried various ways with Collectors and groupingBy, but have not yet found how to do.

List<Row> list = new ArrayList<>();
list.add(new Row("-", "A", "Root"));
list.add(new Row("A", "A1", "Alpha 1"));
list.add(new Row("A", "A2", "Alpha 2"));
list.add(new Row("-", "B", "Root"));
list.add(new Row("B", "B1", "Bravo 1"));
list.add(new Row("B", "B2", "Bravo 2"));

//Edit
Map<Row, List<Row>> tree;

tree = list.stream().collect(Collectors.groupingBy(???))

Upvotes: 3

Views: 1524

Answers (1)

Eran
Eran

Reputation: 393986

You could create a Map of each Row indexed by it's name:

Map<String,Row> nodes = list.stream().collect(Collectors.toMap(Row::getName,Function.identity()));

getName() being the second property passed to the Row constructor.

Now you can use that Map to build the tree:

Map<Row,List<Row>> tree = list.stream().collect(Collectors.groupingBy(r->nodes.get(r.getParent())));

getParent() being the first property passed to the Row constructor.

This would require the Row class to override equals and hashCode properly, so that two Row instances will be considered equal if they have the same name.

You should probably add a root Row to your input List though. Something like:

list.add(new Row(null, "-", "Root"));

EDIT:

I tested it with a full Row class (though I made some shortcuts), including an example of traversing the tree from the root along the first child of each level:

class Row {
    String name;
    String parent;
    Row (String parent,String name,String something) {
        this.parent = parent;
        this.name = name;
    }
    public String getParent () {return parent;}
    public String getName () {return name;}

    public int hashCode () {return name.hashCode ();}
    public boolean equals (Object other) {
        return ((Row) other).name.equals (name);
    }
    public String toString ()
    {
        return name;
    }

    public static void main (String[] args)
    {
        List<Row> list = new ArrayList<>();
        list.add(new Row(null, "-", "Root"));
        list.add(new Row("-", "A", "Root"));
        list.add(new Row("A", "A1", "Alpha 1"));
        list.add(new Row("A1", "A11", "Alpha 11"));
        list.add(new Row("A", "A2", "Alpha 2"));
        list.add(new Row("-", "B", "Root"));
        list.add(new Row("B", "B1", "Bravo 1"));
        list.add(new Row("B", "B2", "Bravo 2"));
        Map<String,Row> nodes = 
            list.stream()
                .collect(Collectors.toMap(Row::getName,Function.identity()));
        Map<Row,List<Row>> tree = 
            list.stream()
                .filter(r->r.getParent()!= null)
                .collect(Collectors.groupingBy(r->nodes.get(r.getParent())));
        System.out.println (tree);
        Row root = nodes.get ("-");
        while (root != null) {
            System.out.print (root + " -> ");
            List<Row> children = tree.get (root);
            if (children != null && !children.isEmpty ()) {
                root = children.get (0);
            } else {
                root = null;
            }
        }
        System.out.println ();
    }
}

Output:

The tree:

{A1=[A11], A=[A1, A2], B=[B1, B2], -=[A, B]}

The traversal:

- -> A -> A1 -> A11 ->

Upvotes: 5

Related Questions