package unionFind

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.

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.

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.

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
  set s (union s x y) (f vx vy)

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.

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