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="{(_at_)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 >= (@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 >= (@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.
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--