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

type 'a 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.

val copy : 'a store -> 'a 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.

type 'a rref

A reference of type 'a rref can be thought of as (a pointer to) an object that exists in some store.

val make : 'a store -> 'a -> 'a rref

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.

val get : 'a store -> 'a rref -> 'a

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.

val set : 'a store -> 'a rref -> 'a -> unit

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.

val eq : 'a store -> 'a rref -> 'a rref -> bool

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.

module Make (IntMap : sig ... end) : sig ... end

Make constructs persistent stores based on immutable integer maps.