# Re: Re: Keeping a running total?

 Subject: Re: Re: Keeping a running total? From: "Dimitre Novatchev" Date: Fri, 14 Jul 2006 22:46:44 -0700
```> Having to perform such shifts on template calls again leads to

This is not correct.

```A template call will occur in 2 cases:
1. quota < capacity, in which case quota is consumed and quotas are shifted
2. capacity < quota, in which case you shift to the next factory```

Order(Qn) + Order(Fn)

```Like I said, "It is O(N) because it monotonically advances through both
lists (factories and quotas) without backtracking"```

So, how many times will parameter shift be required?

```Cheers,
Dimitre Novatchev```

On 7/14/06, Andrew Franz <afranz0@xxxxxxxxxxxxxxxx> wrote:
Dimitre Novatchev wrote:

```>> > 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}" />
>>        ...
>>    </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="name0">Widget</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

This is not correct.

```A template call will occur in 2 cases:
1. quota < capacity, in which case quota is consumed and quotas are shifted
2. capacity < quota, in which case you shift to the next factory```

Order(Qn) + Order(Fn)

```Like I said, "It is O(N) because it monotonically advances through both
lists (factories and quotas) without backtracking"```

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

### PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!