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)
+ }
+
}