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