This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- To: Jeni Tennison <jeni at jenitennison dot com>, xsl-list at lists dot mulberrytech dot com
- Subject: Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- From: Dimitre Novatchev <dnovatchev at yahoo dot com>
- Date: Thu, 8 Nov 2001 11:55:31 -0800 (PST)
- Cc: Dimitre Novatchev <dnovatchev at yahoo dot com>
- Reply-To: xsl-list at lists dot mulberrytech dot com
--- Jeni Tennison <jeni@jenitennison.com> wrote:
> Mike Kay wrote:
> > As for the divide-and-conquer algorithm, it looks interesting and
> > performs well, but as it produces completely different output from
> > the other two, I can't quite see the relevance.
>
> Gah, yes, my idiocy. Dimitre, can you see a way of using a divide
> and conquer algorithm to produce a multiply-nested tree?
>
> <xsl:call-template name="accumDivAndConquer">
> <xsl:with-param name="count" select="3" />
> <xsl:with-param name="base" select="'foo'" />
> </xsl:call-template>
>
> producing:
>
> <foo>
> <foo>
> <foo>foo</foo>
> </foo>
> </foo>
>
Hi Jeni,
Is this what you wished? I'm afraid it's performance seems to be no better than
O(N*N), hope I'm wrong.
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:msxsl="urn:schemas-microsoft-com:xslt"
>
<xsl:output indent="yes" omit-xml-declaration="yes"/>
<xsl:template match="/">
<xsl:call-template name="accumDivAndConquer">
<xsl:with-param name="count" select="10" />
<xsl:with-param name="base" select="'foo'" />
</xsl:call-template>
</xsl:template>
<xsl:template name="accumDivAndConquer">
<xsl:param name="count" />
<xsl:param name="base"/>
<xsl:choose>
<xsl:when test="$count = 1">
<xsl:element name="{$base}">
<xsl:value-of select="$base"/>
</xsl:element>
</xsl:when>
<xsl:when test="$count >= 2">
<xsl:variable name="vHalf" select="floor($count div 2)"/>
<xsl:variable name="vrtfPart1">
<xsl:call-template name="accumDivAndConquer">
<xsl:with-param name="count" select="$vHalf" />
<xsl:with-param name="base" select="'foo'" />
</xsl:call-template>
</xsl:variable>
<xsl:variable name="vrtfPart2">
<xsl:call-template name="accumDivAndConquer">
<xsl:with-param name="count" select="$count - $vHalf" />
<xsl:with-param name="base" select="'foo'" />
</xsl:call-template>
</xsl:variable>
<xsl:apply-templates select="msxsl:node-set($vrtfPart1)/*"
mode="mergeTrees">
<xsl:with-param name="pTree2" select="msxsl:node-set($vrtfPart2)/*"/>
<xsl:with-param name="base" select="'foo'" />
</xsl:apply-templates>
</xsl:when>
</xsl:choose>
</xsl:template>
<xsl:template match="node() | @*" mode="mergeTrees">
<xsl:param name="pTree2" select="/.."/>
<xsl:param name="base" select="'foo'" />
<xsl:choose>
<xsl:when test="self::text() and . = $base">
<xsl:copy-of select="$pTree2"/>
</xsl:when>
<xsl:otherwise>
<xsl:copy>
<xsl:apply-templates select="node() | @*" mode="mergeTrees">
<xsl:with-param name="pTree2" select="$pTree2"/>
<xsl:with-param name="base" select="'foo'" />
</xsl:apply-templates>
</xsl:copy>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
Cheers,
Dimitre Novatchev.
__________________________________________________
Do You Yahoo!?
Find a job, post your resume.
http://careers.yahoo.com
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list