source: Deliverables/D2.2/8051/src/utilities/unionFind.mli

Last change on this file was 486, checked in by ayache, 9 years ago

Deliverable D2.2

File size: 1.5 KB
Line 
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. *)
11type '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]. *)
15val fresh: 'a -> 'a point
16
17(** [find point] returns the descriptor associated with [point]'s
18    equivalence class. *)
19val 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]. *)
24val union: 'a point -> 'a point -> unit
25
26(** [equivalent point1 point2] tells whether [point1] and [point2]
27    belong to the same equivalence class. *)
28val 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. *)
32val eunion: 'a point -> 'a point -> unit
33
34(** [redundant] maps all members of an equivalence class, but one, to
35    [true]. *)
36val redundant: 'a point -> bool
37
38(** [change p d] updates the descriptor of [p] to [d]. *)
39val change: 'a point -> 'a -> unit
Note: See TracBrowser for help on using the repository browser.