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
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
