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 |
---|