Dimitre Novatchev wrote:
On 7/12/06, Andrew Franz <afranz0(_at_)optushome(_dot_)com(_dot_)au> 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?
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>
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.
This only works for a finite number of quotas, e.g. like a table where
the number of columns is fixed.
It is O(N) because it monotonically advances through both lists
(factories and quotas) without backtracking.
Sorry if this is a bit crude (and untested) - sometimes deadlines
require less-than-elegant solutions ;-)
--~------------------------------------------------------------------
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>
--~--