Module 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.

Parameters

module S : sig ... end

Signature

type 'a content

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.

type 'a store = 'a content S.store

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.

val copy : 'a store -> 'a 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.

type 'a rref = 'a content S.rref

A reference of type 'a rref can be thought of as (a pointer to) an object that exists in some store.

val make : 'a store -> 'a -> 'a rref

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.

val get : 'a store -> 'a rref -> 'a

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.

val set : 'a store -> 'a rref -> 'a -> unit

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.

val eq : 'a store -> 'a rref -> 'a rref -> bool

eq s x y determines whether the references x and y are the same reference. It may update the store in place, and returns a Boolean result. The references x and y must belong to the store s.

val union : 'a store -> 'a rref -> 'a rref -> 'a rref

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.

val merge : 'a store -> ( 'a -> 'a -> 'a ) -> 'a rref -> 'a rref -> 'a rref

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
val find : 'a store -> 'a rref -> 'a rref

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.

val is_representative : 'a store -> 'a rref -> bool

is_representative s x determines whether x is the representative element of its equivalence class. It is equivalent to find s x == x.