Module Classic.ArrayWithCopy

Reference implementation: this implements union-find as a mutable array. Warning: it is NOT persistent, but provides a copy function

Parameters

module Config : Parameters.ARRAY_CONFIG

module Node : Parameters.NODE_WITH_COMPARE

Signature

type node = Node.t

the type of nodes, i.e. elements of the union-find.

type t

the type of the union-find

Union-find operations

val make : int -> t

make n creates a new union-find supporting up to n nodes:

• PatriciaTree implementations disregard this n and can always support any number of nodes.
• ArrayWithCopy will crash if used with node whose NODE.to_int is >= n.
• PersistentArray will use n to set the initial array size. If PERSISTENT_ARRAY_CONFIG.extendable is true (the default), the array may then grow beyond that size if needed. Otherwise it will fail.

val find : t -> node -> node

find uf n returns a unique representative of the node n in uf.

val union : t -> node -> node -> t

union uf a b returns a new version of uf where the classes of a and b have been merged.

val check_related : t -> node -> node -> bool

check_related uf a b is true if and only if a and b are in the same equivalence class in uf.

Lattice operations

val incl : t -> t -> bool

incl uf_a uf_b is lattice inclusion, uf_a <= uf_b, i.e. forall x y, if check_related uf_b x y then check_related uf_a x y

val join : t -> t -> t

join uf_a uf_b is the least upper-bound of uf_a and uf_b, i.e. forall x y, check_related (join uf_a uf_b) x y iff check_related uf_b x y and check_related uf_a x y

val meet : t -> t -> t

meet uf_a uf_b is the greatest lower bound of uf_a and uf_b, its relation check_related (meet uf_a uf_b) is the transitive closure of check_related uf_a or check_related uf_b.

Testing and debugging

val copy : t -> t

To compare persistent union-find with non-persistent version, we need an explicit copy operation. This is Fun.id for all persistent versions.

val check_invariants : t -> string option

For testing, check_invariant uf returns None if all internal invariants hold. Otherwise, it returns Some error_msg.

val pretty : Stdlib.Format.formatter -> t -> unit

pretty printer.