Hello all,

I am working on scheduling functionality that needs to calculate start/end dates for interrelated tasks. Task C may be dependent on Task A and Task B and thus cannot begin until Tasks A and B are both completed. Likewise, moving Task A's end date will move Task C's end date also.

My basic approach is to find all tasks which have end dates (set A). Then I find all tasks which are fully dependent on set A and do not have end dates (set B) and calculate their end dates. I continue doing this process until all tasks end dates have been calculated.

A typical data set will have 200-400 tasks; a large data set my have up to 1200 tasks.

I could do this by segregating the data into this format:
        <data>
                <tasks-with-dates><task .../>...</tasks-with-dates>
                <tasks-without-dates><task .../>...</tasks-without-dates>
        </data>
and then performing a transform in a loop on the segregated data until all dates have been calculated as shown in this pseudo-code:
        doc = xml('tasks');
        doc = xsl('segregate-tasks').transform( doc );
        while (doc.has( '//tasks-with-dates/task' ))
                doc = xsl('calculate-dates-and-segregate').transform( doc )
Alternatively, I could use a recursive template similar to this pseudo-code:
        <template name="calc-dates">
                <param name="with-dates"/>
                <param name="without-dates"/>
                <variable name="calculated">
                   <copy-of select="$with-dates" />
                   <for-each select="$without-dates[ parent-task/@ref = $with-dates/@id ]"/>
                        ... calculate date and write task...
                   </for-each>
                </variable>
                <variable name="remaining"
                   select="$without-dates[not( @id = node-set($calculated)
[@id] )]" />
                <choose>
                <when test="$remaining">
              <call-template name="calc-dates">
                 <with-param name="with-dates" select="node-set
($calculated)"/>
                 <with-param name="without-dates" select="$remaining"/>
              </call-template>
           </when>
           <otherwise>
              <xsl:copy-of select="$calculated" />
           </otherwise>
                </choose>
        </template>
I'm leaning towards doing this via the loop. The drawbacks for doing so
are the overhead of loading the doc and transform engine repeatedly
(perhaps 200 times or more). But I could declare a key in calculate-
dates-and-segregate.xsl to make the task lookups fairly efficient.

The recursive template has the benefit of only one load but I'm not sure
how well node-set()ing a variable over and over will perform. I also
find recursive templates more opaque and confusing for future
maintenance.

Do any of you have opinions/suggestions?



Antonio Collins

My instinct is definitely to do this within a single stylesheet, using the recursive call-template. It's a simple tail-call so any processor with a decent optimizer should be able to handle it without blowing the stack (and 200 calls is usually possible even without tail-call optimization). I would imagine this will save a lot of "start-up" overhead compared with running multiple transformations, and it means your program is essentially all written in one language rather than being split between two, which is always a good thing from the point of view of maintenance, debugging, portability, etc.

Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference

Thanks for the feedback. I'll go ahead and try it that way.

I was told that node-set() was just as expensive as parsing and loading a doc (fragment) so I'll probably prototype it both ways and benchmark to determine the final implementation.

P.S.: The application is written in another language (javascript or c#) and it just uses XSLT for data manipulations.

Antonio Collins

There might be implementations on which node-set() is expensive, though I would be a little surprised if anyone implements it by serializing and re-parsing. In Saxon 6.x, it involves flipping a single bit.

Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference