Re: [xslt] key() in match pattern of xsl:key

["Joel E. Denny" <jdenny ces clemson edu>]

On Mon, 12 Dec 2005, Vincent Lefevre wrote:

> I haven't looked at your specific problem, but I think that *some*
> O(n^2) -> O(n) optimizations can be done with two passes, by storing
> a temporary RTF, that could be used as a nodeset in the second pass.
> With XSLT 1.0, this solution really needs two passes, by calling the
> XSLT processor twice, but with EXSLT, you can use the function that
> converts a RTF into a nodeset.

Thanks for this suggestion.  XSLT 1.0 allows variables to reference 
variables (so why do the errata prohibit this for keys?) as long as there 
are no cycles. I can imagine constructing RTFs for the sets A and B but 
sorted by value.  That's O(n*log(n)) for each. I can then construct 
another RTF for the set AnotB in O(n) time.

The total O(n*log(n)) is better than O(n^2), but lookup time for the final 
RTF would be O(n) rather than the O(1) for real keys.  Of course, the n 
here is much smaller than the n of the original document. Nevertheless, it 
would be nice to be able to construct a key off of the final RTF, but keys 
referencing variables is prohibited in XSLT 1.0 (even before the errata), 
and I've already seen posts from Daniel supporting that rule.

Joel