RE: Group on deep equal criterion

Tough one. If you're not worried about O(n^2) performance, you can start by
building a data structure that captures the memberships of the groups by
doing

<xsl:for-each select="$in">
  <xsl:variable name="x" select="."/>
  <item id="generate-id()">
    <xsl:for-each select="$in[deep-equal(., current())]">
      <duplicate id="{generate-id()}"/>
    </xsl:for-each>
  </item>
</xsl:for-each>

You can then use conventional grouping to identify the distinct groups (not
trivial, but I assume you can solve that one), and use

<xsl:key name="gid" match="*" use="generate-id()"/>

to get back from the generated ids to the original nodes.

If you are worried about O(n^2) performance, but don't want to resort to
extensions, then you can try and define a hash function that will give the
same result for two nodes if they are deep-equal. You can then modify the
above to start by doing value-based grouping on the hash key, and then apply
the O(n^2) logic only within each of these groups. A simple but quite
effective hash key might be something like concat(count(.//*), string(.)).

(Of course this still has O(n^2) performance in the worst case where all the
input nodes are deep-equal to each other, but one assumes that case is
unlikely).

Michael Kay
http://www.saxonica.com/
     

> -----Original Message-----
> From: Vladimir Nesterovsky [mailto:vladimir@xxxxxxxxxxxxxxxxxxxx] 
> Sent: 22 October 2008 07:50
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject:  Group on deep equal criterion
> 
> Hello!
> 
> What is the best way to group elements by deep-equal() criterion?
> 
> Thanks.
> --
> Vladimir Nesterovsky
> http://www.nesterovsky-bros.com