unionFind.mli

   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