commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Rahul Akolkar <rahul.akol...@gmail.com>
Subject Re: [digester] Need help with simple digester usage
Date Fri, 14 Jan 2011 03:41:56 GMT
On Thu, Jan 13, 2011 at 7:40 PM, KARR, DAVID (ATTSI) <dk068x@att.com> wrote:
>> -----Original Message-----
>> From: Rahul Akolkar
>> Sent: Thursday, January 13, 2011 2:07 PM
>> To: Commons Users List
>> Subject: Re: [digester] Need help with simple digester usage
>>
>> On Thu, Jan 13, 2011 at 12:39 PM, KARR, DAVID (ATTSI) <dk068x@att.com>
>> wrote:
>> >> -----Original Message-----
>> >> From: Rahul Akolkar
>> >> Sent: Monday, December 20, 2010 10:18 PM
>> >> To: Commons Users List
>> >> Subject: Re: [digester] Need help with simple digester usage
>> >>
>> >> On Mon, Dec 20, 2010 at 11:08 PM, KARR, DAVID (ATTSI)
>> <dk068x@att.com>
>> >> wrote:
>> >> >> -----Original Message-----
>> >> >> From: KARR, DAVID (ATTSI)
>> >> >> Sent: Monday, December 20, 2010 7:54 PM
>> >> >> To: user@commons.apache.org
>> >> >> Subject: [digester] Need help with simple digester usage
>> >> >>
>> >> >> I'm trying to use Digester for a simple application.  I want to
>> >> define
>> >> >> the structure of a binary tree in XML, and then construct that
>> node
>> >> >> tree
>> >> >> using Digester.
>> >> >>
>> >> >> The trivial "Node" class is just this:
>> >> >> --------------------
>> >> >>     public static class Node {
>> >> >>         private Node left;
>> >> >>         private Node right;
>> >> >>         private String value;
>> >> >>
>> >> >>         public Node getLeft() { return left; }
>> >> >>         public Node getRight() { return right; }
>> >> >>         public String getValue() { return value; }
>> >> >>
>> >> >>         public void setLeft(Node left) { this.left = left;
}
>> >> >>         public void setRight(Node right) { this.right = right;
}
>> >> >>         public void setValue(String value) { this.value = value;
>> }
>> >> >>     }
>> >> >> ------------
>> >> >>
>> >> >> The XML is composed of nested "node" elements.  The first "node"
>> >> child
>> >> >> gets set as the "left" property of the root, and the second gets
>> set
>> >> > as
>> >> >> the "right" property.
>> >> >>
>> >> >> For instance:
>> >> >>
>> >> >>   <node value="abc">
>> >> >>     <node value="def"/>
>> >> >>   </node>
>> >> >>
>> >> >> Should result in a root Node with a "left" property referring to
>> the
>> >> >> second node.
>> >> >>
>> >> >> So, going through the Digester documentation, which I haven't
>> looked
>> >> > at
>> >> >> in many years, I figured it would be something like this:
>> >> >>
>> >> >>         digester.addRule("*/node", new
>> >> >> ObjectCreateRule(AugmentedNode.class));
>> >> >>         digester.addRule("*/node", new SetPropertiesRule());
>> >> >>         digester.addRule("*/node", new SetNextRule("addChild",
>> >> >> AugmentedNode.class.getName()));
>> >> >>
>> >> >> Where "AugmentedNode" extends "Node", adding:
>> >> >>
>> >> >>        public void addChild(Node node) {
>> >> >>             if (getLeft() == null)
>> >> >>                 setLeft(node);
>> >> >>             else
>> >> >>                 setRight(node);
>> >> >>         }
>> >> >>
>> >> >> For those well steeped in Digester lore, I imagine you can
>> >> immediately
>> >> >> tell this won't work.  You're right, of course.  This dies with
>> an
>> >> NPE
>> >> >> in "MethodUtils.invokeMethod()" (object is null).  I have no clue
>> >> >> what's
>> >> >> wrong with this, or what I should be doing instead.
>> >> >
>> >> > Oh, ok.  I figured out one thing.  I have to push an AugmentedNode
>> on
>> >> > the stack before I start parsing, and then I take the result as
>> the
>> >> > "left" property of that top node.  Is that all I should have
>> figured
>> >> > out?  Is there a better way to do this in the first place?
>> >> >
>> >> <snip/>
>> >>
>> >> Add this as the first rule, then the parse method will get you the
>> >> actual (root) node:
>> >>
>> >>   digester.addRule("node", new
>> ObjectCreateRule(AugmentedNode.class));
>> >>
>> >> This calls out the root as different from other nodes -- the root
>> >> doesn't need a SetNextRule (thats the one causing the NPE since it
>> has
>> >> no parent).
>> >
>> > I'm still not quite sure how to transform my existing code so I can
>> use the top node, not the "left" of the top node.
>> >
>> > My existing code is this:
>> >
>> >        digester.push(new AugmentedNode());
>> >
>> >        digester.addRule("*/node", new
>> ObjectCreateRule(AugmentedNode.class));
>> >        digester.addRule("*/node", new SetPropertiesRule());
>> >        digester.addRule("*/node", new SetNextRule("addChild",
>> AugmentedNode.class.getName()));
>> >
>> >        return ((Node) digester.parse(new
>> StringReader(xml))).getLeft();
>> >
>> > I've tried several variations with adding that line you suggest, but
>> I can't get it to work, and I'm not sure exactly what it's trying to
>> accomplish.
>> >
>> <snip/>
>>
>> Try this, per previous email:
>>
>>     digester.addRule("node", new
>> ObjectCreateRule(AugmentedNode.class));
>>     // above line is better match for root (not using push)
<snip/>

