RE: [xsl] How efficient is DVC? - A grouping example

["Michael Kay" <mhk@xxxxxxxxx>]

This is fascinating stuff, but the proof of the pudding is in the
eating: have you made any comparative performance measurements, using a
non-trivial input file?

Michael Kay
Software AG
home: Michael.H.Kay@xxxxxxxxxxxx
work: Michael.Kay@xxxxxxxxxxxxxx 

> -----Original Message-----
> From: owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx 
> [mailto:owner-xsl-list@xxxxxxxxxxxxxxxxxxxxxx] On Behalf Of 
> Robbert van Dalen
> Sent: 22 March 2003 21:07
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: [xsl] How efficient is DVC? - A grouping example
> 
> 
> Hello all,
> 
> Everyone interested in efficient algorithms might be 
> interested in this 'article'. Note that I'm not used to write 
> articles so excuse me if I'm not making a point clearly.
> 
> All the code is free - copy it if you like.
> 
> Cheers,
> 
> RvD
> 
> _____________________________________________________________
> ABSTRACT
> 
> Grouping without using the key() function is not very 
> difficult in practice. But to implement it efficiently is not 
> easy task. This article presents a modified Divide And 
> Conquer (DVC) algorithm to implement grouping. The algorithm 
> is not only useful for grouping, but may be generalised to 
> help improve other DVC algorithms.
> 
> 
> INTRODUCTION
> 
> Muenchian grouping is by far the most efficient method to 
> group nodes with XSLT. But there are some situations when 
> Muenchian grouping can't be used, for example if you want to 
> group tree-fragments Tree-fragments are heavily used when 
> multiple passes are needed to compute a result with only one 
> stylesheet. However, you cannot use the key() function on 
> tree-fragments because XSLT doesn't allow you to (there is no 
> nodeset parameter)
> 
> PREREQUISITES
> All examples are tested against XALAN. Make sure you always 
> include the following stylesheet header:
> 
> <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
> xmlns:xalan="http://xml.apache.org/xalan"; version="1.1" 
> exclude-result-prefixes="xalan">
> 
> 
> GROUPING EXAMPLE
> The following example will give you an idea of grouping 
> tree-fragments without using the key() function.
> 
> Input XML (taken from Michael Kay's book)
> 
> <cities>
>   <city name="Barcelona" country="Espana"/>
>   <city name="Paris" country="France"/>
>   <city name="Roma" country="Italia"/>
>   <city name="Madrid" country="Espana"/>
>   <city name="Milano" country="Italia"/>
>   <city name="Firenze" country="Italia"/>
>   <city name="Napoli" country="Italia"/>
>   <city name="Lyon" country="France"/>
> </cities>
> 
> Stylesheet (partly copied from Michael Kay's book)
> 
> <xsl:template match="cities">
>   <xsl:variable name="sorted">
>     <xsl:for-each select="./city">
>       <xsl:sort select="@country"/>
>       <xsl:copy-of select="."/>
>     </xsl:for-each>
>   </xsl:copy-of>
> 
>   <xsl:variable name="sorted-tree-fragment" 
> select="xalan:nodeset($sorted)/*"/>
> 
>   <!-- Gets the groups -->
>   <xsl:variable name="groups">
>     <xsl:apply-templates select="$sorted-tree-fragment"/>
>   </xsl:variable>
> 
>   <!-- Iterate through all the groups -->
>   <xsl:for-each select="xalan:nodeset($groups)/*">
>     <xsl:variable name="country" select="."/>
>     <xsl:copy>
>         <!-- Copy the nodes with the same country -->
>       <xsl:copy-of select="$sorted-tree-fragment[country = 
> $country]"/>
>       <xsl:copy-of select="@*"/>
>     </xsl:copy>
>   </xsl:for-each>
> </xsl:template>
> 
> <xsl:template match="city">
>   <variable name="preceding" select="./preceding-sibling::*[1]"/>
>   <xsl:if test="not(./@country = $preceding/@country)">
>     <group id="{$preceding/@country}"/>
>   </xsl:if>
> </xsl:template>
> 
> Output:
> 
> <group id="Espana">
>   <city name="Barcelona" country="Espana"/>
>   <city name="Madrid" country="Espana"/>
> </group>
> <group id="France">
>   <city name="Paris" country="France"/>
>   <city name="Lyon" country="France"/>
> </group>
> <group id="Italia">
>   <city name="Roma" country="Italia"/>
>   <city name="Milano" country="Italia"/>
>   <city name="Firenze" country="Italia"/>
>   <city name="Napoli" country="Italia"/>
> </group>
> 
> This looks like a OK solution, but let's get a closer look on 
> what is going on.
> 
> 1) First the cities are sorted on the @country attribute. 
> After this, cities that share the same @country value will be 
> following each other, which is a property we can exploit in step 2.
> 2) Then the template that matches city nodes will be called N 
> times if there are N cities to be grouped. For each city node 
> in the sorted set the 'following-sibling::*[1]' node(s) are 
> matched. If they're not equal, the city node will mark a new 
> group. As Michael Kay already pointed out in his book, the 
> efficiency of this approach depends on the implementation of 
> 'following-sibling::*[1]'. If this expression has time 
> complexity O(1) then the overall time complexity of getting 
> all the groups will be O(N) (leaving sorting out of the equation).
> 3) Strangely enough, the last step is actually the most 
> problematic. Let's say the second step gave us 3 groups. 
> Then, for each group, the expression 
> '$sorted-tree-fragment[country = $country] will be evaluated 
> with time complexity O(N).
> 
> So, does this mean the overall time complexity will be 3*N = 
> O(N)? The answer is definitely no! It does hold for a small 
> number of groups, but if we have N/2 groups then time 
> complexity will be O(N^2). Selecting nodes with XPATH 
> expressions is usually OK, but in this example we want to 
> select the K cities that share the same @country value in 
> O(K) time, not
> O(N) time.
> So the question we really want to anwer is: 'how can we 
> efficiently select a subset of nodes without traversing them 
> all?'. The anwser is: 'this all depends on the selection 
> criterium.' Still, if the selection criterium isn't too 
> complex, we can still hope for a better solution. One 
> solution is that we don't use XPATH expressions to select 
> nodes, but rather walk through the nodes by using recursive calls.
> 
> 
> GROUPING USING RECURSION
> 
> One idea to reduce time complexity of the previous example is 
> by slightly modifying the match='city' template:
> 
> <xsl:template match="city">
>   <variable name="preceding" select="./preceding-sibling::*[1]"/>
>   <xsl:choose>
>     <xsl:when test="not(./@country = $preceding/@country)">
>       <group id="{./@country}">
>         <xsl:copy-of select="."/>
>         <xsl:apply-templates name="./following-sibling::*[1]"/>
>       </group>
>     </xsl:when>
>     <xsl:otherwise>
>       <xsl:copy-of select="."/>
>       <xsl:apply-templates name="./following-sibling::*[1]"/>
>     </xsl:otherwise>
>   </xsl:choose>
> </xsl:template>
> 
> If we take the same input and use the following 'apply-templates'
> 
> <xsl:apply-templates match="xalan:nodeset($sorted)/*[1]"/>
> 
> ...we get the following result.
> 
> <group id="Espana">
>   <city name="Barcelona" country="Espana"/>
>   <city name="Madrid" country="Espana"/>
>   <group id="France">
>     <city name="Paris" country="France"/>
>     <city name="Lyon" country="France"/>
>     <group id="Italia">
>       <city name="Roma" country="Italia"/>
>       <city name="Milano" country="Italia"/>
>       <city name="Firenze" country="Italia"/>
>       <city name="Napoli" country="Italia"/>
>     </group>
>   </group>
> </group>
> 
> This is almost what we want. The following 'apply-templates' 
> will flatten the tree structure to return the same result as 
> the previous example.
> 
> <xsl:apply-templates select="xalan:nodeset($groups)"/>
> 
> <xsl:template match="group">
>   <xsl:copy>
>     <xsl:apply-templates select="./group"/>
>     <xsl:copy-of select="./city"/>
>     <xsl:copy-of select="@*"/>
>   </xsl:copy>
> </xsl:template>
> 
> The time complexity of the recursive solution can be proven 
> to be O(N) but with the recursion depth also to be O(N). 
> Unfortunately, most XSLT implementations have a maximum 
> recursion depth (~1000) so this is not a general solution.
> 
> 
> DVC AND THE BINARY TREE
> Dimitre Novatchev was one of the first to mention Divide and 
> Conquer (DVC) algorithms to reduce recursion depth. Because 
> most XSLT implementations out there still do not support 
> tail-recursion elimination, DVC is the way to go if you want 
> to process a lot of nodes. The idea behind DVC is that to 
> attack a big problem, you should divide it into a number of 
> smaller problems. Not surprisingly, dividing a problem into 
> just 2 subproblems is enough to reduce recursion depth to be 
> O(log2(N)). The following example will give you an idea of 
> how this works:
> 
> 
> The XML input:
> 
> <nodes>
>   <node v="1"/>
>   <node v="2"/>
>   <node v="3"/>
>   <node v="4"/>
>   <node v="5"/>
>   <node v="6"/>
>   <node v="7"/>
>   <node v="8"/>
> </nodes>
> 
> The Stylesheet:
> 
> <xsl:template match="/">
>   <xsl:call-template name="partition">
>     <xsl:with-param name="nodes" select="//node"/>
>   </xsl:call-template>
> </xsl:template>
> 
> 
> <xsl:template name="partition">
>   <xsl:param name="nodes"/>
> 
>   <xsl:variable name="half" select="floor(count($nodes) div 2)"/>
> 
>   <b>
>   <xsl:choose>
>     <xsl:when test="count($nodes) &lt;= 1">
>     <!-- There is only one node left: stop dividing problem -->
>       <xsl:copy-of select="$nodes"/>
>     </xsl:when>
>     <xsl:otherwise>
>     <!-- divide in first half of nodes (left) -->
>         <xsl:call-template name="partition">
>           <xsl:with-param name="nodes" 
> select="$nodes[position() &lt;= $half]"/>
>         </xsl:call-template>
>     <!-- divide in second half of nodes (right) -->
>         <xsl:call-template name="partition">
>           <xsl:with-param name="nodes" 
> select="$nodes[position() &gt; $half]"/>
>         </xsl:call-template>
>     </xsl:otherwise>
>   </xsl:choose>
>   </b>
> </xsl:template>
> 
> The output:
> 
> <b>
>   <b>
>     <b>
>       <b>
>         <node v="1"/>
>       </b>
>       <b>
>         <node v="2"/>
>       </b>
>     </b>
>     <b>
>       <b>
>         <node v="3"/>
>       </b>
>       <b>
>         <node v="4"/>
>       </b>
>     </b>
>   </b>
>   <b>
>     <b>
>       <b>
>         <node v="5"/>
>       </b>
>       <b>
>         <node v="6"/>
>       </b>
>     </b>
>     <b>
>       <b>
>         <node v="7"/>
>       </b>
>       <b>
>         <node v="8"/>
>       </b>
>     </b>
>   </b>
> </b>
> 
> The result is what is called a binary tree representation. At 
> first this representation doesn't seem all that useful. Later 
> we will see that specialised binary trees can be (re-)used to 
> implement almost any recursive function without exceeding the 
> maximum recursion depth.
> 
> Let's sum all the @v values with the use of the binary 
> (fragment) tree:
> 
> <xsl:template match="/"/>
>   <xsl:variable name="btree">
>       <xsl:call-template name="partition">
>         <xsl:with-param name="nodes" select="//node"/>
>       </xsl:call-template>
>   </xsl:variable>
> 
>   <xsl:call-template name="sum-binary-tree">
>     <xsl:with-param name="bnode" select="xalan:nodeset($btree)/*"/>
>   </xsl:call-template>
> </xsl:template>
> 
> <xsl:template name="sum-binary-tree">
>   <xsl:param name="bnode"/>
> 
>   <xsl:choose>
>     <xsl:when test="$bnode/node">
>       <xsl:value-of select="$bnode/node/@v"/>
>     </xsl:when>
>     <xsl:otherwise>
>     <xsl:variable name="first">
>       <xsl:call-template name="sum-binary-tree">
>         <xsl:with-param name="bnode" select="$bnode/b[1]"/>
>       </xsl:call-template>
>     </xsl:variable>
>       <xsl:variable name="second">
>       <xsl:call-template name="sum-binary-tree">
>         <xsl:with-param name="bnode" select="$bnode/b[2]"/>
>       </xsl:call-template>
>     </xsl:variable>
>       <xsl:value-of select="$first + $second"/>
>     </xsl:otherwise>
>   </xsl:choose>
> </xsl:template>
> 
> This gives the result: 36
> 
> Let's analyse the partition template in terms of time 
> complexity. It's easy to prove that it is equal to the number 
> nodes being copied. The partition algorithm uses the XPATH 
> expression '$nodes[count() &gt; $half]' to split the nodes in 
> half. This construction is almost exclusively used by all DVC 
> or 'chunk' algorithms including many of Dimitre Novatchev's 
> examples. But how about the number of nodes being copied? The 
> following table lists the number of nodes being copied for 
> each partition.
> 
> partition(1)
>   number of copies 1
> 
> partition(2)
>   number of copies
>     l: 1 + partition(1)
>     r: 1 + partition(1)
> 
> partition(4)
>   number of copies
>     l: 2 + partition(2)
>     r: 2 + partition(2)
> 
> partition(8)
>   number of copies
>     l: 4 + partition(4)
>     r: 4 + partition(4)
> 
> etc.
> 
> The number of copies when calling partition(4) is:
> (2 + (1 + 1) + 2 + (1 + 1)) = 2*4
> 
> The number of copies when calling partition(8) is:
> 4 + (2 + (1 + 1) + 2 + (1 + 1)) + 4 + (2 + (1 + 1) + 2 + (1 + 
> 1)) = 3*8
> 
> So the overall 'copy' complexity is O(log2(N)*N).
> Although the number of recursive calls is O(N) the XSLT 
> processor still spends at least O(log2(N)*N) time because it 
> must copy (and select) half of the nodes for the each 
> recursive call (twice). Copying nodes should be avoided as 
> much as possible because it slows down recursion considerably.
> 
> 
> MODIFIED DVC ALGORITHM: RANGE PARTITIONING
> 
> The following implementation of a binary partition doesn't 
> copy a list of nodes but just one node at each recursive 
> call. It uses the so called 'sibling' axis to walk through 
> the list. Because there are O(N) recursive calls, this means 
> that O(N) nodes are copied. Does this mean that the overall 
> time complexity will be O(N) too? The answer is: probably 
> yes, but at worst it will be O(N^2).
> 
> Input XML:
> 
> <nodes>
>   <node v="1"/>
>   <node v="2"/>
>   <node v="3"/>
>   <node v="4"/>
>   <node v="5"/>
>   <node v="6"/>
>   <node v="7"/>
>   <node v="8"/>
> </nodes>
> 
> The Stylesheet:
> 
> <xsl:template match="/">
>   <xsl:call-template name="partition-ranges">
>     <xsl:with-param name="node" select="//node[1]"/>
>   </xsl:call-template>
> </xsl:template>
> 
> <xsl:template name="partition-ranges">
>   <xsl:param name="node"/>
>   <xsl:param name="s" 
> select="(count($node/preceding-sibling::*)) + 1"/>
>   <xsl:param name="e" 
> select="(count($node/following-sibling::*)) + $s"/>
> 
>   <xsl:if test="$node">
>     <xsl:element name="r">
>       <xsl:attribute name="s">
>         <xsl:value-of select="$s"/>
>       </xsl:attribute>
>       <xsl:attribute name="e">
>         <xsl:value-of select="$e"/>
>       </xsl:attribute>
>       <xsl:choose>
>         <xsl:when test="$s = $e">
>             <xsl:copy-of select="$node"/>
>         </xsl:when>
>         <xsl:otherwise>
>           <xsl:variable name="w" select="floor(($e - $s + 1) div 2)"/>
>           <xsl:variable name="m" select="$s + $w"/>
>           <xsl:call-template name="partition-ranges">
>             <xsl:with-param name="node" select="$node"/>
>             <xsl:with-param name="s" select="$s"/>
>             <xsl:with-param name="e" select="$m - 1"/>
>           </xsl:call-template>
>           <xsl:call-template name="partition-ranges">
>             <xsl:with-param name="node" 
> select="$node/following-sibling::*[$w]"/>
>             <xsl:with-param name="s" select="$m"/>
>             <xsl:with-param name="e" select="$e"/>
>           </xsl:call-template>
>         </xsl:otherwise>
>       </xsl:choose>
>     </xsl:element>
>   </xsl:if>
> </xsl:template>
> 
> The output:
> 
> <r s="1" e="8">
>   <r s="1" e="4">
>     <r s="1" e="2">
>       <r s="1" e="1">
>         <node v="1"/>
>       </r>
>       <r s="2" e="2">
>         <node v="2"/>
>       </r>
>     </r>
>     <r s="3" e="4">
>       <r s="3" e="3">
>         <node v="3"/>
>       </r>
>       <r s="4" e="4">
>         <node v="4"/>
>       </r>
>     </r>
>   </r>
>   <r s="5" e="8">
>     <r s="5" e="6">
>       <r s="5" e="5">
>         <node v="5"/>
>       </r>
>       <r s="6" e="6">
>         <node v="6"/>
>       </r>
>     </r>
>     <r s="7" e="8">
>       <r s="7" e="7">
>         <node v="7"/>
>       </r>
>       <r s="8" e="8">
>         <node v="8"/>
>       </r>
>     </r>
>   </r>
> </r>
> 
> Note that the output resembles the previous example but 
> instead of <b> nodes, <r> (Range) nodes are used. This just 
> makes it more convenient to select ranges of nodes later on. 
> The actual 'splitting' is done through the following 
> expression '[$node/following-sibling::*[$w]' with $w being 
> the lenght of the list divided by 2. Let's compare overall 
> time complexity with the possible implementations of 
> 'following-sibling::[w]'
> 
> following-sibling::*[w] | total time 
> _____________________________________
> O(1)                    | O(N)
> O(w)                    | O(log2(N)*N)
> O(N)                    | O(N^2)
> 
> So at worst it will be quadratic. So the question still 
> remains if it is theoretically possible to do binary 
> partitioning without copying to much nodes. Nevertheless, 
> experiments with XALAN have shown that the implementation is 
> not quadratic.
> 
> 
> GROUPING WITH A BINARY TREE
> 
> The new and improved grouping algorithm is more or less the 
> same as the first one except where using ranges to select 
> nodes which are in the same group.
> Thus:
> 
> 1) we sort the nodes for a given key
> 2) then compute the ranges of nodes which have the same key
> 3) and then select the (sorted) nodes for each range.
> 
> To efficiently select a range of nodes we will be using the 
> binary tree.
> 
> Here's the whole solution:
> 
> Input XML:
> 
> <cities>
>   <city name="Barcelona" country="Espana"/>
>   <city name="Paris" country="France"/>
>   <city name="Roma" country="Italia"/>
>   <city name="Madrid" country="Espana"/>
>   <city name="Milano" country="Italia"/>
>   <city name="Firenze" country="Italia"/>
>   <city name="Napoli" country="Italia"/>
>   <city name="Lyon" country="France"/>
> </cities>
> 
> 
> The stylesheet (WARNING, THIS IS A BIT LENGHTY):
> 
> <!-- Group cities on country -->
> <xsl:template match="/">
>   <xsl:call-template name="group-on-key">
>     <xsl:with-param name="nodes" select="//city"/>
>     <xsl:with-param name="key" select="'country'"/>
>   </xsl:call-template>
> </xsl:template>
> 
> <!--
>   Template: group-on-key
>   Use this template to group <nodes> which share a common 
> attribute <key>
>   The result will be sub-sets of <nodes> surrounded by <group/> tags
> -->
> 
> 
> <xsl:template name="group-on-key">
>   <xsl:param name="nodes"/>
>   <xsl:param name="key"/>
> 
>   <xsl:variable name="items">
>     <xsl:for-each select="$nodes">
>       <item>
>         <key>
>           <xsl:value-of select="./@*[name() = $key]"/>
>         </key>
>         <value>
>           <xsl:copy-of select="."/>
>         </value>
>       </item>
>     </xsl:for-each>
>   </xsl:variable>
> 
>   <xsl:variable name="grouped-items">
>     <xsl:call-template name="group-on-item">
>       <xsl:with-param name="nodes" select="xalan:nodeset($items)/*"/>
>       <xsl:with-param name="key" select="$key"/>
>     </xsl:call-template>
>   </xsl:variable>
> 
>   <xsl:for-each select="xalan:nodeset($grouped-items)/*">
>     <xsl:copy>
>       <xsl:for-each select="./*">
>         <xsl:copy-of select="./value/*[1]"/>
>       </xsl:for-each>
>     </xsl:copy>
>   </xsl:for-each>
> </xsl:template>
> 
> <!--
>  Template: group-on-item
>  Use this template to group <nodes> which share a common 
> structure.  You can build this structure yourself if you want 
> to group on something else
> 
>  The structure is the <item> structure and has the following 
> layout  <item>
>   <key>
>    aKey (can be anything, preferrably a string)
>   </key>
>   <value>
>    aValue (can be anything, probably a node(set))
>   </value>
>  </item>
> 
>  <items> will we grouped on the string value of <key>
>  The result will be sub-sets of <items> surrounded by <group/> tags
> -->
> 
> <xsl:template name="group-on-item">
>   <xsl:param name="nodes"/>
> 
>   <!-- Step 1 -->
>   <xsl:variable name="sorted">
>     <xsl:for-each select="$nodes">
>       <xsl:sort select="./key[1]/"/>
>       <xsl:copy-of select="."/>
>     </xsl:for-each>
>   </xsl:variable>
> 
>   <xsl:variable name="sorted-tree" select="xalan:nodeset($sorted)/*"/>
> 
>   <!-- Step 2.1 -->
>   <xsl:variable name="pivots">
>     <xsl:call-template name="pivots">
>       <xsl:with-param name="nodes" select="$sorted-tree"/>
>     </xsl:call-template>
>   </xsl:variable>
> 
>   <!-- Step 2.2 -->
>   <xsl:variable name="ranges">
>     <xsl:call-template name="ranges">
>       <xsl:with-param name="pivots" 
> select="xalan:nodeset($pivots)/*"/>
>       <xsl:with-param name="length" select="count($sorted-tree)"/>
>     </xsl:call-template>
>   </xsl:variable>
> 
>   <!-- Step 3.1 -->
>   <xsl:variable name="partition-ranges">
>     <xsl:call-template name="partition-ranges">
>       <xsl:with-param name="node" select="$sorted-tree[1]"/>
>     </xsl:call-template>
>   </xsl:variable>
> 
>   <xsl:variable name="root-partition" 
> select="xalan:nodeset($partition-ranges)/*[1]"/>
> 
>   <!-- Step 3.2 -->
>   <xsl:for-each select="xalan:nodeset($ranges)/r">
>     <xsl:variable name="s" select="./@s"/>
>     <xsl:variable name="e" select="./@e"/>
> 
>     <group>
>       <xsl:call-template name="range-in-partition">
>         <xsl:with-param name="s" select="$s"/>
>         <xsl:with-param name="e" select="$e"/>
>         <xsl:with-param name="p" select="$root-partition"/>
>       </xsl:call-template>
>     </group>
>   </xsl:for-each>
> 
> </xsl:template>
> 
> <xsl:template name="pivots">
>   <xsl:param name="nodes"/>
>   <xsl:param name="key"/>
> 
>   <xsl:for-each select="$nodes">
>     <xsl:if test="not(string(./key[1]/) = 
> string(./following-sibling::*[1]/key[1]/))">
>       <pivot>
>         <xsl:value-of select="position()"/>
>       </pivot>
>     </xsl:if>
>   </xsl:for-each>
> </xsl:template>
> 
> <xsl:template name="ranges">
>   <xsl:param name="pivots" select="../"/>
>   <xsl:param name="length" select="0"/>
> 
>   <xsl:choose>
>   <xsl:when test="count($pivots) &gt;= 1">
>   <xsl:for-each select="$pivots">
>     <xsl:variable name="p" select="./preceding-sibling::*[1]"/>
>     <r>
>       <xsl:attribute name="s">
>         <xsl:choose>
>           <xsl:when test="$p">
>             <xsl:value-of select="$p + 1"/>
>           </xsl:when>
>           <xsl:otherwise>
>             <xsl:value-of select="1"/>
>           </xsl:otherwise>
>         </xsl:choose>
>       </xsl:attribute>
>       <xsl:attribute name="e">
>         <xsl:value-of select="string(.)"/>
>       </xsl:attribute>
>     </r>
>   </xsl:for-each>
>   </xsl:when>
>   <xsl:otherwise>
>     <r>
>       <xsl:attribute name="s">
>         <xsl:value-of select="1"/>
>       </xsl:attribute>
>       <xsl:attribute name="e">
>         <xsl:value-of select="$length"/>
>       </xsl:attribute>
>     </r>
>   </xsl:otherwise>
>   </xsl:choose>
> </xsl:template>
> 
> <!--
>  Template: range-in-partition
>  Selects a RANGE of nodes using a binary tree
> 
>  XSLT isn't really helping to make things easy but try to do 
> this in a DVC style directly without the help of a binary tree.
> -->
> 
> <xsl:template name="range-in-partition">
>   <xsl:param name="p"/>
>   <xsl:param name="s" select="$p/@s"/>
>   <xsl:param name="e" select="$p/@e"/>
> 
>   <xsl:variable name="ps" select="number($p/@s)"/>
>   <xsl:variable name="pe" select="number($p/@e)"/>
> 
>   <xsl:if test="$s &lt;= $pe and $e &gt;= $ps">
>     <xsl:if test="$ps = $pe">
>       <xsl:copy-of select="$p/*[1]"/>
>     </xsl:if>
>     <xsl:choose>
>       <xsl:when test="$s &gt; $ps">
>         <xsl:variable name="s1" select="$s"/>
>         <xsl:choose>
>           <xsl:when test="$e &lt; $pe">
>             <xsl:variable name="e1" select="$e"/>
>             <xsl:for-each select="$p/*">
>               <xsl:call-template name="range-in-partition">
>                 <xsl:with-param name="s" select="$s1"/>
>                 <xsl:with-param name="e" select="$e1"/>
>                 <xsl:with-param name="p" select="."/>
>               </xsl:call-template>
>             </xsl:for-each>
>           </xsl:when>
>           <xsl:otherwise>
>             <xsl:variable name="e1" select="$pe"/>
>             <xsl:for-each select="$p/*">
>               <xsl:call-template name="range-in-partition">
>                 <xsl:with-param name="s" select="$s1"/>
>                 <xsl:with-param name="e" select="$e1"/>
>                 <xsl:with-param name="p" select="."/>
>               </xsl:call-template>
>             </xsl:for-each>
>           </xsl:otherwise>
>         </xsl:choose>
>       </xsl:when>
>       <xsl:otherwise>
>         <xsl:variable name="s1" select="$ps"/>
>         <xsl:choose>
>           <xsl:when test="$e &lt; $pe">
>             <xsl:variable name="e1" select="$e"/>
>             <xsl:for-each select="$p/*">
>               <xsl:call-template name="range-in-partition">
>                 <xsl:with-param name="s" select="$s1"/>
>                 <xsl:with-param name="e" select="$e1"/>
>                 <xsl:with-param name="p" select="."/>
>               </xsl:call-template>
>             </xsl:for-each>
>           </xsl:when>
>           <xsl:otherwise>
>             <xsl:variable name="e1" select="$pe"/>
>             <xsl:for-each select="$p/*">
>               <xsl:call-template name="range-in-partition">
>                 <xsl:with-param name="s" select="$s1"/>
>                 <xsl:with-param name="e" select="$e1"/>
>                 <xsl:with-param name="p" select="."/>
>               </xsl:call-template>
>             </xsl:for-each>
>           </xsl:otherwise>
>         </xsl:choose>
>       </xsl:otherwise>
>     </xsl:choose>
>   </xsl:if>
> </xsl:template>
> 
> Output XML:
> 
> <group>
>   <city name="Barcelona" country="Espana"/>
>   <city name="Madrid" country="Espana"/>
> </group>
> <group>
>   <city name="Paris" country="France"/>
>   <city name="Lyon" country="France"/>
> </group>
> <group>
>   <city name="Roma" country="Italia"/>
>   <city name="Milano" country="Italia"/>
>   <city name="Firenze" country="Italia"/>
>   <city name="Napoli" country="Italia"/>
> </group>
> 
> 
> CONCLUSION
> 
> An efficient DVC algorithm is given for grouping using a 
> binary tree. That binary trees can be build with time 
> complexity O(N) and 'copy' complexity O(N) - without relying 
> to much on implementations - is still an open question.
> 
> 
> 
>  XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
> 


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list