Re: [xsl] Finding the maximun number of nodes

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

Jeni,

> I'm not sure that I understand: in order to know whether 'this row'
> has more cells in it than any of the following rows, you *have* to
> look at the rest of the rows, so even the best solution has to look
> at
> every row.
> 

My algorithm is quite different -- at each step (recursive call to
traverse the rest of the nodeset) *** only the really necessary
nodes*** are considered -- not "all the rest".

Due to this there are "worst" and "best" cases. For a nodeset with N
nodes in the best case (when the first node has the maximum number of
children) no recursive call is made at all and the depth of the
call-stack is 1.

In the "worst" case (when there's a single node with maximum number of
children, and this is the last node) -- then the depth of the call
stack will be N.

When the next recursive call is performed, only those nodes, that have
not already been eliminated in the previous steps are passed to this
next step. For example, if we have 5 nodes with the following number of
children each -- 3, 2, 3, 2, 4 -- then the depth of the call stack when
the maximum number of children is determined will be only 2. The 2nd,
3rd and 4th node will be eliminated at the very first call, then at the
second (and final) call there'd be no comparisons to be made at all.

Please, note also that this algorithm is a little bit more general,
will process an arbitrary nodeset and does not rely on relationships
like following-sibling.

As for wishes for new features in the next versions of XSLT, it is
obvious that the speed of many such algorithms will be considerably
increased by using a modification of the key() function that returns a
nodeset of all nodes with value ***greater than given value*** for a
named key.

Here's the template:

<xsl:template name="nodeWithMaxChildren">
  <xsl:param name="theNodes"/>
  <xsl:param name="childName"/>
	
  <xsl:variable name="myNumChildren"
    select="count($theNodes[1]/*[name()=$childName])"/>
	 
  <xsl:variable name="nextNodes" 
    select="$theNodes[position() > 1]
                 [$myNumChildren &lt; count(*[name()=$childName])]"/>
	
  <xsl:choose>
    <xsl:when test="not($nextNodes)">
      <xsl:value-of select="$myNumChildren"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="nodeWithMaxChildren">
        <xsl:with-param name="theNodes" select="$nextNodes"/>
        <xsl:with-param name="childName" select="$childName"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
	
</xsl:template>


Cheers,
Dimitre.

__________________________________________________
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