Specialized Structures

Three purpose-built structures, a packed bit set, a union-find structure, and a prefix tree, each solving one specific algorithmic shape that the general-purpose collections do not cover.

Summary

Scylla Core provides three structures that each answer one narrow question well:

• ScyllaBitArray is a packed bit set for compact boolean storage and bitwise set operations.
• ScyllaDisjointSet is a union-find (disjoint set union) structure for tracking which elements currently belong to the same group.
• The ScyllaTrie family is a prefix tree for storing strings with fast prefix existence tests and ordered enumeration.

The three barely resemble each other under the hood, a flat word array, a forest of parent pointers, and a tree of character edges, but they belong on the same page because each one implements a specific algorithm that System.Collections.Generic simply does not provide. They share the same theme already introduced on the Collections Overview page: a specialized algorithm the standard library does not give you, packaged behind the same IScyllaCollection contract, fluent builder, and optional thread-safe wrapper as every other Scylla collection.

Reach for one of these when the problem is not “store some items” but “answer this specific structural question fast”: Which bits are set? Are these two things in the same group? Does anything start with this text?

Use the specialized structures for:

• Compact boolean storage for large flag sets (fog-of-war reveal masks, dirty markers, visited-node sets in search algorithms) combined with bitwise And, Or, Xor, and Not across two same-sized arrays.
• Connected-component and grouping queries: procedural dungeon region detection, faction or alliance membership after a merge, Kruskal-style minimum spanning tree construction.
• Prefix-keyed lookup: console autocomplete, cheat-code recognition, command registries keyed by name.
• Burst-compiled jobs that need a bit set or a union-find structure without touching the managed heap, via ScyllaBitArrayDOTS and ScyllaDisjointSetDOTS.
• Backing the ConnectedComponents graph algorithm, which returns a ScyllaDisjointSet directly; see Graph.

Features

• Packed 64-bit storage. ScyllaBitArray stores 64 boolean flags per ulong word, so 1024 flags cost 128 bytes instead of the 1 KB a bool[1024] would take, with better cache locality on top of the raw memory saving.
• O(1) popcount. Count and the equivalent PopCount() method maintain an incremental set-bit counter on every single-bit mutation and recompute it in one pass over the words after a bulk operation, so reading the population count never costs more than an int read.
• Full bitwise operator set with allocation-free enumeration. And, Or, Xor, and Not combine two arrays in place at O(Capacity/64); foreach over a ScyllaBitArray uses a value-type enumerator that skips whole zero words with a trailing-zero-count trick instead of testing every bit.
• Burst-ready DOTS twin. ScyllaBitArrayDOTS mirrors the full API over a NativeArray<ulong>, decorated with [BurstCompile], for per-entity flag storage inside jobs.
• Union-Find with both classic optimizations. ScyllaDisjointSet applies path compression on every Find and union-by-rank on every Union, giving amortized near-constant-time operations (O(alpha(n)), where alpha is the inverse Ackermann function) on both.
• Dense integer-indexed elements. Elements are addressed as 0..Capacity-1; Capacity and Count are always equal because the structure operates over a fixed, pre-allocated index range rather than a dynamic key set.
• Component bookkeeping built in. ComponentCount tracks the current number of disjoint groups without a separate counting pass, decrementing by one on every Union call that actually merges two components.
• Burst-ready DOTS twin. ScyllaDisjointSetDOTS mirrors Find, Union, Connected, and Clear over two NativeArray<int> buffers for use inside Burst jobs, such as parallel maze generation or job-computed graph connectivity.
• Two variants, one shape. ScyllaTrie is the set form (keys only); ScyllaTrie<TValue> is the map form (keys with an associated value). Both share the same node/edge storage model and the same TryAdd / ContainsPrefix / TryRemove vocabulary.
• ContainsPrefix is the whole point. It answers “does anything start with this text” in one traversal, without scanning every stored key, which is what makes a trie the right structure for autocomplete where a hash map falls short.
• Lexicographic enumeration. CopyMatches, CopyTo/CopyKeysTo, and CopyKeyValuePairsTo emit results in ascending lexicographic order because edges within a node are kept in sorted order by transition character.
• Optional case-insensitive matching with free-list reuse. Passing ignoreCase: true normalizes characters with char.ToUpperInvariant during traversal while preserving the original casing of stored keys; TryRemove prunes dead nodes and edges back into internal free lists rather than shrinking the arrays.

