Module UnionFind.Make

Parameters

module X : Element
module XSet : IStdlib.IStd.Caml.Set.S with type elt = X.t
module XMap : IStdlib.IStd.Caml.Map.S with type key = X.t

Signature

type t
include Ppx_compare_lib.Comparable.S with type t := t
val compare : t Base__Ppx_compare_lib.compare
include Ppx_compare_lib.Equal.S with type t := t
val equal : t Base__Ppx_compare_lib.equal
val pp : (F.formatter -> X.t -> unit) -> F.formatter -> t -> unit
type repr = private X.t
val empty : t
val is_empty : t -> bool
val union : t -> X.t -> X.t -> t * (X.t * repr) option

return the optional new equality added between the old representatives of the two items in the form of "old representative = new representative", None if they were already in the same congruence class

val find : t -> X.t -> repr

return the element given if it wasn't found in the relation

val fold_congruences : (t, repr * XSet.t, 'acc) IStdlib.IStd.Container.fold

fold over the equivalence classes of the relation, singling out the representative for each class

val reorient : should_keep:(X.t -> bool) -> t -> X.t XMap.t

the relation x -> x' derived from the equality relation that relates all x, x' such that ¬(should_keep x), should_keep x', and x=x', as well as y -> y' when no element in the equivalence class of y satisfies should_keep and y' is the representative of the class

val apply_subst : _ XMap.t -> t -> t

apply_subst subst uf eliminate all variables in the domain of subst from uf, keeping the smallest representative not in the domain of subst for each class. Classes without any such elements are kept intact.

val filter : f:(X.t -> bool) -> t -> t

only keep items satisfying f

val fold_elements : (t, X.t, 'acc) IStdlib.IStd.Container.fold