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

[Andrew Franz <afranz0@xxxxxxxxxxxxxxxx>]

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 ;-)