Package de.xima.fc.common.tree

Class TreeVisit

java.lang.Object

de.xima.fc.common.tree.TreeVisit

public final class TreeVisit
extends Object

Static methods for visiting tree data structures. Uses a ITreeAccessor as an adapter to allow different classes to function as tree nodes.

Consider using e.g. TreePreOrderIterable when you only need to visit all nodes in order.

Here is a simple example (that TreePreOrderIterable would suffice for):

     record Node(String id, int value, List<Node> children) {}
     enum NodeTreeAccessor implements ITreeAccessor<Node, String> {
         INSTANCE;
         public Node getChildren(Node node) { return node.children; }
         public String getId(Node node) { return node.id; }
     }
     class SummingVisitor implements ITreeVisitor.Pathless<Node> {
         int total;
         public boolean visit(Node node) { total = node.value ; return true; }
     }

     var n30 = new Node("ncr(3,0)", 1, List.of());
     var n31 = new Node("ncr(3,1)", 3, List.of());
     var n32 = new Node("ncr(3,2)", 3, List.of());
     var n33 = new Node("ncr(3,3)", 1, List.of());
     var n20 = new Node("ncr(2,0)", 1, List.of(n30));
     var n21 = new Node("ncr(2,1)", 2, List.of(n31));
     var n22 = new Node("ncr(2,2)", 1, List.of(n32, n33));
     var n10 = new Node("ncr(1,0)", 1, List.of(n20));
     var n11 = new Node("ncr(1,1)", 1, List.of(n21, n22));
     var n00 = new Node("ncr(0,0)", 1, List.of(n11, n10));

     var params = TreeVisitParams.params(NodeTreeAccessor.INSTANCE).includePath(false).build();
     var summingVisitor = new SummingVisitor();
     TreeVisit.visitTree(node, params, summingVisitor);

     // Prints 15, i.e. the geometric sum 2^0 + 2^1 + 2^2 + 2^3
     System.out.println(geometricSum);
 

Since:

8.2.0

Author:

XIMA MEDIA GmbH

See Also:

TreePreOrderIterable, TreeReversePostOrderIterable

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static class	TreeVisit.ETreeVisitResult	Indicates how to proceed with a tree visit, see TreeVisit and TreeVisit.ITreeVisitor.
static interface	TreeVisit.ITreeVisitor<Node>	Visitor for a tree data structure.
static class	TreeVisit.TreePathFragment<Node>	Represents a fragment or part of the path of a node in a tree data structure.
static class	TreeVisit.TreeVisitParams<Node,Id>	Parameters for TreeVisit.

Method Summary

Modifier and Type	Method	Description
static <Node> void	visitTree(Iterable<Node> startNodes, TreeVisit.TreeVisitParams<Node,?> params, TreeVisit.ITreeVisitor<Node> visitor)	Performs a visit operation on a tree data structure, invoking the given visitor for each node.
static <Node> void	visitTree(Node startNode, TreeVisit.TreeVisitParams<Node,?> params, TreeVisit.ITreeVisitor<Node> visitor)	Performs a visit operation on a tree data structure, invoking the given visitor for each node.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

visitTree

public static <Node> void visitTree(Iterable<Node> startNodes,
                                    TreeVisit.TreeVisitParams<Node,?> params,
                                    TreeVisit.ITreeVisitor<Node> visitor)

Performs a visit operation on a tree data structure, invoking the given visitor for each node. Nodes are visited in pre-order.

Assume the following tree:

• a
  • a1
  • a2
• b
  • b1
  • b2

Then the visitor methods are called in the following order:

• enter(a)
• visit(a)
• enter(a1)
• visit(a1)
• exit(a1)
• enter(a2)
• visit(a2)
• exit(a2)
• exit(a)
• enter(b)
• visit(b)
• enter(b1)
• visit(b1)
• exit(b1)
• enter(b2)
• visit(b2)
• exit(b2)
• exit(b)

Type Parameters:

Node - Type of the tree nodes.

Parameters:

startNodes - List of root nodes at which to start the visit. These nodes are visited as well.

params - Settings for the visit operation.

visitor - Visitor to inform when visiting nodes.

visitTree

public static <Node> void visitTree(Node startNode,
                                    TreeVisit.TreeVisitParams<Node,?> params,
                                    TreeVisit.ITreeVisitor<Node> visitor)

Performs a visit operation on a tree data structure, invoking the given visitor for each node. Nodes are visited in pre-order.

Assume the following tree:

• a
  • a1
  • a2
• b
  • b1
  • b2

Then the visitor methods are called in the following order:

• enter(a)
• visit(a)
• enter(a1)
• visit(a1)
• exit(a1)
• enter(a2)
• visit(a2)
• exit(a2)
• exit(a)
• enter(b)
• visit(b)
• enter(b1)
• visit(b1)
• exit(b1)
• enter(b2)
• visit(b2)
• exit(b2)
• exit(b)

Type Parameters:

Node - Type of the tree nodes.

Parameters:

startNode - A root nodes at which to start the visit. This node is visited as well.

params - Settings for the visit operation.

visitor - Visitor to inform when visiting nodes.