Subject: Re: topological sort From: "Peter B. West" <pbwest@xxxxxxxxxxxxxx> Date: Fri, 10 Nov 2000 21:30:18 +0000 |
Joerg, David & Jeni, I am just staring at two new solutions. As it takes me a few days to struggle through each iteration, I don't expect to understand these for a while yet. In the meantime, I have been experimenting with the use of keys. Here's the stylesheet: <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0"> <xsl:output method="text"/> <xsl:key name="nodesReferringTo" match="/structs/struct/name" use="../field/type/ref"/> <xsl:key name="references" match="/structs/struct/field/type/ref" use="../../../name"/> <xsl:key name="nodesReferredTo" match="/structs/struct/name" use="."/> <xsl:template match="structs"> <xsl:variable name="nodes" select="struct/name[not(key('nodesReferringTo', .))]"/> <xsl:call-template name="resolve"> <xsl:with-param name="testnodes" select="$nodes"/> <xsl:with-param name="resolved" select="/.."/> </xsl:call-template> </xsl:template> <xsl:template name="resolve"> <xsl:param name="testnodes"/> <xsl:param name="resolved"/> <xsl:if test="$testnodes"> <xsl:variable name="finished" select="$testnodes[not(../field/type/ref)]"/> <xsl:apply-templates select="$finished[not($resolved)]"/> <xsl:call-template name="resolve"> <xsl:with-param name="testnodes" select="key('nodesReferredTo', key('references', $testnodes))"/> <xsl:with-param name="resolved" select="$resolved|$finished"/> </xsl:call-template> <xsl:for-each select="$testnodes"> <xsl:if test="count($resolved|$finished|.) > count($resolved|$finished)"> <xsl:apply-templates select="."/> </xsl:if> </xsl:for-each> </xsl:if> </xsl:template> <xsl:template match="name"> <xsl:value-of select="."/> <xsl:text> </xsl:text> </xsl:template> </xsl:stylesheet> Notes: Firstly, this takes FOUR times as long for the transformation as Joerg's model, as massaged by me and David. I'm using Xalan, as distributed with Cocoon 1.8. I think it's 1.0.1. The output is, like Jeni's version, A C E B D. This is because of the start conditions. I have made no attempt to protect against circular references. I think that involves another parameter, but I can't see how to do it. The algorithm is find the set of nodes which have no references to them I.e., that are the start of the reference chains. (This is what the key 'nodesReferringTo' is for.) call the template 'resolve' with that set as as the nodes to test, and an empty 'resolved' set. resolve($testnodes, $resolved) if the $testnodes set is non-empty construct the set $finished from $testnodes with no type/ref output the nodes in $finished unless they are also in $resolved (This takes care of multiple references.) construct a new $testnodes set from nodes referred to by current $testnodes (the keys 'references' and 'nodesReferredTo' used here) construct a new $resolved set from the union of $resolved and $finished resolve($testnodes, $resolved) (resolve all nodes further along the reference chain) output nodes in original $testnodes unless they are members of $resolved or $finished Use of sets. The property that node-sets have no duplicates was useful, but in some cases my attempts at set manipulation failed. My first cut was outputting individual struct names within for-each loops. I tried to eliminate these by forming node-sets and using apply-templates to pass output handling on to the "name" template. However, this did not always work. E.g., although commands like <xsl:apply-templates select="$finished[not($resolved)]"/> worked, when I changed <xsl:for-each select="$testnodes"> <xsl:if test="count($resolved|$finished|.) > count($resolved|$finished)"> <xsl:apply-templates select="."/> </xsl:if> </xsl:for-each> to begin with <xsl:for-each select="$testnodes[not($resolved|$finished)]"> with the intention of going to <xsl:apply-templates select="$testnodes[not($resolved|$finished)]"/> the stylesheet broke. What, if anything, is wrong with the above expression? I was originally passing around sets of "struct" nodes, but, because all of the key manipulations were focussed on "name" nodes, I changed to using sets of "name" nodes. This made the nested key call feasible. I'm sorry that this is such a long posting, but this is my school for XSLT. Peter -- Peter B. West pbwest@xxxxxxxxxxxxxx http://powerup.com.au/~pbwest "Lord, to whom shall we go?" XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re[2]: topological sort, Jeni Tennison | Thread | Re[2]: topological sort, Jeni Tennison |
Re: Saxon and validating, Mike Brown | Date | Re: use <xsl:value-of> within an at, Mike Brown |
Month |