#### unionFind

Library

Module

Module type

Parameter

Class

Class type

`'a elem`

is the type of elements, or references. Like the type `'a ref`

of ordinary references, this type supports the operations of creating a new reference, reading a reference, writing a reference, and testing whether two references are the same. Unlike ordinary references, this type also supports a form of merging: `union`

merges two references, making them "the same reference".

`val make : 'a -> 'a elem`

`make v`

creates a fresh reference and sets its content to `v`

.

`val get : 'a elem -> 'a`

`get x`

returns the current content of the reference `x`

.

`val set : 'a elem -> 'a -> unit`

`set x v`

sets the content of the reference `x`

to `v`

.

`eq x y`

determines whether the references `x`

and `y`

are "the same reference". At any point in time, `eq`

is an equivalence relation on references: it is reflexive, symmetric, and transitive. When two references `x`

and `y`

are merged by invoking `union x y`

, they become the same reference: `eq x y`

becomes true, and remains forever true.

If `eq x y`

is true initially, then `union x y`

has no observable effect. Otherwise, `union x y`

merges the references `x`

and `y`

. In either case, after the call, `eq x y`

is true. `union x y`

returns either `x`

or `y`

. The content of the reference that is returned is unchanged. The content of the reference that is not returned is lost.

If `eq x y`

is true initially, then `merge f x y`

has no observable effect. Otherwise, `merge 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.

`merge f x y`

is equivalent to:

```
if not (eq x y) then
let vx, vy = get x, get y in
let v = f vx vy in
set (union x y) v
```

`find 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 x`

must return the same result, provided no calls to `union`

take place in between. `eq x y`

is equivalent to `find x == find y`

.

`val is_representative : 'a elem -> bool`

`is_representative x`

determines whether `x`

is the representative element of its equivalence class. It is equivalent to `find x == x`

.

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 StoreMap : sig ... end`

This module offers **stores based on immutable integer maps**. These stores support a constant-time `copy`

operation. The module `UnionFind.StoreMap`

itself is an implementation of stores based on OCaml's `Map`

module. The functor `UnionFind.StoreMap.Make`

can also be used to construct an implementation of stores based on a user-provided implementation of immutable maps.

`module StoreRef : sig ... end`

This module offers **mutable stores based on primitive mutable references**. These stores do not support `copy`

.

`module StoreTransactionalRef : sig ... end`

This module offers **mutable stores based on mutable transactional references**. These stores support a simple form of transactions that can be either aborted or committed. Transactions cannot be nested. These stores do not support `copy`

.

`module StoreVector : sig ... end`

This module offers **mutable stores based on mutable extensible arrays**. These stores support copying, but `copy`

is not cheap; its cost is linear in the size of the store.