001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *     http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.configuration2.tree;
018
019import java.util.LinkedList;
020import java.util.List;
021
022/**
023 * <p>
024 * A class providing different algorithms for traversing a hierarchy of configuration nodes.
025 * </p>
026 * <p>
027 * The methods provided by this class accept a {@link ConfigurationNodeVisitor} and visit all nodes in a hierarchy
028 * starting from a given root node. Because a {@link NodeHandler} has to be passed in, too, arbitrary types of nodes can
029 * be processed. The {@code walk()} methods differ in the order in which nodes are visited. Details can be found in the
030 * method documentation.
031 * </p>
032 * <p>
033 * An instance of this class does not define any state; therefore, it can be shared and used concurrently. The
034 * {@code INSTANCE} member field can be used for accessing a default instance. If desired (e.g. for testing purposes),
035 * new instances can be created.
036 * </p>
037 *
038 * @since 2.0
039 */
040public class NodeTreeWalker {
041    /** The default instance of this class. */
042    public static final NodeTreeWalker INSTANCE = new NodeTreeWalker();
043
044    /**
045     * Helper method for performing a BFS traversal. Implementation node: This method organizes the nodes to be visited in
046     * structures on the heap. Therefore, it can deal with larger structures than would be the case in a recursive approach
047     * (where the stack size limits the size of the structures which can be traversed).
048     *
049     * @param root the root node to be navigated
050     * @param visitor the visitor
051     * @param handler the handler
052     * @param <T> the type of the nodes involved
053     */
054    private static <T> void bfs(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
055        final List<T> pendingNodes = new LinkedList<>();
056        pendingNodes.add(root);
057        boolean cancel = false;
058
059        while (!pendingNodes.isEmpty() && !cancel) {
060            final T node = pendingNodes.remove(0);
061            visitor.visitBeforeChildren(node, handler);
062            cancel = visitor.terminate();
063            pendingNodes.addAll(handler.getChildren(node));
064        }
065    }
066
067    /**
068     * Helper method for checking the parameters for the walk() methods. If mandatory parameters are missing, an exception
069     * is thrown. The return value indicates whether an operation can be performed.
070     *
071     * @param root the root node
072     * @param visitor the visitor
073     * @param handler the handler
074     * @param <T> the type of the nodes involved
075     * @return <b>true</b> if a walk operation can be performed, <b>false</b> otherwise
076     * @throws IllegalArgumentException if a required parameter is missing
077     */
078    private static <T> boolean checkParameters(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
079        if (visitor == null) {
080            throw new IllegalArgumentException("Visitor must not be null!");
081        }
082        if (handler == null) {
083            throw new IllegalArgumentException("NodeHandler must not be null!");
084        }
085        return root != null;
086    }
087
088    /**
089     * Recursive helper method for performing a DFS traversal.
090     *
091     * @param node the current node
092     * @param visitor the visitor
093     * @param handler the handler
094     * @param <T> the type of the nodes involved
095     */
096    private static <T> void dfs(final T node, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
097        if (!visitor.terminate()) {
098            visitor.visitBeforeChildren(node, handler);
099            handler.getChildren(node).forEach(c -> dfs(c, visitor, handler));
100            if (!visitor.terminate()) {
101                visitor.visitAfterChildren(node, handler);
102            }
103        }
104    }
105
106    /**
107     * Visits all nodes in the hierarchy represented by the given root node in <em>breadth first search</em> manner. This
108     * means that the nodes are visited in an order corresponding to the distance from the root node: first the root node is
109     * visited, then all direct children of the root node, then all direct children of the first child of the root node,
110     * etc. In this mode of traversal, there is no direct connection between the encounter of a node and its children.
111     * <strong>Therefore, on the visitor object only the {@code visitBeforeChildren()} method gets called!</strong>.
112     *
113     * @param root the root node of the hierarchy to be processed (may be <b>null</b>, then this call has no effect)
114     * @param visitor the {@code ConfigurationNodeVisitor} (must not be <b>null</b>)
115     * @param handler the {@code NodeHandler} (must not be <b>null</b>)
116     * @param <T> the type of the nodes involved
117     * @throws IllegalArgumentException if a required parameter is <b>null</b>
118     */
119    public <T> void walkBFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
120        if (checkParameters(root, visitor, handler)) {
121            bfs(root, visitor, handler);
122        }
123    }
124
125    /**
126     * Visits all nodes in the hierarchy represented by the given root node in <em>depth first search</em> manner. This
127     * means that first {@link ConfigurationNodeVisitor#visitBeforeChildren(Object, NodeHandler)} is called on a node, then
128     * recursively all of its children are processed, and eventually
129     * {@link ConfigurationNodeVisitor#visitAfterChildren(Object, NodeHandler)} gets invoked.
130     *
131     * @param root the root node of the hierarchy to be processed (may be <b>null</b>, then this call has no effect)
132     * @param visitor the {@code ConfigurationNodeVisitor} (must not be <b>null</b>)
133     * @param handler the {@code NodeHandler} (must not be <b>null</b>)
134     * @param <T> the type of the nodes involved
135     * @throws IllegalArgumentException if a required parameter is <b>null</b>
136     */
137    public <T> void walkDFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
138        if (checkParameters(root, visitor, handler)) {
139            dfs(root, visitor, handler);
140        }
141    }
142}