Hi all,
I just added set datastructures for guile-log. I realized that I could implement those for guile as well.
The algorithm is plain in that it adds an extra fields 'size and hashvalue to the vhash struct so
at unification
Use the largest set as a base and add the extra elements from the other one ontop of this.
hash -> hash(x) xor h
n -> n + 1
at intersection
Use the smallest hash as a base and delete the arguments that is not in both by simply add a delete
value to the vhash.
hash -> hash(x) xor h
n -> n - 1
and likewise for set difference.
the logic for equivalent is
(cond
((not (= nx ny)) #f)
((nat (= hashx hashy) #f)
(else
direct check)
The trick is to detect when size(vhash) > 2*n after each operation in in such cases just create a new vhash where deleted elements are removed.
+ subset and superset operators as well as.
This interface depends on a functional hash, we know that vhashes in guile is not thread safe so we might want other such datastructures in the future, I will make the setup as a module
set-generic, with a macro that if applied generate the interface assuming hash-cons hash-assoc vlist-null and will define the operators regarding those, I will then add a vhash-sets and clos-sets as interfaces that use that, I would suggest the namespace
(ice-9 set *) for the datastructure.
WDYT, do we need this in guile?
Regards
Stefan