# MutDisjointSets

`enum MutDisjointSets[t: Type, r: Eff]`

Source`case MutDisjointSets({ forest = MutMap[t, Node[t, r], r], rc = Region[r] })`

Represents a mutable disjoint set data structure using union-by-rank and path compression.

## Definitions

`def empty(rc: Region[r]): MutDisjointSets[t, r] \ r`

SourceReturns new and empty `MutDisjointSets`

in the region `rc`

.

Returns true if `x`

and `y`

are in the same disjoint set.
This is equivalent to having the same representative / root.
Returns false if either `x`

or `y`

is not in `s`

.

Returns the representative / root of the set that contains `x`

.

Updates `s`

with a new disjoint set containing `x`

if `x`

is not already in `s`

.

`def makeSets(m: m, s: MutDisjointSets[elt, r]): Unit \ r + Aef[m] with Iterable[m], Order[elt] where Iterable.Elm[m] ~ elt`

SourceUpdates `s`

with the elements of the iterable `m`

.

Returns `true`

iff `x`

is a member of `s`

.

Returns the number of elements in `s`

.

Merges the sets that contain `x`

and `y`

if both `x`

and `y`

are in `s`

.
If `x`

and `y`

have the same rank, then `y`

becomes the new parent of `x`

.
Otherwise, the element with the highest rank becomes the new representative.

The rank of an element is determined by how many times it is made the new representative after a union with another element of the same rank.

Further reading:
https://en.wikipedia.org/wiki/Disjoint-set*data*structure