| /* |
| * Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| package org.apache.commons.configuration2.tree; |
| |
| import java.util.LinkedList; |
| import java.util.List; |
| |
| /** |
| * <p> |
| * A class providing different algorithms for traversing a hierarchy of configuration nodes. |
| * </p> |
| * <p> |
| * The methods provided by this class accept a {@link ConfigurationNodeVisitor} and visit all nodes in a hierarchy |
| * starting from a given root node. Because a {@link NodeHandler} has to be passed in, too, arbitrary types of nodes can |
| * be processed. The {@code walk()} methods differ in the order in which nodes are visited. Details can be found in the |
| * method documentation. |
| * </p> |
| * <p> |
| * An instance of this class does not define any state; therefore, it can be shared and used concurrently. The |
| * {@code INSTANCE} member field can be used for accessing a default instance. If desired (e.g. for testing purposes), |
| * new instances can be created. |
| * </p> |
| * |
| * @since 2.0 |
| */ |
| public class NodeTreeWalker { |
| /** The default instance of this class. */ |
| public static final NodeTreeWalker INSTANCE = new NodeTreeWalker(); |
| |
| /** |
| * Helper method for performing a BFS traversal. Implementation node: This method organizes the nodes to be visited in |
| * structures on the heap. Therefore, it can deal with larger structures than would be the case in a recursive approach |
| * (where the stack size limits the size of the structures which can be traversed). |
| * |
| * @param root the root node to be navigated |
| * @param visitor the visitor |
| * @param handler the handler |
| * @param <T> the type of the nodes involved |
| */ |
| private static <T> void bfs(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) { |
| final List<T> pendingNodes = new LinkedList<>(); |
| pendingNodes.add(root); |
| boolean cancel = false; |
| |
| while (!pendingNodes.isEmpty() && !cancel) { |
| final T node = pendingNodes.remove(0); |
| visitor.visitBeforeChildren(node, handler); |
| cancel = visitor.terminate(); |
| pendingNodes.addAll(handler.getChildren(node)); |
| } |
| } |
| |
| /** |
| * Helper method for checking the parameters for the walk() methods. If mandatory parameters are missing, an exception |
| * is thrown. The return value indicates whether an operation can be performed. |
| * |
| * @param root the root node |
| * @param visitor the visitor |
| * @param handler the handler |
| * @param <T> the type of the nodes involved |
| * @return <b>true</b> if a walk operation can be performed, <b>false</b> otherwise |
| * @throws IllegalArgumentException if a required parameter is missing |
| */ |
| private static <T> boolean checkParameters(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) { |
| if (visitor == null) { |
| throw new IllegalArgumentException("Visitor must not be null!"); |
| } |
| if (handler == null) { |
| throw new IllegalArgumentException("NodeHandler must not be null!"); |
| } |
| return root != null; |
| } |
| |
| /** |
| * Recursive helper method for performing a DFS traversal. |
| * |
| * @param node the current node |
| * @param visitor the visitor |
| * @param handler the handler |
| * @param <T> the type of the nodes involved |
| */ |
| private static <T> void dfs(final T node, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) { |
| if (!visitor.terminate()) { |
| visitor.visitBeforeChildren(node, handler); |
| handler.getChildren(node).forEach(c -> dfs(c, visitor, handler)); |
| if (!visitor.terminate()) { |
| visitor.visitAfterChildren(node, handler); |
| } |
| } |
| } |
| |
| /** |
| * Visits all nodes in the hierarchy represented by the given root node in <em>breadth first search</em> manner. This |
| * means that the nodes are visited in an order corresponding to the distance from the root node: first the root node is |
| * visited, then all direct children of the root node, then all direct children of the first child of the root node, |
| * etc. In this mode of traversal, there is no direct connection between the encounter of a node and its children. |
| * <strong>Therefore, on the visitor object only the {@code visitBeforeChildren()} method gets called!</strong>. |
| * |
| * @param root the root node of the hierarchy to be processed (may be <b>null</b>, then this call has no effect) |
| * @param visitor the {@code ConfigurationNodeVisitor} (must not be <b>null</b>) |
| * @param handler the {@code NodeHandler} (must not be <b>null</b>) |
| * @param <T> the type of the nodes involved |
| * @throws IllegalArgumentException if a required parameter is <b>null</b> |
| */ |
| public <T> void walkBFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) { |
| if (checkParameters(root, visitor, handler)) { |
| bfs(root, visitor, handler); |
| } |
| } |
| |
| /** |
| * Visits all nodes in the hierarchy represented by the given root node in <em>depth first search</em> manner. This |
| * means that first {@link ConfigurationNodeVisitor#visitBeforeChildren(Object, NodeHandler)} is called on a node, then |
| * recursively all of its children are processed, and eventually |
| * {@link ConfigurationNodeVisitor#visitAfterChildren(Object, NodeHandler)} gets invoked. |
| * |
| * @param root the root node of the hierarchy to be processed (may be <b>null</b>, then this call has no effect) |
| * @param visitor the {@code ConfigurationNodeVisitor} (must not be <b>null</b>) |
| * @param handler the {@code NodeHandler} (must not be <b>null</b>) |
| * @param <T> the type of the nodes involved |
| * @throws IllegalArgumentException if a required parameter is <b>null</b> |
| */ |
| public <T> void walkDFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) { |
| if (checkParameters(root, visitor, handler)) { |
| dfs(root, visitor, handler); |
| } |
| } |
| } |