Module Imperative.GenericRelationalValuedSource

Imperative union find

Performs union by size, and path compression in find.

This is fully imperative and mutable.

Parameters

Signature

include Signatures.IMPERATIVE_GENERIC_RELATIONAL with type 'a t = 'a Node.t with type ('a, 'b) relation = ('a, 'b) Node.Relation.t
Sourcetype 'a t = 'a Node.t
Sourcetype ('a, 'b) relation = ('a, 'b) Node.Relation.t
Sourcetype 'a node_through_relation =
  1. | NodeThoughRelation : 'b t * ('a, 'b) relation -> 'a node_through_relation

Existential wrapper for returning the representative

Sourceval find_representative : 'a t -> 'a node_through_relation

Find the representative of a node, and the associated relation

check_related a b returns the relation between a and b if they are in the same class.

Sourceval union : 'a t -> 'b t -> ('a, 'b) relation -> (unit, ('a, 'b) relation) result

union m n r adds the m--(r)-->n relation to the union find returns Ok () on success, Error rel if m and n are already related via another relation rel and r != rel.

Sourcetype 'a value = 'a Node.Value.t
Sourcetype 'a value_through_relation =
  1. | ValueThroughRelation : 'b value * ('a, 'b) relation -> 'a value_through_relation

Existential wrapper for returning the value

Sourcetype 'a node_and_value_through_relation =
  1. | NodeValueThroughRelation : 'b t * 'b value * ('a, 'b) relation -> 'a node_and_value_through_relation

Existential wrapper for returning the value and the representative

Find operations

Sourceval find_value : 'a t -> 'a value_through_relation

Find the value of a node, and the associated relation

Find the value and representative of a node, and the associated relation

Other misc operations

Sourceval add_value : 'a t -> 'a value -> unit

add_value a v adds with the value v added to a (Or more precisely, the value is added to the representative of a, via the relation between a and its representative). Intersects with previous value via Value.meet if one is present