Strengthen the specification of
merge. It is now guaranteed that,
if the user function
fraises an exception, then the union-find
data structure is unaffected.
UnionFind.Make, introduce a new operation
a variant of
unionthat is parameterized with a join function
fis not allowed to perform reentrant accesses to the
union-find data structure.
UnionFindonly, introduce an optimization that reduces the amount
of memory allocation. This leads to a speed improvement of about 10%
in the micro-benchmark.
Incompatible changes in the signature
STORE, which appears in the type of
Instead of having every operation return a possibly-updated store, we
assume that stores are updated in place. A new
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 makes
UnionFind.Makemuch more pleasant to use in practice.
unionis no longer parameterized with a join function
This API was flawed and could lead to meaningless behavior if the function
fprovided by the user performed reentrant calls to the union-find
unionnow returns a reference of type
of a unit value. This makes
which it was not.
findamong the operations offered by
is_representativeto the operations offered by
Add a micro-benchmark, which is executed by
Add a fast path (an optimization) in the
eqfunctions, both in
the basic union-find (
UnionFind) and the one that is parameterized over a
Initial release of the package.