[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] Dimitre's algorithm, fixed: quadratic, not exponential
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
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|