[Solved] How can I create a Map of my nested List objects in java?

by


First, it would be impossible to create a map of parentId to each childId if there is a list of children in each node because in general case a parentId key may have multiple childId values and this conflict has to be resolved somehow.

So, either a Map<Integer, List<Integer>> where List<Integer> contains ids of all children, or a List<List<Integer>> (where the inner List<Integer> contains a pair of parentId and childId) may be created.

And finally, it needs to be defined whether the result contains roots or leafs.
The difference may be described as: roots have their parentId = null and non-null childId, leafs always have non-null parentId while childId may be null.

Let’s assume the input list of nodes is defined like this:

List<XNode> list = Arrays.asList(
    new XNode(1, Arrays.asList(new XNode(11, Arrays.asList(new XNode(111), new XNode(112))), new XNode(12), new XNode(13))),
    new XNode(2),
    new XNode(3, Arrays.asList(new XNode(31, Arrays.asList(new XNode(311)))))
);

Then the map may be created as follows:

Map<Integer, List<Integer>> map = list.stream()
    .flatMap(Main::flatMapEntry)
    .collect(Collectors.toMap(
        Map.Entry::getKey, Map.Entry::getValue, (a, b) -> a, LinkedHashMap::new
    ));  
System.out.println("map example: " + map);

with a recursive method flatMapEntry:

static Stream<Map.Entry<Integer, List<Integer>>> flatMapEntry(XNode node) {
    return node.getChildren().isEmpty()
        ? Stream.of(Map.entry(node.getId(), Collections.emptyList()))
        : Stream.concat(
            Stream.of(Map.entry(
                node.getId(), 
                node.getChildren().stream()
                    .map(XNode::getId)
                    .collect(Collectors.toList())
            )),
            node.getChildren().stream().flatMap(Main::flatMapEntry)
        );
}

Output for the given input (10 keys, 13 values):

map example: {1=[11, 12, 13], 11=[111, 112], 111=[], 112=[], 12=[], 13=[], 2=[], 3=[31], 31=[311], 311=[]}

Examples of building the lists of pairs:

  • Traversing the List<XNode> by breadth:
List<List<Integer>> leafsBreadth = flatList(list).collect(Collectors.toList());

System.out.println("leafs(breadth): " + leafsBreadth.size() + ": " + leafsBreadth);
// ---
static Stream<List<Integer>> flatList(List<XNode> list) {
    return list.stream()
        .flatMap(x -> x.getChildren().isEmpty() 
            ? Stream.of(Arrays.asList(x.getId(), null)) 
            : Stream.concat(x.getChildren().stream()
                .map(c -> Arrays.asList(x.getId(), c.getId())),
                flatList(x.getChildren())
        ));
}

Output:

leafs(breadth): 13: [[1, 11], [1, 12], [1, 13], [11, 111], [11, 112], [111, null], [112, null], [12, null], [13, null], [2, null], [3, 31], [31, 311], [311, null]]

  • Traversing the List<XNode> by depth (per each XNode in the list):
List<List<Integer>> leafsDepth = list.stream()
    .flatMap(x -> flatChildren(x)).collect(Collectors.toList());
System.out.println("leafs(depth):   " + leafsDepth.size() + ": " + leafsDepth);
// ----
static Stream<List<Integer>> flatChildren(XNode node) {
    return node.getChildren().isEmpty()
        ? Stream.of(Arrays.asList(node.getId(), null))
        : node.getChildren().stream().flatMap(x -> Stream.concat(
            Stream.of(Arrays.asList(node.getId(), x.getId())),
            flatChildren(x)
        ));
}

Output:

leafs(depth): 13: [[1, 11], [11, 111], [111, null], [11, 112], [112, null], [1, 12], [12, null], [1, 13], [13, null], [2, null], [3, 31], [31, 311], [311, null]]

  • Building roots by depth
List<List<Integer>> rootsDepth = list.stream()
    .flatMap(x -> flatRoots(null, x)) // using null for missing parentId
    .collect(Collectors.toList());
System.out.println("roots(depth):   " + rootsDepth.size() + ": " + rootsDepth);
// ----
static Stream<List<Integer>> flatRoots(Integer parentId, XNode node) {
    return Stream.concat(
        Stream.of(Arrays.asList(parentId, node.getId())),
        node.getChildren().stream().flatMap(x -> flatRoots(node.getId(), x))
    );
}

Output:

roots(depth): 10: [[null, 1], [1, 11], [11, 111], [11, 112], [1, 12], [1, 13], [null, 2], [null, 3], [3, 31], [31, 311]]

solved How can I create a Map of my nested List objects in java?