Traverse a list of tree nodes

Question 1

I am wondering if there is a better way to traverse a list of trees.

Here is my current algorithm:

Collect the parent IDs in a Map
Traverse all the groups and find ones where their ID is not in the map
Calculate each of those groups overall status, based on their data
Go through them again and find their parent
Check if the parent has been visited before, if not
Find its child groups and its data and calculate an overall status

I have included 6 classes below:

Main.java ~ Builds the groups, sets the status, and prints the tree(s)
NodeUtils.java ~ Main library code for traversing the nodes
Node.java ~ Simple interface that represents a node
GroupNode.java ~ Represents a group that can hold data and child groups
DataNode.java ~ Stores a status and other data
Status.java ~ Represents a status of NORMAL, WARNING, CRITICAL, and UNKNOWN

Here is my current output, which is correct:

A: (WARNING) {0}
 C: (WARNING) {2}
B: (CRITICAL) {1}
 D: (CRITICAL) {1}
 E: (WARNING) {1}
 F: (UNKNOWN) {0}

The output is group label, status, child count
Indentation is added for each depth

Main.java

import java.util.List;
public class Main {
 public static void main(String[] args) {
 List<GroupNode> groups = createGroups();
 NodeUtils.calculateStatuses(groups);
 NodeUtils.drawTree(groups);
 }
 private static List<GroupNode> createGroups() {
 GroupNode groupA = new GroupNode(1, "A");
 GroupNode groupB = new GroupNode(2, "B");
 GroupNode groupC = new GroupNode(3, "C");
 GroupNode groupD = new GroupNode(4, "D");
 GroupNode groupE = new GroupNode(5, "E");
 GroupNode groupF = new GroupNode(6, "F");
 DataNode<String> data1 = new DataNode<>(1, "AC1");
 DataNode<String> data2 = new DataNode<>(2, "AC2");
 DataNode<String> data3 = new DataNode<>(3, "BD1");
 DataNode<String> data4 = new DataNode<>(4, "BE1");
 DataNode<String> data5 = new DataNode<>(5, "B1");
 groupC.setParentId(groupA.getId());
 groupD.setParentId(groupB.getId());
 groupE.setParentId(groupB.getId());
 groupF.setParentId(groupE.getId());
 groupC.getChildren().add(data1);
 groupC.getChildren().add(data2);
 groupD.getChildren().add(data3);
 groupE.getChildren().add(data4);
 groupB.getChildren().add(data5);
 data1.setStatus(Status.NORMAL);
 data2.setStatus(Status.WARNING);
 data3.setStatus(Status.CRITICAL);
 data4.setStatus(Status.WARNING);
 data5.setStatus(Status.NORMAL);
 return List.of(groupA, groupB, groupC, groupD, groupE, groupF);
 }
}

NodeUtils.java

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Optional;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class NodeUtils {
 public static void calculateStatuses(List<GroupNode> groups) {
 Map<Long, Boolean> parentIds = buildParentIdMap(groups);
 for (GroupNode group : groups) {
 if (!parentIds.containsKey(group.getId())) {
 // Does not have any child groups
 group.setStatus(calculateMaxStatus(group.getChildren()));
 }
 }
 for (GroupNode group : groups) {
 if (!parentIds.containsKey(group.getId())) {
 // If unvisited
 if (!parentIds.get(group.getParentId())) {
 GroupNode parent = findParentGroup(group, groups);
 List<GroupNode> childGroups = findChildGroups(parent, groups);
 List<Node> groupsAndData = Stream.concat(childGroups.stream(), parent.getChildren().stream()).collect(Collectors.toList());
 parent.setStatus(calculateMaxStatus(groupsAndData));
 parentIds.put(group.getParentId(), true); // Visited
 }
 }
 }
 }
 public static void drawTree(List<GroupNode> groups) {
 List<GroupNode> topLevel = groups.stream().filter(NodeUtils::isRootNode).collect(Collectors.toList());
 topLevel.forEach(node -> visitGroup(node, 0, groups));
 }
 private static void visitGroup(GroupNode group, int depth, List<GroupNode> groups) {
 String indent = "\t".repeat(depth);
 System.out.printf("%s%s: (%s) {%d}%n", indent, group.getLabel(), group.getStatus(), group.getChildren().size());
 findChildGroups(group, groups).forEach(child -> visitGroup(child, depth + 1, groups));
 }
 private static GroupNode findParentGroup(GroupNode group, List<GroupNode> groups) {
 return groups.stream().filter(curr -> curr.getId() == group.getParentId()).findFirst().orElse(null);
 }
 private static List<GroupNode> findChildGroups(GroupNode group, List<GroupNode> groups) {
 return groups.stream().filter(curr -> curr.getParentId() == group.getId()).collect(Collectors.toList());
 }
 private static <E extends Node> Status calculateMaxStatus(List<E> nodes) {
 Status status = Status.UNKNOWN;
 for (E node : nodes) {
 if (node.getStatus().getWeight() < status.getWeight()) {
 status = node.getStatus();
 }
 }
 return status;
 }
 private static boolean invalidId(long id) {
 return id < 1;
 }
 private static boolean isRootNode(GroupNode node) {
 return Optional.of(node).map(GroupNode::getParentId).map(NodeUtils::invalidId).orElse(false);
 }
 private static Map<Long, Boolean> buildParentIdMap(List<GroupNode> groups) {
 Map<Long, Boolean> parentIds = new HashMap<>();
 for (GroupNode group : groups) {
 if (group.getParentId() > 0) {
 parentIds.put(group.getParentId(), false);
 }
 }
 return parentIds;
 }
}

