bundles/menhirLib/menhir-20120123/src/unionFind.mli

   1 (**************************************************************************)
   2 (*                                                                        *)
   3 (*  Menhir                                                                *)
   4 (*                                                                        *)
   5 (*  François Pottier, INRIA Rocquencourt                                  *)
   6 (*  Yann Régis-Gianas, PPS, Université Paris Diderot                      *)
   7 (*                                                                        *)
   8 (*  Copyright 2005-2008 Institut National de Recherche en Informatique    *)
   9 (*  et en Automatique. All rights reserved. This file is distributed      *)
  10 (*  under the terms of the Q Public License version 1.0, with the change  *)
  11 (*  described in file LICENSE.                                            *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* $Id: unionFind.mli,v 1.5 2005/12/01 16:20:07 regisgia Exp $ *)
  16
  17 (** This module implements a simple and efficient union/find algorithm.
  18     See Robert E. Tarjan, ``Efficiency of a Good But Not Linear Set
  19     Union Algorithm'', JACM 22(2), 1975. *)
  20
  21 (** The abstraction defined by this module is a set of points,
  22     partitioned into equivalence classes. With each equivalence class,
  23     a piece of information, of abstract type ['a], is associated; we
  24     call it a descriptor. *)
  25 type 'a point
  26
  27 (** [fresh desc] creates a fresh point and returns it. It forms an
  28     equivalence class of its own, whose descriptor is [desc]. *)
  29 val fresh: 'a -> 'a point
  30
  31 (** [find point] returns the descriptor associated with [point]'s
  32     equivalence class. *)
  33 val find: 'a point -> 'a
  34
  35 (** [union point1 point2] merges the equivalence classes associated
  36     with [point1] and [point2] (which must be distinct) into a single
  37     class whose descriptor is that originally associated with [point2]. *)
  38 val union: 'a point -> 'a point -> unit
  39
  40 (** [equivalent point1 point2] tells whether [point1] and [point2]
  41     belong to the same equivalence class. *)
  42 val equivalent: 'a point -> 'a point -> bool
  43
  44 (** [eunion point1 point2] is identical to [union], except it does
  45     nothing if [point1] and [point2] are already equivalent. *)
  46 val eunion: 'a point -> 'a point -> unit
  47
  48 (** [redundant] maps all members of an equivalence class, but one, to
  49     [true]. *)
  50 val redundant: 'a point -> bool
  51
  52 (** [change p d] updates the descriptor of [p] to [d]. *)
  53 val change: 'a point -> 'a -> unit