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