Re: [xsl] Re: Keeping a running total?

Subject: Re: [xsl] Re: Keeping a running total?
From: Andrew Franz <afranz0@xxxxxxxxxxxxxxxx>
Date: Thu, 13 Jul 2006 22:50:50 +1000
Dimitre Novatchev wrote:

On 7/12/06, Andrew Franz <afranz0@xxxxxxxxxxxxxxxx> wrote:

Okay, assuming the following input:

<xml>
 <factory x="A" capacity = "3" />
 <factory x="B" capacity= "5" />
 <factory x="C" capacity = "3" />
 <factory x="D" capacity = "2" />
 <factory x="E" capacity = "2" />
 ...etc...
</xml>


O(N) algorithm using recursion (not tested):



Good!


I was able to make it work after a few corrections.

What about having a bigger than 2 (variable) number of quotas? How
would your solution change to tackle this?

I suppose a general solution would have a list of quotas (and a corresponding list of quota names), e.g. :
<quotas>
<quota id="Widget" left="{$Widget_quota}" />
<quota id="Gadget" left="{$Gadget_quota}" />
...
</quotas>



In the past I've 'cheated' by using the stack as a list, e.g. as follows:


<xsl:template match="xml">
  <xsl:apply-templates select="factory">
      <xsl:with-param name="left0" select="$Widget_quota" />
      <xsl:with-param name="left1" select="$Gadget_quota" />
      ...
      <xsl:with-param name="name0">Widget</xsl:with-param>
      <xsl:with-param name="name1">Gadget</xsl:with-param>
      ...
  </xsl:apply-templates>
</xsl:template>

then in the factory template, each factory would consume $left0 until it was depleted and then shift by assigning $left1 to $left0, $left2 to $left1 and so on through parameters.
e.g.
<xsl:with-param name="left0" select="$left1" /> <!-- shift to next quota -->
<xsl:with-param name="left1" select="$left2" />
<xsl:with-param name="left2" select="$left3" />
<xsl:with-param name="left3" select="$left4" />


Quota-recursion would end when $left0 was empty then capacity would accumulate in $excess until factories were depleted.

This only works for a finite number of quotas, e.g. like a table where the number of columns is fixed.
It is O(N) because it monotonically advances through both lists (factories and quotas) without backtracking.


Sorry if this is a bit crude (and untested) - sometimes deadlines require less-than-elegant solutions ;-)

Current Thread