package codex

  1. Overview
  2. Docs
package codex
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Functional.GenericRelationalValuedSource

Functional union find

  • with generic types (parameterised by 'a)
  • with relations ('a, 'b) Relation.t on edges between elements and representatives
  • with values attached to each representative This interface can easily be reused to remove any of the above features if needed.

This is functional and immutable

Parameters

module Value : Parameters.GENERIC_VALUE with type ('a, 'b) relation = ('a, 'b) Relation.t

Signature

Set of 'a Elt.t

Sourcetype t

Type of the union-find structure

Sourceval pretty : Format.formatter -> t -> unit

Prints equivalence classes

Sourceval pretty_debug : Format.formatter -> t -> unit

Prints whole data structure

Sourceval equal : t -> t -> bool
Sourceval subseteq : t -> t -> bool
Sourceval empty : t

Existential wrappers for the return type of find operations

Sourcetype 'a elt_through_relation =
  1. | EltThroughRel : 'b Elt.t * ('a, 'b) Relation.t -> 'a elt_through_relation
Sourcetype 'a value_through_relation =
  1. | ValueThroughRelation : 'b Value.t option * ('a, 'b) Relation.t -> 'a value_through_relation
Sourcetype 'a all_through_relation =
  1. | AllThroughRelation : 'b Elt.t * 'b Value.t option * EltSet.t * ('a, 'b) Relation.t -> 'a all_through_relation

Find operations

Sourceval find_representative : t -> 'a Elt.t -> 'a elt_through_relation

Returns the representative of the given element, along with the relation between the given element and its representative. O(1) complexity

Sourceval find_class : t -> 'a Elt.t -> EltSet.t

Returns the class of the given element, O(1) complexity

Sourceval find_value : t -> 'a Elt.t -> 'a value_through_relation

Returns the value of the given element's representative (None for top), along with the relation between the given element and its representative. O(1) complexity

Sourceval find : t -> 'a Elt.t -> 'a all_through_relation

Returns the given element's representative, associated value (None for top), along with the relation between the given element and its representative. O(1) complexity

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

Sourceval add_value : t -> 'a Elt.t -> 'a Value.t -> t

add_value uf a v is uf 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

Union and join

Sourceval union : t -> 'a Elt.t -> 'b Elt.t -> ('a, 'b) Relation.t -> (t, ('a, 'b) Relation.t) result

union uf a b r adds the r a b relation in uf. Returns Ok uf' with the new value if successful, and Error rel if a and b are already related by rel and r != rel.

Sourceval join : t -> t -> t

join a b joins the two union find-structures:

  • The new classes are the intersection of the old classes
  • The new values are the Value.join of the old values