Re[2]: topological sort

Subject: Re[2]: topological sort
From: Jeni Tennison <mail@xxxxxxxxxxxxxxxx>
Date: Mon, 13 Nov 2000 10:18:33 +0000

Just a couple of things about the keys:

>   <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="."/>

With xsl:key, the 'match' value is a pattern.  Just like with
xsl:template 'match' attributes, you don't need to point the processor
from the root node to the nodes you're interested in right from the
root node, just give enough information so that the key space holds
values for the nodes you're interested in.  So, to get the key to hold
information about all names:


To get it to hold information only about those names that are names of


and so on.

The second thing is that the match pattern should usually match the
node you're actually interested in rather than a supplementary node.
In your case, you're interested in 'struct' elements, not really
interested in their names (except as identifiers).  Therefore I'd
recast the first and last to:

<xsl:key name="nodesReferringTo" match="struct" use="field/type/ref" />
<xsl:key name="nodesReferredTo" match="struct" use="name" />

And pass around the structs rather than the names, e.g.:

  struct[not(key('nodesReferringTo', name))]

Given the way that you are using the second key, you may as well use:

  key('nodesReferredTo', $testnodes/field/type/ref)

instead of a key at all for the second argument, though it's obviously
a matter of personal preference.

I can't comment on the logic of the algorithm, but you say that you're
trying to:

>    output the nodes in $finished unless they are also in $resolved
>          (This takes care of multiple references.)

The XPath $finished[not($resolved)] says "the structs in $finished for
which it is true that there are no nodes in $resolved".  In other
words, the not($resolved) part will always evaluate to true() if there
are no nodes in $resolved and to false if there *are* nodes in
$resolved.  Thus, the XPath $finished[not($resolved)] either gives all
the $finished nodes or none of them.

If you want to select only those nodes that are in $finished that are
not in $resolved, then you need to do something like:

   $finished[not(name = $resolved/name)]

[given that you're passing around structs rather than names] In other
words, the structs in $finished for which it is not true that the name
of the struct is the same as the name of a struct in $resolved.  I
think that this will help address the problems you're having with the
node sets elsewhere as well.

I hope that helps,


Jeni Tennison

 XSL-List info and archive:

Current Thread