Module Core_kernel.Union_find
Imperative data structure for representing disjoint sets.
Union find is used to implement an equivalence relation on objects, where the equivalence relation can dynamically be coarsened by "union"ing two equivalence classes together.
All of the operations are effectively (amortized) constant time.
See Wikipedia.
This implementation is not thread-safe.
type 'a t
type 'a t
is the type of objects, where each object is part of an equivalence class that is associated with a single value of type'a
.
include Core_kernel__.Import.Invariant.S1 with type 'a t := 'a t
val invariant : 'a Base__.Invariant_intf.inv -> 'a t Base__.Invariant_intf.inv
val create : 'a -> 'a t
create v
returns a new object in its own equivalence class that has valuev
.
val get : 'a t -> 'a
get t
returns the value of the class oft
.
val set : 'a t -> 'a -> Core_kernel__.Import.unit
set t v
sets the value of the class oft
tov
.
val same_class : 'a t -> 'a t -> Core_kernel__.Import.bool
same_class t1 t2
returns true ifft1
andt2
are in the same equivalence class.
val union : 'a t -> 'a t -> Core_kernel__.Import.unit
union t1 t2
makes the class oft1
and the class oft2
be the same (if they are already equal, then nothing changes). The value of the combined class is the value oft1
ort2
; it is unspecified which. Afterunion t1 t2
, it will always be the case thatsame_class t1 t2
.
module Private : sig ... end