John, Thank you very much for the links. I started toying and modifying with your files. I already succeeded in inserting nodes with an optional ordering function parameters. That's exactly what I needed. I will run also some performance analysis of your red black tree.
Tell me if there is any interest in publishing the result, casewhere I could reach something stable of course. Cheers, JohnLeM 2013/11/20 John Snelson <[email protected]> > The following libraries are written in pure XQuery 3.0: > > rbtree.xq - https://github.com/jpcs/rbtree.xq > > Functional implementation of a red/black tree (ordered set) that allows a > custom implementation of the comparison function. See the included "map.xq" > for how this can be used to implement a map data structure using "lt" > comparison. Should be easy to implement an alternative map that allows node > keys with a suitable comparison function. > > hamt.xq - https://github.com/jpcs/hamt.xq > > Functional implementation of a hash array mapped trie (hash set) that > allows a custom hash function and equality function. See the included > "hashmap.xq" for how this can be used to implement a map data structure. > > Hope that helps, > > John > > > On 20/11/13 09:43, jean-marc Mercier wrote: > >> Hello, >> >> I am looking for a map module in XQUERY that would have the following >> behavior. Does somebody ever heard of such a module ? >> >> 1) The default behavior for inserting keys should be using the >> fn:distinct-values(). Note that map module using this mechanism already >> exists, see for instance BaseX map:module : >> http://docs.basex.org/wiki/Map_Module >> >> 2) Accept functions as values. Why this could be useful ? Well, it is >> really useful for a lot of things. The first very useful things would be >> to use this functionality to bind external parameters to functions. >> For instance I could write, (useful for the point 3) below) >> >> declare function >> local:is_data1_smaller_than_data2($data1,$data2,$map_bindings){ >> map:get($map_bindings,"less")($data1,$data2) >> }; >> >> 3) Accept an optional, external ordering predicate. This is actually >> what is done with every structured languages. For instance, set in C++ >> (that are indeed maps) are defined as >> >> template < class T, // set::key_type/value_type >> */_class Compare = less<T>_/*, // >> set::key_compare/value_compare >> >> class Alloc = allocator<T> > // set::allocator_type >> > class set; >> >> where the ordering predicate is optional (*/_class Compare = less<T>). >> _/*Why having an optional ordering predicate could be useful in ? >> >> Because of point 4) below : to use node() as keys in map. >> >> 4) Accept node() as keys. This is very useful to a lot of things. >> However, it does not exists a canonical ordering for nodes. The function >> deep-equal() could be a candidate, but it does not define an ordering, >> and performances in insertion using this function would be tremendous. >> Thus, to accept node() as keys for maps, one need first to provide an >> external ordering predicate for nodes, see point 3) above. >> > > -- > John Snelson, Lead Engineer http://twitter.com/jpcs > MarkLogic Corporation http://www.marklogic.com > _______________________________________________ > [email protected] > http://x-query.com/mailman/listinfo/talk >
_______________________________________________ [email protected] http://x-query.com/mailman/listinfo/talk
