# LispKit Disjoint-Set

Library `(lispkit disjoint-set)` implements disjoint sets, a mutable union-find data structure that tracks a set of elements partitioned into disjoint subsets. Disjoint sets are based on hashtables and require the definition of an equality and a hash function.

disjoint-set-type-tag [constant]

Symbol representing the `disjoint-set` type. The `type-for` procedure of library `(lispkit type)` returns this symbol for all disjoint set objects.

(disjoint-set? obj) [procedure]

Returns `#t` if obj is a disjoint set object; otherwise `#f` is returned.

(make-eq-disjoint-set) [procedure]

Returns a new empty disjoint set using `eq` as equality and `eq-hash` as hash function.

(make-eqv-disjoint-set) [procedure]

Returns a new empty disjoint set using `eqv` as equality and `eqv-hash` as hash function.

(make-disjoint-set comparator) [procedure]
(make-disjoint-set hash eql)

Returns a new empty disjoint set using eql as equality and hash as hash function. Instead of providing two functions, a new disjoint set can also be created based on a comparator.

(disjoint-set-make dset x) [procedure]

Adds a new singleton set x to dset if element x does not exist already in disjoint set dset.

(disjoint-set-find dset x) [procedure]
(disjoint-set-find dset x default)

Looks up element x in dset and returns the set in which x is currently contained. Returns default if element x is not found. If default is not provided, `disjoint-set-find` uses `#f` instead.

(disjoint-set-union dset x y) [procedure]

Unifies the sets containing x and y in disjoint set dset.

(disjoint-set-size dset) [procedure]

Returns the number of sets in dset.