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

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

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: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.


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