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

Re: Dependency Sorting, first of kind

Subject: Re: Dependency Sorting, first of kind
From: Francis Norton <francis@xxxxxxxxxxx>
Date: Thu, 04 Nov 1999 15:55:56 +0000
sorting dependencies
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


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.