How to iterate through a list of nodes which might have sub-lists of nodes (unknown depth levels)-CodePudding

I have a list of nodes, and each node might have a list of subNodes (the number of levels are unknown):

class Node {
    int score;
    boolean selected;
    List<Node> subNodes;
}

Here's how an hypothetical structure might look like:

NODE
    NODE
        NODE
        NODE
            NODE
        NODE
    NODE
        NODE
            NODE
            NODE
                NODE
                NODE

Combinations are just countless. I need a way to sum NODE.score for all those nodes that have NODE.selected set to true, possibly using Java 8 features. Any hints would be really appreciated.

CodePudding user response：

Something like:

public int recursiveTotal(final Node node) {
    //node not select, don't count the node or any of its subnodes
    if (!node.selected) {
        return 0;
    }
    //no subnodes, only node score counts
    if (node.subNodes.isEmpty()) {
        return node.score;
    }
    //node has subnodes, recursively count subnode score   parent node score
    int totalScore = node.score;
    for (final Node subNode : node.subNodes) {
        totalScore  = recursiveTotal(subNode);
    }
    return totalScore;
}

Coded using stackoverflow as an IDE, no guarantee against compilation errors ;)

CodePudding user response：

Create a recursive method in your Node class which returns a stream of nodes concatenating a stream of the parent node and the sub nodes:

class Node {
    int score;
    boolean selected;
    List<Node> subNodes;

    public Stream<Node> streamNodes() {
        return Stream.concat(Stream.of(this), subNodes.stream().flatMap(Node::streamNodes));
    }
}

and use it like below to stream over your list:

List<Node> myNodes = //your list
int sum = myNodes.stream()
                 .flatMap(Node::streamNodes)
                 .filter(Node::isSelected)
                 .mapToInt(Node::getScore)
                 .sum();

CodePudding user response：

You can create a helper method responsible for flattening the nodes which would be called from the stream.

List<Node> nodes = List.of();
        
long totalScore = nodes.stream()
    .flatMap(node -> flatten(node).stream())
    .filter(Node::isSelected)
    .mapToLong(Node::getScore)
    .sum();

Recursive auxiliary method:

public static List<Node> flatten(Node node) {
    if (node.getSubNodes().isEmpty()) {
        return List.of(node);
    }
    
    List<Node> result = new ArrayList<>();
    result.add(node);
    node.getSubNodes().forEach(n -> result.addAll(flatten(n)));
    return result;
}

To avoid StackOverflowError method flatten() can be implemented without recursion:

public static List<Node> flatten(Node node) {
    List<Node> result = new ArrayList<>();
    Deque<Node> level = new ArrayDeque<>();
    level.add(node);

    while (!level.isEmpty()) {
        Node current = level.poll();
        result.add(current);
        
        current.getSubNodes().forEach(level::add);
    }
    return result;
}