[xsl] Sorting with unknown number of sort keys (Was: Re: Sort question)

Subject: [xsl] Sorting with unknown number of sort keys (Was: Re: Sort question)
From: "Dimitre Novatchev" <dnovatchev@xxxxxxxxx>
Date: Sat, 1 Mar 2003 20:07:39 +0100
"Tom Whitehouse" <whitehousetom@xxxxxxxxxxx> wrote in message
news:F112qZ2GWc4Ct2VREdA0000ba40@xxxxxxxxxxxxxx
> Thanks for your help and I understand what your getting at, but what if
the
> XML wasn`t quite so simple, ie:

Hi Tom,

As I said in my previous message, in the general case it would be necessary
to use a generic sort template and pass to it a function (template reference
in XSLT 1.0) that compares two nodes.

Here's the general solution:

testhSort2.xsl:
---------------
<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
  xmlns:myFunGT="my:myFunGT"
  exclude-result-prefixes="myFunGT"
>

  <xsl:import href="hSort.xsl"/>

  <xsl:output omit-xml-declaration="yes" indent="yes"/>

  <xsl:template match="/">
    <xsl:call-template name="hSort">
      <xsl:with-param name="pList" select="/*/*"/>
      <xsl:with-param name="pFunGT"
       select="document('')/*/myFunGT:*[1]"/>
    </xsl:call-template>
  </xsl:template>

  <myFunGT:myFunGT/>
  <xsl:template match="myFunGT:*">
    <xsl:param name="arg1" select="/.."/>
    <xsl:param name="arg2" select="/.."/>

    <xsl:variable name="vcnt1" select="count($arg1/ANCESTOR/NAME)"/>
    <xsl:variable name="vcnt2" select="count($arg2/ANCESTOR/NAME)"/>

     <xsl:variable name="vComnLength"
       select="$vcnt1 * ($vcnt2 >= $vcnt2)
              +
               $vcnt2 * ($vcnt1 > $vcnt2)"/>

     <xsl:call-template name="compareStringList">
       <xsl:with-param name="plistStr1"
         select="$arg1/ANCESTOR/NAME[position() &lt;= $vComnLength]"/>
       <xsl:with-param name="plistStr2"
         select="$arg2/ANCESTOR/NAME[position() &lt;= $vComnLength]"/>
       <xsl:with-param name="pLength" select="$vComnLength"/>
     </xsl:call-template>
  </xsl:template>

  <xsl:template name="compareStringList">
    <xsl:param name="plistStr1" select="/.."/>
    <xsl:param name="plistStr2" select="/.."/>
    <xsl:param name="pLength" select="0"/>

    <xsl:if test="$pLength">
      <xsl:variable name="vComp">
        <xsl:call-template name="node-strComp">
          <xsl:with-param name="n1" select="$plistStr1[1]"/>
          <xsl:with-param name="n2" select="$plistStr2[1]"/>
        </xsl:call-template>
      </xsl:variable>

      <xsl:choose>
        <xsl:when test="$vComp = 1">1</xsl:when>
        <xsl:when test="$vComp = 0">
          <xsl:call-template name="compareStringList">
            <xsl:with-param name="plistStr1"
                    select="$plistStr1[position() > 1]"/>
            <xsl:with-param name="plistStr2"
                    select="$plistStr2[position() > 1]"/>
            <xsl:with-param name="pLength" select="$pLength - 1"/>
          </xsl:call-template>
        </xsl:when>
      </xsl:choose>
    </xsl:if>
  </xsl:template>

<xsl:template name="node-strComp">
  <xsl:param name="n1"/>
  <xsl:param name="n2"/>

  <xsl:choose>
    <xsl:when test="string($n1)=string($n2)">0</xsl:when>
    <xsl:otherwise>
      <xsl:for-each select="$n1 | $n2">
        <xsl:sort select="."/>

        <xsl:if test="position()=1">
          <xsl:choose>
            <xsl:when test="string(.) = string($n1)">-1</xsl:when>
            <xsl:otherwise>1</xsl:otherwise>
          </xsl:choose>
        </xsl:if>
      </xsl:for-each>
    </xsl:otherwise>
  </xsl:choose>

</xsl:template>

</xsl:stylesheet>

It uses a generic "hSort" template from the following stylesheet module:

hSort.xsl
----------
<xsl:stylesheet version="1.0"
  xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
  xmlns:vendor="urn:schemas-microsoft-com:xslt"
  xmlns:fxslDefaultGT="f:fxslDefaultGT"
  exclude-result-prefixes="vendor fxslDefaultGT">

  <xsl:template name="hSort">
    <xsl:param name="pList" select="/.."/>
    <xsl:param name="pFunGT" select="document('')/*/fxslDefaultGT:*[1]"/>

    <xsl:variable name="vLength" select="count($pList)"/>

    <xsl:choose>
      <xsl:when test="$vLength > 1">
        <xsl:variable name="vrtfH1Sorted">
          <xsl:call-template name="hSort">
            <xsl:with-param name="pList" select="$pList[position() &lt;=
$vLength div 2]"/>
            <xsl:with-param name="pFunGT" select="$pFunGT"/>
          </xsl:call-template>
        </xsl:variable>

        <xsl:variable name="vrtfH2Sorted">
          <xsl:call-template name="hSort">
            <xsl:with-param name="pList" select="$pList[position() >
$vLength div 2]"/>
            <xsl:with-param name="pFunGT" select="$pFunGT"/>
          </xsl:call-template>
        </xsl:variable>

        <xsl:call-template name="merge">
          <xsl:with-param name="pList1"
select="vendor:node-set($vrtfH1Sorted)/*"/>
          <xsl:with-param name="pList2"
select="vendor:node-set($vrtfH2Sorted)/*"/>
          <xsl:with-param name="pFunGT" select="$pFunGT"/>
        </xsl:call-template>
      </xsl:when>
      <xsl:when test="$vLength = 1">
        <xsl:copy-of select="$pList[1]"/>
      </xsl:when>
    </xsl:choose>
  </xsl:template>

  <xsl:template name="merge">
    <xsl:param name="pList1" select="/.."/>
    <xsl:param name="pList2" select="/.."/>
    <xsl:param name="pFunGT" select="/.."/>

    <xsl:choose>
      <xsl:when test="not($pList1) or not($pList2)">
        <xsl:copy-of select="$pList1 | $pList2"/>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="vGT">
          <xsl:apply-templates select="$pFunGT">
            <xsl:with-param name="arg1" select="$pList1[1]"/>
            <xsl:with-param name="arg2" select="$pList2[1]"/>
          </xsl:apply-templates>
        </xsl:variable>
        <xsl:choose>
          <xsl:when test="not(string($vGT))">
            <xsl:copy-of select="$pList1[1]"/>

            <xsl:call-template name="merge">
              <xsl:with-param name="pList1" select="$pList1[position() >
1]"/>
              <xsl:with-param name="pList2" select="$pList2"/>
              <xsl:with-param name="pFunGT" select="$pFunGT"/>
            </xsl:call-template>
          </xsl:when>
          <xsl:otherwise>
            <xsl:copy-of select="$pList2[1]"/>
            <xsl:call-template name="merge">
              <xsl:with-param name="pList2" select="$pList2[position() >
1]"/>
              <xsl:with-param name="pList1" select="$pList1"/>
              <xsl:with-param name="pFunGT" select="$pFunGT"/>
            </xsl:call-template>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

    <fxslDefaultGT:fxslDefaultGT/>
    <xsl:template match="fxslDefaultGT:*">
      <xsl:param name="arg1" select="/.."/>
      <xsl:param name="arg2" select="/.."/>

        <xsl:if test="$arg1 > $arg2">1</xsl:if>
    </xsl:template>

</xsl:stylesheet>

When applied on your source.xml:

testhSort.xml
--------------
<CRUMBTRAILS>
  <CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>21</NODEID>
      <NAME>Families</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
  <CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>73</NODEID>
      <NAME>Hobbies</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>83</NODEID>
      <NAME>Travel &amp; Transport</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>52</NODEID>
      <NAME>Transport</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
  <CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>117</NODEID>
      <NAME>Toys, Games &amp; Hobbies</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>797</NODEID>
      <NAME>Toys</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
  <CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>117</NODEID>
      <NAME>Toys, Games &amp; Hobbies</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>798</NODEID>
      <NAME>Games</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
  <CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>117</NODEID>
      <NAME>Toys, Games &amp; Hobbies</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>800</NODEID>
      <NAME>Computer Games</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
</CRUMBTRAILS>


The result is as required:

<CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>73</NODEID>
      <NAME>Hobbies</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>83</NODEID>
      <NAME>Travel &amp; Transport</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>52</NODEID>
      <NAME>Transport</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
<CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>21</NODEID>
      <NAME>Families</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
<CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>117</NODEID>
      <NAME>Toys, Games &amp; Hobbies</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>800</NODEID>
      <NAME>Computer Games</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
<CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>117</NODEID>
      <NAME>Toys, Games &amp; Hobbies</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>798</NODEID>
      <NAME>Games</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>
<CRUMBTRAIL>
    <ANCESTOR>
      <NODEID>889</NODEID>
      <NAME>Top</NAME>
      <TREELEVEL>0</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>72</NODEID>
      <NAME>Life</NAME>
      <TREELEVEL>1</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>117</NODEID>
      <NAME>Toys, Games &amp; Hobbies</NAME>
      <TREELEVEL>2</TREELEVEL>
    </ANCESTOR>
    <ANCESTOR>
      <NODEID>797</NODEID>
      <NAME>Toys</NAME>
      <TREELEVEL>3</TREELEVEL>
    </ANCESTOR>
  </CRUMBTRAIL>


Hope this helped.


=====
Cheers,

Dimitre Novatchev.
http://fxsl.sourceforge.net/ -- the home of FXSL




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


Current Thread