commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ohe...@apache.org
Subject svn commit: r1570345 - in /commons/proper/configuration/branches/immutableNodes/src: main/java/org/apache/commons/configuration/tree/NodeTreeWalker.java test/java/org/apache/commons/configuration/tree/TestNodeTreeWalker.java
Date Thu, 20 Feb 2014 20:46:46 GMT
Author: oheger
Date: Thu Feb 20 20:46:46 2014
New Revision: 1570345

URL: http://svn.apache.org/r1570345
Log:
Added NodeTreeWalker class.

This class implements functionality for traversing nodes structures using a
ConfigurationNodeVisitor. Multiple traversal strategies are provided.

Added:
    commons/proper/configuration/branches/immutableNodes/src/main/java/org/apache/commons/configuration/tree/NodeTreeWalker.java
    commons/proper/configuration/branches/immutableNodes/src/test/java/org/apache/commons/configuration/tree/TestNodeTreeWalker.java

Added: commons/proper/configuration/branches/immutableNodes/src/main/java/org/apache/commons/configuration/tree/NodeTreeWalker.java
URL: http://svn.apache.org/viewvc/commons/proper/configuration/branches/immutableNodes/src/main/java/org/apache/commons/configuration/tree/NodeTreeWalker.java?rev=1570345&view=auto
==============================================================================
--- commons/proper/configuration/branches/immutableNodes/src/main/java/org/apache/commons/configuration/tree/NodeTreeWalker.java
(added)
+++ commons/proper/configuration/branches/immutableNodes/src/main/java/org/apache/commons/configuration/tree/NodeTreeWalker.java
Thu Feb 20 20:46:46 2014
@@ -0,0 +1,185 @@
+/*
+ * 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.configuration.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>
+ *
+ * @version $Id$
+ * @since 2.0
+ */
+public class NodeTreeWalker
+{
+    /** The default instance of this class. */
+    public static final NodeTreeWalker INSTANCE = new NodeTreeWalker();
+
+    /**
+     * 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(T root, ConfigurationNodeVisitor<T> visitor,
+            NodeHandler<T> handler)
+    {
+        if (checkParameters(root, visitor, handler))
+        {
+            dfs(root, visitor, 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(T root, ConfigurationNodeVisitor<T> visitor,
+            NodeHandler<T> handler)
+    {
+        if (checkParameters(root, visitor, handler))
+        {
+            bfs(root, visitor, handler);
+        }
+    }
+
+    /**
+     * 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(T node, ConfigurationNodeVisitor<T> visitor,
+            NodeHandler<T> handler)
+    {
+        if (!visitor.terminate())
+        {
+            visitor.visitBeforeChildren(node, handler);
+            for (T c : handler.getChildren(node))
+            {
+                dfs(c, visitor, handler);
+            }
+            if (!visitor.terminate())
+            {
+                visitor.visitAfterChildren(node, handler);
+            }
+        }
+    }
+
+    /**
+     * 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(T root, ConfigurationNodeVisitor<T> visitor,
+            NodeHandler<T> handler)
+    {
+        List<T> pendingNodes = new LinkedList<T>();
+        pendingNodes.add(root);
+        boolean cancel = false;
+
+        while (!pendingNodes.isEmpty() && !cancel)
+        {
+            T node = pendingNodes.remove(0);
+            visitor.visitBeforeChildren(node, handler);
+            cancel = visitor.terminate();
+            for (T c : handler.getChildren(node))
+            {
+                pendingNodes.add(c);
+            }
+        }
+    }
+
+    /**
+     * 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(T root,
+            ConfigurationNodeVisitor<T> visitor, 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;
+    }
+}

Added: commons/proper/configuration/branches/immutableNodes/src/test/java/org/apache/commons/configuration/tree/TestNodeTreeWalker.java
URL: http://svn.apache.org/viewvc/commons/proper/configuration/branches/immutableNodes/src/test/java/org/apache/commons/configuration/tree/TestNodeTreeWalker.java?rev=1570345&view=auto
==============================================================================
--- commons/proper/configuration/branches/immutableNodes/src/test/java/org/apache/commons/configuration/tree/TestNodeTreeWalker.java
(added)
+++ commons/proper/configuration/branches/immutableNodes/src/test/java/org/apache/commons/configuration/tree/TestNodeTreeWalker.java
Thu Feb 20 20:46:46 2014
@@ -0,0 +1,301 @@
+/*
+ * 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.configuration.tree;
+
+import static org.junit.Assert.assertEquals;
+
+import java.util.LinkedList;
+import java.util.List;
+
+import org.easymock.EasyMock;
+import org.junit.Test;
+
+/**
+ * Test class for {@code NodeTreeWalker}.
+ *
+ * @version $Id$
+ */
+public class TestNodeTreeWalker
+{
+    /**
+     * Generates a name which indicates that the corresponding node was visited
+     * after its children.
+     *
+     * @param name the node name to be decorated
+     * @return the name with the after indicator
+     */
+    private static String visitAfterName(String name)
+    {
+        return "->" + name;
+    }
+
+    /**
+     * Creates a mock for a visitor.
+     *
+     * @return the visitor mock
+     */
+    private static ConfigurationNodeVisitor<ImmutableNode> visitorMock()
+    {
+        @SuppressWarnings("unchecked")
+        ConfigurationNodeVisitor<ImmutableNode> visitor =
+                EasyMock.createMock(ConfigurationNodeVisitor.class);
+        return visitor;
+    }
+
+    /**
+     * Creates a mock for a node handler.
+     *
+     * @return the handler mock
+     */
+    private static NodeHandler<ImmutableNode> handlerMock()
+    {
+        @SuppressWarnings("unchecked")
+        NodeHandler<ImmutableNode> handler =
+                EasyMock.createMock(NodeHandler.class);
+        return handler;
+    }
+
+    /**
+     * Tries a walk() operation without a node handler.
+     */
+    @Test(expected = IllegalArgumentException.class)
+    public void testWalkNoNodeHandler()
+    {
+        NodeTreeWalker.INSTANCE.walkDFS(NodeStructureHelper.ROOT_AUTHORS_TREE,
+                new TestVisitor(), null);
+    }
+
+    /**
+     * Tries a walk operation without a visitor.
+     */
+    @Test(expected = IllegalArgumentException.class)
+    public void testWalkNoVisitor()
+    {
+        NodeTreeWalker.INSTANCE.walkDFS(NodeStructureHelper.ROOT_AUTHORS_TREE,
+                null, new InMemoryNodeModel());
+    }
+
+    /**
+     * Tests whether walkDFS() can handle a null node.
+     */
+    @Test
+    public void testWalkDFSNoNode()
+    {
+        ConfigurationNodeVisitor<ImmutableNode> visitor = visitorMock();
+        NodeHandler<ImmutableNode> handler = handlerMock();
+        EasyMock.replay(visitor, handler);
+        NodeTreeWalker.INSTANCE.walkDFS(null, visitor, handler);
+    }
+
+    /**
+     * Tests a DFS traversal.
+     */
+    @Test
+    public void testWalkDFS()
+    {
+        List<String> expected = expectDFS();
+        TestVisitor visitor = new TestVisitor();
+        NodeTreeWalker.INSTANCE.walkDFS(NodeStructureHelper.ROOT_AUTHORS_TREE,
+                visitor, new InMemoryNodeModel());
+        assertEquals("Wrong visited nodes", expected, visitor.getVisitedNodes());
+    }
+
+    /**
+     * Prepares a list with the names of nodes encountered during a DFS walk.
+     *
+     * @return the expected node names in DFS mode
+     */
+    private List<String> expectDFS()
+    {
+        List<String> expected = new LinkedList<String>();
+        expected.add(NodeStructureHelper.ROOT_AUTHORS_TREE.getNodeName());
+        for (int authorIdx = 0; authorIdx < NodeStructureHelper.authorsLength(); authorIdx++)
+        {
+            expected.add(NodeStructureHelper.author(authorIdx));
+            for (int workIdx = 0; workIdx < NodeStructureHelper
+                    .worksLength(authorIdx); workIdx++)
+            {
+                expected.add(NodeStructureHelper.work(authorIdx, workIdx));
+                for (int personaIdx = 0; personaIdx < NodeStructureHelper
+                        .personaeLength(authorIdx, workIdx); personaIdx++)
+                {
+                    String persona =
+                            NodeStructureHelper.persona(authorIdx, workIdx,
+                                    personaIdx);
+                    expected.add(persona);
+                    expected.add(visitAfterName(persona));
+                }
+                expected.add(visitAfterName(NodeStructureHelper.work(authorIdx,
+                        workIdx)));
+            }
+            expected.add(visitAfterName(NodeStructureHelper.author(authorIdx)));
+        }
+        expected.add(visitAfterName(NodeStructureHelper.ROOT_AUTHORS_TREE
+                .getNodeName()));
+        return expected;
+    }
+
+    /**
+     * Tests whether the terminate flag is taken into account during a DFS walk.
+     */
+    @Test
+    public void testWalkDFSTerminate()
+    {
+        TestVisitor visitor = new TestVisitor();
+        final int nodeCount = 5;
+        visitor.setMaxNodeCount(nodeCount);
+        NodeTreeWalker.INSTANCE.walkDFS(NodeStructureHelper.ROOT_AUTHORS_TREE,
+                visitor, new InMemoryNodeModel());
+        assertEquals("Wrong number of visited nodes", nodeCount, visitor
+                .getVisitedNodes().size());
+    }
+
+    /**
+     * Tests a BFS walk if node is passed in.
+     */
+    @Test
+    public void testWalkBFSNoNode()
+    {
+        ConfigurationNodeVisitor<ImmutableNode> visitor = visitorMock();
+        NodeHandler<ImmutableNode> handler = handlerMock();
+        EasyMock.replay(visitor, handler);
+        NodeTreeWalker.INSTANCE.walkBFS(null, visitor, handler);
+    }
+
+    /**
+     * Tests a traversal in BFS mode.
+     */
+    @Test
+    public void testWalkBFS()
+    {
+        List<String> expected = expectBFS();
+        TestVisitor visitor = new TestVisitor();
+        NodeTreeWalker.INSTANCE.walkBFS(NodeStructureHelper.ROOT_AUTHORS_TREE,
+                visitor, new InMemoryNodeModel());
+        assertEquals("Wrong visited nodes", expected, visitor.getVisitedNodes());
+    }
+
+    /**
+     * Prepares a list with the names of nodes encountered during a BFS walk.
+     *
+     * @return the expected node names in BFS mode
+     */
+    private List<String> expectBFS()
+    {
+        List<String> expected = new LinkedList<String>();
+        List<String> works = new LinkedList<String>();
+        List<String> personae = new LinkedList<String>();
+        expected.add(NodeStructureHelper.ROOT_AUTHORS_TREE.getNodeName());
+        for (int authorIdx = 0; authorIdx < NodeStructureHelper.authorsLength(); authorIdx++)
+        {
+            expected.add(NodeStructureHelper.author(authorIdx));
+            for (int workIdx = 0; workIdx < NodeStructureHelper
+                    .worksLength(authorIdx); workIdx++)
+            {
+                works.add(NodeStructureHelper.work(authorIdx, workIdx));
+                for (int personIdx = 0; personIdx < NodeStructureHelper
+                        .personaeLength(authorIdx, workIdx); personIdx++)
+                {
+                    personae.add(NodeStructureHelper.persona(authorIdx,
+                            workIdx, personIdx));
+                }
+            }
+        }
+        expected.addAll(works);
+        expected.addAll(personae);
+        return expected;
+    }
+
+    /**
+     * Tests whether the terminate flag is evaluated in BFS mode.
+     */
+    @Test
+    public void testWalkBFSTerminate()
+    {
+        TestVisitor visitor = new TestVisitor();
+        final int nodeCount = 9;
+        visitor.setMaxNodeCount(nodeCount);
+        NodeTreeWalker.INSTANCE.walkBFS(NodeStructureHelper.ROOT_AUTHORS_TREE,
+                visitor, new InMemoryNodeModel());
+        assertEquals("Wrong number of visited nodes", nodeCount, visitor
+                .getVisitedNodes().size());
+    }
+
+    /**
+     * A visitor implementation used for testing purposes. The visitor produces
+     * a list with the names of the nodes visited in the order it was called.
+     * With this it can be tested whether the nodes were visited in the correct
+     * order.
+     */
+    private static class TestVisitor implements
+            ConfigurationNodeVisitor<ImmutableNode>
+    {
+        /** A list with the names of the visited nodes. */
+        private final List<String> visitedNodes = new LinkedList<String>();
+
+        /** The maximum number of nodes to be visited. */
+        private int maxNodeCount = Integer.MAX_VALUE;
+
+        /**
+         * Returns the list with the names of the visited nodes.
+         *
+         * @return the visit list
+         */
+        public List<String> getVisitedNodes()
+        {
+            return visitedNodes;
+        }
+
+        /**
+         * Returns the maximum number of nodes visited by this visitor.
+         *
+         * @return the maximum number of nodes
+         */
+        public int getMaxNodeCount()
+        {
+            return maxNodeCount;
+        }
+
+        /**
+         * Sets the maximum number of nodes to be visited. After this the
+         * terminate flag is set.
+         *
+         * @param maxNodeCount the maximum number of nodes
+         */
+        public void setMaxNodeCount(int maxNodeCount)
+        {
+            this.maxNodeCount = maxNodeCount;
+        }
+
+        public void visitBeforeChildren(ImmutableNode node,
+                NodeHandler<ImmutableNode> handler)
+        {
+            visitedNodes.add(handler.nodeName(node));
+        }
+
+        public void visitAfterChildren(ImmutableNode node,
+                NodeHandler<ImmutableNode> handler)
+        {
+            visitedNodes.add(visitAfterName(handler.nodeName(node)));
+        }
+
+        public boolean terminate()
+        {
+            return visitedNodes.size() >= getMaxNodeCount();
+        }
+    }
+}



Mime
View raw message