[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] 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) > $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
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|