The disjoint-sets vocabulary implements the disjoint set data structure (also known as union-find, after the two main operations which it supports) that represents a set of elements partitioned into disjoint equivalence classes, or alternatively, an equivalence relation on a set.

The two main supported operations are equating two elements, which joins their equivalence classes, and checking if two elements belong to the same equivalence class. Both operations have the time complexity of the inverse Ackermann function, which for all intents and purposes is constant time.

The class of disjoint sets:

disjoint-set

Creating new disjoint sets:

<disjoint-set> ( -- disjoint-set )

assoc>disjoint-set ( assoc -- disjoint-set )

Queries:

equiv? ( a b disjoint-set -- ? )

equiv-set-size ( a disjoint-set -- n )

Adding elements:

add-atom ( a disjoint-set -- )

Equating elements:

equate ( a b disjoint-set -- )

Additionally, disjoint sets implement the clone generic word.