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

In my case - extraction of common subexpessions from an expression 
tree - any approach works, as I'm dealing with small sequences. However, 
out of curiosity for bigger sequences, I was thinking of a quicksort-like 
xslt
algorithm, and x:compare(element(), element()) function returning -1, 0, or 
1.

In practice this probably won't work well due to expenses of xslt engine 
comparing with built in algorithms.
--
Vladimir Nesterovsky
http://www.nesterovsky-bros.com

-------- Original Message --------
> From: "Michael Kay" <mike@xxxxxxxxxxxx>
> Sent: Wednesday, October 22, 2008 11:10 AM
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: 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?