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

[Andrew Franz <afranz0@xxxxxxxxxxxxxxxx>]

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:with-param name="leftG" select="$Gadget_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.