StaticDisjointSet
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:23
Union-find: tracks a partition of items into disjoint sets, answering “are these two in the same set” and merging two sets, both in near-constant time.
“Static” names the shape of the problem, not the API — sets only ever merge, never split, which is what allows the flattening that makes it fast. Items may be added at any time.
Both optimisations are present: path compression on find (every node
walked is re-pointed straight at the root) and union by rank (the
shallower tree is hung under the deeper one). Together they give O(α(n))
amortised per operation, where α is the inverse Ackermann function — at most
4 for any n that fits in memory, so constant in practice.
Items are compared by SameValueZero, native Map semantics.
Type Parameters
Section titled “Type Parameters”T extends DefinedValue = DefinedValue
The item type.
Implements
Section titled “Implements”IDisjointSet<T>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new StaticDisjointSet<
T>(iterable?):StaticDisjointSet<T>
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:37
Parameters
Section titled “Parameters”iterable?
Section titled “iterable?”Iterable<T, any, any>
Returns
Section titled “Returns”StaticDisjointSet<T>
Methods
Section titled “Methods”connected()
Section titled “connected()”connected(
a,b):boolean
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:132
Whether a and b are in the same set. A query, so an unknown item is
simply not connected to anything rather than being added.
Parameters
Section titled “Parameters”T
T
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”count()
Section titled “count()”count():
number
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:49
The number of items across every set. O(1).
Returns
Section titled “Returns”number
find()
Section titled “find()”find(
item):T|undefined
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:86
The representative of item’s set — the same value for every member, and
stable until the set is merged into another.
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”T | undefined
The representative, or undefined if item was never added.
Implementation of
Section titled “Implementation of”groups()
Section titled “groups()”groups():
IterableIterator<readonlyT[]>
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:144
Each set as its own array of members, in no particular order. O(n).
Returns
Section titled “Returns”IterableIterator<readonly T[]>
has(
item):boolean
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:76
Whether item belongs to any set. O(1).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”boolean
makeSet()
Section titled “makeSet()”makeSet(
item):void
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:54
Adds item as a set of its own. A no-op if it is already known. O(1).
Parameters
Section titled “Parameters”T
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”makeSets()
Section titled “makeSets()”makeSets(
items):void
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:69
O(m) in the number of items.
Parameters
Section titled “Parameters”Iterable<T>
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”setCount()
Section titled “setCount()”setCount():
number
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:44
The number of disjoint sets, not the number of items. O(1).
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”union()
Section titled “union()”union(
a,b):boolean
Defined in: packages/data/src/disjoint-set/static-disjoint-set.ts:100
Merges the sets holding a and b. Either operand not yet known is added
first, so building a partition from a stream of pairs needs no separate
makeSet pass; isolated items still do.
Parameters
Section titled “Parameters”T
T
Returns
Section titled “Returns”boolean
true if two distinct sets were merged, false if a and b
were already in the same one.