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(_at_)saxonica(_dot_)com>
Sent: Wednesday, October 22, 2008 11:10 AM
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: RE: [xsl] 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(_at_)nesterovsky-bros(_dot_)com]
Sent: 22 October 2008 07:50
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: [xsl] Group on deep equal criterion
Hello!
What is the best way to group elements by deep-equal() criterion?
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--