Recipe5.4.Performing a Preorder Traversal

Recipe 5.4. Performing a Preorder Traversal

Problem

You want to recursively process an element first and then process its child elements.

Solution

Solutions to this recipe have the following general form:

<xsl:template match="node( )">      <!-- Do something with current node -->          <!--Process children -->      <xsl:apply-templates/> </xsl:template>

Discussion

The term preorder is computer-science jargon for traversing a tree, so you visit the root and recursively visit the children of the root in preorder. This process is arguably the most common means of processing XML. Of this idiom's many applications, this chapter will consider two. As you review recipes in later sections, you will see this mode of traversal arise frequently.

Consider an organization chart (Example 5-2) encoded in a simplistic fashion so that an employee element B is a child of another employee element A if B reports to A. Example 5-1 employs a preorder traversal to explain who manages whom. Example 5-2 shows the output.

Example 5-3. Stylesheet

<?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:strip-space elements="*"/>       <xsl:template match="/employee" priority="10">      <xsl:value-of select="@name"/><xsl:text> is the head of the company. </xsl:text>      <xsl:call-template name="HeShe"/><xsl:text> manages </xsl:text>      <xsl:call-template name="manages"/>      <xsl:apply-templates/> </xsl:template>       <xsl:template match="employee[employee]">      <xsl:value-of select="@name"/><xsl:text> is a manager. </xsl:text>      <xsl:call-template name="HeShe"/> <xsl:text> manages </xsl:text>      <xsl:call-template name="manages"/>      <xsl:apply-templates/> </xsl:template>     <xsl:template match="employee">      <xsl:value-of select="@name"/><xsl:text> has no worries. </xsl:text>      <xsl:text>&#xa;&#xa;</xsl:text> </xsl:template>     <xsl:template name="HeShe">      <xsl:choose>           <xsl:when test="@sex = 'male' ">                <xsl:text>He</xsl:text>           </xsl:when>           <xsl:otherwise>                <xsl:text>She</xsl:text>           </xsl:otherwise>      </xsl:choose> </xsl:template>       <xsl:template name="manages">      <xsl:for-each select="*">           <xsl:choose>             <xsl:when test="position( ) != last( ) and last( ) > 2">               <xsl:value-of select="@name"/><xsl:text>, </xsl:text>             </xsl:when>             <xsl:when test="position( ) = last( ) and last( ) > 1">               <xsl:text> and </xsl:text><xsl:value-of                           select="@name"/><xsl:text>. </xsl:text>             </xsl:when>             <xsl:when test="last( ) = 1">               <xsl:value-of select="@name"/><xsl:text>. </xsl:text>             </xsl:when>             <xsl:otherwise>               <xsl:value-of select="@name"/>             </xsl:otherwise>           </xsl:choose>       </xsl:for-each>      <xsl:text>&#xa;&#xa;</xsl:text> </xsl:template> </xsl:stylesheet>

Example 5-4. Output

Jil Michel is the head of the company. She manages Nancy Pratt, Jane Doe, and Mike  Rosenbaum.      Nancy Pratt is a manager. She manages Phill McKraken and Ima Little.      Phill McKraken has no worries.      Ima Little is a manager. She manages Betsy Ross.      Betsy Ross has no worries.      Jane Doe is a manager. She manages Walter H. Potter and Wendy B.K. McDonald.      Walter H. Potter has no worries.      Wendy B.K. McDonald is a manager. She manages Craig F. Frye, Hardy Hamburg, and Rich  Shaker.      Craig F. Frye has no worries.      Hardy Hamburg has no worries.      Rich Shaker has no worries.      Mike Rosenbaum is a manager. He manages Cindy Post-Kellog and Oscar A. Winner.      Cindy Post-Kellog is a manager. She manages Allen Bran, Frank N. Berry, and Jack Apple.      Allen Bran has no worries.      Frank N. Berry has no worries.      Jack Apple has no worries.      Oscar A. Winner is a manager. He manages Jack Nickolas, Tom Hanks, and Susan Sarandon.      Jack Nicklaus is a manager. He manages R.P. McMurphy.      R.P. McMurphy has no worries.      Tom Hanks is a manager. He manages Forrest Gump and Andrew Beckett.      Forrest Gump has no worries.      Andrew Beckett has no worries.      Susan Sarandon is a manager. She manages Helen Prejean.      Helen Prejean has no worries.

A more serious application of preorder traversal is the conversion of an expression tree to prefix notation. Given the MathML content fragment in Example 5-3 and Example 5-4, you can create a transformation to a Lisp-like syntax. Example 5-5 shows the output.

Example 5-5. MathML fragment representing x2+4x+4 = 0

<apply>      <eq/>      <apply>           <plus/>           <apply>                <power/>                <ci>x</ci>                <cn>2</cn>           </apply>           <apply>                <times/>                <cn>4</cn>                <ci>x</ci>           </apply>           <cn>4</cn>      </apply>      <cn>0</cn> </apply>

Example 5-6. Stylesheet to convert MathML fragment to prefix notation

<?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:strip-space elements="*"/>            <xsl:template match="apply">           <xsl:value-of select="local-name(*[1])"/>           <xsl:text>(</xsl:text>           <xsl:apply-templates/>           <xsl:text>)</xsl:text>           <xsl:if test="following-sibling::*">,</xsl:if>      </xsl:template>            <xsl:template match="ci|cn">           <xsl:value-of select="."/>           <xsl:if test="following-sibling::*">,</xsl:if>      </xsl:template> </xsl:stylesheet>

Example 5-7. Output

eq(plus(power(x,2),times(4,x),4),0)

The MathML converter is not the purest example of a preorder traversal, largely because MathML encodes mathematical expressions unconventionally. This is largely an instance of the preorder idiom because the code processes the apply element first (and outputs the name of its first child element) and then processes its child elements recursively (via <xsl:apply-templates/>). The code following apply-templates balances the parentheses, inserts commas where necessary, and involves no further traversal.