package unionFind
Install
Dune Dependency
Authors
Maintainers
Sources
md5=7238ac49fba7c730e90cf1a577207347
sha512=c49dd3f9a6689f6a5efe39c26efe2c137f8812b4be6ee76c2cc20068cf86ad73c0ac97ec9a543245dddb63792ce8c1904576b3435bf419cc7837bc5e368eee6d
CHANGES.md.html
CHANGES
2022/01/22
Strengthen the specification of
merge
. It is now guaranteed that, if the user functionf
raises an exception, then the union-find data structure is unaffected.
2022/01/09
In
UnionFind
andUnionFind.Make
, introduce a new operationmerge
, a variant ofunion
that is parameterized with a join functionf
. The functionf
is not allowed to perform reentrant accesses to the union-find data structure.In
UnionFind
only, introduce an optimization that reduces the amount of memory allocation. This leads to a speed improvement of about 10% in the micro-benchmark.
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.