On This Page
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
package unionFind
This functor offers a union-find data structure based on disjoint set forests, with path compression and linking by rank. It does not use primitive mutable state. Instead, it is parameterized over an implementation of stores. This allows the user to choose between many different representations of stores, such as stores based on primitive references, stores based on a (possibly extensible) primitive array, stores based on persistent maps, stores based on persistent or semi-persistent arrays, stores based on transactional references, and so on. The result of this functor is also an implementation of stores, extended with a union operation that merges two references.
Parameters
module S : sig ... endSignature
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, say, opening and committing a transaction, assuming that the store S supports a form of transaction) may be 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 may be persistent or mutable, depending on which data structure is used to implement it.
val new_store : unit -> 'a storenew_store() creates an empty store.
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 returns a pair of an updated store and the newly-created reference.
get s x reads the current content of the reference x in the store s. It returns a pair of a possibly-updated store and 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 returns an updated store.
eq s x y determines whether the references x and y are the same reference. It returns a pair of a possibly-updated store and a Boolean result. The references x and y must belong to the store s.
If eq s x y is true, then union f s x y has no observable effect. Otherwise, union f s x y merges the references x and y, using the function f to combine the original contents of the references x and y. In either case, a possibly-updated store s' is returned, such that eq s' x y is true.
On This Page