Module `Union_Find.Imperative`

Imperative Union Find structures. These are mutable and can only grow (i.e. add new equalities), using union by size and lazy path compression.

Nodes

Functors used to build nodes out of elements, relations and values

module MakeNode
  (Elt : Parameters.SIMPLE_GENERIC_ELT)
  (Relation : Parameters.GENERIC_GROUP) : 
  sig ... end

Create a simple node by wrapping an elt with a pointer

module MakeNumberedNode
  (Elt : HetHashtbl.HETEROGENEOUS_HASHED_TYPE)
  (Relation : Parameters.GENERIC_GROUP)
  () : 
  sig ... end

Same as MakeNode, but also remembers all built node in a hash-table so we can check if elements already have an associated node

module MakeValuedNode
  (Elt : Parameters.SIMPLE_GENERIC_ELT)
  (Relation : Parameters.GENERIC_GROUP)
  (Value : 
    Parameters.SIMPLE_GENERIC_VALUE
      with type ('a, 'b) relation = ('a, 'b) Relation.t) : 
  sig ... end

This creates a valued node by wrapping an elt with a pointer (same as MakeSimpleNode), but here representatives also have a Value.t attached.

module MakeValuedNumberedNode
  (Elt : HetHashtbl.HETEROGENEOUS_HASHED_TYPE)
  (Relation : Parameters.GENERIC_GROUP)
  (Value : 
    Parameters.SIMPLE_GENERIC_VALUE
      with type ('a, 'b) relation = ('a, 'b) Relation.t)
  () : 
  sig ... end

Same as MakeValuedNode, but also remembers all built node in a hash-table so we can check if elements already have an associated node

module HashtblSimpleNode
  (Elt : HetHashtbl.HETEROGENEOUS_HASHED_TYPE)
  (Relation : Parameters.GENERIC_GROUP) : 
  Parameters.UF_NODE with type 'a t = 'a Elt.t and module Relation = Relation

Union find structures

module GenericRelationalValued
  (Node : Parameters.UF_NODE_WITH_VALUE) : 
  Signatures.IMPERATIVE_GENERIC_RELATIONAL_VALUED
    with type 'a t = 'a Node.t
     and type ('a, 'b) relation = ('a, 'b) Node.Relation.t
     and type 'a value = 'a Node.Value.t

Imperative union find

module GenericRelational
  (Node : Parameters.UF_NODE) : 
  Signatures.IMPERATIVE_GENERIC_RELATIONAL
    with type 'a t = 'a Node.t
     and type ('a, 'b) relation = ('a, 'b) Node.Relation.t

Same as GenericRelationalValued, but without the values

Module Union_Find.Imperative

Nodes

Union find structures

Module `Union_Find.Imperative`