Node.java

public interface Node {
 long getId();
 String getLabel();
 Status getStatus();
}

GroupNode.java

import java.util.ArrayList;
import java.util.List;
public class GroupNode implements Node {
 private long id;
 private long parentId;
 private String label;
 private Status status;
 private List<Node> children;
 public GroupNode(long id, String label) {
 this.id = id;
 this.label = label;
 this.status = Status.UNKNOWN;
 this.children = new ArrayList<>();
 }
 public long getId() {
 return id;
 }
 public void setId(long id) {
 this.id = id;
 }
 public long getParentId() {
 return parentId;
 }
 public void setParentId(long parentId) {
 this.parentId = parentId;
 }
 @Override
 public String getLabel() {
 return label;
 }
 public void setLabel(String label) {
 this.label = label;
 }
 @Override
 public Status getStatus() {
 return status;
 }
 public void setStatus(Status status) {
 this.status = status;
 }
 public List<Node> getChildren() {
 return children;
 }
 public void setChildren(List<Node> children) {
 this.children = children;
 }
}

DataNode.java

public class DataNode<T> implements Node {
 private long id;
 private String label;
 private Status status;
 private T data;
 public DataNode(long id, String label) {
 this.id = id;
 this.label = label;
 this.status = Status.UNKNOWN;
 }
 public long getId() {
 return id;
 }
 public void setId(long id) {
 this.id = id;
 }
 @Override
 public String getLabel() {
 return label;
 }
 public void setLabel(String label) {
 this.label = label;
 }
 @Override
 public Status getStatus() {
 return status;
 }
 public void setStatus(Status status) {
 this.status = status;
 }
 public T getData() {
 return data;
 }
 public void setData(T data) {
 this.data = data;
 }
}

Status.java

public enum Status {
 NORMAL(100),
 WARNING(10),
 CRITICAL(0),
 UNKNOWN(Integer.MAX_VALUE);
 private int weight;
 Status(int weight) {
 this.weight = weight;
 }
 public int getWeight() {
 return weight;
 }
}

Question 2

So the groups only have references to their parents; groups don't have lists of their child groups but they do have lists of their child data nodes?

Question 3

@md2perpe yes, groups only know about their parent group. The group does not know about its child groups. Groups know about their children data.

Question 4

Why do groups not know their child GroupNodes as well as their child DataNodes? As designed, they can hold them both in children. Can the group nodes be modified to contain their child groups?

Question 5

@EricStein I only made the group and data nodes share in interface so that I can compare them for status. When a group is added or updated, you select a parent group. That is how they are stored in a database.

Question 6

NodeUtils is misrepresented as a static. Convert it to a Tree class with basically all of the same members; most of them will become non-static member functions that refer to a groups member. Once this is a real class, you can add supporting members like an ID index map.

You have too much mutability and too many boilerplate getters+setters (common for Java). In createGroups, there should be no set() calls at all. In fact, given a light refactor of your code, the existing algorithm only needs to mutate one thing, which is your .status. getChildren() should be returning either an unmodifiable list or a stream (which is by its nature unmodifiable).

Many of your List<> arguments can be demoted to Collection<> to be more accepting of multiple collection subclasses.

You have a tendency of flipping between streams and lists a lot. Much of your business logic can stay in the stream domain without intermediate lists.

isRootNode belongs on the node class as a non-static, not in the utils class.

Rather than calling .repeat() on a tab character, consider adding a variable field width in spaces to your format string. Tab formatting is unpredictable.

Your parent ID being "0 for no parent" is not, I think, sufficient distinction from normal integers that do represent parents. Consider a nullable Long instead. invalidId will go away.

calculateMaxStatus is problematic. First, its name is a lie: you're doing a min, not a max. Also, this can be done pretty easily with streams and a lambda comparator.

Node should not be an interface. You have common members and methods so make it an abstract class.

You aren't using the generic data support on DataNode so delete it.

Suggested

Same output as yours.

Main.java

