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

--- Jeni Tennison <jeni@xxxxxxxxxxxxxxxx> 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