(* $Header: /home/pauillac/formel1/fpottier/cvs/modulo/unionFind.mli,v 1.1 2002/04/08 09:55:51 fpottier Exp $ *)

(* This module provides support for a basic union/find algorithm. *)

(* The abstraction defined by this module is a set of points,
   partitioned into equivalence classes. With each equivalence class,
   a piece of information, of abstract type ['a], is associated; we
   call it a descriptor. *)

type 'a point

(* [equivalent point1 point2] tells whether [point1] and [point2] belong to
   the same equivalence class. *)

val equivalent: 'a point -> 'a point -> bool

(* [describe point] returns the descriptor associated with [point]'s
   equivalence class. *)

val describe: 'a point -> 'a

(* [fresh desc] creates a fresh point and returns it. It forms an
   equivalence class of its own, whose descriptor is [desc]. *)

val fresh: 'a -> 'a point

(* [self desc] creates a fresh point [point] and returns it. It forms an
   equivalence class of its own, whose descriptor is [desc point]. In
   other words, the descriptor is allowed to recursively refer to
   the point that is being created. Use with caution -- the function
   [desc] is allowed to store a pointer to [point], but must not use it
   in any other way. *)

val self: ('a point -> 'a) -> 'a point

(* [alias point1 point2] merges the equivalence classes associated
   with [point1] and [point2], which must be distinct, into a single
   class, whose descriptor is that originally associated with
   [point2]'s equivalence class. *)

val alias: 'a point -> 'a point -> unit

(* [redundant] maps all members of an equivalence class, but one,
   to [true]. *)

val redundant: 'a point -> bool