Re: Finding the maximun number of nodes

Hi Jenni,

I feel really excited as we together have almost arrived to some very
good result!

Your last solution was following the same principles as mine --
eliminating as much nodes as possible at each step
(xsl:apply-templates).

This solution can be generalised for an arbitrary nodeset and it will
possess all good features we've discussed -- elimination of all
unnecessary steps, lack of recursive calls, linear complexity (in case
of a cleverly optimised XSLT Processor) -- the time to copy the nodeset
is only a linear increase -- so as a result the total complexity stays
linear.

The idea is to start with copying the nodeset into a tree -- then apply
the template to the first child of this tree.

Here's the result:

<xsl:stylesheet version="1.0"
	xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
	xmlns:msxsl="urn:schemas-microsoft-com:xslt"
	>
	<xsl:output method="text"/>
	
	<xsl:variable name="theNodes">
		<xsl:for-each select="//tr">
			<xsl:copy-of select="."/>
		</xsl:for-each>
	</xsl:variable>
	
<xsl:template match="/">	
	<xsl:apply-templates select="msxsl:node-set($theNodes)/tr[1]"
mode="maxCols"/>
</xsl:template>

<xsl:template match="tr" mode="maxCols">
  <xsl:variable name="nCols" select="count(td)" />
  <xsl:variable
    name="next"
    select="following-sibling::tr[count(td) &gt; $nCols][1]" />
  <xsl:choose>
    <xsl:when test="$next">
      <xsl:apply-templates select="$next" mode="maxCols" />
    </xsl:when>
    <xsl:otherwise><xsl:value-of select="$nCols" /></xsl:otherwise>
  </xsl:choose>
</xsl:template>
</xsl:stylesheet>

It produces the right result: '4', when applied to the following xml
source:

<tables>
<table ID="1">
   <tr><td>(1,1)</td></tr>
   <tr><td>(2,1)</td><td>(2,2)</td><td>(2,3)</td></tr>
   <tr><td>(3,1)</td><td>(3,2)</td></tr>
   <tr><td>(4,1)</td><td>(4,2)</td><td>(4,3)</td></tr>
</table>

<table ID="2">
   <tr><td>(0,1)</td><td>(0,2)</td><td>(0,3)</td><td>(0,4)</td></tr>
   <tr><td>(2,1)</td><td>(2,2)</td><td>(2,3)</td></tr>
   <tr><td>(3,1)</td><td>(3,2)</td><td>(3,3)</td><td>(3,4)</td></tr>
</table>

</tables>


Once again -- thanks a lot -- now I feel enthusiastic for our next
dialogue... :o)))

Cheers,
Dimitre Novatchev.


--- Jeni Tennison <mail@xxxxxxxxxxxxxxxx> wrote:
> Hi Dimitre,
> 
> > To be able to minimise the depth of recursion is something ***very
> > important*** when confronted with the reality of some wellknown
> > vendours' XSLT processors crashing during deep recursive
> processing.
> 
> Again a good point. The being the case, it looks like solutions that
> mixes the non-exponential growth in required processing of recursive
> solutions with the shallow recursive processing of non-recursive
> solutions would be best.
> 
> With an arbitrary node set or a really really huge node set, I think
> that restricts us to using the xsl:sort method, e.g.:
> 
> <xsl:template name="maxCols">
>   <xsl:for-each select="//tr">
>     <xsl:sort select="count(td)" order="descending" />
>     <xsl:if test="position() = 1">
>       <xsl:value-of select="." />
>     </xsl:if>
>   </xsl:for-each>
> </xsl:template>
> 
> With a node set based on a axis relationship (like
> following-sibling::), then you could also use:
> 
> <xsl:template name="maxCols">
>   <xsl:apply-templates select="//tr[1]" mode="maxCols" />
> </xsl:template>
> 
> <xsl:template match="tr" mode="maxCols">
>   <xsl:variable name="nCols" select="count(td)" />
>   <xsl:variable
>     name="next"
>     select="following-sibling::tr[count(td) > $nCols][1]" />
>   <xsl:choose>
>     <xsl:when test="$next">
>       <xsl:apply-templates select="$next" mode="maxCols" />
>     </xsl:when>
>     <xsl:otherwise><xsl:value-of select="$nCols" /></xsl:otherwise>
>   </xsl:choose>
> </xsl:template>
> 
> This works on the same principal as the solution you gave most
> recently, but is linear as long as the XSLT processor optimises
> XPaths
> that end in [1] (ref the setting of the $next variable), and of
> course
> depends on being able to navigate the source node tree to move from
> one node to the next and thus won't work on arbitrary node sets.
> 
> I dunno - so much seems to depend on how the individual processor
> does
> something, whether it's implemented to crash with deep recursion or
> not, whether it sorts in a sensible way and so on, that the only
> really safe guideline is "[expletive deleted] it and See".
> 
> Cheers,
> 
> Jeni
> 
> ---
> Jeni Tennison
> http://www.jenitennison.com/
> 
> 



__________________________________________________
Do You Yahoo!?
Yahoo! Photos - Share your holiday photos online!
http://photos.yahoo.com/

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