The structures

Picking between these three is rarely a judgment call the way picking a spatial structure or a queue variant can be; each one is built for a distinct question, and the three are not interchangeable. The table below lines up what each solves, its core operations, and whether a Burst-compatible DOTS (Data-Oriented Technology Stack) variant exists.

Structure	Solves	Key operations	DOTS variant
ScyllaBitArray	Dense boolean storage and bitwise set operations	Set, Unset, Get, Toggle, SetAll, Clear, PopCount, And, Or, Xor, Not. O(1) per bit; O(Capacity/64) for bulk operations.	ScyllaBitArrayDOTS
ScyllaDisjointSet	Union-Find / connected-component tracking with path compression and union-by-rank	Find(x), Union(x, y), Connected(x, y), Clear(), ComponentCount. Amortized near-constant-time (O(alpha(n))) on Find and Union.	ScyllaDisjointSetDOTS
ScyllaTrie / ScyllaTrie<TValue>	Prefix-keyed string storage with fast prefix existence tests and lexicographic enumeration	TryAdd, Contains/ContainsKey, ContainsPrefix, TryRemove, CopyTo/CopyKeysTo, CopyMatches. O(k) per operation, where k is the key length.	none

All three implement the same IScyllaCollection base (Count, IsEmpty, Capabilities, ThreadSafety, SyncRoot, Clear()) described on the Collections Overview page, expose a CreateBuilder() fluent builder, and default to ScyllaCollectionThreadSafety.Unsynchronized with an AsSynchronized() escape hatch.

Recipes

Each recipe below is self-contained and covers one of the three structures end to end; the fourth and fifth also demonstrate the DOTS variants and the trie’s fixed-capacity builder path.

Track fog-of-war visibility with a compact bit set

Problem. A strategy or exploration game needs to track, per tile, whether a tile has ever been revealed and whether it is currently visible, across a map that can hold tens of thousands of tiles. A bool[] per state doubles memory for something that is fundamentally one bit of information per tile per state, and a hand-rolled bit-packing scheme means reimplementing Set/Get/PopCount from scratch.

Solution. ScyllaBitArray packs one bit per tile per state into ulong words and exposes the bitwise combinators needed to merge or intersect visibility masks directly, without ever unpacking to booleans.

/* One bit per tile. 4096 tiles cost 512 bytes per mask instead of 4 KB for a bool[]. */
var tileCount = mapWidth * mapHeight;
var everRevealed = new ScyllaBitArray(capacity: tileCount);
var currentlyVisible = new ScyllaBitArray(capacity: tileCount);

/* A unit's sensor sweep marks tiles as visible this frame. */
foreach (var tileIndex in tilesInSensorRange)
{
    currentlyVisible.Set(tileIndex);
}

/* Merge this frame's visibility into the permanent reveal history.
 * everRevealed is a superset of currentlyVisible after this call. */
everRevealed.Or(currentlyVisible);

/* Fog-of-war render pass: fully fogged, dimly remembered, or fully lit. */
for (var i = 0; i < tileCount; i++)
{
    if (currentlyVisible.Get(i))
    {
        RenderTileLit(i);
    }
    else if (everRevealed.Get(i))
    {
        RenderTileRemembered(i);
    }
    else
    {
        RenderTileFogged(i);
    }
}

/* How many tiles has the player explored in total? O(1), not a manual loop. */
var exploredCount = everRevealed.PopCount();

/* Clear this frame's visibility before the next sensor sweep. */
currentlyVisible.Clear();

Detect connected regions after a dungeon generation pass

