CODEWITHSUNDEEP
javaalgorithmjava-8
Nick
Nick

Reputation: 1269

Streams Tree Transformation

I'm fairly new to the Java 8 Streams API stuff, but I've decided to use it for a new piece of functionality but have hit a brick wall!

I have a bunch of MenuItem objects:

MenuItem parent1 = new MenuItem(0L, "Code Parent", "Description Parent");
MenuItem item1 = new MenuItem(1L, "Code1", "Description1");
MenuItem item2 = new MenuItem(2L, "Code2", "Description2");
MenuItem item3 = new MenuItem(3L, "Code3", "Description3");
MenuItem item4 = new MenuItem(4L, "Code4", "Description4");

I also have a bunch of MenuHierarchy objects which represent the hierarchical relationships between MenuItem (parent/child). This model is fixed as is, so have to work with what I've got.

Constructor - MenyHierarchy(id, parent, child, displayOrder)

MenuHierarchy hierarchy1 = new MenuHierarchy(1L, null, parent1);
MenuHierarchy hierarchy2 = new MenuHierarchy(2L, parent1, item1, 1);
MenuHierarchy hierarchy3 = new MenuHierarchy(3L, item1, item2, 2);
MenuHierarchy hierarchy4 = new MenuHierarchy(4L, item2, item3, 3);
MenuHierarchy hierarchy5 = new MenuHierarchy(5L, item3, item4, 4);

MenuHierarchy objects will a null parent are considered root nodes.

Now using the streams API I want to transform this relationship into a Tree like structure using a MenuNode entity that I've created:

public class MenuNode implements GenericNode<MenuItem> {

    private MenuItem data;
    private List<GenericNode<MenuItem>> children;

    public MenuNode(MenuItem data) {
        this.data = data;
        this.children = new ArrayList<GenericNode<MenuItem>>();
    }

    // Getters, setters

}

I'll explain what I have so far:

        /* This is the list of Root Menus (Menus which have no parent) */
    List<MenuNode> rootNodes = new ArrayList<>();
    List<MenuHierarchy> hierarchyList = Arrays.asList(hierarchy1, hierarchy2, hierarchy3, hierarchy4, hierarchy5);

    /* This first stream adds a new root MenuNode object to the above list ordered by the hierarchy display order */
    hierarchyList.parallelStream()
        .filter((h) -> Objects.isNull(h.getParentMenu()))
        .sorted((h, i) -> h.getDisplayOrder().compareTo(i.getDisplayOrder()))
        .map(MenuHierarchy::getChildMenu)
        .forEachOrdered((i) -> rootNodes.add(new MenuNode(i)));

    /* This second one is where i've sort of failed...
       What i need this to do is iterate over the menu hierarchies and for each non-root one
       add it to the MenuNode children collection where MenuNode.data == MenyHeirarchy.parentMenu
       Resulting in a tree of MenuItems...
     */
    hierarchyList.stream()
        .filter((h) -> Objects.nonNull(h.getParentMenu()))
        .sorted((h, i) -> h.getDisplayOrder().compareTo(i.getDisplayOrder()))
        .forEachOrdered((h) -> {

            rootNodes.stream()
                .filter((n) -> n.getData().equals(h.getParentMenu()))
                .forEach((n) -> {
                    n.getChildren().add(new MenuNode(h.getChildMenu()));
                });

        });

enter image description here

As you can see this doesn't work properly at the moment as it doesn't represent all of the hierarchy... I'm not sure if this is even possible with streams?

Any ideas will be greatly recommended.

Upvotes: 3

Views: 3458

Answers (1)

Misha
Misha

Reputation: 28133

Do I understand correctly that you want to end up with a bunch of MenuNode objects that represent the menu? If that's the case, I think it would be easier to premake all the node objects and then populate their children list. 

// first we make all the nodes and map them to ID
Map<Long, MenuNode> nodes = hierarchies.stream()
    .map(MenuHierarchy::getChildMenu)
    .collect(toMap(MenuItem::getId, MenuNode::new));

// and now we go over all hierarchies and add children to appropriate node
hierarchies.stream()
    .filter(h -> h.getParent() != null)
    .sorted(comparing(MenuHierarchy::getDisplayOrder))
    .forEach(h -> {
        long parentId = h.getParentMenu().getId();
        long childId  = h.getChildMenu().getId();
        nodes.get(parentId).getChildren().add(nodes.get(childId))
    });

Alternatively, the second part can be written by going over nodes first. The advantage of doing it this way is that you can make the child list in MenuNode immutable. The downside is that you might find the idea of repeatedly iterating over all hierarchies distasteful (even though it shouldn't matter for any realistic menu size):

nodes.values().forEach( node ->
    node.setChildren(
        hierarchies.stream()
            .filter(h -> h.getParentMenu().getId() == node.getData().getId())
            .sorted(comparing(MenuHierarchy::getDisplayOrder))
            .map(MenuHierarchy::getChildMenu)
            .map(MenuItem::getId)
            .map(nodes::get)
            .collect(toList())
    )
);

And, for completeness sake, you can group up the hierarchies for the same parent using streams and rewrite the second part like this:

hierarchies.stream()
    .filter(h -> null != h.getParent())
    .collect(
        groupingBy(h->g.getParentMenu().getId(), toList())
    ) // now we have a map of parent Ids to list of MenuHierarchy for that parent
    .forEach( (parentId, children) ->
        nodes.get(parentId)).setChildren(
            children.stream()
                .sorted(comparing(MenuHierarchy::getDisplayOrder))
                .map(h -> nodes.get(h.getChildMenu().getId()))
                .collect(toList())
        )
    );

You decide what's clearer to you.

Edit: I wasn't sure if hierarchy id is always the same as the child id. If it is, the code can be simplified a bit.

Upvotes: 5

Related Questions