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 Source

Returns new and empty MutDisjointSets in the region rc.

def equivalent(x: t, y: t, s: MutDisjointSets[t, r]): Bool \ r with Order[t] Source

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.

def find(x: t, s: MutDisjointSets[t, r]): Option[t] \ r with Order[t] Source

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

def makeSet(x: t, s: MutDisjointSets[t, r]): Unit \ r with Order[t] Source

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

Source

Updates s with the elements of the iterable m.

def memberOf(x: t, s: MutDisjointSets[t, r]): Bool \ r with Order[t] Source

Returns true iff x is a member of s.

def size(s: MutDisjointSets[t, r]): Int32 \ r with Order[t] Source

Returns the number of elements in s.

def union(x: t, y: t, s: MutDisjointSets[t, r]): Unit \ r with Order[t] Source

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-setdatastructure