How to group multiple adjacent elements by 'columns' in XSLT?

Question

Suppose there is this XML fragment:

<a>t1</a> <a>t2</a> <b>t3</b> <b>t4</b> <b>t5</b> <c>t6</c>

We could visualize it as:

<a>t1</a> <a>t2</a>
<b>t3</b> <b>t4</b> <b>t5</b>
<c>t6</c>

I want to iterate, so that the elements iterated in the first pass are:

<a>t1</a> <b>t3</b> <c>t6</c>

in the second pass:

<a>t2</a> <b>t4</b>

and third:

<b>t5</b>

The above data is only one example. It is possible to have longer sequences of adjacent siblings and not just this fixed set of data.

The requirement is that each group contains elements that share the same count of preceding siblings sharing the same element name.

For example, in the first 'column' <a />, <b />, and <c /> have no preceding siblings with the same name, respectively.

The second 'column' <a />, and <b /> have preceeding sibling count with the same name of 1, respectively.

I want to be able to iterate the items this way in a for-each-group statement, but I am unsure how to express the group-by clause.

Answer 1

The currently accepted answer has O(N^2) time complexity, because it uses preceding-sibling::* for every element.

Here is a solution which may be more efficient - no preceding-sibling::* axis used:

<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output method="text"/>

  <xsl:template match="/*">
    <xsl:variable name="vTop" select="."/>
    <xsl:variable name="vNames" select="distinct-values(*/name())"/>
    <xsl:variable name="vCountNames" select="count($vNames)"/>

    <xsl:for-each select="1 to $vCountNames">
      <xsl:variable name="vCol" select="position()"/>
      <xsl:for-each select="$vNames">
        <xsl:apply-templates select="$vTop/*[name() eq current()][$vCol]"/>
      </xsl:for-each>
    </xsl:for-each>
  </xsl:template>
</xsl:stylesheet>

When this transformation is applied on the following XML document (The provided fragment surrounded by a top (document) element):

<t>
 <a>t1</a> <a>t2</a>
 <b>t3</b> <b>t4</b> <b>t5</b>
 <c>t6</c>
</t>

The wanted result is produced (the values of each element when traversed by columns):

t1t3t6t2t4t5

This solution is O(N * M) where N is the number of elements and M is the number of their distinct names.

Thus if N = k times M then this solution is going to be, asymptotically, k times faster than an O(N^2) solution.

---

II. A single, pure XPath 2.0 expression visiting the elements in column-wise manner:

  for $vTop in /*,
      $vCol in 1 to count(distinct-values($vTop/*/name())),
      $vName in distinct-values($vTop/*/name())
     return
      $vTop/*[name() eq $vName][$vCol]  

XSLT-based verification:

  <xsl:template match="/*">
    <xsl:sequence select=
     "for $vTop in /*,
          $vCol in 1 to count(distinct-values($vTop/*/name())),
          $vName in distinct-values($vTop/*/name())
         return
          $vTop/*[name() eq $vName][$vCol]  
     "/>
  </xsl:template>
</xsl:stylesheet>

When applied on the same XML document, this transformation evaluates the XPath expression and outputs the result of this evaluation:

t1t3t6t2t4t5

---

III. XSLT 1.0 solution:

This transformation:

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output method="text"/>

 <xsl:key name="kByName" match="/*/*" use="name()"/>

 <xsl:variable name="vDistinctNamed" select=
  "/*/*[generate-id() = generate-id(key('kByName', name())[1])]"/>

  <xsl:variable name="vNumCols">
    <xsl:for-each select="/*/*[generate-id() = generate-id(key('kByName', name())[1])]">
      <xsl:sort select=
       "count(key('kByName', name()))" data-type="number" order="descending"/>
      <xsl:if test="position()=1">
        <xsl:value-of select="count(key('kByName', name()))"/>
      </xsl:if>
    </xsl:for-each>
  </xsl:variable>

  <xsl:template match="/*">
    <xsl:for-each select="*[not(position() > $vNumCols)]">
      <xsl:variable name="vCol" select="position()"/>
      <xsl:for-each select="$vDistinctNamed">
        <xsl:variable name="vthisElement" select="/*/*[name() = name(current())][$vCol]"/>
        <xsl:if test="$vthisElement">
           <xsl:value-of select="concat(/*/*[name() = name(current())][$vCol],', ')"/>
        </xsl:if>
      </xsl:for-each>
    </xsl:for-each>
  </xsl:template>
</xsl:stylesheet>

when applied on the same XML document, produces the same correct result:

t1, t3, t6, t2, t4, t5, 

Answer 2

The template

<xsl:template match="div">
    <xsl:for-each-group select="*" group-by="count(preceding-sibling::*[node-name(.) = node-name(current())])">
        <group key="{current-grouping-key()}">
            <xsl:copy-of select="current-group()"/>
        </group>
    </xsl:for-each-group>
</xsl:template>

transforms

<div>
    <a>t1</a> <a>t2</a> <b>t3</b> <b>t4</b> <b>t5</b> <c>t6</c>
</div>

into

<group key="0">
   <a>t1</a>
   <b>t3</b>
   <c>t6</c>
</group>
<group key="1">
   <a>t2</a>
   <b>t4</b>
</group>
<group key="2">
   <b>t5</b>
</group>