Problem. After a procedural pass (cellular automata, a BSP (Binary Space Partition) split, or a corridor carver) produces a grid of passable and impassable tiles, the generator needs to know which floor tiles form one connected region before placing the start, the exit, and loot, so nothing ends up sealed inside an unreachable pocket.

Solution. ScyllaDisjointSet is a union-find structure: every tile starts in its own singleton component, and unioning adjacent passable tiles merges them into shared regions. ComponentCount reports how many disconnected regions remain without a separate counting pass.

var tileCount = mapWidth * mapHeight;
var regions = new ScyllaDisjointSet(capacity: tileCount);

/* Union every passable tile with its passable right and bottom neighbor.
 * Checking only right and bottom visits every adjacent pair exactly once. */
for (var row = 0; row < mapHeight; row++)
{
    for (var col = 0; col < mapWidth; col++)
    {
        if (!IsPassable(row, col))
        {
            continue;
        }

        var tile = row * mapWidth + col;

        if (col + 1 < mapWidth && IsPassable(row, col + 1))
        {
            regions.Union(tile, tile + 1);
        }

        if (row + 1 < mapHeight && IsPassable(row + 1, col))
        {
            regions.Union(tile, tile + mapWidth);
        }
    }
}

/* Reject a generation attempt that produced more than one sizeable region. */
if (regions.ComponentCount > 1)
{
    RetryGeneration();
    return;
}

/* Place the exit only if it is reachable from the start tile. */
var startTile = FirstPassableTile();
var exitTile = CandidateExitTile();

if (!regions.Connected(startTile, exitTile))
{
    ChooseAnotherExitCandidate();
}

/* Regenerate: reset every tile back to its own singleton component
 * without reallocating the parent and rank arrays. */
regions.Clear();

Power autocomplete and cheat-code recognition for a debug console

Problem. An in-game console needs to suggest completions as a player types a partial command name, recognize when a typed cheat code matches a known one, and do both without scanning every stored string on every keystroke.

Solution. ScyllaTrie (the set form) stores plain string keys; ScyllaTrie<TValue> (the map form) associates a value, such as a handler index, with each key. Both expose ContainsPrefix, which is what makes a trie faster than a hash map for this job: it walks one edge per character rather than testing every stored key against the prefix.

/* Map form: command name -> handler index, case-insensitive lookup. */
var commands = new ScyllaTrie<int>(nodeCapacity: 128, ignoreCase: true);
commands.TryAdd("spawn", value: 0);
commands.TryAdd("speed", value: 1);
commands.TryAdd("spawnall", value: 2);

/* As the player types "sp", decide whether to open the suggestion popup. */
var hasSuggestions = commands.ContainsPrefix("sp"); /* true */

/* List every completion for the current partial input, alphabetically. */
Span<string> suggestions = stackalloc string[8];
var suggestionCount = commands.CopyMatches("sp", suggestions);

for (var i = 0; i < suggestionCount; i++)
{
    ShowSuggestion(suggestions[i]);
}

/* Resolve a confirmed command to its handler. */
commands.TryGetValue("speed", out var handlerIndex);

/* Set form: no associated value, just recognized cheat codes. */
var cheatCodes = new ScyllaTrie(ignoreCase: false);
cheatCodes.TryAdd("GODMODE");
cheatCodes.TryAdd("NOCLIP");

var isKnownCheat = cheatCodes.Contains(enteredCode);

Run bit sets and union-find inside a Burst-compiled job

Problem. A per-entity dirty-flag pass or a collision-clustering step runs across thousands of entities every frame, and driving it through the managed ScyllaBitArray and ScyllaDisjointSet from a single thread is too slow; the work needs to move into a Burst-compiled job.

Solution. ScyllaBitArrayDOTS and ScyllaDisjointSetDOTS mirror the managed APIs almost method-for-method over NativeArray-backed storage and are decorated with [BurstCompile], so job code reads nearly the same as the managed version. Both are disposable; the caller owns their lifetime.

[BurstCompile]
public struct MarkDirtyAndClusterJob : IJob
{
    public ScyllaBitArrayDOTS DirtyFlags;
    public ScyllaDisjointSetDOTS Clusters;
    [ReadOnly] public NativeArray<int2> CollisionPairs;

