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

["Dimitre Novatchev" <dnovatchev@xxxxxxxxx>]

> > What about having a bigger than 2 (variable) number of quotas? How
> > would your solution change to tackle this?
> >
> I suppose a general solution would have a list of quotas (and a
> corresponding list of quota names), e.g. :
>    <quotas>
>        <quota id="Widget" left="{$Widget_quota}" />
>        <quota id="Gadget" left="{$Gadget_quota}" />
>        ...
>    </quotas>


Updating this list on every template call leads to O(Qn)*O(Fn)  time
complexity, where Fn is the number of factories and Qn the number of
quotas.

In the general case this is quite similar to quadratic time complexity.


> In the past I've 'cheated' by using the stack as a list, e.g. as follows:
>
> <xsl:template match="xml">
>   <xsl:apply-templates select="factory">
>       <xsl:with-param name="left0" select="$Widget_quota" />
>       <xsl:with-param name="left1" select="$Gadget_quota" />
>       ...
>       <xsl:with-param name="name0">Widget</xsl:with-param>
>       <xsl:with-param name="name1">Gadget</xsl:with-param>
>       ...
>   </xsl:apply-templates>
> </xsl:template>
>
> then in the factory template, each factory would consume $left0 until it
> was depleted and then shift by assigning $left1 to $left0, $left2 to
> $left1 and so on through parameters.
> e.g.
>        <xsl:with-param name="left0" select="$left1" />   <!-- shift to
> next quota -->
>        <xsl:with-param name="left1" select="$left2" />
>        <xsl:with-param name="left2" select="$left3" />
>        <xsl:with-param name="left3" select="$left4" />
>
> Quota-recursion would end when $left0 was empty then capacity would
> accumulate in $excess until factories were depleted.


Having to perform such shifts on template calls again leads to
quadratic-like time complexity.

Better time complexity can be achieved if the running totals for
*both* factories and quotas are calculated with an O(N) (linear)
algorithm.

The implementation I provided could have better than quadratic time
complexity if it used a more efficient way to find overlapping
intervals -- a binary search with an f:binSearch() - like function
would be O(Log2(Qn)). In this case the time complexity would be:

 O(Fn)*O(Log2(Qn))

For simplicity, in the implementation I provided the identification of
overlapping intervals traverses all quotas intervals for every
factory.

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