package unionFind
Install
Dune Dependency
Authors
Maintainers
Sources
md5=b92f29d7b920cf99651e0681aef1faf7
sha512=c4830c54269752706d90f29afe174a14c235b860c720ef3a873ca7672738e7f342d1dad381f7b1021a8d5f8a86f33774756dcf1fc23e0b4cfcbcb468e718a860
CHANGES.md.html
CHANGES
2022/01/07
Incompatible changes in the signature
STORE
, which appears in the type of the functorUnionFind.Make
.Instead of having every operation return a possibly-updated store, we assume that stores are updated in place. A new
copy
operation is introduced, so a persistent store is now simulated by a mutable store that can be copied in constant time. The main motivation for this change is that it makesUnionFind.Make
much more pleasant to use in practice.The operation
union
is no longer parameterized with a join functionf
. This API was flawed and could lead to meaningless behavior if the functionf
provided by the user performed reentrant calls to the union-find algorithm.The operation
union
now returns a reference of type'a rref
instead of a unit value. This makesUnionFind.Make
analogous toUnionFind
, which it was not.
Expose
find
among the operations offered byUnionFind.Make
.Add
is_representative
to the operations offered byUnionFind
and byUnionFind.Make
.Add a micro-benchmark, which is executed by
make test
.
2022/01/01
Improved documentation.
2020/03/20
Add a fast path (an optimization) in the
find
andeq
functions, both in the basic union-find (UnionFind
) and the one that is parameterized over a store (UnionFind.Make
).
2019/08/27
Initial release of the package.