    public void Execute()
    {
        /* Flag every entity touched by a collision this frame and union
         * colliding entities into the same cluster. */
        for (var i = 0; i < CollisionPairs.Length; i++)
        {
            DirtyFlags.Set(CollisionPairs[i].x);
            DirtyFlags.Set(CollisionPairs[i].y);
            Clusters.Union(CollisionPairs[i].x, CollisionPairs[i].y);
        }
    }
}

/* Schedule with TempJob allocations; both structs must be disposed
 * once the job completes and the results have been read. */
var job = new MarkDirtyAndClusterJob
{
    DirtyFlags = new ScyllaBitArrayDOTS(entityCount, Allocator.TempJob),
    Clusters = new ScyllaDisjointSetDOTS(entityCount, Allocator.TempJob),
    CollisionPairs = collisionPairsThisFrame
};

var handle = job.Schedule();
handle.Complete();

/* Cluster membership queries are safe on the original struct after Complete()
 * because Find/Connected read the shared NativeArray-backed parent links. */
var sameCluster = job.Clusters.Connected(entityA, entityB);

job.DirtyFlags.Dispose();
job.Clusters.Dispose();

Pre-size a fixed-capacity trie for a bounded command set

Problem. A shipped build’s console command set is fixed and known ahead of time; growing the trie’s internal arrays at runtime is wasted work, and a project that wants a hard guarantee against runtime allocation wants insertion to fail loudly rather than silently reallocate.

Solution. The builder’s WithNodeCapacity combined with FixedCapacity() pre-sizes the node and edge arrays once and makes TryAdd return false instead of growing when the arrays are full. EnsureCapacity can still grow a non-fixed trie ahead of a bulk insert to avoid incremental reallocation.

/* Fixed capacity, pre-sized for exactly the shipped command set.
 * TryAdd returns false rather than reallocating once slots run out. */
var commands = ScyllaTrie.CreateBuilder()
    .WithNodeCapacity(64)
    .FixedCapacity()
    .IgnoreCase()
    .Build();

var added = commands.TryAdd("spawn"); /* true */
/* ... insert the rest of the shipped command set ... */

/* A command that would need more node/edge slots than remain is
 * rejected outright, not silently grown. */
var rejected = !commands.TryAdd("a-command-name-past-remaining-capacity");

/* Non-fixed trie: grow ahead of a bulk import to avoid repeated doubling. */
var importedTrie = ScyllaTrie<int>.CreateBuilder().Build();
importedTrie.EnsureCapacity(minNodeCapacity: 500, minEdgeCapacity: 1000);

API Sketch

The public surface across the three structures and their DOTS variants. See the API reference for full signatures, remarks, and exception contracts on every member.

namespace Scylla.Core.Structures
{
    /* ------------------------------------------------------------------ */
    /* BIT ARRAY                                                          */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaBitArray : IScyllaCollection
    {
        public ScyllaBitArray(int capacity = 64);
        public int  Capacity { get; }
        public int  Count    { get; } /* popcount, maintained incrementally */
        public bool IsEmpty  { get; }
        public void Set      (int index);
        public void Unset    (int index);
        public void Set      (int index, bool value);
        public bool Get      (int index);
        public void Toggle   (int index);
        public void Clear    ();
        public void SetAll   ();
        public int  PopCount ();
        public void And      (ScyllaBitArray other);
        public void Or       (ScyllaBitArray other);
        public void Xor      (ScyllaBitArray other);
        public void Not      ();
        public Enumerator GetEnumerator();
        public static Builder CreateBuilder();
        public SynchronizedScyllaBitArray AsSynchronized(object syncRoot = null);
        public sealed class Builder
        {
            public Builder WithCapacity(int capacity);
            public Builder Synchronized(object syncRoot = null);
            public IScyllaCollection Build();
            public ScyllaBitArray    BuildConcrete();
        }
    }

