On This Page
package flatunionfind
On This Page
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
Applying the functor MakeWithData creates a fresh instance of the union-find data structure. In comparison with Make, this data structure offers one additional feature: it maintains a map of equivalence classes to user data. This functor is generative: each application returns a new module, with its own mutable internal state and its own abstract type point.
Parameters
module D : sig ... endSignature
type data = D.tThis signature extends UF with new functionality: with every equivalence class, a datum of type data is associated. To create a new point, the function fresh cannot be used; instead, make must be used.
include UF
point is the type of a point in the union-find data structure. It is an abstract type. The keyword private indicates that a point x can be converted to an integer index, by writing x :> int. This integer index lies in the semi-open interval from 0 to population(). The conversion in the reverse direction is not permitted.
type t = pointval population : unit -> populationpopulation() is the total number of points created so far.
val iter : (point -> unit) -> unititer f applies the user-supplied function f to every point that was ever created (whose creation was not undone via drop).
val drop : point -> unitdrop x undoes the creation of the point x. This is permitted only if no new point was created since x was created (or if those new points were themselves dropped) and no union operation took place since x was created. This operation is unsafe: the user must promise to not use the point x afterwards.
val validate : point -> unitIf runtime assertions are enabled, then validate x checks that the point x is a valid point, and fails otherwise. drop is the only operation that can cause a point to become invalid.
find x finds the current representative element of the equivalence class of the point x.
val is_representative : point -> boolis_representative x determines whether x is currently the representative element of its equivalence class.
equal x y determines whether x and y are equal, that is, whether they are the same point. It is equivalent to (x :> int) = (y :> int).
compare is a total order on points. compare x y is equivalent to Int.compare (x :> int) (y :> int).
val hash : point -> inthash is a hash function on points. hash x equivalent to Int.hash (x :> int).
val show : point -> stringshow x produces a human-readable representation of the point x.
equiv x y determines whether x and y are equivalent, that is, whether they are members of the same equivalence class. (If they are now, then they will be forever.)
If equiv x y is true, then union x y has no observable effect. Otherwise, union x y merges the equivalence classes of the points x and y. In either case, after the call, equiv x y is true.
union x y returns a point z such that equiv x z and equiv y z and is_representative z are true.
module Vector : Hector.MONOVECTOR with type element = pointThe submodule Vector offers vectors that contain points.
module HashSet (_ : sig ... end) : Hachis.HashSet.SET with type element = pointThe submodule HashSet offers hash sets that contain points. It is a functor: an equivalence relation on points must be chosen by the user.
make v creates a new point, which forms a new singleton equivalence class, and associates the value v with this class.
get x returns the value that is currently associated with the equivalence class of the point x.
set x v associates the value v with the equivalence class of the point x.
If eq x y is true initially, then merge f x y has no observable effect. Otherwise, merge f x y merges the equivalence classes of the points x and y and associates the value f vx vy with the new class, where vx and vy are the values initially associated with the classes of x and y. The function f is not allowed to access the union-find data structure.
On This Page