#### unionFind

Library

Module

Module type

Parameter

Class

Class type

## Parameters

`module S : sig ... end`

## Signature

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

`merge s f x y`

is equivalent to:

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

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

.