    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 *     https://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 (for example 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 <strong>true</strong> if a walk operation can be performed, <strong>false</strong> 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     * Constructs a new instance.
    108     */
    109    public NodeTreeWalker() {
    110        // empty
    111    }
    112
    113    /**
    114     * Visits all nodes in the hierarchy represented by the given root node in <em>breadth first search</em> manner. This
    115     * means that the nodes are visited in an order corresponding to the distance from the root node: first the root node is
    116     * visited, then all direct children of the root node, then all direct children of the first child of the root node,
    117     * etc. In this mode of traversal, there is no direct connection between the encounter of a node and its children.
    118     * <strong>Therefore, on the visitor object only the {@code visitBeforeChildren()} method gets called!</strong>.
    119     *
    120     * @param root the root node of the hierarchy to be processed (may be <strong>null</strong>, then this call has no effect)
    121     * @param visitor the {@code ConfigurationNodeVisitor} (must not be <strong>null</strong>)
    122     * @param handler the {@code NodeHandler} (must not be <strong>null</strong>)
    123     * @param <T> the type of the nodes involved
    124     * @throws IllegalArgumentException if a required parameter is <strong>null</strong>
    125     */
    126    public <T> void walkBFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
    127        if (checkParameters(root, visitor, handler)) {
    128            bfs(root, visitor, handler);
    129        }
    130    }
    131
    132    /**
    133     * Visits all nodes in the hierarchy represented by the given root node in <em>depth first search</em> manner. This
    134     * means that first {@link ConfigurationNodeVisitor#visitBeforeChildren(Object, NodeHandler)} is called on a node, then
    135     * recursively all of its children are processed, and eventually
    136     * {@link ConfigurationNodeVisitor#visitAfterChildren(Object, NodeHandler)} gets invoked.
    137     *
    138     * @param root the root node of the hierarchy to be processed (may be <strong>null</strong>, then this call has no effect)
    139     * @param visitor the {@code ConfigurationNodeVisitor} (must not be <strong>null</strong>)
    140     * @param handler the {@code NodeHandler} (must not be <strong>null</strong>)
    141     * @param <T> the type of the nodes involved
    142     * @throws IllegalArgumentException if a required parameter is <strong>null</strong>
    143     */
    144    public <T> void walkDFS(final T root, final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler) {
    145        if (checkParameters(root, visitor, handler)) {
    146            dfs(root, visitor, handler);
    147        }
    148    }
    149}