Hi

I have an information, that could be interesting for others and a question about BaseX map:module.

1) I implemented in pure XQUERY 3.0 a map having the desired behavior. I can now define optionally an ordering function, and thus is able to insert nodes, maps, sequences. It is very useful for a lot of things. I would not recommend to external person to use it at present time (not tested, functionalities to add, bugs suspected), but I can provide the file on demand.
Notice also that the heavy work is an implementation of Red Black Tree (at my knowledge, the standard technology for maps in imperative language), kindly provided here https://github.com/jpcs/rbtree.xq. 

2) A question about the BaseX map module : what kind of tree technology is used behind ? (the standard Java RBtree ?). If you don't know, could you be kind enough to provide me a link to the implementation at BaseX repository ? Thanks in advance.

Cheers








2013/11/18 jean-marc Mercier <jeanmarc.mercier@gmail.com>
>You’ve got me stumped here. The talk@xquery.com mailing list may be
> the best place to get more details on this.
I will try to post to this mailing list, thanks for the link. Indeed I started to implement through xquery a map version able to handle nodes for my needs. It is not obvious, because a map requires to define an equality properties over set. For nodes, deep-equal is a natural candidate, but it does not define an ordering, and performances are lost. For database nodes, it is possible to achieve this with internal (or maybe pre-database) ids, but I can't use it for dynamically created nodes. I guess that the best choice is to provide an optional binding to an external ordering function, something like map:new($maps as map(*)*, binding as map(*)) as map(*), where the binding provides an option to the ordering function (e.g. $order(key1,key2) := binding["order"](key1,key2)). This is actually what is done for C++ or Java sets : 

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;

>> - A remark of minor importance : if distinct-values() is used to select
>> keys, the map:module shouldn't accept sequences as keys ? If I try a
>> map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.

> I guess you answered your own question? ;)
:) not really. My sentence was not correct, I meant "shouldn't the map:module accept sequences as keys ?" : since the baseX map:module is distinct-value based, it should work with sequences as keys.



2013/11/18 Christian Grün <christian.gruen@gmail.com>
> - might this mechanism not be a little bit misleading ? Indeed, I was
> expecting somehow that map:key(map:new({<node>:""})) to be an identity for
> <node>.

You’ve got me stumped here. The talk@xquery.com mailing list may be
the best place to get more details on this.

> - A remark of minor importance : if distinct-values() is used to select
> keys, the map:module shouldn't accept sequences as keys ? If I try a
> map:new({("dummy","dummy"):""}), I am actually raising a XPTY0004 error.

I guess you answered your own question? ;)

All the best,
Christian

[1] http://x-query.com/mailman/listinfo/talk