Up
# module UnionFind

: sig

This module implements a simple and efficient union/find algorithm. See Robert E. Tarjan, ``Efficiency of a Good But Not Linear Set Union Algorithm'', JACM 22(2), 1975.

#

type 'a point

The abstraction defined by this module is a set of points,
partitioned into equivalence classes. With each equivalence class,
a piece of information, of abstract type `'a`

, is associated; we
call it a descriptor.

#

val fresh : 'a -> 'a point

`fresh desc`

creates a fresh point and returns it. It forms an
equivalence class of its own, whose descriptor is `desc`

.

#

val find : 'a point -> 'a

`find point`

returns the descriptor associated with `point`

's
equivalence class.

end