   ### 15.3.366  src/lib/src/disjoint-sets-with-constant-time-union.api

`# 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! :-)`   