[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Recursive grouping - simple, XSLT 1.0, fast non-Muench

Subject: Recursive grouping - simple, XSLT 1.0, fast non-Muenchian grouping method
From: "Sergiu Ignat (dyve)" <sergiu.ignat@xxxxxxxx>
Date: Thu, 16 Dec 2004 19:27:46 +0200
isaak asimov
Hello everybody.

I would like to present you a simple, XSLT 1.0, fast grouping method with a
O(N*log(N)) complexity, the same as sorting. The only grouping method I knew
so far is Muenchian that has O(N^2) complexity.

The main idea is to have a named template that takes as a parameter the node
list that should be grouped, processes the group defined by the first
element and recursively calls itself for the rest of the list excluding that
group.

The example below will group books in a book list and will compute how many
books each author has (input XML is shown after it).

<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:template match="/booklist">
  <authors>
   <xsl:call-template name="RecursiveGrouping">
    <xsl:with-param name="list" select="book"/>
   </xsl:call-template>
  </authors>
 </xsl:template>

 <xsl:template name="RecursiveGrouping">
  <xsl:param name="list"/>

  <!-- Selecting the first author name as group identifier and the group
itself-->
  <xsl:variable name="group-identifier" select="$list[1]/@author"/>
  <xsl:variable name="group" select="$list[@author=$group-identifier]"/>

  <!-- Do some work for the group -->
  <author name="{$group-identifier}" number-of-books="{count($group)}"/>

  <!-- If there are other groups left, calls itself -->
  <xsl:if test="count($list)>count($group)">
  <xsl:call-template name="RecursiveGrouping">
    <xsl:with-param name="list"
select="$list[not(@author=$group-identifier)]"/>
  </xsl:call-template>
  </xsl:if>
 </xsl:template>
</xsl:stylesheet>

The input XML for this example is the shown below.

<booklist>
   <book author="Frank Herbert" title="Dune"/>
   <book author="Roberto Quaglia" title="Bread, Butter and Paradoxine"/>
   <book author="Kate Wilhelm" title="Where Late the Sweet Bird Sang"/>
   <book author="Anthony Burgess" title="A Clockwork Orange"/>
   <book author="Frank Herbert" title="Dragon in the Sea"/>
   <book author="Anthony Burgess" title="Earthly Powers"/>
   <book author="Isaak Asimov" title="The Foundation Trilogy"/>
   <book author="Frank Herbert" title="Children of Dune"/>
   <book author="Isaak Asimov" title="The Caves of Steel"/>
</booklist>

Sergiu Ignat
Dynamic Ventures
www.dyve.com

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

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

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.