Given the root node can also have a value attribute, need this (insert
after the line above):

    digester.addRule("node", new SetPropertiesRule());

-Rahul



>>     digester.addRule("*/node", new
>> ObjectCreateRule(AugmentedNode.class));
>>     digester.addRule("*/node", new SetPropertiesRule());
>>     digester.addRule("*/node", new SetNextRule("addChild",
>> AugmentedNode.class.getName()));
>>     return ((Node) digester.parse(new StringReader(xml)));
>>     // above line is without getLeft()
>
> That causes my tests to fail.  It appears as if it's not returning the root node, but
some other node.
>
> How about if I include my CUT and test class here?
> -----------------------
> package binarytree;
>
> import java.util.HashSet;
> import java.util.Set;
> import java.util.Stack;
>
> /**
>  * Perform pre, in, and post order traversal of a binary tree, using nonrecursive methods.
>  *
>  * Based on algorithms from <http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal>.
>  *
>  * @author dk068x
>  */
> public class NonRecursiveBinaryTreeTraversal {
>    /**
>     * Perform a preorder traversal.  This will process the data in the node before
processing the data in the
>     * left and right child.
>     */
>    public static void preOrder(Node rootNode, Visitor visitor) {
>        Stack<Node>   nodeStack   = new Stack<Node>();
>        nodeStack.push(rootNode);
>        while (!nodeStack.empty()) {
>            // At each level, we process the data in the node and then push the
right and left child and then repeat.
>            Node    node        = nodeStack.pop();
>            visitor.visit(node);
>            Node    rightNode    = node.getRight();
>            if (rightNode != null)
>                nodeStack.push(rightNode);
>            Node    leftNode    = node.getLeft();
>            if (leftNode != null)
>                nodeStack.push(leftNode);
>        }
>    }
>
>    /**
>     * Perform an inorder traversal. This will process the data in the node after processing
the data in the left child,
>     * and before processing the data in the right child.
>     */
>    public static void inOrder(Node rootNode, Visitor visitor) {
>        Stack<Node>   nodeStack   = new Stack<Node>();
>        Node    currentNode = rootNode;
>        while (true) {
>            // We walk the left branch, pushing nodes until we reach the end, then
we process the data at the top
>            // of the stack, then walk to the right child, and then repeat.
>            if (currentNode != null) {
>                nodeStack.push(currentNode);
>                currentNode = currentNode.getLeft();
>            }
>            else if (nodeStack.size() > 0){
>                currentNode = nodeStack.pop();
>                visitor.visit(currentNode);
>                currentNode = currentNode.getRight();
>            }
>            else
>                break;
>        }
>    }
>
>    /**
>     * Perform a postorder traversal.  This will process the data in the node after
processing the data in the left
>     * and right child.
>     */
>    public static void postOrder(Node rootNode, Visitor visitor) {
>        Stack<Node> nodeStack   = new Stack<Node>();
>        Set<Node>   visitedSet  = new HashSet<Node>();
>        nodeStack.push(rootNode);
>        while (!nodeStack.isEmpty()) {
>            // At each iteration, we peek at the top node, and push the left and
right child if they are not null,
>            // and we haven't visited those nodes.  If both left and right are
null OR we've visited both of them,
>            // then process the data in the current node (the one we've peeked at),
add it to the visited set,
>            // and pop it.
>            Node    node    = nodeStack.peek();
>            if (node.getLeft() != null && !visitedSet.contains(node.getLeft()))
>                nodeStack.push(node.getLeft());
>            else if (node.getRight() != null && !visitedSet.contains(node.getRight()))
>                nodeStack.push(node.getRight());
>            else {
>                visitor.visit(node);
>                visitedSet.add(node);
>                nodeStack.pop();
>            }
>        }
>    }
>
>    public static class PrintVisitor implements Visitor {
>        @Override
>        public void visit(Node node) {
>            System.out.println("node.value[" + node.getValue() + "]");
>        }
>    }
>
>    public static interface Visitor {
>        public void visit(Node node);
>    }
>
>    public static class Node {
>        private Node left;
>        private Node right;
>        private String value;
>
>        public Node getLeft() { return left; }
>        public Node getRight() { return right; }
>        public String getValue() { return value; }
>
>        public void setLeft(Node left) { this.left = left; }
>        public void setRight(Node right) { this.right = right; }
>        public void setValue(String value) { this.value = value; }
>    }
> }
> -----------------------
> package binarytree;
>
> import static org.junit.Assert.*;
>
> import java.io.IOException;
> import java.io.StringReader;
> import java.util.ArrayList;
> import java.util.List;
>
> import org.apache.commons.digester.Digester;
> import org.apache.commons.digester.ObjectCreateRule;
> import org.apache.commons.digester.SetNextRule;
> import org.apache.commons.digester.SetPropertiesRule;
> import org.junit.Test;
> import org.xml.sax.SAXException;
>
> import binarytree.NonRecursiveBinaryTreeTraversal.Node;
> import binarytree.NonRecursiveBinaryTreeTraversal.Visitor;
>
> public class NonRecursiveBinaryTreeTraversalTest {
>    @Test
>    public void testPreorderTrivial() throws Exception {
>        Node    rootNode    =
>            parseXml("<node value=\"1\">" +
>                     "</node>");
>        final List<String>  foundNodes          = new ArrayList<String>();
>        Visitor             addToListVisitor    = new AddToListVisitor(foundNodes);
>
>        NonRecursiveBinaryTreeTraversal.preOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "1");
>
>        NonRecursiveBinaryTreeTraversal.inOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "1");
>
>        NonRecursiveBinaryTreeTraversal.postOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "1");
>    }
>
>    @Test
>    public void testPreorderSimple1() throws Exception {
>        Node    rootNode    =
>            parseXml("<node value=\"1\">" +
>                     " <node value=\"2\"/>" +
>                     "</node>");
>        final List<String>  foundNodes          = new ArrayList<String>();
>        Visitor             addToListVisitor    = new AddToListVisitor(foundNodes);
>
>        NonRecursiveBinaryTreeTraversal.preOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "1", "2");
>
>        NonRecursiveBinaryTreeTraversal.inOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "2", "1");
>
>        NonRecursiveBinaryTreeTraversal.postOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "2", "1");
>    }
>
>    @Test
>    public void testPreorderSimple2() throws Exception {
>        Node    rootNode    =
>            parseXml("<node value=\"1\">" +
>                     " <node value=\"2\"/>" +
>                     " <node value=\"3\"/>" +
>                     "</node>");
>        final List<String>  foundNodes          = new ArrayList<String>();
>        Visitor             addToListVisitor    = new AddToListVisitor(foundNodes);
>
>        NonRecursiveBinaryTreeTraversal.preOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "1", "2", "3");
>
>        NonRecursiveBinaryTreeTraversal.inOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "2", "1", "3");
>
>        NonRecursiveBinaryTreeTraversal.postOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "2", "3", "1");
>    }
>
>    @Test
>    public void testPreorderSimple3() throws Exception {
>        Node    rootNode    =
>            parseXml("<node value=\"1\">" +
>                     " <node value=\"2\">" +
>                     "   <node value=\"3\"/>" +
>                     " </node>" +
>                     " <node value=\"4\"/>" +
>                     "</node>");
>        final List<String>  foundNodes          = new ArrayList<String>();
>        Visitor             addToListVisitor    = new AddToListVisitor(foundNodes);
>
>        NonRecursiveBinaryTreeTraversal.preOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "1", "2", "3", "4");
>
>        NonRecursiveBinaryTreeTraversal.inOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "3", "2", "1", "4");
>
>        NonRecursiveBinaryTreeTraversal.postOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "3", "2", "4", "1");
>    }
>
>    @Test
>    public void testPreorderSimple4() throws Exception {
>        Node    rootNode    =
>            parseXml("<node value=\"1\">" +
>                     " <node value=\"2\">" +
>                     "  <node value=\"4\"/>" +
>                     "  <node value=\"5\">" +
>                     "   <node value=\"8\"/>" +
>                     "  </node>" +
>                     " </node>" +
>                     " <node value=\"3\">" +
>                     "  <node value=\"6\"/>" +
>                     "  <node value=\"7\"/>" +
>                     " </node>" +
>                     "</node>");
>        final List<String>  foundNodes          = new ArrayList<String>();
>        Visitor             addToListVisitor    = new AddToListVisitor(foundNodes);
>
>        NonRecursiveBinaryTreeTraversal.preOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "1", "2", "4", "5", "8", "3", "6", "7");
>
>        NonRecursiveBinaryTreeTraversal.inOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "4", "2", "8", "5", "1", "6", "3", "7");
>
>        NonRecursiveBinaryTreeTraversal.postOrder(rootNode, addToListVisitor);
>        verifyOrder(foundNodes, "4", "8", "5", "2", "6", "7", "3", "1");
>    }
>
>    private void verifyOrder(List<String> foundOrder, String... requiredOrder)
{
>        if (requiredOrder.length != foundOrder.size())
>            fail("Found " +
>                    foundOrder.size() + " node" + (foundOrder.size() == 0 ?
"" : "s") +
>                    ", but needed " +
>                    requiredOrder.length + " node" + (requiredOrder.length ==
0 ? "" : "s") +
>                    ", with required order " + renderOrder(requiredOrder) +
" and found order " +
>                    renderOrder(foundOrder) + ".");
>        else {
>            for (int ctr = 0; ctr < foundOrder.size(); ++ ctr) {
>                if (!foundOrder.get(ctr).equals(requiredOrder[ctr])) {
>                    fail("Order entry " + ctr + " should have been " + requiredOrder[ctr]
+ ", but it was " +
>                            foundOrder.get(ctr) + ", required order " +
renderOrder(requiredOrder) +
>                            " and found order " + renderOrder(foundOrder)
+ ".");
>                }
>            }
>        }
>
>        // This is a side effect for the convenience of the tests.
>        foundOrder.clear();
>    }
>
>    private String renderOrder(String[] strs) {
>        StringBuilder   sb  = new StringBuilder();
>        for (int ctr = 0; ctr < strs.length; ++ ctr) {
>            sb.append(strs[ctr]);
>            if (ctr < strs.length - 1)
>                sb.append(", ");
>        }
>        return sb.toString();
>    }
>
>    private String renderOrder(List<String> strs) {
>        return renderOrder(strs.toArray(new String[strs.size()]));
>    }
>
>    private Node    parseXml(String xml) throws IOException, SAXException {
>        Digester    digester    = new Digester();
>
>        // The easiest way to do this with Digester is to push a fake node on the
top of the stack.  The "left"
>        // property of that node will be the resulting tree. Also note that we have
to define a Node subclass with a
>        // single method to add a child, and it figures out whether to add the child
as the left or the right property.
>
>        // digester.push(new AugmentedNode());
>
> //        digester.addRule("node", new ObjectCreateRule(AugmentedNode.class));
>        digester.addRule("*/node", new ObjectCreateRule(AugmentedNode.class));
>        digester.addRule("*/node", new SetPropertiesRule());
>        digester.addRule("*/node", new SetNextRule("addChild", AugmentedNode.class.getName()));
>
>        return ((Node) digester.parse(new StringReader(xml))).getLeft();
> //        return ((Node) digester.parse(new StringReader(xml)));
>    }
>
>    public static class AddToListVisitor implements Visitor {
>        private List<String>    list;
>
>        public AddToListVisitor(List<String> list) {
>            this.list   = list;
>        }
>
>        @Override
>        public void visit(Node node) {
>            list.add(node.getValue());
>        }
>    }
>
>    public static class AugmentedNode extends Node {
>        public void addChild(Node node) {
>            if (getLeft() == null)
>                setLeft(node);
>            else
>                setRight(node);
>        }
>    }
> }
> -----------------------

---------------------------------------------------------------------
To unsubscribe, e-mail: user-unsubscribe@commons.apache.org
For additional commands, e-mail: user-help@commons.apache.org


Mime
View raw message