Re: Ordering of Blocks based on Input/Output

If it's performance we may need some input from Mr. Kay...

Dan Diebolt wrote:
> 
> Thanks Francis. I will have to study this and compare it.

I'm afraid the comparison with my old one won't help much - I basically
re-wrote it in a slightly more polished style. (I thought it was
suspicious that I could write 32 lines of code that ran correctly first
time!)

> but I now have to start looking for the best implementation
> (fastest) as I have thousand upon thousand of nodes. 

Here's what should be a slightly faster version, in that it minimises
the number of passes and node-set operations, and uses a key to speed up
the selection of relevent links. It goes about the same speed in saxon
but faster in msxsl - I think you need to do timings on a larger data
set to make these choices.
 
> The suggestion from Ingo to process in two passes is something
> I am strongly considering. 

You could try something like

<block name="b3">
	<depends-on>b1</depends-on>
	<depends-on>b2</depends-on>
</block>

to avoid one node-set operation.

> I am still looking for more input (from Jeni?) so please feel
> free to comment on various approaches.
> 
I can't see any way of improving the gross structure of *this* approach,
but you might well get mileage by tuning the node-set operations against
a large data set. Alternatively some smart person may have a totally
different approach?

Francis.

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
  <xsl:output method="xml" version="1.0" encoding="UTF-8" indent="yes"/>
  <xsl:key name="into" match="/root/system/connect" use="input/@block"
/>
  <xsl:template match="/">
    <order>
      <!-- call the order function with the parameters -->
      <xsl:call-template name="order">
        <xsl:with-param name="todo" select="/root/system/block/name"/>
      </xsl:call-template>
    </order>
  </xsl:template>
  <!-- recurse through this printing out one block at a time -->
  <xsl:template name="order">
    <xsl:param name="todo"/>
    <!-- always need a terminate condition in recursive functions -->
    <xsl:if test="count($todo) > 0">
      <!-- links into todo -->
      <xsl:variable name="into" select="key('into', $todo)"/>
      <!-- find all blocks in $todo that have no inputs from the outputs
of any (other) block in $todo -->
      <xsl:variable name="next" select="$todo[. !=
$into/output/@block]"/>
      <!-- now copy them out -->
      <xsl:copy-of select="$next"/>
      <!-- now recurse with $next removed from $todo -->
      <xsl:call-template name="order">
        <xsl:with-param name="todo" select="$todo[count(. | $next) >
count($next)]"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>
</xsl:stylesheet>

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