Hi all, To report over this topic, I've written in XQUERY a Map that have the desired properties, rewriting John Snelson rbtree.xq - It can handle nodes or functions as keys, if of course the user provides its external ordering function, this point being left under the user responsibility. - It can remove nodes.
However, it suffers from performance issues : creating a map is quadratic (n^2) in map length (n), to be compared to n log_2(n) complexity for a normal red / black tree insertion. It seems that this is due to the fact that XQUERY lacks of a container for doubly chained lists. At my knowledge, the only container available for set of items are sequences. And creating a sequence in XQUERY have a quadratic complexity in sequence length with all the interpreters I've tried... Thus, as long as such containers will not be available, I can't see any way to write an efficient implementation of such a map in pure XQUERY. Indeed, I can't see any way to write any algorithm that would use extensively a stack or a vector in pure XQUERY. Do not hesitate to comment if I missed something. Cheers, Jean-Marc 2013/11/27 jean-marc Mercier <[email protected]> > Hi Michael, > > Thx for answering. > > >[1] As an example of the complexity, how do you compare two maps if they > have "different" ordering functions, and how can you > tell whether the > ordering functions are "different" anyway? > > A suggestion would be to use the W3C recommendation : when there are > duplicates, the last one wins. Maps can only have one ordering function. To > follow the recomendation, the ordering function must be the one given by > the first inserted map into the Ctor map:new(maps*). > > >I think we've done well to resist feature creep on this one > > 1) I don't know concerning XQUERY. I just notice that this is the standard > mechanism for other languages (see for instance map definitions for C++ and > JAVA). > 2) To be frank and honest, I think that the actual W3C recommendation on > maps is actually dangerous. For instance, it accepts maps of nodes, since > the segregation mechanism among key is given by fn:distinct-values. Telling > from my personal experience, I used a map module implementing the actual > map W3C recommendation to insert nodes as keys. It took me a while to > realize that, then a another amount of time to understand why, inserting my > document-nodes into that map ruins the performance of my app. And now, it > is taking me also a while to implement a proper map mechanism written in > XQUERY. Hope this will help others. > > > > > 2013/11/27 Michael Kay <[email protected]> > >> >> On 27 Nov 2013, at 06:43, jean-marc Mercier <[email protected]> >> wrote: >> >> Hi Michael. thx for pointing me out this link. . It points out also that >> "Each >> entry comprises a key which is an arbitrary atomic value", and that >> ordering is implicited by fn:distinct-values. Hence functions or nodes >> can not be accepted as keys, neither can we supply external ordering >> functions. Maps of maps, maps of nodes are not possible with this >> specification. >> >> Is it possible to propose / suggest changes to this specification ? >> >> >> It's certainly possible to suggest changes. However, these matters have >> been discussed quite extensively so the WGs will tend to defend the >> consensus they have already reached. >> >> The reason for not having functions as keys is that defining an equality >> operation on functions is notoriously difficult. >> >> The reason for not having nodes as keys is a bit more subtle. There are a >> variety of possible equality operations on nodes, exemplified by "is", >> "eq", and "deep-equal". It's not clear that any one of these would meet all >> use cases. >> >> Parameterizing a map to allow user-defined equality or ordering functions >> as a property of the map is certainly possible, but it all adds complexity >> [1]. Just because something is possible doesn't mean it is desirable. >> There's a natural tendency in standards groups to add a feature if one >> person thinks it is a good idea, despite the fact that everyone wants to >> keep things as simple as possible. I think we've done well to resist >> feature creep on this one. >> >> Michael Kay >> Saxonica >> >> [1] As an example of the complexity, how do you compare two maps if they >> have "different" ordering functions, and how can you tell whether the >> ordering functions are "different" anyway? >> > >
_______________________________________________ [email protected] http://x-query.com/mailman/listinfo/talk
