    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
    025 * configuration nodes.
    026 * </p>
    027 * <p>
    028 * The methods provided by this class accept a {@link ConfigurationNodeVisitor}
    029 * and visit all nodes in a hierarchy starting from a given root node. Because a
    030 * {@link NodeHandler} has to be passed in, too, arbitrary types of nodes can be
    031 * processed. The {@code walk()} methods differ in the order in which nodes are
    032 * visited. Details can be found in the method documentation.
    033 * </p>
    034 * <p>
    035 * An instance of this class does not define any state; therefore, it can be
    036 * shared and used concurrently. The {@code INSTANCE} member field can be used
    037 * for accessing a default instance. If desired (e.g. for testing purposes), new
    038 * instances can be created.
    039 * </p>
    040 *
    041 * @version $Id: NodeTreeWalker.java 1842194 2018-09-27 22:24:23Z ggregory $
    042 * @since 2.0
    043 */
    044public class NodeTreeWalker
    045{
    046    /** The default instance of this class. */
    047    public static final NodeTreeWalker INSTANCE = new NodeTreeWalker();
    048
    049    /**
    050     * Visits all nodes in the hierarchy represented by the given root node in
    051     * <em>depth first search</em> manner. This means that first
    052     * {@link ConfigurationNodeVisitor#visitBeforeChildren(Object, NodeHandler)}
    053     * is called on a node, then recursively all of its children are processed,
    054     * and eventually
    055     * {@link ConfigurationNodeVisitor#visitAfterChildren(Object, NodeHandler)}
    056     * gets invoked.
    057     *
    058     * @param root the root node of the hierarchy to be processed (may be
    059     *        <b>null</b>, then this call has no effect)
    060     * @param visitor the {@code ConfigurationNodeVisitor} (must not be
    061     *        <b>null</b>)
    062     * @param handler the {@code NodeHandler} (must not be <b>null</b>)
    063     * @param <T> the type of the nodes involved
    064     * @throws IllegalArgumentException if a required parameter is <b>null</b>
    065     */
    066    public <T> void walkDFS(final T root, final ConfigurationNodeVisitor<T> visitor,
    067            final NodeHandler<T> handler)
    068    {
    069        if (checkParameters(root, visitor, handler))
    070        {
    071            dfs(root, visitor, handler);
    072        }
    073    }
    074
    075    /**
    076     * Visits all nodes in the hierarchy represented by the given root node in
    077     * <em>breadth first search</em> manner. This means that the nodes are
    078     * visited in an order corresponding to the distance from the root node:
    079     * first the root node is visited, then all direct children of the root
    080     * node, then all direct children of the first child of the root node, etc.
    081     * In this mode of traversal, there is no direct connection between the
    082     * encounter of a node and its children. <strong>Therefore, on the visitor
    083     * object only the {@code visitBeforeChildren()} method gets
    084     * called!</strong>.
    085     *
    086     * @param root the root node of the hierarchy to be processed (may be
    087     *        <b>null</b>, then this call has no effect)
    088     * @param visitor the {@code ConfigurationNodeVisitor} (must not be
    089     *        <b>null</b>)
    090     * @param handler the {@code NodeHandler} (must not be <b>null</b>)
    091     * @param <T> the type of the nodes involved
    092     * @throws IllegalArgumentException if a required parameter is <b>null</b>
    093     */
    094    public <T> void walkBFS(final T root, final ConfigurationNodeVisitor<T> visitor,
    095            final NodeHandler<T> handler)
    096    {
    097        if (checkParameters(root, visitor, handler))
    098        {
    099            bfs(root, visitor, handler);
    100        }
    101    }
    102
    103    /**
    104     * Recursive helper method for performing a DFS traversal.
    105     *
    106     * @param node the current node
    107     * @param visitor the visitor
    108     * @param handler the handler
    109     * @param <T> the type of the nodes involved
    110     */
    111    private static <T> void dfs(final T node, final ConfigurationNodeVisitor<T> visitor,
    112            final NodeHandler<T> handler)
    113    {
    114        if (!visitor.terminate())
    115        {
    116            visitor.visitBeforeChildren(node, handler);
    117            for (final T c : handler.getChildren(node))
    118            {
    119                dfs(c, visitor, handler);
    120            }
    121            if (!visitor.terminate())
    122            {
    123                visitor.visitAfterChildren(node, handler);
    124            }
    125        }
    126    }
    127
    128    /**
    129     * Helper method for performing a BFS traversal. Implementation node: This
    130     * method organizes the nodes to be visited in structures on the heap.
    131     * Therefore, it can deal with larger structures than would be the case in a
    132     * recursive approach (where the stack size limits the size of the
    133     * structures which can be traversed).
    134     *
    135     * @param root the root node to be navigated
    136     * @param visitor the visitor
    137     * @param handler the handler
    138     * @param <T> the type of the nodes involved
    139     */
    140    private static <T> void bfs(final T root, final ConfigurationNodeVisitor<T> visitor,
    141            final NodeHandler<T> handler)
    142    {
    143        final List<T> pendingNodes = new LinkedList<>();
    144        pendingNodes.add(root);
    145        boolean cancel = false;
    146
    147        while (!pendingNodes.isEmpty() && !cancel)
    148        {
    149            final T node = pendingNodes.remove(0);
    150            visitor.visitBeforeChildren(node, handler);
    151            cancel = visitor.terminate();
    152            for (final T c : handler.getChildren(node))
    153            {
    154                pendingNodes.add(c);
    155            }
    156        }
    157    }
    158
    159    /**
    160     * Helper method for checking the parameters for the walk() methods. If
    161     * mandatory parameters are missing, an exception is thrown. The return
    162     * value indicates whether an operation can be performed.
    163     *
    164     * @param root the root node
    165     * @param visitor the visitor
    166     * @param handler the handler
    167     * @param <T> the type of the nodes involved
    168     * @return <b>true</b> if a walk operation can be performed, <b>false</b>
    169     *         otherwise
    170     * @throws IllegalArgumentException if a required parameter is missing
    171     */
    172    private static <T> boolean checkParameters(final T root,
    173            final ConfigurationNodeVisitor<T> visitor, final NodeHandler<T> handler)
    174    {
    175        if (visitor == null)
    176        {
    177            throw new IllegalArgumentException("Visitor must not be null!");
    178        }
    179        if (handler == null)
    180        {
    181            throw new IllegalArgumentException("NodeHandler must not be null!");
    182        }
    183        return root != null;
    184    }
    185}