Re: Dependency Sorting, first of kind

[Ray Waldin <rwaldin@xxxxxxxxxxx>]

Here's a solution of sorts, but it depends on your definition of
reasonable... :)

With a reasonable limitation on the depth of any given dependency path
through the XML, you can use a brute-force sort expression like:

  count(id(@dep|id(@dep|id(@dep ... )/@dep)/@dep)) 

with one id(@dep...)/@dep recursion per possible dependency depth minus
one.  It works by recognizing that, if A is dependent on B, then A is
dependent on at least one more element than is B.  Here's a sample XML
file:

<!DOCTYPE x [
  <!ELEMENT x (a)*>
  <!ELEMENT a EMPTY>
  <!ATTLIST a name ID     #REQUIRED
              dep  IDREFS #IMPLIED>
]>
<x>
  <a name="seven" dep="six"/>
  <a name="six" dep="five"/>
  <a name="five" dep="four"/>
  <a name="four" dep="three two"/>
  <a name="three" dep="two"/>
  <a name="two" dep="one"/>
  <a name="one"/>
</x>

and a sample stylesheet that handles up to 5 levels of dependency
correctly...

<xsl:stylesheet xmlns:xsl="http://www.w3.org/XSL/Transform/1.0";>
<xsl:template match="x">
  <xsl:apply-templates select="a">
    <xsl:sort
      select="count(id(@dep|id(@dep|id(@dep|id(@dep)/@dep)/@dep)/@dep))"/>
  </xsl:apply-templates>
</xsl:template>
<xsl:template match="a">
  <xsl:apply-templates select="@*"/>
  <xsl:text>&#10;</xsl:text>
</xsl:template>
<xsl:template match="@name">
  <xsl:value-of select="."/><xsl:text>: </xsl:text>
</xsl:template>
<xsl:template match="@dep">
  <xsl:value-of select="translate(normalize(.),' ',',')"/>
  <xsl:text> (depth: </xsl:text>
  <xsl:value-of select="count(id(.|id(.|id(.|id(.)/@dep)/@dep)/@dep))"/>
  <xsl:text>)</xsl:text>
</xsl:template>
</xsl:stylesheet>

You get the following results:

one:
two: one (depth: 1)
three: two (depth: 2)
four: three,two (depth: 3)
five: four (depth: 4)
seven: six (depth: 5)
six: five (depth: 5)

...so it works up to five levels deep, and then falls apart.  If you need
more depth, just add more id(@dep...)/@dep recursions.  Is that reasonable
enough?

-Ray

---
Paul Prescod wrote:
> 
> Let's say that we have a document type like this:
> 
> <a name="foo"/>
> <a name="bar" depends-on="foo"/>
> <a name="baz" depends-on="foo"/>
> <a name="jaz" depends-on="foo bar"/>
> <a name="spaz"/>
> <a name="maz" depends-on="spaz bar"/>
> 
> You can see that some elements depen on other elements as functions
> might depend on other functions in a programming language or classes
> upon superclasses in an object oriented language. I've listed them in
> dependence order above (all dependents are listed after their dependees)
> but the goal is actually to be able to do that sort. I want to take
> randomly sorted elements and print them in their sorted order.
> 
> I cannot think of a reasonably easy way to do that. Is there one?
> 
>  Paul Prescod


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