Sets in oz

[Filip Konvička]

Christophe Taton (27.4.2007 10:20):
> I did not find any general set data structure included in the standard
> Oz modules (like the one we find in java of c/c++)?
> Is there any? and if not, are there valuable reasons for this?
>
> Of course I can implement a set over a standard linked list, but when
> efficiency is an issue, this solution does not help anymore.
> The main issue appears to me to be the way to get a hash code for any
> value. Did someone already try to provide such features?
>   
Hi,

I think that two of my packages that I've put into MOGUL could be used 
for this purpose:

http://www.mozart-oz.org/mogul/info/fkonvick/rbtree.html
http://www.mozart-oz.org/mogul/info/fkonvick/ldictionary.html

They are ordered (RBTree) and unordered (LDictionary) associative 
containers. LDictionary has an interface similar to that of the standard 
Dictionary, but does not restrict the keys to atoms. The contract for 
the keys is that they must be comparable
 - using equality operator "==" in case of LDictionary
 - using the standard "<" operator in case of RBTree, or by some 
user-supplied comparator.

LDictionary has the disadvantage that most operations (even "get") are 
write operations, because the implementation always puts the accessed 
element to the front of the underlying list. This is a drawback for 
using this structure with nested spaces. (However, can be worked around 
using server ports in the parent space.)

Given the above, you can use almost any determined oz structure as keys, 
and, in case of RBTree's custom comparators, you can use arbitrary 
values as keys. (However, all comparators should be consistent as the 
keys get more determined - no constraint magic here....)

If you're worried about performance, this probably rules out LDictionary 
- but RBTree might be useful.

Hope this helps,
Filip