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

 Subject: Re: [xsl] Re: Keeping a running total? From: "Dimitre Novatchev" Date: Wed, 12 Jul 2006 16:01:38 -0700
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?```

```--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.```

```<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)">
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.```

```--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.```