Struct ScyllaDisjointSetDOTS

A DOTS/Burst-compatible Union-Find (Disjoint Set Union) data structure backed by Unity.Collections.NativeArray<T> buffers, providing the same path compression and union-by-rank optimizations as ScyllaDisjointSet in a form suitable for use inside Burst-compiled jobs.

Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
[BurstCompile]
public struct ScyllaDisjointSetDOTS : IDisposable
Remarks

This struct partitions N elements (addressed as integer indices 0..N-1) into non-overlapping groups called components. The two fundamental operations are:

  • Find(int) Locates the canonical representative (root) of the component containing a given element, applying full two-pass path compression as a side effect.
  • Union(int, int) Merges two components into one using union-by-rank, decreasing ComponentCount by one when a real merge occurs.

Both operations run in O(alpha(n)) amortized time, where alpha is the inverse Ackermann function - effectively constant for all realistic input sizes.

Native memory ownership: The struct owns two Unity.Collections.NativeArray<T> allocations (parent links and rank values). You must call Dispose() when finished, or use a using statement / block, to avoid native memory leaks. The struct reports whether it has been allocated via IsCreated.

Fixed capacity: The element count is fixed at construction. Clear() resets all union information without re-allocating the buffers.

Thread safety: This struct provides no synchronization. In a Burst job context, use separate struct instances per thread (e.g., per-thread scratch buffers) or coordinate access externally. Do not access the same instance from multiple threads simultaneously without external locking.

Safety handles: This struct is not decorated with [NativeContainer] because it delegates safety tracking entirely to its contained Unity.Collections.NativeArray<T> fields. The arrays carry their own AtomicSafetyHandle and DisposeSentinel in the Editor, so Unity's job safety system will detect invalid concurrent access and use-after-dispose bugs at development time.

Common use-cases include connectivity queries in job-computed graphs, parallel maze generation, Kruskal's minimum spanning tree in geometry processing jobs, and clustering in spatial data processing pipelines. 

// Direct construction with a temporary allocator for single-frame use.
using var dsu = new ScyllaDisjointSetDOTS(100, Allocator.TempJob);
dsu.Union(0, 1);
dsu.Union(1, 2);
bool connected = dsu.Connected(0, 2); // true

// Fluent builder - persistent allocator for long-lived data.
var dsu = ScyllaDisjointSetDOTS.CreateBuilder()
.WithCapacity(256)
.WithAllocator(Allocator.Persistent)
.Build();
// ... use dsu ...
dsu.Dispose();

Constructors

ScyllaDisjointSetDOTS(int, Allocator)

Initializes a new ScyllaDisjointSetDOTS with the specified number of elements and allocator, placing every element in its own singleton component.

Declaration
public ScyllaDisjointSetDOTS(int capacity, Allocator allocator)
Parameters
Type Name Description
int capacity

The total number of elements tracked by this set, addressed as integer indices 0..capacity-1. Values less than 0 are silently clamped to 0.
Allocator allocator

The Unity Collections allocator used for the two internal Unity.Collections.NativeArray<T> buffers. Must be a valid allocator other than Unity.Collections.Allocator.None and Unity.Collections.Allocator.Invalid. Common choices:

  • Unity.Collections.Allocator.TempSingle-frame or very short-lived; fastest allocation.
  • Unity.Collections.Allocator.TempJobUp to four frames; required when passing to a Burst job.
  • Unity.Collections.Allocator.PersistentLong-lived data; must be disposed manually.
Remarks

After construction, ComponentCount equals capacity because no elements have been merged. The rank buffer is zero-initialized, while the parent buffer is initialized with each element pointing to itself. You must call Dispose() when finished to release the native memory.

Exceptions
Type Condition
ArgumentException

Thrown when allocator is Unity.Collections.Allocator.None or Unity.Collections.Allocator.Invalid.

Properties

Capacity

Gets the total number of elements managed by this disjoint set.

Declaration
public int Capacity { get; }
Property Value
Type Description
int

The fixed element count established at construction time. Returns 0 when the struct has not been created or has already been disposed. For a created instance, Capacity always equals Count because the set operates over a dense pre-allocated index range.

ComponentCount

Gets the current number of disjoint connected components.

Declaration
public int ComponentCount { get; }
Property Value
Type Description
int

Starts at Capacity after construction (every element is a singleton). Decreases by one each time Union(int, int) successfully merges two previously unconnected elements. Resets to Capacity after Clear(). Set to 0 after Dispose().

Count

Gets the number of elements tracked by this disjoint set.

Declaration
public int Count { get; }
Property Value
Type Description
int

Identical to Capacity for this fixed-size structure. Returns 0 when the struct has not been created or has been disposed.

IsCreated

Gets a value indicating whether the underlying native buffers have been allocated and not yet disposed.

