Re: Dependency Sorting, first of kind

[Francis Norton <francis@xxxxxxxxxxx>]

Solution below....

Paul Prescod wrote:
> 
...
> Okay, but if you normalize them, the input would need to look like this:
> 
> <a name="foo"/>
> <a name="bar" depends-on="foo"/>
> <a name="baz" depends-on="foo"/>
> <a name="jaz" depends-on="foo"/>
> <a name="jaz" depends-on="bar"/>
> <a name="spaz"/>
> <a name="maz" depends-on="spaz"/>
> <a name="maz" depends-on="bar"/>
> 
> I don't think your code would work for this form. This is where I ran
> into the roadblock. How do you print out jaz only once even though it
> occurs as a dependent of both "foo" and "bar"? Maybe I can do something
> with preceding::. I'll pursue that route.
> 

I'm sorry to be obsessive, but if you can't solve your problem with set
operators, your sets just ain't normalised.

Here's a pretty general solution. I've broken it down into lots of steps
and tried to comment it because heavy use of XSLT node-sets in a SQL-ish
way is new to me, and maybe to some others.

The general answer is that that you can do all the basic set operations
in XSLT. Use them and strip out your buggy iterative code. I can't
answer for the performance effects, however!

I'll write up the following in a note tonight - I have tested them, and
they all work sweetly:

	set union (any node in a or in b):
	<xsl:variable name="x" select="$a | $b" />

	set intersection (any node in a and in b):
	<xsl:variable name="x" select="$a[. = $b]" />

	set difference (any node in a but not in b):
	<xsl:variable name="x" select="$a[not(. = $b)]" />

Francis.

G:\xmlSchema>type t_.xml
<?xml version="1.0"?>
<data>

        <!-- entities -->
        <a name="foo"/>
        <a name="bar" />
        <a name="baz" />
        <a name="jaz" />
        <a name="maz" />
        <a name="spaz" />

        <!-- relationships -->
        <dependency by="bar" on="foo"/>
        <dependency by="baz" on="foo"/>
        <dependency by="jaz" on="foo"/>
        <dependency by="jaz" on="bar"/>
        <dependency by="maz" on="spaz"/>
        <dependency by="maz" on="bar"/>

</data>

G:\xmlSchema>type t_.xsl
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";>

<xsl:template match="/">

  <!-- start by calling untangler with the node-set of roots
    (ie no dependencies) as a parameter
        -->
  <xsl:call-template name="untangler">

    <!-- there must be a better way of creating an empty node set... -->
    <xsl:with-param name="done-set" select="/IDontExist" />

  </xsl:call-template>

</xsl:template>


<xsl:template name="untangler">

  <!-- the set of nodes that have already been accepted -->
  <xsl:param name="done-set" />

  <!-- get nodes that haven't been processed -->
  <xsl:variable name="not-done" select="/data/a/@name[not(. =
$done-set)]" />

  <!-- now filter out those which depend on something that's "not-done"
-->
  <xsl:variable name="do-now" 
      select="$not-done[not(. = /data/dependency/@by[../@on =
$not-done])]" />

  <xsl:call-template name="dump-nodeset">
    <xsl:with-param name="nodeset" select="$do-now" />
  </xsl:call-template>

  <xsl:if test="$not-done">
    <xsl:call-template name="untangler">

      <!-- add newly-done nodes to the done-list with the Union operator
-->
      <xsl:with-param name="done-set" select="$done-set | $do-now" />

    </xsl:call-template>
  </xsl:if>

</xsl:template>

<!-- utility function -->
<xsl:template name="dump-nodeset">
  <xsl:param name="nodeset" />

  dump-nodeset called...
  <xsl:for-each select="$nodeset">
    <xsl:value-of select="concat('[processing: ', .)" />]
  </xsl:for-each>
</xsl:template>

</xsl:stylesheet>

G:\xmlSchema>saxon t_.xml t_.xsl


  dump-nodeset called...
  [processing: foo]
  [processing: spaz]


  dump-nodeset called...
  [processing: bar]
  [processing: baz]


  dump-nodeset called...
  [processing: jaz]
  [processing: maz]


  dump-nodeset called...
  Elapsed time: 841 milliseconds


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list