1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.configuration2.tree;
18
19 import java.util.LinkedList;
20 import java.util.List;
21
22 /**
23 * <p>
24 * A class providing different algorithms for traversing a hierarchy of configuration nodes.
25 * </p>
26 * <p>
27 * The methods provided by this class accept a {@link ConfigurationNodeVisitor} and visit all nodes in a hierarchy
28 * starting from a given root node. Because a {@link NodeHandler} has to be passed in, too, arbitrary types of nodes can
29 * be processed. The {@code walk()} methods differ in the order in which nodes are visited. Details can be found in the
30 * method documentation.
31 * </p>
32 * <p>
33 * An instance of this class does not define any state; therefore, it can be shared and used concurrently. The
34 * {@code INSTANCE} member field can be used for accessing a default instance. If desired (e.g. for testing purposes),
35 * new instances can be created.
36 * </p>
37 *
38 * @since 2.0
39 */
40 public class NodeTreeWalker {
41 /** The default instance of this class. */
42 public static final NodeTreeWalker INSTANCE = new NodeTreeWalker();
43
44 /**
45 * Visits all nodes in the hierarchy represented by the given root node in <em>depth first search</em> manner. This
46 * means that first {@link ConfigurationNodeVisitor#visitBeforeChildren(Object, NodeHandler)} is called on a node, then
47 * recursively all of its children are processed, and eventually
48 * {@link ConfigurationNodeVisitor#visitAfterChildren(Object, NodeHandler)} gets invoked.
49 *
50 * @param root the root node of the hierarchy to be processed (may be <b>null</b>, then this call has no effect)
51 * @param visitor the {@code ConfigurationNodeVisitor} (must not be <b>null</b>)
52 * @param handler the {@code NodeHandler} (must not be <b>null</b>)
53 * @param <T> the type of the nodes involved
54 * @throws IllegalArgumentException if a required parameter is <b>null</b>
55 */
56 public <T> void walkDFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
57 if (checkParameters(root, visitor, handler)) {
58 dfs(root, visitor, handler);
59 }
60 }
61
62 /**
63 * Visits all nodes in the hierarchy represented by the given root node in <em>breadth first search</em> manner. This
64 * means that the nodes are visited in an order corresponding to the distance from the root node: first the root node is
65 * visited, then all direct children of the root node, then all direct children of the first child of the root node,
66 * etc. In this mode of traversal, there is no direct connection between the encounter of a node and its children.
67 * <strong>Therefore, on the visitor object only the {@code visitBeforeChildren()} method gets called!</strong>.
68 *
69 * @param root the root node of the hierarchy to be processed (may be <b>null</b>, then this call has no effect)
70 * @param visitor the {@code ConfigurationNodeVisitor} (must not be <b>null</b>)
71 * @param handler the {@code NodeHandler} (must not be <b>null</b>)
72 * @param <T> the type of the nodes involved
73 * @throws IllegalArgumentException if a required parameter is <b>null</b>
74 */
75 public <T> void walkBFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
76 if (checkParameters(root, visitor, handler)) {
77 bfs(root, visitor, handler);
78 }
79 }
80
81 /**
82 * Recursive helper method for performing a DFS traversal.
83 *
84 * @param node the current node
85 * @param visitor the visitor
86 * @param handler the handler
87 * @param <T> the type of the nodes involved
88 */
89 private static <T> void dfs(final T node, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
90 if (!visitor.terminate()) {
91 visitor.visitBeforeChildren(node, handler);
92 handler.getChildren(node).forEach(c -> dfs(c, visitor, handler));
93 if (!visitor.terminate()) {
94 visitor.visitAfterChildren(node, handler);
95 }
96 }
97 }
98
99 /**
100 * Helper method for performing a BFS traversal. Implementation node: This method organizes the nodes to be visited in
101 * structures on the heap. Therefore, it can deal with larger structures than would be the case in a recursive approach
102 * (where the stack size limits the size of the structures which can be traversed).
103 *
104 * @param root the root node to be navigated
105 * @param visitor the visitor
106 * @param handler the handler
107 * @param <T> the type of the nodes involved
108 */
109 private static <T> void bfs(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
110 final List<T> pendingNodes = new LinkedList<>();
111 pendingNodes.add(root);
112 boolean cancel = false;
113
114 while (!pendingNodes.isEmpty() && !cancel) {
115 final T node = pendingNodes.remove(0);
116 visitor.visitBeforeChildren(node, handler);
117 cancel = visitor.terminate();
118 pendingNodes.addAll(handler.getChildren(node));
119 }
120 }
121
122 /**
123 * Helper method for checking the parameters for the walk() methods. If mandatory parameters are missing, an exception
124 * is thrown. The return value indicates whether an operation can be performed.
125 *
126 * @param root the root node
127 * @param visitor the visitor
128 * @param handler the handler
129 * @param <T> the type of the nodes involved
130 * @return <b>true</b> if a walk operation can be performed, <b>false</b> otherwise
131 * @throws IllegalArgumentException if a required parameter is missing
132 */
133 private static <T> boolean checkParameters(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
134 if (visitor == null) {
135 throw new IllegalArgumentException("Visitor must not be null!");
136 }
137 if (handler == null) {
138 throw new IllegalArgumentException("NodeHandler must not be null!");
139 }
140 return root != null;
141 }
142 }