How To Iterate over an MinXML Tree

Processing a Tree of Elements

On this page we look at the convenience classes that simplify doing something recursively to the elements of a tree. The diagram below shows a simple tree-of-elements and the MinXML expression that generates it, which we will use as a running example.

tree.png

We can construct this EXAMPLE_TREE as follows:

    import com.steelypip.powerups.minxml.FlexiMinXML;
    ...
    MinXML EXAMPLE = FlexiMinXML.fromString( '<A><B><C/><D/></B><E><F/><G/></E></A>' );

MinXMLWalker: Walking an MinXML Tree

'Walking' means all doing something to all the elements of a tree in turn. We provide a convenience class called MinXMLWalker to encapsulate this simple recursive algorithm. The order in which MinXMLWalker processes elements is depth-first and left-to-right. In fact each element is visited twice, once on the way "down" and once on the way "up", as shown in the diagram below, corresponding to the start and end tags of the rendered XML in fact.

path.png

To use the class MinXMLWalker, you need to implement a derived class that overrides the startWalk and endWalk abstract methods. You then create an instance of the class and apply the walk method to a MinXML element that you want to process.

    static class CountElements extends MinXMLWalker {
 
        int count = 0;
 
        public int getCount() {
            return count;
        }
 
        @Override
        public void startWalk( MinXML subject ) {
            this.count += 1;
        }
 
        @Override
        public void endWalk( MinXML subject ) {
        }        
 
    }
 
    System.out.println( new CountElements().walk( EXAMPLE ).getCount() ); // Will print 7.

Searching an MinXML Tree

By contrast, 'searching' gives you a bit more control over which nodes you visit. We provide MinXMLSearcher that gives you control the continuation of the search by a cutoff (or 'found') flag. The intention is that when you find a node that satisfies some search criteria, you can skip recursively scanning the children or other siblings.

To use the class MinXMLSearcher, you need to implement a derived class that overrides the startSearch and endSearch abstract methods. You then create an instance of the class and apply the search method to a MinXML element that you want to process.

This may sound a very like the MinXMLWalker class we introduced in the previous section: the difference is that how the cutoff flags get passed around. The startSearch method has the signature boolean startSearch(); when it returns true the algorithm skips searching the children. The endSearch method has the signature boolean endSearch( boolean skipped_children ); it is passed the value that startSearch returned, which it is free to ignore, and if it returns true then the unprocessed siblings are skipped.

The most straightforward use of the MinXMLSearcher class is to implement a simple search. For example, we could process our example tree looking for an element whose name was "B". We wouldn't have to look far, so we would want to cut our search off early:

    static class FindB extends MinXMLSearcher {
 
        StringBuilder visited = new StringBuilder();
 
        public String getVisited() {
            return visited.toString();
        }
 
        @Override
        public boolean startSearch( MinXML subject ) {
            visited.append( subject.getName() );
            return "B".equals( subject.getName() );
        }
 
        @Override
        public boolean endSearch( MinXML subject, boolean found ) {
            return found;
        }        
 
    }
 
    FindB f = new FindB();
    MinXML b = f.search( EXAMPLE );
    System.out.println( b );  // Will print <b><c/><d/></b>
    System.out.println( f.getVisited() ); // Will print AB.

The above code only searches nodes A & B in our example. The search starts at A, calling startSearch and then moves onto the first child B and calls startSearch again. This time it discovers that B is the node it is looking for and returns true, causing the algorithm to skip the children C and D. Then the endSearch method is called on B, which simply passes up the true value. This signals to the algorithm that any other siblings of B should be skipped, so E is skipped and the search backs up to A, calling endSearch.

Note that the value returned from search is the element we were looking for. If the search had failed this would have been null.

The MinXMLSearcher class isn't just for searching, it's a way of guiding the processing of an element tree. This is important to remember in the context of the next section, which linearises the processing.

Turning an MinXML Tree into a List (actually an Iterable)

Sometimes it is helpful to be able to turn a recursive scan into a linear scan. Both MinXMLWalker and MinXMLSearcher can convert an element tree into a sequence of elements. In fact the two methods preOrder and postOrder return an Iterable<MinXML>, which is suitable for use in a for-each loop.

The difference between the two methods is that preOrder yields the elements in the order that startWalk /startSearch gets applied whereas postOrder yields elements in the order that endWalk/{endSearch}} gets applied.

For instance, if we take a pre-order walk of our example tree, we will see the elements in alphabetical order ABCDEFG. A post-order walk will include the elements in the order CDBFGEA.

    static class IdWalker extends MinXMLWalker {
 
        @Override
        public void startWalk( MinXML subject ) {
        }
 
        @Override
        public void endWalk( MinXML subject ) {
        }
 
    }
 
    {
        StringBuilder b = new StringBuilder();
        for ( MinXML m : new IdWalker().preOrder( EXAMPLE ) ) {
            b.append( m.getName() );
        }
        System.out.println( b.toString() );  // prints ABCDEFG
    }
    {
        StringBuilder b = new StringBuilder();
        for ( MinXML m : new IdWalker().postOrder( EXAMPLE ) ) {
            b.append( m.getName() );
        }
        System.out.println( b.toString() );  // prints CDBFGEA
    }

We can use the FindB example code above to illustrate pre-order and post-order traversals for a MinXMLSearcher:

    StringBuilder pre_order = new StringBuilder();
    for ( MinXML m : new Find().preOrder( EXAMPLE ) ) {
        pre_order.append( m.getName() );
    }
    System.out.println( pre_order.toString() );     // prints AB
 
    StringBuilder post_order = new StringBuilder();
    for ( MinXML m : new Find().postOrder( EXAMPLE ) ) {
        post_order.append( m.getName() );
    }
    System.out.println( post_order.toString() );     // prints BA!

Note that a pre-order traversal applies startWalk/startSearch to an element before it yields it in the iterable. Similarly a post-order traversal applies endWalk/endSearch to an element before it is yielded.