## Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once?

 Subject: Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once? From: Tom Myers Date: Thu, 08 Nov 2001 19:24:00 -0500
```Jeni Tennison 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>
>Jeni
>- ---
here's one version, based on the idea that
dC(5,"foo") = <X><X><X><X><X>foo</X></X></X></X></X> via
dC(0,A) = A
dC(2*N,A) = dC(N,dC(N,A))
dC(2*N+1,A) = dC(N, dC(N, cons("X",A) ) )
so I expect stack depth to be O(log(N)), time to be O(N^2),
max space to be O(N), space allocation to be O(N^2)...rather
like the tail-recursive except for O(log(N)) instead of O(1)
stack space, and of course not needing anything special in
the engine.
------------------------------

<xsl:template name="divConq">
<xsl:param name="N" select="10"/>
<xsl:param name="A" select="/.."/>
<xsl:param name="Ndiv2" select="(\$N - \$N mod 2) div 2"/>
<xsl:choose>
<xsl:when test="not(\$N)"><xsl:copy-of select="\$A"/></xsl:when>
<xsl:otherwise>
<xsl:variable name="onebase">
<xsl:choose>
<xsl:when test="\$N mod 2">
<X><xsl:copy-of select="\$A"/></X>
</xsl:when>
<xsl:otherwise>
<xsl:copy-of select="\$A"/>
</xsl:otherwise>
</xsl:choose>
</xsl:variable>
<xsl:variable name="halfway">
<xsl:call-template name="divConq">
<xsl:with-param name="N" select="\$Ndiv2"/>
<xsl:with-param name="A" select="\$onebase"/>
</xsl:call-template>
</xsl:variable>
<xsl:call-template name="divConq">
<xsl:with-param name="N" select="\$Ndiv2"/>
<xsl:with-param name="A" select="\$halfway"/>
</xsl:call-template>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
----------------------------------------

hope that makes sense...

Tom Myers

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

```