# Re: Re: Keeping a running total?

 Subject: Re: Re: Keeping a running total? From: Andrew Franz 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}" />
...
</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="name0">Widget</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 ;-)

### PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!