package unionFind

You can search for identifiers within the package.

in-package search v0.2.0

unionFind
- UnionFind
  - Make
    
    S
  - STORE
  - StoreMap
    
    Make
    
    IntMap
  - StoreRef
  - StoreTransactionalRef
  - StoreVector

Legend:
Library
Module
Module type
Parameter
Class
Class type

A type of elements, also known as references.

type 'a elem

Operations for creating a new reference, reading and writing a reference, and testing whether two references are equivalent. (Two references are considered equivalent after they have been merged by union.)

val make : 'a -> 'a elem

val get : 'a elem -> 'a

val set : 'a elem -> 'a -> unit

val eq : 'a elem -> 'a elem -> bool

union x y does nothing if the references x and y are equal, and merges them if they are distinct. In the latter case, the content of the merged reference is arbitrarily chosen to be the previous content of x or y.

val union : 'a elem -> 'a elem -> 'a elem

find x returns the representative element of x's equivalence class.

val find : 'a elem -> 'a elem

Instead of hard-coding the use of mutable state, we parameterize the module over an implementation S of stores, as described by the signature STORE. This allows the client to choose between many different representations of the store: e.g., based on primitive references, based on a (possibly extensible) primitive array, based on a persistent map, based on a persistent or semi-persistent array, based on transactional references, etc.

The signature provided by this module is also STORE, extended with an operation for merging two references.

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

module type STORE = sig ... end

module StoreMap : sig ... end

This module offers an implementation of STORE based on immutable integer maps. The stores thus obtained are persistent.

module StoreRef : sig ... end

This module offers an implementation of STORE based on mutable references.

module StoreTransactionalRef : sig ... end

This module offers an implementation of STORE based on a simple form of mutable transactional references.

module StoreVector : sig ... end

This module offers an implementation of STORE based on a single mutable extensible array.