Declaration
public bool IsCreated { get; }
Property Value
Type Description
bool

true after a successful constructor call and before Dispose() is invoked; false on a default-initialized struct or after disposal. Always check IsCreated before using the struct when its lifecycle is uncertain.

Methods

Clear()

Resets every element to its own singleton component, restoring the structure to its post-construction state without releasing or reallocating the native buffers.

Declaration
public void Clear()
Remarks

After this call, ComponentCount equals Capacity and every element is its own root with rank 0. Existing native buffer allocations are reused, so no heap allocation occurs. This is the preferred way to reuse a ScyllaDisjointSetDOTS instance across frames or job dispatches without incurring allocator overhead.

Exceptions
Type Condition
InvalidOperationException

Thrown when the struct has not been created or has already been disposed (IsCreated is false).

Connected(int, int)

Determines whether elements x and y belong to the same component.

Declaration
public bool Connected(int x, int y)
Parameters
Type Name Description
int x

The zero-based index of the first element. Must satisfy 0 <= x < Capacity.
int y

The zero-based index of the second element. Must satisfy 0 <= y < Capacity.
Returns
Type Description
bool

true if x and y share the same root (i.e., are in the same component); false otherwise. Returns true when both arguments are the same index.
Remarks

Internally calls Find(int) twice and compares roots. Path compression is applied to both elements as a side effect.

Exceptions
Type Condition
InvalidOperationException

Thrown when the struct has not been created or has already been disposed.
ArgumentOutOfRangeException

Thrown when x or y is out of range, propagated from the internal Find(int) calls.

CreateBuilder()

Creates and returns a new fluent ScyllaDisjointSetDOTS.Builder for configuring and constructing a ScyllaDisjointSetDOTS instance.

Declaration
public static ScyllaDisjointSetDOTS.Builder CreateBuilder()
Returns
Type Description
ScyllaDisjointSetDOTS.Builder

A fresh ScyllaDisjointSetDOTS.Builder pre-configured with the default capacity of 16 and no allocator set. Call WithCapacity(int), WithAllocator(Allocator), and finally Build() to obtain the finished struct.

Dispose()

Releases the native memory backing this disjoint set and marks the struct as unallocated.

Declaration
public void Dispose()
Remarks

Disposes both the parent and rank Unity.Collections.NativeArray<T> buffers if they are currently allocated. After this call, IsCreated returns false and ComponentCount is reset to 0.

It is safe to call Dispose() multiple times; subsequent calls are no-ops because the guard checks Unity.Collections.NativeArray<T>.IsCreated before disposing. This matches the recommended pattern for IDisposable implementations backed by Unity native containers.

Always call Dispose() (or use a using statement) to prevent native memory leaks. In the Unity Editor, the DisposeSentinel embedded in the Unity.Collections.NativeArray<T> fields will report a leak warning if the GC collects this struct before disposal.

Find(int)

Returns the canonical representative (root) of the component that contains element x, applying full two-pass path compression as a side effect.

Declaration
public int Find(int x)
Parameters
Type Name Description
int x

The zero-based index of the element whose component root is to be found. Must satisfy 0 <= x < Capacity.
Returns
Type Description
int

The root index of the component containing x. Two elements a and b belong to the same component if and only if Find(a) == Find(b).
Remarks

Path compression is applied via a two-pass walk: the first pass traverses parent links up to the root; the second pass rewires every visited node to point directly at the root. This flattens the internal tree for future operations. The amortized complexity is O(alpha(n)), where alpha is the inverse Ackermann function.

Exceptions
Type Condition
InvalidOperationException

Thrown when the struct has not been created or has already been disposed (IsCreated is false).
ArgumentOutOfRangeException

Thrown when x is negative or greater than or equal to Capacity.

Union(int, int)

Merges the components containing elements x and y into a single component, using union-by-rank to keep the internal trees shallow.

Declaration
public bool Union(int x, int y)
Parameters
Type Name Description
int x

The zero-based index of the first element. Must satisfy 0 <= x < Capacity.
int y

The zero-based index of the second element. Must satisfy 0 <= y < Capacity.
Returns
Type Description
bool

true if x and y were in distinct components and have been merged, reducing ComponentCount by one. false if they already share the same component, leaving the structure unchanged.
Remarks

Union-by-rank attaches the root of the shallower tree under the root of the deeper tree. When both roots have equal rank, the root of y's component is attached under the root of x's component, and that root's rank is incremented.

Note: because NativeArray element access does not support compound assignment operators in all Burst contexts, the rank increment is written as _rank[rootX] = _rank[rootX] + 1 rather than _rank[rootX]++.

Exceptions
Type Condition
InvalidOperationException

Thrown when the struct has not been created or has already been disposed.
ArgumentOutOfRangeException

Thrown when x or y is out of range. Validation is performed by the internal Find(int) calls.

Implements

See Also