[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

[xsl] Dimitre's algorithm, fixed: quadratic, not exponential: Re: HOWTO: convert flat list w/ level

---

---

Hello,

thanks to Michael Kay, I have discovered that however expressions in the
Dimitre's algorithm lead to exponential time, they are incorrect. I hope that
this corrected version of Dimitre Novachev's algorithm both produces the
correct result and has quadratic time. The changes are around line the second
following-sibling:: expression.


<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output omit-xml-declaration="yes" indent="yes"/>
  <xsl:template match="/node">
    <node>
      <xsl:apply-templates select="node[1]">
        <xsl:with-param name="pParentLevel"
                        select="-1"/>
      </xsl:apply-templates>
    </node>
  </xsl:template>

  <xsl:template match="node">
    <xsl:param name="pParentLevel"/>
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:apply-templates
       select="following-sibling::node[1]
                       [@level > current()/@level]">
         <xsl:with-param name="pParentLevel" select="@level"/>
       </xsl:apply-templates>
    </xsl:copy>
    <xsl:apply-templates
      select="following-sibling::node
                  [not(@level > current()/@level)]
		  [1]
		  [@level > $pParentLevel]">
      <xsl:with-param name="pParentLevel" select="$pParentLevel"/>
    </xsl:apply-templates>
  </xsl:template>
</xsl:stylesheet>



Sincerely,
David Tolpin

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

---