# disjoint-sets-with-constant-time-union.api
#
# Disjoint-set union and membership in essentially constant time.
#
# The basic idea here is to represent a set by an inverted tree
# in which children point to their parent (but not vice versa)
# and then do a union of two sets just by pointing the root node
# of one set to the root node of the other -- a constant time
# operation. Working out the details requires subtleties both
# algorithmic and analytical -- see:
#
# http://en.wikipedia.org/wiki/Disjoint-set_data_structure
#
# The canonical application for this datastructure is in identifying
# the connected components of a graph: Start with each graph node in
# its own set and then merge all sets joined by an edge -- voila!
# With unions being O(1) this algorithm is O(N) -- if we were to use
# vanilla sets with O(N) union operations, the algorithm would be O(N**2),
# which is usually prohibitively slow.
#
# For applications see:
#
# src/lib/graph/loop-structure-g.pkg# src/lib/graph/graph-minor-view.pkg# src/lib/graph/node-partition.pkg# src/lib/compiler/back/low/block-placement/weighted-block-placement-g.pkg#
# Essentially the same algorithm is independently
# implemented, using int-vectors, for speed in:
#
# src/lib/compiler/back/low/main/nextcode/find-nextcode-cccomponents.pkg#
#
#
# DESCRIPTION
#
# A Union/Find package consists of
#
# A type constructor Union_Find(X)
# A fn to make an instance of Union_Find(X)
# A fn to get the contents of a Union_Find(X)
# A fn to test equality of two Union_Find(X)s
# A fn to take the union of two Union_Find(X)s
#
# The link, union, and unify functions return TRUE
# when the elements were previously NOT equal.
#
# For vanilla sets see:
# src/lib/src/set.api# Compiled by:
# src/lib/std/standard.lib# Compiled by:
# src/lib/std/standard.lib### "It is not enough to have a good mind.
### The main thing is to use it well."
###
### -- Rene Descartes
# This api is implemented in:
#
# src/lib/src/disjoint-sets-with-constant-time-union.pkg# src / lib/src/disjoint-sets-with-constant-time-union-simple-version.pkg
#
api Disjoint_Sets_With_Constant_Time_Union {
#
Disjoint_Set(X); # Type of disjoint set containing elements of type X.
make_singleton_disjoint_set: X -> Disjoint_Set(X); # Creates a new singleton set containing x.
equal: (Disjoint_Set(X), Disjoint_Set(X)) -> Bool;
#
# equal (e, e') returns TRUE if and only if e and e' are either made by
# the same call to union_find or if they have been unioned (see below).
get: Disjoint_Set(X) -> X;
#
# Returns the value supplied to create Disjoint_Set(x).
#
# If X is an equality type then contents_of(union_find x) == x, and
# equal (union_find (get x), x) == FALSE.
set: (Disjoint_Set(X), X) -> Void;
#
# set (e, x) updates the contents of e to be x
unify: ((X, X) -> X) -> (Disjoint_Set(X), Disjoint_Set(X)) -> Bool;
#
# unify f (e, e') makes e and e' equal; if v and v' are the
# contents of e and e', respectively, before unioning them,
# then the contents of the unioned element is f (v, v'). Returns
# TRUE, when elements were not equal prior to the call.
union: (Disjoint_Set(X), Disjoint_Set(X)) -> Bool;
#
# union (e, e') makes e and e' equal; the contents of the unioned
# element is the contents of one of e and e' before the union operation.
# After union (e, e') elements e and e' will be congruent in the
# sense that they are interchangeable in any context.. Returns
# TRUE, when elements were not equal prior to the call.
link: (Disjoint_Set(X), Disjoint_Set(X)) -> Bool;
#
# link (e, e') makes e and e' equal; the contents of the linked
# element is the contents of e' before the link operation.
#
# Returns TRUE when elements were not equal prior to the call.
};
# Original Author:
# Fritz Henglein
# DIKU, University of Copenhagen
# henglein@diku.dk
#
# (Much modified since -- don't blame Fritz for any bugs! :-)