Grouping algorithm in XSLT

Sorting a list of elements in XML seems to be as simple as using known <xsl:sort> element, but what to do if you need to group elements by category?

Let’s see a xml example:

<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="article.xsl" ?>
<countries>
   <country>
      <name>France</name>
      <language>French</language>
      <image>assets/images/french.png</image>
   </country>
   <country>
      <name>Spain</name>
      <language>Spanish</language>
      <image>assets/images/spanish.png</image>
   </country>
   <country>
      <name>England</name>
      <language>English</language>
      <image>assets/images/english.png</image>
   </country>
   <country>
      <name>Mexico</name>
      <language>Spanish</language>
      <image>assets/images/spanish.png</image>
   </country>
    <country>
      <name>Canada</name>
      <language>English</language>
      <image>assets/images/english.png</image>
   </country>
</countries>

Our initial .xsl file looks like:

<xsl:template match="/">
<html>
<head>
    <link rel="stylesheet" href="assets/css/styles.css" media="screen" title="no title" charset="utf-8" />
</head>
    <body>
        <div class="newsletter">
        <div class="newsletter-wrapper">
            <header>
                <h1 id="top"><span class="newsletter-date">COUNTRIES AND LANGUAGES</span></h1>
            </header>
            <main>
                 <xsl:apply-templates select="countries/country" />
             </main>
        </div>
        </div>
    </body>
</html>
</xsl:template>


<xsl:template match="country">
         <country>
                <div class="column-1">
                    <img src="{image}" alt="" />
                </div>
                <div class="column-2">
                    <header>
                        <h2><a href="#"><xsl:value-of select="name"</a></h2>
                    </header>
                    <p><xsl:value-of select="language" /></p>
                </div>
                <div class="clearfix"></div>
         </country>
</xsl:template>

and output looks like:

Countries1_1

So, we have the above elements in a specific order defined by our customer. They’ ve requested grouping countries with the same language but keeping original order, they don’t want them alphabetically sorted.

If we attempt to do it just using <xslt:sort> by language element like below green code:

<xsl:apply-templates select="countries/country" >
      <xsl:sort select="language" />
</xsl:apply-templates>

we’ll get countries grouped by language but alphabetically sorted, i.e: English, French and Spanish, see image below:

Countries2_1

Note: previous xslt code remains the same, but we’re just repeating the most important lines for our purposes.

After some investigation, I’ve stumbled with an algorithm well documented that just resolved my problem, it’s known as the “Muench method”, a grouping nodes algorithm that use the <xsl:key> approach. It’s a three steps method [1] :

1. Define a key for the property we want to use for grouping.
2. Select all of the nodes we want to group. We’ll do some tricks with the key() and generate-id() functions to find the unique grouping values.
3. For each unique grouping value, use the key() function to retrieve all nodes that match it. Because the key() function returns a node-set, we can do further sorts on the set of nodes that match any given grouping value.

Let’s see our implementation of Muench method (green lines):

<!-- Step 1  -->
<xsl:key name="languages" match="country" use="language"/>
<xsl:template match="/">         
    <xsl:apply-templates select="countries/country" />       
</xsl:template>

<xsl:template match="country">
<!-- Step 2 -->
    <xsl:for-each select="self::node()[generate-id(.)=generate-id(key('languages', language)[1])]">
        <xsl:sort select="language"/>

<!-- Step 3 -->
              <xsl:for-each select="key('languages', language)">
                <country>
                 .
                 .
                 .
                </country>
            </xsl:for-each>

     </xsl:for-each>
</xsl:template>

Or well, if you don’t like <xsl:for-each> element you can use  <xsl:apply-templates> instead of it. In this case code looks like:

<!-- Step 1  -->
<xsl:key name="languages" match="country" use="language"/>
<xsl:template match="/">
      <xsl:apply-templates select="countries/country" />
</xsl:template>

<xsl:template match="country">
<!-- Step 2  -->
    <xsl:apply-templates select="self::node()[generate-id(.)=generate-id(key('languages', language)[1])]"  mode="groupByLanguage">
        <xsl:sort select="language"/>
     </xsl:apply-templates>
</xsl:template>

<xsl:template match="country" mode="groupByLanguage">
<!-- Step 3  -->
        <xsl:apply-templates select="key('languages', language)" mode="countryDetails" />
</xsl:template>

<xsl:template  match="country" mode="countryDetails">
    <country>
       .
       .
       .
    </country>
</xsl:template>

And the output of this xsl file is just what we want:

Countries3_1

Now that elements are grouped  by a category,  we can for example reducing icons and languages’ name to just one for language, it’ll depends on our requirements.