Re: [xsl] How to QuickSort a map?

Subject: Re: [xsl] How to QuickSort a map?
From: "Sean B. Durkin" <sean@xxxxxxxxxxxxxxxxx>
Date: Fri, 30 Aug 2013 01:53:55 +1000
Hi Roger,

You can perform a quick sort in XPath 3 of strings with this expression ...

function( $s as xs:string, $sort-2 as function(xs:string, function()) as xs:string*
{ if (count($s) lt 2 then $s
else $sort-2( $s[. lt $s[1]]) , $s[1] , $sort-2( $s[( . ge $s[1]) and (position() ne 1))}


The same technique can be applied to any other atomic data type. To use a different collation, supply a comparison function as an additional argument.

For example this xpath expression ....

let $quick-sort := function( $s as xs:string, $sort-2 as function(xs:string, function()) as xs:string*
{ if (count($s) lt 2 then $s
else $sort-2( $s[. lt $s[1]]) , $s[1] , $sort-2( $s[( . ge $s[1]) and (position() ne 1))}
return $quick-sort( ('def', 'abc', 'ghi'), $quick=sort())


should return ('abc','def','ghi') . This is untested

You can't sort a map, as your question suggestion. That doesn't make any sense, because a map is just a single item. You can't sort the map's internal store of item, because maps are by definition an unsorted list of associations between a key and a value. But you can sort the print-out of a map's keys.

For example: This function prints out the contents of a map in alphabetical order of the keys. Is that better than non-deterministic order? It probably is if the output is intended for human readership.

<xsl:function name="f:print-map" as="xs:string*">
  <xsl:param name="m" as="map(xs:anyAtomicType, item()*)" />

  <xsl:value-of select="
    let $quick-sort := function( $s as xs:string, $sort-2 as function(xs:string, function()) as xs:string*
    { if (count($s) lt 2 then $s
      else $sort-2( $s[. lt $s[1]]) , $s[1] , $sort-2( $s[( . ge $s[1]) and (position() ne 1))}
      return $quick-sort( map:keys($m), $quick=sort()) ! (., '-', map:get($m, .))"/>
</xsl:function>

I don't have any facility to test this, except the XPath processor of my imagination. So there is probably some errors. Even so, the technique is will still be valid.

In XPath 2, you could also sort, but it was painful. I am not sure that XPath sort will ever be popular. I suspect that most developers will prefer the direct simplicity of XSLT sort. I don't know. It remains to be seen.

Faithfully,
Sean B. Durkin

For example to sort
On 29/08/2013 7:51 PM, Costello, Roger L. wrote:
Sean Durkin wrote:

XPath 3 can now implement QuickSort in 3 lines of code.
Sean (or anyone) would you show how to implement the QuickSort please?

That is, would you replace the ??? in the below function with the code please?

---------------------------------------------------------------------
<xsl:function name="f:sort-map" as="map(xs:anyAtomicType, item()*)">
<xsl:param name="m" as="map(xs:anyAtomicType, item()*)" />
???
</xsl:function>
---------------------------------------------------------------------


/Roger

Current Thread