set operations ontop of vhashes

set operations ontop of vhashes

[Stefan Israelsson Tampe]

[-- Attachment #1: Type: text/plain, Size: 1403 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 1880 bytes --]