import java.util.List;
public class Main {
 public static void main(String[] args) {
 Tree tree = createTree();
 tree.calculateStatuses();
 tree.draw();
 }
 private static Tree createTree() {
 DataNode data1 = new DataNode(1L, "AC1", Status.NORMAL),
 data2 = new DataNode(2L, "AC2", Status.WARNING),
 data3 = new DataNode(3L, "BD1", Status.CRITICAL),
 data4 = new DataNode(4L, "BE1", Status.WARNING),
 data5 = new DataNode(5L, "B1", Status.NORMAL);
 List<GroupNode> groups = List.of(
 new GroupNode(1L, "A"),
 new GroupNode(2L, "B", data5),
 new GroupNode(3L, 1L, "C", data1, data2),
 new GroupNode(4L, 2L, "D", data3),
 new GroupNode(5L, 2L, "E", data4),
 new GroupNode(6L, 5L, "F")
 );
 return new Tree(groups);
 }
}

Node.java

public abstract class Node {
 public final long id;
 public final String label;
 public Status status;
 protected Node(long id, String label) {
 this(id, label, Status.UNKNOWN);
 }
 protected Node(long id, String label, Status status) {
 this.id = id;
 this.label = label;
 this.status = status;
 }
}

DataNode.java

public class DataNode extends Node {
 public DataNode(long id, String label, Status status) {
 super(id, label, status);
 }
}

GroupNode.java

import java.util.Arrays;
import java.util.stream.Stream;
public class GroupNode extends Node {
 public final Long parentId;
 private final Node[] children;
 public GroupNode(long id, String label, Node... children) {
 super(id, label);
 this.parentId = null;
 this.children = children;
 }
 public GroupNode(long id, Long parentId, String label, Node... children) {
 super(id, label);
 this.parentId = parentId;
 this.children = children;
 }
 public Stream<Node> getChildren() {
 return Arrays.stream(children);
 }
 public boolean isRootNode() {
 return parentId == null;
 }
 public int countChildren() {
 return children.length;
 }
}

Status.java

public enum Status {
 NORMAL(100),
 WARNING(10),
 CRITICAL(0),
 UNKNOWN(Integer.MAX_VALUE);
 public final int weight;
 Status(int weight) {
 this.weight = weight;
 }
}

Tree.java

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class Tree {
 private final Collection<GroupNode> groups;
 private final Map<Long, GroupNode> byID;
 private final Map<Long, List<GroupNode>> byParent;
 public Tree(Collection<GroupNode> groups) {
 this.groups = groups;
 this.byID = groups.stream()
 .collect(Collectors.toMap(
 g -> g.id, g -> g
 ));
 this.byParent = groups.stream()
 .filter(g -> g.parentId != null)
 .collect(Collectors.groupingBy(g -> g.parentId));
 }
 public void calculateStatuses() {
 Map<Long, Boolean> parentsVisited = buildParentIdMap();
 for (GroupNode group: groups) {
 if (!parentsVisited.containsKey(group.id)) {
 // Does not have any child groups
 group.status = calculateMinStatus(group.getChildren());
 }
 }
 for (GroupNode group: groups) {
 if (!parentsVisited.containsKey(group.id)) {
 // If unvisited
 if (!parentsVisited.get(group.parentId)) {
 GroupNode parent = findParentGroup(group);
 List<GroupNode> childGroups = findChildGroups(parent);
 Stream<Node> groupsAndData = Stream.concat(childGroups.stream(), parent.getChildren());
 parent.status = calculateMinStatus(groupsAndData);
 parentsVisited.put(group.parentId, true); // Visited
 }
 }
 }
 }
 public void draw() {
 groups.stream()
 .filter(GroupNode::isRootNode)
 .forEach(node -> visitGroup(node, 0));
 }
 private void visitGroup(GroupNode group, int depth) {
 System.out.printf(
 "%" + (1 + depth*4) + "s: (%s) {%d}%n",
 group.label, group.status, group.countChildren()
 );
 findChildGroups(group)
 .forEach(child -> visitGroup(child, depth + 1));
 }
 private GroupNode findParentGroup(GroupNode group) {
 return byID.get(group.parentId);
 }
 private List<GroupNode> findChildGroups(GroupNode group) {
 return byParent.getOrDefault(group.id, Collections.emptyList());
 }
 private static Status calculateMinStatus(Stream<Node> nodes) {
 return nodes
 .map(n -> n.status)
 .filter(s -> s != Status.UNKNOWN)
 .min(Comparator.comparing(stat -> stat.weight))
 .orElse(Status.UNKNOWN);
 }
 private Map<Long, Boolean> buildParentIdMap() {
 return byParent.keySet().stream()
 .collect(Collectors.toMap(
 id -> id, // key
 id -> false, // value
 (v1, v2) -> false // merge
 ));
 }
}

Question 7

Personally I'd avoid using public final fields on immutable classes. They easily lead to accidentally writable fields (see the missing final on status in Node). Fields can't overwrite or be overwritten. I'd, for example, would have a Node interface, but a separate abstract class for the common code with a getStatus() implementation that just returns Status.UNKNOWN instead of storing the same value in all instances. And it leads to an ugly mixture of getters and field access (see getChildren() in GroupNode).

Reinderien Reinderien 71k5 gold badges76 silver badges256 bronze badges · Answer 1 · 2022-07-03 16:49:46Z