package grenier
Install
Dune Dependency
Authors
Maintainers
Sources
sha256=271ae9461d012c99449e5233386b13ab99ae2e474ed570e05bf0c9947e5eff1e
sha512=73c89aa6281f612c499eb734c6fc4d33b961ed82d6cc7380b03acb196233c27107e103b11f55e50f543f0f1dedb4924e6691a5c3c353ef4d8177bc661fc2bfd4
doc/grenier.dset/Dset/index.html
Module Dset
A set of abstract elements annotated with values of type 'a
that can be efficiently diffed.
val empty : 'a t
The empty set
val element : 'a -> 'a t
element x
creates a new set element tagged with metadata x
(O(1)). It is the physical identity of the element that is considered when computing set difference, not the tag. Therefore diff (element x) (element x) = { added = [x]; removed = [x]; }
But (let e = element x in diff e e) = { added = []; removed = []; }
Compute the difference between two sets.
diff old_set new_set = { added; removed }
where removed
lists the tag of elements only present in old_set
and added
lists the tag of elements only present in new_set
_Conjecture_: the algorithm is linear in the number of changes between old_set
and new_set
.
When used in a linear fashion (you have a sequence of sets s_i
and only compare s_i
and s_i+1
, at most once for each i
), it should not affect the complexity of the program.
val unmark : 'a marking -> unit