Re: Re: lookup-table thoughts (was Re: matching multip

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