commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "KARR, DAVID (ATTSI)" <dk0...@att.com>
Subject RE: [digester] Need help with simple digester usage
Date Fri, 14 Jan 2011 00:40:48 GMT
> -----Original Message-----
> From: Rahul Akolkar [mailto:rahul.akolkar@gmail.com]
> 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)
>     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);
        }
    }
}
-----------------------

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


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


Mime
View raw message