1 | (* Pasted from Pottier's PP compiler *) |
---|
2 | |
---|
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. *) |
---|
6 | |
---|
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. *) |
---|
11 | type 'a point |
---|
12 | |
---|
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 |
---|
16 | |
---|
17 | (** [find point] returns the descriptor associated with [point]'s |
---|
18 | equivalence class. *) |
---|
19 | val find: 'a point -> 'a |
---|
20 | |
---|
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 |
---|
25 | |
---|
26 | (** [equivalent point1 point2] tells whether [point1] and [point2] |
---|
27 | belong to the same equivalence class. *) |
---|
28 | val equivalent: 'a point -> 'a point -> bool |
---|
29 | |
---|
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 |
---|
33 | |
---|
34 | (** [redundant] maps all members of an equivalence class, but one, to |
---|
35 | [true]. *) |
---|
36 | val redundant: 'a point -> bool |
---|
37 | |
---|
38 | (** [change p d] updates the descriptor of [p] to [d]. *) |
---|
39 | val change: 'a point -> 'a -> unit |
---|