Module Valued.PatriciaTree

Patricia-tree based union-find lattice with attached values.

Parameters

module Config : Parameters.PATRICIA_TREE_CONFIG

module Node : Parameters.NODE

module Value : Parameters.VALUE with type node = Node.t

Signature

include Sig.UNION_FIND_LATTICE with type node = Node.t

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.

Values

type value = Value.t

the type of values, one optional value is attached to each equivalence class.

val get_value : t -> node -> value option

get_value uf n returns the optional value attached to the class of n.

val set_value : intersect:bool -> t -> node -> value -> t

set_value ~intersect uf n v returns a new union-find, where the value attached to the class of n is now v. If intersect is true, this value will be combined with the previous value (should one exists) via Parameters.VALUE.meet.