lib/lib.x

Disjoint sets with union-find.

Advanced and interop API

DisjointSet

DisjointSet.find

int DisjointSet.find(DisjointSet set, int x)

Returns the representative of x and compresses its traversed path. set must be live and x must be between zero and set.length - 1.

Source: lib/lib.x:54

DisjointSet.free

void DisjointSet.free(DisjointSet set)

Releases a live set and its arrays, invalidating every alias.

Source: lib/lib.x:45

DisjointSet.new

DisjointSet DisjointSet.new(int n)

Creates a union-find over elements 0 through n - 1. n must be nonnegative. The result belongs to the active Scope and starts with each element in its own component.

Raises: <size-limit> or <alloc-fail> while allocating the structure or its arrays.

Source: lib/lib.x:31

DisjointSet.num_components

int DisjointSet.num_components(DisjointSet set)

Returns the live set’s current number of disjoint components.

Source: lib/lib.x:98

DisjointSet.sizes

List DisjointSet.sizes(DisjointSet set)

Returns canonical (size representative) rows for the current roots. Rows are ordered by Var.compare, ascending first by size and then by representative. Returned Lists live through their owning List pool, which may be an ancestor of the active pool.

Raises: <size-limit> or <alloc-fail> while collecting or sorting rows.

Source: lib/lib.x:88

DisjointSet.union

void DisjointSet.union(DisjointSet set, int a, int b)

Merges the components containing a and b by size. set must be live and both elements must be in range. The larger component’s root wins unless the sizes tie, when the root of a wins. Merging an existing component is a no-op.

Source: lib/lib.x:70

Public types

DisjointSet

typedef struct DisjointSet { int *parent, *size, length, ncmpnts; } *DisjointSet

Owns a mutable union-find forest over integer elements.

DisjointSet.new creates the only valid state. The structure and its two arrays are Scope-owned; DisjointSet.free releases them early and invalidates every alias.

Source: lib/lib.x:19

Design notes

This module is aggregated into the x2c.x runtime and implicitly available through the prelude. DisjointSet owns a mutable union-find structure behind a pointer typedef; callers release it with DisjointSet.free.