UnionFind.Make
This functor offers a union-find data structure based on disjoint set forests, with path compression and linking by rank. It does not use primitive mutable state. Instead, it is parameterized over an implementation of stores. This allows the user to choose between many different representations of stores, such as stores based on primitive references, stores based on a (possibly extensible) primitive array, stores based on persistent maps, stores based on persistent or semi-persistent arrays, stores based on transactional references, and so on. The result of this functor is also an implementation of stores, extended with a union
operation that merges two references.
module S : sig ... end
The abstract type 'a content
describes the meta-data that is required by the union-find machinery. Thus, a reference of type 'a rref
in the new store can also be viewed as a reference of type 'a content S.rref
in the original store. Similarly, a new store of type 'a store
is also an original store of type 'a content S.store
. By revealing this information, we advertise the fact that the new store is implemented on top of the original store S
provided by the user. This means that some of the operations supported by the store S
(such as copying, or (say) creating a transaction, assuming that the store S
supports a form of transaction) are applicable to the new store as well.
A store can be thought of as a region of memory in which objects, known as references, can be dynamically allocated, read, and written. Stores are homogeneous: all references in a store of type 'a store
have the content type, namely 'a
. In general, a store should be thought of as a mutable object. Some stores support a cheap copy
operation, because the underlying data structure allows it: for instance, a store implemented as a reference to a persistent map supports cheap copies. Some stores do not support copy
at all: for instance, a store implemented using primitive references does not support copies.
val new_store : unit -> 'a store
new_store()
creates an empty store.
copy s
returns a copy of the store s
. Every reference that is valid in the store s
is also valid in the new store, and has the same content in both stores. The two stores are independent of one another: updating one of them does not affect the other. When supported, copy
is cheap: it can be expected to run in constant time. However, some stores does not support copy
; in that case, an unspecified exception is raised.
A reference of type 'a rref
can be thought of as (a pointer to) an object that exists in some store.
make s v
creates a fresh reference in the store s
and sets its content to v
. It updates the store in place and returns the newly-created reference.
get s x
reads the current content of the reference x
in the store s
. It may update the store in place, and returns the current content of the reference.
set s x v
updates the store s
so as to set the content of the reference x
to v
. It updates the store in place.
If eq s x y
is true, then union s x y
has no observable effect. Otherwise, union s x y
merges the references x
and y
. In either case, after the call eq s x y
is true.
union s x y
returns a reference z
such that eq s x z
and eq s y z
and is_representative s z
are true.
The content of the reference that is returned is unchanged. The content of the reference that is not returned is lost.
If eq s x y
is true initially, then merge f s x y
has no observable effect. Otherwise, merge s f x y
merges the references x
and y
and sets the content of the reference to f vx vy
, where vx
and vy
are the initial contents of the references x
and y
. The function f
is not allowed to access the union-find data structure. Under this restriction, merge s f x y
is equivalent to:
if eq s x y then
find s x
else
let vx, vy = get s x, get s y in
let v = f vx vy in
let z = union s x y in
set s z v;
z
find s x
returns a representative element of x
's equivalence class. This element is chosen in an unspecified but deterministic manner, so two calls to find s x
must return the same result, provided no calls to union
take place in between. eq s x y
is equivalent to find s x == find s y
.