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: xsl-list at lists dot mulberrytech dot com
- Subject: Re: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
- From: Tom Myers <tommy at cs dot colgate dot edu>
- Date: Thu, 08 Nov 2001 19:24:00 -0500
- Cc: Jeni Tennison <jeni at jenitennison dot com>
- Reply-To: xsl-list at lists dot mulberrytech dot com
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
>- ---
and probably Dimitre has already answered (I'm on digest) but
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