[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Finding the maximun number of nodes

Subject: Re: Finding the maximun number of nodes
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Tue, 9 Jan 2001 08:34:15 -0800 (PST)
recursion 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


Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.