RE: [xsl] Counting nodes efficiently

Subject: RE: [xsl] Counting nodes efficiently
From: Wendell Piez <wapiez@xxxxxxxxxxxxxxxx>
Date: Thu, 19 Feb 2004 11:57:31 -0500
Oops,

At 05:19 AM 2/19/2004, Dimitre wrote:
In this and similar problems one can re-use the identity transformation,
which processes strictly one node at a time (would a native English
speaker, please, suggest a good name? The best I could arrive at was "one
node at a time identity transformation"):

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
 <xsl:output omit-xml-declaration="yes"/>

  <xsl:template match="@* | node()">
    <xsl:copy>
      <xsl:apply-templates select="@*"/>
      <xsl:apply-templates select="node()[1]"/>
    </xsl:copy>
    <xsl:apply-templates select="following-sibling::node()[1]"/>
  </xsl:template>

</xsl:stylesheet>

In my last e-mail I was reading too quickly, and neglected to observe, before answering, that you're stepping forward one node at a time along the following-sibling axis.


I'd probably distinguish this from the usual identity transform-by-tree-traversal by referring to its "stepping forward". "Stepping forward" or even "tiptoeing forward" (since you're often conducting a test as you go) is the way I usually describe the family of methods that traverse the following-sibling axis to allow this kind of fine-grained control.

In practice, however, I also find that XSLT newbies need the concepts explained in any case, and more experienced users get the idea quickly from a short description ("no, I mean an identity transform that steps forward one node at a time along the following-sibling axis"), so that the lack of a fixed technical terminology for all this stuff doesn't really hurt that much.

"Muenchian grouping" is probably the exception that proves this rule, since that method is tricky enough to defy a one-line description, but the problem it deals with is common enough to come up often....

Cheers,
Wendell


This transformation produces the same results as the more well-known
identity rule.

The difference is that we now have the finest possible grain-level of
controll as every xsl:apply-templates instruction above always selects at
most one node.

It is trivial to add parameters and to override the one-at-a-time identity
for elements. Thus we finally have:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>
 <xsl:output omit-xml-declaration="yes"/>

  <xsl:template match="@* | node()">
    <xsl:param name="pnAncestors" select="0"/>
    <xsl:param name="pnPreceding" select="0"/>
    <xsl:copy>
      <xsl:apply-templates select="@*"/>
      <xsl:apply-templates select="node()[1]">
        <xsl:with-param name="pnAncestors"
                        select="$pnAncestors+1"/>
        <xsl:with-param name="pnPreceding"
                        select="$pnPreceding"/>
      </xsl:apply-templates>
    </xsl:copy>
    <xsl:apply-templates select="following-sibling::node()[1]">
      <xsl:with-param name="pnAncestors"
                      select="$pnAncestors"/>
      <xsl:with-param name="pnPreceding"
                      select="$pnPreceding+1"/>

    </xsl:apply-templates>
  </xsl:template>

  <xsl:template match="*">
    <xsl:param name="pnAncestors" select="0"/>
    <xsl:param name="pnPreceding" select="0"/>

    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:attribute name="_id">
        <xsl:value-of select=
                    "concat(name(), '_',
                            $pnAncestors, '_',
                            $pnPreceding
                            )"/>
      </xsl:attribute>
    </xsl:copy>
    <xsl:apply-templates select="node()[1]">
      <xsl:with-param name="pnAncestors"
                      select="$pnAncestors+1"/>
      <xsl:with-param name="pnPreceding"
                      select="$pnPreceding"/>
    </xsl:apply-templates>
    <xsl:apply-templates select="following-sibling::node()[1]">
      <xsl:with-param name="pnAncestors"
                      select="$pnAncestors"/>
      <xsl:with-param name="pnPreceding"
                      select="$pnPreceding+1"/>

</xsl:apply-templates>

</xsl:template>

</xsl:stylesheet>

This transformation is not long, it can be written almost mechanically, it
makes exactly one pass over the tree and it has a linear time complexity
(checked with inputs of different size).


Cheers,


Dimitre Novatchev
FXSL developer,

http://fxsl.sourceforge.net/ -- the home of FXSL
Resume: http://fxsl.sf.net/DNovatchev/Resume/Res.html




__________________________________ Do you Yahoo!? Yahoo! Mail SpamGuard - Read only the mail you want. http://antispam.yahoo.com/tools

XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list


======================================================================
Wendell Piez                            mailto:wapiez@xxxxxxxxxxxxxxxx
Mulberry Technologies, Inc.                http://www.mulberrytech.com
17 West Jefferson Street                    Direct Phone: 301/315-9635
Suite 207                                          Phone: 301/315-9631
Rockville, MD  20850                                 Fax: 301/315-8285
----------------------------------------------------------------------
  Mulberry Technologies: A Consultancy Specializing in SGML and XML
======================================================================


XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list



Current Thread