    [BurstCompile]
    public struct ScyllaBitArrayDOTS : IDisposable
    {
        public ScyllaBitArrayDOTS(int capacity, Allocator allocator);
        public bool IsCreated { get; }
        public int  Capacity  { get; }
        public int  Count     { get; }
        public bool IsEmpty   { get; }
        public void Set(int index); public void Unset(int index); public void Set(int index, bool value);
        public bool Get(int index);  public void Toggle(int index);
        public void Clear();  public void SetAll();  public int PopCount();
        public void And(ScyllaBitArrayDOTS other); public void Or(ScyllaBitArrayDOTS other);
        public void Xor(ScyllaBitArrayDOTS other);  public void Not();
        public Enumerator GetEnumerator();
        public void Dispose();
        public static Builder CreateBuilder();
        public sealed class Builder
        {
            public Builder WithAllocator(Allocator allocator);
            public Builder WithCapacity(int capacity);
            public ScyllaBitArrayDOTS Build();
        }
    }

    /* ------------------------------------------------------------------ */
    /* DISJOINT SET                                                       */
    /* ------------------------------------------------------------------ */

    public sealed class ScyllaDisjointSet : IScyllaCollection
    {
        public ScyllaDisjointSet(int capacity = 16);
        public int  Capacity       { get; } /* always equal to Count */
        public int  Count          { get; }
        public bool IsEmpty        { get; }
        public int  ComponentCount { get; }
        public int  Find      (int x);
        public bool Union     (int x, int y);
        public bool Connected (int x, int y);
        public void Clear     ();
        public static Builder CreateBuilder();
        public SynchronizedScyllaDisjointSet AsSynchronized(object syncRoot = null);
        public sealed class Builder
        {
            public Builder WithCapacity(int capacity);
            public Builder Synchronized(object syncRoot = null);
            public IScyllaCollection    Build();
            public ScyllaDisjointSet    BuildConcrete();
        }
    }

    [BurstCompile]
    public struct ScyllaDisjointSetDOTS : IDisposable
    {
        public ScyllaDisjointSetDOTS(int capacity, Allocator allocator);
        public bool IsCreated       { get; }
        public int  Capacity        { get; }
        public int  Count           { get; }
        public int  ComponentCount  { get; }
        public int  Find      (int x);
        public bool Union     (int x, int y);
        public bool Connected (int x, int y);
        public void Clear     ();
        public void Dispose   ();
        public static Builder CreateBuilder();
        public sealed class Builder
        {
            public Builder WithAllocator(Allocator allocator);
            public Builder WithCapacity(int capacity);
            public ScyllaDisjointSetDOTS Build();
        }
    }

    /* ------------------------------------------------------------------ */
    /* TRIE                                                               */
    /* ------------------------------------------------------------------ */

    public interface IScyllaTrie : IScyllaCollection
    {
        bool Contains      (string key);
        bool ContainsPrefix(string prefix);
        bool TryAdd        (string key);
        bool TryRemove     (string key);
        int  CopyTo        (Span<string> destination);
        int  CopyTo        (string[] destination, int destinationIndex);
        int  CopyMatches   (string prefix, Span<string> destination);
        int  CopyMatches   (string prefix, string[] destination, int destinationIndex);
    }

    public sealed class ScyllaTrie : IScyllaTrie
    {
        public ScyllaTrie(int nodeCapacity = 16, bool fixedCapacity = false, bool ignoreCase = false);
        public bool IsFixedCapacity { get; }
        public bool IgnoreCase     { get; }
        public int  NodeCapacity   { get; }
        public int  EdgeCapacity   { get; }
        public void EnsureCapacity(int minNodeCapacity, int minEdgeCapacity);
        public static Builder CreateBuilder();
        public SynchronizedScyllaTrie AsSynchronized(object syncRoot = null);
        public sealed class Builder
        {
            public Builder WithNodeCapacity(int nodeCapacity);
            public Builder FixedCapacity(bool value = true);
            public Builder IgnoreCase(bool value = true);
            public Builder Synchronized(object syncRoot = null);
            public IScyllaTrie Build();
            public ScyllaTrie  BuildConcrete();
        }
    }

