# Re: Re: Keeping a running total?

 Subject: Re: Re: Keeping a running total? From: Andrew Franz Date: Thu, 13 Jul 2006 02:07:02 +1000
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):

<xsl:template match="xml">
<xsl:apply-templates select="factory">
<xsl:with-param name="leftW" select="\$Widget_quota" />
<xsl:apply-templates select="factory">
</xsl:template>

<xsl:template match="factory">
<!-- running totals of capacity already used   -->
<xsl:param name="used">0</xsl:param>
<xsl:param name="usedW">0</xsl:param>
<xsl:param name="usedG">0</xsl:param>
<!-- running totals of quota not used   -->
<xsl:param name="leftW">0</xsl:param>
<xsl:param name="leftG">0</xsl:param>

<xsl:choose>
<!-- Capacity used up, output used and move on -->
<xsl:when test="(@capacity = \$used)">
<out factory="{@x}" Widgets="{\$usedW}" Gadgets="{\$usedG}" Excess="{\$used - (\$usedW + \$usedG)}" />
<xsl:apply-templates select="following-sibling::factory[1]">
<xsl:with-param name="leftW" select="\$leftW" />
<xsl:with-param name="leftG" select="\$leftG" />
</xsl:apply-templates>
</xsl:when>

<xsl:when test="not(\$leftW = 0)">
<xsl:choose>
<xsl:when test="(\$leftW &gt;= (@capacity - \$used))">
<xsl:apply-templates select=".">
<xsl:with-param name="used" select="@capacity" />
<xsl:with-param name="usedW" select="(\$usedW + @capacity - \$used)" />
<xsl:with-param name="leftW" select="(\$leftW - (@capacity - \$used))" />
<xsl:with-param name="leftG" select="\$leftG" />
</xsl:apply-templates>
</xsl:when>
<xsl:otherwise>
<xsl:apply-templates select=".">
<xsl:with-param name="used" select="(\$used + \$leftQ)" />
<xsl:with-param name="usedW" select="(\$usedW + \$leftW)" />
<xsl:with-param name="leftG" select="\$leftG" />
</xsl:apply-templates>
</xsl:otherwise>
</xsl:choose>
</xsl:when>

<xsl:when test="not(\$leftG = 0)">
<xsl:choose>
<xsl:when test="(\$leftG &gt;= (@capacity - \$used))">
<xsl:apply-templates select=".">
<xsl:with-param name="used" select="@capacity" />
<xsl:with-param name="usedW" select="\$usedW" />
<xsl:with-param name="usedG" select="(\$usedG + @capacity - \$used)" />
<xsl:with-param name="leftG" select="(\$leftG - (@capacity - \$used))" />
</xsl:apply-templates>
</xsl:when>
<xsl:otherwise>
<xsl:apply-templates select=".">
<xsl:with-param name="used" select="(\$used + \$leftG)" />
<xsl:with-param name="usedW" select="\$usedW" />
<xsl:with-param name="usedG" select="(\$usedG + \$leftG)" />
</xsl:apply-templates>
</xsl:otherwise>
</xsl:choose>
</xsl:when>

<xsl:otherwise>
<xsl:apply-templates select=".">
<xsl:with-param name="used" select="@capacity" />
<xsl:with-param name="usedW" select="\$usedW" />
<xsl:with-param name="usedG"  select="\$usedG" />
</xsl:apply-templates>
</xsl:otherwise>

</xsl:choose>
</xsl:template>

Dimitre Novatchev wrote:

This is one possible solution, however it's time complexity is O(N^2)
and can be unacceptable for producing intermediate results from an
operation over a list of N items.

A recursive solution (such as using the FXSL scanl()
template/function) can have a O(N) complexity.

### PURCHASE STYLUS STUDIO ONLINE TODAY!

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