1 (* Pasted from Pottier's PP compiler *)
3 (** This module implements a simple and efficient union/find algorithm.
4 See Robert E. Tarjan, ``Efficiency of a Good But Not Linear Set
5 Union Algorithm'', JACM 22(2), 1975. *)
7 (** The abstraction defined by this module is a set of points,
8 partitioned into equivalence classes. With each equivalence class,
9 a piece of information, of abstract type ['a], is associated; we
10 call it a descriptor. *)
13 (** [fresh desc] creates a fresh point and returns it. It forms an
14 equivalence class of its own, whose descriptor is [desc]. *)
15 val fresh: 'a -> 'a point
17 (** [find point] returns the descriptor associated with [point]'s
19 val find: 'a point -> 'a
21 (** [union point1 point2] merges the equivalence classes associated
22 with [point1] and [point2] (which must be distinct) into a single
23 class whose descriptor is that originally associated with [point2]. *)
24 val union: 'a point -> 'a point -> unit
26 (** [equivalent point1 point2] tells whether [point1] and [point2]
27 belong to the same equivalence class. *)
28 val equivalent: 'a point -> 'a point -> bool
30 (** [eunion point1 point2] is identical to [union], except it does
31 nothing if [point1] and [point2] are already equivalent. *)
32 val eunion: 'a point -> 'a point -> unit
34 (** [redundant] maps all members of an equivalence class, but one, to
36 val redundant: 'a point -> bool
38 (** [change p d] updates the descriptor of [p] to [d]. *)
39 val change: 'a point -> 'a -> unit