    public interface IScyllaTrie<TValue> : IScyllaCollection
    {
        bool ContainsKey   (string key);
        bool ContainsPrefix(string prefix);
        bool TryGetValue   (string key, out TValue value);
        bool TryAdd        (string key, TValue value);
        bool TrySet        (string key, TValue value);
        bool TryRemove     (string key);
        int  CopyKeysTo         (Span<string> destination);
        int  CopyKeysTo         (string[] destination, int destinationIndex);
        int  CopyKeyValuePairsTo(Span<KeyValuePair<string, TValue>> destination);
        int  CopyMatches   (string prefix, Span<string> destinationKeys);
        int  CopyMatches   (string prefix, Span<KeyValuePair<string, TValue>> destinationPairs);
    }

    public sealed class ScyllaTrie<TValue> : IScyllaTrie<TValue>
    {
        public ScyllaTrie(int nodeCapacity = 16, bool fixedCapacity = false, bool ignoreCase = false);
        public bool IsFixedCapacity { get; }
        public bool IgnoreCase     { get; }
        public int  NodeCapacity   { get; }
        public int  EdgeCapacity   { get; }
        public void EnsureCapacity(int minNodeCapacity, int minEdgeCapacity);
        public static Builder CreateBuilder();
        public SynchronizedScyllaTrie AsSynchronized(object syncRoot = null);
        public sealed class Builder
        {
            public Builder WithNodeCapacity(int nodeCapacity);
            public Builder FixedCapacity(bool value = true);
            public Builder IgnoreCase(bool value = true);
            public Builder Synchronized(object syncRoot = null);
            public IScyllaTrie<TValue> Build();
            public ScyllaTrie<TValue>  BuildConcrete();
        }
    }
}

See the API reference for full signatures, remarks, and exception contracts on every member.

Operations reference

ScyllaBitArray

Method	Effect
Set(index) / Unset(index)	Sets or clears a single bit; a no-op (with no double counting) when the bit already has that value.
Set(index, value)	Delegates to Set or Unset based on value.
Get(index)	Returns whether the bit is currently set.
Toggle(index)	Flips a single bit and adjusts Count accordingly.
SetAll() / Clear()	Sets or clears every bit; Count becomes Capacity or 0.
PopCount() / Count	O(1) population count, maintained incrementally.
And / Or / Xor (other)	In-place bitwise combine over the overlapping word range with other.
Not()	In-place bitwise complement of every bit.

Builder setting	Default	Effect
WithCapacity(n)	64	Requested bit count, rounded up to the next multiple of 64.
Synchronized(syncRoot)	off	Wraps the result in SynchronizedScyllaBitArray.

ScyllaDisjointSet

Method	Effect
Find(x)	Returns the root of x‘s component, applying path compression.
Union(x, y)	Merges the components containing x and y; returns false if already connected.
Connected(x, y)	Whether x and y share a root.
Clear()	Resets every element to its own singleton component without reallocating.
ComponentCount	Current number of disjoint groups.

Builder setting	Default	Effect
WithCapacity(n)	16	Number of elements, addressable as 0..n-1.
Synchronized(syncRoot)	off	Wraps the result in SynchronizedScyllaDisjointSet.

ScyllaTrie and ScyllaTrie<TValue>

Method	Effect
TryAdd(key) / TryAdd(key, value)	Inserts a new key (set form) or key/value pair (map form); false if the key exists or a fixed-capacity trie is full.
Contains(key) / ContainsKey(key)	Exact-match test.
ContainsPrefix(prefix)	Whether any stored key starts with prefix.
TryGetValue(key, out value)	Map form only; retrieves the associated value.
TrySet(key, value)	Map form only; updates an existing value without inserting.
TryRemove(key)	Removes a key, pruning dead nodes and edges back into the free lists.
CopyTo / CopyKeysTo	Copies all keys in lexicographic order.
CopyKeyValuePairsTo	Map form only; copies all pairs in key order.
CopyMatches(prefix, ...)	Copies only the keys or pairs that start with prefix.
EnsureCapacity(minNode, minEdge)	Grows ahead of a bulk insert; throws on a fixed-capacity trie.

