Recipe5.7.Performing a Level-Order Traversal


Recipe 5.7. Performing a Level-Order Traversal

Problem

You want to order elements by increasing level (tree depth). In other words, you want to traverse the tree breadth first.

Solution

This form of traversal is tailor-made for using xsl:for-each along with xsl:sort:

<xsl:for-each select="//*">      <xsl:sort select="count(ancestor::*)" data-type="number"/>      <!--  process the current element --> </xsl:for-each>

This recursive solution is longer and less obvious:

<xsl:template match="/*">      <xsl:call-template name="level-order"/> </xsl:template>     <xsl:template name="level-order"> <xsl:param name="max-level" select="10"/> <xsl:param name="current-level" select="1"/>     <xsl:choose>      <xsl:when test="$current-depth &lt;= $max-level">           <!-- process the current level -->           <xsl:call-template name="level-order-aux">                <xsl:with-param name="level"                           select="$current-level"/>                <xsl:with-param name="actual-level"                           select="$current-level"/>           </xsl:call-template>           <!-- process the next level -->           <xsl:call-template name="level-order">                <xsl:with-param name="current-level"                           select="$current-level + 1"/>           </xsl:call-template>      </xsl:when> </xsl:choose>     </xsl:template>     <xsl:template name="level-order-aux">      <xsl:param name="level" select="1"/>      <xsl:param name="actual-level" select="1"/>      <xsl:choose>           <xsl:when test="$level = 1">                <!-- Process the current element here -->                <!-- $actual-level is the number of the current level -->           </xsl:when>           <xsl:otherwise>                <!-- Recursively descend to the next level on                      all children -->                <xsl:for-each select="*">                     <xsl:call-template name="level-order-aux">                          <xsl:with-param name="level"                                select="$level - 1"/>                          <xsl:with-param name="actual-level"                               select="$actual-level"/>                     </xsl:call-template>                </xsl:for-each>           </xsl:otherwise>      </xsl:choose> </xsl:template>

This solution requires that you either set an arbitrary bound for the maximum depth of the tree or compute the maximum depth. One way of doing so is by finding the node that has no children and more ancestors than any other node without children:

<xsl:param name="max-level">   <xsl:for-each select="//*[not(*)]">     <xsl:sort select="count(ancestor::*)" data-type="number" order="descending" />     <xsl:if test="position( ) = 1">       <xsl:value-of select="count(ancestor::*) + 1" />     </xsl:if>   </xsl:for-each> </xsl:param>

Discussion

Arguably, the need to traverse an XML document by level does not arise often. Grouping nodes by depth or distance from the root does not fit into XSLT's natural control flow, which is organized to express traversals that descend the document tree. This is apparent by the fact that that you had to use xsl:sort to coerce the stylesheet to process nodes by their depth or, equivalently, the number of ancestors. The complexity of the recursive solution provides further evidence of this unnatural process.

Still, this form of traversal is sometimes handy. For example, you can use it to process an organizational chart that lists employees by their distance from the top spot, as shown in Example 5-11. The output is shown in Example 5-12.

Example 5-13. Level-order traversal of orgrchart.xml using sort
<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">      <xsl:output method="text"/>     <xsl:template match="/">   <xsl:for-each select="//employee">     <xsl:sort select="count(ancestor::*)" order="ascending"/>     <xsl:variable name="level" select="count(ancestor::*)"/>     <xsl:choose>       <xsl:when test="$level = 0">         <xsl:value-of select="@name"/>         <xsl:text> is the head honcho.&#xA;</xsl:text>       </xsl:when>        <xsl:otherwise>          <xsl:value-of select="@name"/>        <xsl:text> has </xsl:text>        <xsl:value-of select="$level"/>        <xsl:text> boss(es) to knock off.&#xA;</xsl:text>      </xsl:otherwise>     </xsl:choose>   </xsl:for-each> </xsl:template>     </xsl:stylesheet>

Example 5-14. Output
Jil Michel is the head honcho. Nancy Pratt has 1 boss(es) to knock off. Jane Doe has 1 boss(es) to knock off. Mike Rosenbaum has 1 boss(es) to knock off. Phill McKraken has 2 boss(es) to knock off. Ima Little has 2 boss(es) to knock off. Walter H. Potter has 2 boss(es) to knock off. Wendy B.K. McDonald has 2 boss(es) to knock off. Cindy Post-Kellog has 2 boss(es) to knock off. Oscar A. Winner has 2 boss(es) to knock off. Betsy Ross has 3 boss(es) to knock off. Craig F. Frye has 3 boss(es) to knock off. Hardy Hamburg has 3 boss(es) to knock off. Rich Shaker has 3 boss(es) to knock off. Allen Bran has 3 boss(es) to knock off. Frank N. Berry has 3 boss(es) to knock off. Jack Apple has 3 boss(es) to knock off. Jack Nicklaus has 3 boss(es) to knock off. Tom Hanks has 3 boss(es) to knock off. Susan Sarandon has 3 boss(es) to knock off. R.P. McMurphy has 4 boss(es) to knock off. Forrest Gump has 4 boss(es) to knock off. Andrew Beckett has 4 boss(es) to knock off. Helen Prejean has 4 boss(es) to knock off.

