You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@groovy.apache.org by pa...@apache.org on 2015/07/14 12:53:11 UTC

incubator-groovy git commit: GROOVY-7486: In groovy.util.Node.depthFirst please Provide a way to Specify pre-order, post-order Ordering

Repository: incubator-groovy
Updated Branches:
  refs/heads/master 451d73717 -> 56232fe48


GROOVY-7486: In groovy.util.Node.depthFirst please Provide a way to Specify pre-order, post-order Ordering


Project: http://git-wip-us.apache.org/repos/asf/incubator-groovy/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-groovy/commit/56232fe4
Tree: http://git-wip-us.apache.org/repos/asf/incubator-groovy/tree/56232fe4
Diff: http://git-wip-us.apache.org/repos/asf/incubator-groovy/diff/56232fe4

Branch: refs/heads/master
Commit: 56232fe482e16f8af28769b2bb1f3163f7b7c2db
Parents: 451d737
Author: Paul King <pa...@asert.com.au>
Authored: Sat Jul 11 08:27:04 2015 +1000
Committer: Paul King <pa...@asert.com.au>
Committed: Tue Jul 14 20:50:42 2015 +1000

----------------------------------------------------------------------
 src/main/groovy/util/Node.java             | 63 ++++++++++++++++++++-----
 src/test/groovy/tree/NavigationTest.groovy | 62 ++++++++++++++++--------
 2 files changed, 92 insertions(+), 33 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/incubator-groovy/blob/56232fe4/src/main/groovy/util/Node.java
----------------------------------------------------------------------
diff --git a/src/main/groovy/util/Node.java b/src/main/groovy/util/Node.java
index 03f2a1e..47a23ef 100644
--- a/src/main/groovy/util/Node.java
+++ b/src/main/groovy/util/Node.java
@@ -23,6 +23,7 @@ import groovy.lang.DelegatingMetaClass;
 import groovy.lang.GroovySystem;
 import groovy.lang.MetaClass;
 import groovy.xml.QName;
+import org.codehaus.groovy.runtime.DefaultGroovyMethods;
 import org.codehaus.groovy.runtime.InvokerHelper;
 
 import java.io.PrintWriter;
@@ -33,6 +34,7 @@ import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
+import java.util.Stack;
 
 /**
  * Represents an arbitrary tree node which can be used for structured metadata or any arbitrary XML-like tree.
@@ -537,26 +539,40 @@ public class Node implements Serializable, Cloneable {
 
     /**
      * Provides a collection of all the nodes in the tree
-     * using a depth first traversal.
+     * using a depth-first preorder traversal.
      *
      * @return the list of (depth-first) ordered nodes
      */
     public List depthFirst() {
+        return depthFirst(true);
+    }
+
+    /**
+     * Provides a collection of all the nodes in the tree
+     * using a depth-first traversal.
+     *
+     * @param preorder if false, a postorder depth-first traversal will be performed
+     * @return the list of (depth-first) ordered nodes
+     * @since 2.5.0
+     */
+    public List depthFirst(boolean preorder) {
         List answer = new NodeList();
-        answer.add(this);
-        answer.addAll(depthFirstRest());
+        if (preorder) answer.add(this);
+        answer.addAll(depthFirstRest(preorder));
+        if (!preorder) answer.add(this);
         return answer;
     }
 