Builder setting	Default	Effect
WithNodeCapacity(n)	16	Initial node-array size; the edge array is max(32, n * 2).
FixedCapacity(value)	false	Never grow; TryAdd returns false once full.
IgnoreCase(value)	false	Case-insensitive traversal via char.ToUpperInvariant; original casing is preserved in stored keys.
Synchronized(syncRoot)	off	Wraps the result in a SynchronizedScyllaTrie (or its generic counterpart).

Best Practices

• Use ScyllaBitArray for any large boolean array. 64 bits per ulong versus one byte per bool is an 8x memory reduction plus better cache locality, and Count stays O(1) instead of a manual popcount loop. See Collections Overview for the shared collection contract every structure on this page implements.
• Reach for ScyllaDisjointSet whenever the question is “are these in the same group.” Procedural region detection, faction merges, and Kruskal-style minimum spanning tree construction all reduce to union-find. The Graph module’s ConnectedComponents algorithm returns a ScyllaDisjointSet directly, so a hand-rolled union-find pass over graph nodes is rarely necessary.
• Reach for a trie whenever ContainsPrefix is the actual question. A hash map cannot answer “what starts with this text” without scanning every key; a trie answers it in one traversal.
• Pick the set trie or the map trie by whether a lookup needs an associated value. ScyllaTrie for a plain set of recognized strings (cheat codes, tags); ScyllaTrie<TValue> when each key needs a handler, index, or metadata object attached.
• Pre-size every structure when the final size is known. WithCapacity on the bit array and the disjoint set, WithNodeCapacity on the trie builder, all avoid the cost of growing incrementally.
• Combine FixedCapacity() with pre-sizing on the trie for a hard allocation ceiling. TryAdd returns false instead of growing once the arrays are full, the same no-throw contract the rest of the Scylla collection types use.
• Reuse Clear() across generation attempts instead of reallocating. Both ScyllaBitArray (Clear()/SetAll()) and ScyllaDisjointSet (Clear()) reset state without touching the backing arrays, which matters when a procedural generator retries dozens of times per level.
• Use the DOTS variants only inside Burst-compiled jobs. ScyllaBitArrayDOTS and ScyllaDisjointSetDOTS carry disposable native buffers; using them on the main thread outside a job pays that overhead for no Burst benefit.
• Dispose every DOTS instance exactly once. Match the Unity allocator lifetime (Temp, TempJob, Persistent) to how long the job’s results are needed, and dispose after the last read rather than before.
• Check IgnoreCase and casing expectations before wiring up a trie. Keys are stored with their original casing regardless of the setting; only the traversal comparison is affected, so CopyMatches returns the strings exactly as they were inserted.
• Reach for the synchronized wrapper only when a structure is genuinely shared across threads. All three unsynchronized cores report ThreadSafety.Unsynchronized; AsSynchronized() or the builder’s .Synchronized() step wraps any of them in a lock-protected shell with the same API surface.
• Map non-integer domain objects to dense indices before using the disjoint set. ScyllaDisjointSet and its DOTS twin only understand indices in [0, Capacity); keep a side ScyllaMap<TObject, int> (see Collections Overview) when the objects are not already densely indexed.

Pitfalls

Related

• Collections Overview
• Queues, Stacks, and Buffers
• Maps and Dictionaries
• Graph
• API reference: Scylla.Core.Structures.ScyllaBitArray
• API reference: Scylla.Core.Structures.ScyllaBitArrayDOTS
• API reference: Scylla.Core.Structures.ScyllaDisjointSet
• API reference: Scylla.Core.Structures.ScyllaDisjointSetDOTS
• API reference: Scylla.Core.Structures.ScyllaTrie
• API reference: Scylla.Core.Structures.ScyllaTrie`1
• API reference: Scylla.Core.Structures.IScyllaTrie
• API reference: Scylla.Core.Structures.IScyllaTrie`1