One advantage of the recursive variation is that it is easy to tell when you transition from one level to the next. You could use this information to better format your output, as shown in Example 5-13 and Example 5-14.

Example 5-15. Level-order traversal of orgrchart.xml using recursion
<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">     <xsl:output method="text" version="1.0" encoding="UTF-8"/>     <xsl:strip-space elements="*"/>       <xsl:template match="/employee">      <xsl:call-template name="level-order"/> </xsl:template>     <xsl:template name="level-order"> <xsl:param name="max-depth" select="10"/> <xsl:param name="current-depth" select="0"/>     <xsl:choose>   <xsl:when test="$current-depth &lt;= $max-depth">     <xsl:variable name="text">       <xsl:call-template name="level-order-aux">          <xsl:with-param name="level" select="$current-depth"/>         <xsl:with-param name="actual-level" select="$current-depth"/>       </xsl:call-template>     </xsl:variable>     <xsl:if test="normalize-space($text)">       <xsl:value-of select="$text"/>       <xsl:text>&#xa;</xsl:text>       <xsl:call-template name="level-order">         <xsl:with-param name="current-depth" select="$current-depth + 1"/>         </xsl:call-template>     </xsl:if>   </xsl:when> </xsl:choose>     </xsl:template>     <xsl:template name="level-order-aux">   <xsl:param name="level" select="0"/>   <xsl:param name="actual-level" select="0"/>   <xsl:choose>     <xsl:when test="$level = 0">       <xsl:choose>         <xsl:when test="$actual-level = 0">       <xsl:value-of select="@name"/>       <xsl:text> is the head honcho.&#xA;</xsl:text>      </xsl:when>      <xsl:otherwise>        <xsl:value-of select="@name"/>        <xsl:text> has </xsl:text>        <xsl:value-of select="$actual-level"/>        <xsl:text> boss(es) to knock off.&#xA;</xsl:text>      </xsl:otherwise>     </xsl:choose>    </xsl:when>    <xsl:otherwise>       <xsl:for-each select="employee">          <xsl:call-template name="level-order-aux">            <xsl:with-param name="level" select="$level - 1"/>            <xsl:with-param name="actual-level" select="$actual-level"/>          </xsl:call-template>       </xsl:for-each>    </xsl:otherwise>   </xsl:choose> </xsl:template>     </xsl:stylesheet>

Example 5-16. Output
Jil Michel is the head honcho.     Nancy Pratt has 1 boss(es) to knock off. Jane Doe has 1 boss(es) to knock off. Mike Rosenbaum has 1 boss(es) to knock off.     Phill McKraken has 2 boss(es) to knock off. Ima Little has 2 boss(es) to knock off. Walter H. Potter has 2 boss(es) to knock off. Wendy B.K. McDonald has 2 boss(es) to knock off. Cindy Post-Kellog has 2 boss(es) to knock off. Oscar A. Winner has 2 boss(es) to knock off.     Betsy Ross has 3 boss(es) to knock off. Craig F. Frye has 3 boss(es) to knock off. Hardy Hamburg has 3 boss(es) to knock off. Rich Shaker has 3 boss(es) to knock off. Allen Bran has 3 boss(es) to knock off. Frank N. Berry has 3 boss(es) to knock off. Jack Apple has 3 boss(es) to knock off. Jack Nickolas has 3 boss(es) to knock off. Tom Hanks has 3 boss(es) to knock off. Susan Sarandon has 3 boss(es) to knock off.     R.P. McMurphy has 4 boss(es) to knock off. Forrest Gump has 4 boss(es) to knock off. Andrew Beckett has 4 boss(es) to knock off. Helen Prejean has 4 boss(es) to knock off.

If, for some reason, you wished to have random access to nodes at any specific level, you could define a key as follows:

<xsl:key name="level" match="employee" use="count(ancestor::*)"/>     <xsl:template match="/">      <xsl:for-each select="key('level',3)">           <!-- do something with the nodes on level 3 -->       </xsl:for-each> </xsl:template>

You can also make the match more specific or use a predicate with the key function:

<xsl:key name="level" match="//employee" use="count(ancestor::*)"/>     <xsl:template match="/">      <xsl:for-each select="key('level',3)[@sex='female']">           <!-- do something with the female employees on level 3 -->       </xsl:for-each> </xsl:template>

The use of XSLT's key facility is not mandatory because you can always write select="//*[count(ancestors::*)=3]" when you need access to level-3 elements; however, performance will suffer if your stylesheet repeatedly evaluates such an expression. In fact, if your stylesheet has a well-defined structure, you'd be much better off explicitly navigating to the desired level; e.g., select= "/employee/employee/employee", although this navigation can become quite unwieldy.




XSLT Cookbook
XSLT Cookbook: Solutions and Examples for XML and XSLT Developers, 2nd Edition
ISBN: 0596009747
EAN: 2147483647
Year: 2003
Pages: 208
Authors: Sal Mangano

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net