-    private List depthFirstRest() {
+    private List depthFirstRest(boolean preorder) {
         List answer = new NodeList();
         for (Iterator iter = InvokerHelper.asIterator(value); iter.hasNext(); ) {
             Object child = iter.next();
             if (child instanceof Node) {
                 Node childNode = (Node) child;
-                List children = childNode.depthFirstRest();
-                answer.add(childNode);
+                List children = childNode.depthFirstRest(preorder);
+                if (preorder) answer.add(childNode);
                 if (children.size() > 1 || (children.size() == 1 && !(children.get(0) instanceof String))) answer.addAll(children);
+                if (!preorder) answer.add(childNode);
             } else if (child instanceof String) {
                 answer.add(child);
             }
@@ -566,32 +582,53 @@ public class Node implements Serializable, Cloneable {
 
     /**
      * Provides a collection of all the nodes in the tree
-     * using a breadth-first traversal.
+     * using a breadth-first preorder traversal.
      *
      * @return the list of (breadth-first) ordered nodes
      */
     public List breadthFirst() {
+        return breadthFirst(true);
+    }
+
+    /**
+     * Provides a collection of all the nodes in the tree
+     * using a breadth-first traversal.
+     *
+     * @param preorder if false, a postorder breadth-first traversal will be performed
+     * @return the list of (breadth-first) ordered nodes
+     * @since 2.5.0
+     */
+    public List breadthFirst(boolean preorder) {
         List answer = new NodeList();
-        answer.add(this);
-        answer.addAll(breadthFirstRest());
+        if (preorder) answer.add(this);
+        answer.addAll(breadthFirstRest(preorder));
+        if (!preorder) answer.add(this);
         return answer;
     }
 
-    private List breadthFirstRest() {
+    private List breadthFirstRest(boolean preorder) {
         List answer = new NodeList();
-        List nextLevelChildren = getDirectChildren();
+        Stack stack = new Stack();
+        List nextLevelChildren = preorder ? getDirectChildren() : DefaultGroovyMethods.reverse(getDirectChildren());
         while (!nextLevelChildren.isEmpty()) {
             List working = new NodeList(nextLevelChildren);
             nextLevelChildren = new NodeList();
             for (Object child : working) {
-                answer.add(child);
+                if (preorder) {
+                    answer.add(child);
+                } else {
+                    stack.push(child);
+                }
                 if (child instanceof Node) {
                     Node childNode = (Node) child;
                     List children = childNode.getDirectChildren();
-                    if (children.size() > 1 || (children.size() == 1 && !(children.get(0) instanceof String))) nextLevelChildren.addAll(children);
+                    if (children.size() > 1 || (children.size() == 1 && !(children.get(0) instanceof String))) nextLevelChildren.addAll(preorder ? children : DefaultGroovyMethods.reverse(children));
                 }
             }
         }
+        while (!stack.isEmpty()) {
+            answer.add(stack.pop());
+        }
         return answer;
     }
 

http://git-wip-us.apache.org/repos/asf/incubator-groovy/blob/56232fe4/src/test/groovy/tree/NavigationTest.groovy
----------------------------------------------------------------------
diff --git a/src/test/groovy/tree/NavigationTest.groovy b/src/test/groovy/tree/NavigationTest.groovy
index 3e88c8e..d49d79b 100644
--- a/src/test/groovy/tree/NavigationTest.groovy
+++ b/src/test/groovy/tree/NavigationTest.groovy
@@ -22,29 +22,37 @@ package groovy.tree
  * Simple test of tree walking
  */
 class NavigationTest extends GroovyTestCase {
-    
+
     void testDepthFirst() {
-        def tree = createTree()
-        
+        def tree = createTreeFromNodeBuilder()
         def names = tree.depthFirst().collect { it.name() }
-        def expected = ['a', 'b1', 'b2', 'c1', 'c2', 'b3', 'b4', 'c3', 'c4', 'b5']
-        
-        assert names == expected
+        assert names == ['a', 'b1', 'b2', 'c1', 'c2', 'b3', 'b4', 'c3', 'c4', 'b5']
     }
-    
+
     void testBreadthFirst() {
-        def tree = createTree()
-        
+        def tree = createTreeFromNodeBuilder()
         def names = tree.breadthFirst().collect { it.name() }
-        def expected = ['a', 'b1', 'b2', 'b3', 'b4', 'b5', 'c1', 'c2', 'c3', 'c4']
-        
-        assert names == expected
+        assert names == ['a', 'b1', 'b2', 'b3', 'b4', 'b5', 'c1', 'c2', 'c3', 'c4']
+    }
+
+    void testPrePostOrder() {
+        def root = createTreeFromXmlParser()
+        def combos = [[false, true], ['depthFirst', 'breadthFirst']].combinations()
+        def actual = combos.collect{ preorder, type ->
+            root."$type"(preorder)*.name()
+        }*.toString()
+        def expected = [
+            '[child1a, child1b, parent1, child2a, grandchild2, child2b, child2c, parent2, root]', // df post
+            '[root, parent1, child1a, child1b, parent2, child2a, child2b, grandchild2, child2c]', // df pre
+            '[grandchild2, child1a, child1b, child2a, child2b, child2c, parent1, parent2, root]', // bf post
+            '[root, parent1, parent2, child1a, child1b, child2a, child2b, child2c, grandchild2]'  // bf pre
+        ]
+        (0..3).each{ assert actual[it] == expected[it] }
     }
-    
-    protected def createTree() {       
+
+    private static createTreeFromNodeBuilder() {
         def b = NodeBuilder.newInstance()
-        
-        def root = b.a(a:5, b:7) {
+        def root = b.a(a: 5, b: 7) {
             b1()
             b2 {
                 c1()
@@ -57,11 +65,25 @@ class NavigationTest extends GroovyTestCase {
             }
             b5()
         }
-        
         assert root != null
-        
-        println(root)
-        
         return root
     }
+
+    private static createTreeFromXmlParser() {
+        def xml = '''
+        <root>
+          <parent1>
+            <child1a/>
+            <child1b/>
+          </parent1>
+          <parent2>
+            <child2a/>
+            <child2b><grandchild2/></child2b>
+            <child2c/>
+          </parent2>
+        </root>
+        '''
+        new XmlParser().parseText(xml)
+    }
+
 }