Class ScyllaTrie

Concrete trie (prefix tree) that stores a set of strings with O(k) insert, lookup, and removal (where k is the key length), efficient prefix existence tests, and lexicographically ordered enumeration via CopyTo(Span<string>) and CopyMatches(string, Span<string>). This is the set variant; for key/value mapping use ScyllaTrie<TValue>. Unsynchronized by default; use AsSynchronized(object) to obtain a thread-safe wrapper.

Inheritance
object
ScyllaTrie
Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
public sealed class ScyllaTrie : IScyllaTrie, IScyllaCollection
Remarks

Internal storage model: the trie maintains two flat arrays - a Node array and an Edge array - that are indexed by integer handles rather than heap-allocated objects. Each node holds the index of its first outgoing edge (FirstEdge), a terminal flag, and the original key string when terminal. Each edge stores a transition character, the child-node index, and the index of the next edge in the same node's sorted linked list. Because edges within a node are kept in ascending character order, depth-first traversal naturally produces lexicographic output.

Free lists: removed nodes and edges are reclaimed into singly-linked free lists (using NextFree / NextEdge slots as list pointers). Subsequent insertions preferentially consume free-list slots before expanding the arrays, keeping memory usage bounded after repeated add/remove cycles.

Capacity growth: unless IsFixedCapacity is true, both arrays double in size when exhausted. The initial edge-array size is max(32, nodeCapacity * 2) because a typical trie has roughly twice as many edges as nodes. In fixed-capacity mode, TryAdd(string) returns false instead of growing, making it suitable for stack-allocated or pre-sized scenarios.

Case-insensitive mode: when IgnoreCase is true, every character is normalised to upper-case (invariant culture) before traversal. Keys are stored with their original casing so that CopyMatches(string, Span<string>) returns the original strings.

Thread safety: this class is not thread-safe. Call AsSynchronized(object) to obtain a ScyllaTrie.SynchronizedScyllaTrie wrapper that locks all operations on a shared monitor. Alternatively, use Synchronized(object) on the fluent ScyllaTrie.Builder to construct a synchronized instance in one call. 

// Direct construction
var trie = new ScyllaTrie(nodeCapacity: 64, fixedCapacity: true, ignoreCase: true);
// Using fluent builder for complex configuration
var trie = ScyllaTrie.CreateBuilder()
    .WithNodeCapacity(128)
    .IgnoreCase()
    .FixedCapacity()
    .Synchronized()
    .Build();

Constructors

ScyllaTrie(int, bool, bool)

Initializes a new ScyllaTrie with the specified initial capacity, growth policy, and case-sensitivity with the specified initial capacity, growth policy, and case-sensitivity settings.

Declaration
public ScyllaTrie(int nodeCapacity = 16, bool fixedCapacity = false, bool ignoreCase = false)
Parameters
Type Name Description
int nodeCapacity

The initial number of node slots to allocate. Values less than 1 are clamped to 1. The internal edge array is initialised to max(32, nodeCapacity * 2) slots because a typical trie has approximately twice as many edges as nodes. Use a larger value to reduce early re-allocations when the expected key count is known. Defaults to 16.
bool fixedCapacity

When true, the trie will never grow its internal arrays beyond the initial allocation. TryAdd(string) returns false instead of resizing when the arrays are full. Combine with a pre-sized nodeCapacity to bound memory usage. Defaults to false (automatic doubling growth).
bool ignoreCase

When true, every character is converted to upper-case using ToUpperInvariant(char) before traversal, making all lookups and prefix searches case-insensitive. Original casing is preserved in the stored key strings returned by CopyMatches(string, Span<string>). Defaults to false (case-sensitive).

Properties

Capabilities

Gets the capability flags that describe which optional operations this trie instance supports.

Declaration
public ScyllaCollectionCapabilities Capabilities { get; }
Property Value
Type Description
ScyllaCollectionCapabilities

Always includes HasCapacity, SupportsContains, and SupportsCopyTo.

Count

Gets the number of keys currently stored in the trie.

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

A non-negative integer representing the current key count. Incremented by successful TryAdd(string) calls and decremented by successful TryRemove(string) calls.

EdgeCapacity

Gets the current total number of edge slots allocated in the internal edge array, including both active edges and free-list slots.

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

The length of the internal edge array. In dynamic mode this doubles whenever the array is exhausted. In fixed-capacity mode it never changes after construction.

IgnoreCase

Gets a value indicating whether this trie performs case-insensitive character matching using invariant-culture upper-case normalisation.

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

true if every character is converted via ToUpperInvariant(char) before traversal; false for exact (case-sensitive) character matching. Keys are always stored with their original casing regardless of this setting.

IsEmpty

Gets a value indicating whether the trie contains no keys.

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

true when Count is 0; false otherwise. Equivalent to Count == 0 but may be used as a more readable shorthand.

IsFixedCapacity

Gets a value indicating whether this trie is operating in fixed-capacity mode, where the internal node and edge arrays will never grow beyond their initial allocation.

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

true if the trie was constructed with fixedCapacity: true or FixedCapacity(bool) was called; false if the arrays may double in size automatically when exhausted.

NodeCapacity

Gets the current total number of node slots allocated in the internal node array, including both active nodes and free-list slots.

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

The length of the internal node array. In dynamic mode this doubles whenever the array is exhausted. In fixed-capacity mode it never changes after construction.

SyncRoot

Gets the synchronization root for this trie.

Declaration
public object SyncRoot { get; }
Property Value
Type Description
object

Always null for the unsynchronized ScyllaTrie. A non-null value is only returned by the ScyllaTrie.SynchronizedScyllaTrie wrapper.

ThreadSafety

Gets the thread-safety guarantee for this trie instance.

Declaration
public ScyllaCollectionThreadSafety ThreadSafety { get; }
Property Value
Type Description
ScyllaCollectionThreadSafety

Always Unsynchronized for this class. Use AsSynchronized(object) to obtain a wrapper that reports Synchronized.

Methods

AsSynchronized(object)

Creates and returns a thread-safe ScyllaTrie.SynchronizedScyllaTrie wrapper around this trie. All operations on the returned wrapper are protected by a monitor lock.

Declaration
public ScyllaTrie.SynchronizedScyllaTrie AsSynchronized(object syncRoot = null)
Parameters
Type Name Description
object syncRoot

An optional external lock object to use for synchronization. When null, the wrapper allocates a private object as its lock. Supply a custom sync root to coordinate locking with other synchronized resources.
Returns
Type Description
ScyllaTrie.SynchronizedScyllaTrie

A new ScyllaTrie.SynchronizedScyllaTrie that wraps this instance and reports Synchronized.

Clear()

Removes all keys from the trie, resetting it to an empty state without releasing the internal node and edge arrays. All terminal key string references are cleared to allow garbage collection. After this call, Count is 0 and only the root node at index 0 is considered live.

Declaration
public void Clear()
Remarks

This method is a no-op if the trie is already empty and only the root node exists. Array sizes (NodeCapacity / EdgeCapacity) are unchanged.

Contains(string)

Determines whether the trie contains the specified key as an exact, complete match.

Declaration
public bool Contains(string key)
Parameters
Type Name Description
string key

The key to search for. Must not be null. An empty string is a valid key and returns true only if an empty string was previously inserted.
Returns
Type Description
bool

true if a terminal node is reached by traversing every character of key; false if the path does not exist or the node at the end of that path has not been marked as a complete stored key.
Exceptions
Type Condition
ArgumentNullException

Thrown when key is null.

ContainsPrefix(string)

Determines whether the trie contains at least one key whose characters begin with prefix.

Declaration
public bool ContainsPrefix(string prefix)
Parameters
Type Name Description
string prefix

The prefix to test. Must not be null. An empty string returns true whenever the trie holds any key, because every key trivially starts with the empty string.
Returns
Type Description
bool

true if the node reached by traversing prefix exists and is either itself a terminal (i.e. prefix is exactly a stored key) or has at least one outgoing edge (i.e. a longer key shares this prefix); false otherwise.
Exceptions
Type Condition
ArgumentNullException

Thrown when prefix is null.

CopyMatches(string, Span<string>)

Copies all keys that start with prefix in ascending lexicographic order into destination, stopping when the span is full or all matching keys have been written. This is the primary method for implementing autocomplete / tab-completion.

Declaration
public int CopyMatches(string prefix, Span<string> destination)
Parameters
Type Name Description
string prefix

The prefix to filter by. Must not be null. An empty string matches all stored keys and is equivalent to calling CopyTo(Span<string>).
Span<string> destination

The target span to write matching keys into. If shorter than the number of matching keys, only the first destination.Length matches (in lexicographic order) are written.
Returns
Type Description
int

The number of keys written. Returns 0 if no key matches the prefix, the trie is empty, or the span has length zero.
Exceptions
Type Condition
ArgumentNullException

Thrown when prefix is null.

CopyMatches(string, string[], int)

Copies all keys that start with prefix in ascending lexicographic order into the provided array starting at destinationIndex, stopping when the remaining array space is exhausted or all matching keys have been written.

Declaration
public int CopyMatches(string prefix, string[] destination, int destinationIndex)
Parameters
Type Name Description
string prefix

The prefix to filter by. Must not be null. An empty string matches all stored keys and is equivalent to calling CopyTo(string[], int).
string[] destination

The target array to write matching keys into. Must not be null.
int destinationIndex

The zero-based index in destination at which writing begins. Must be in the range [0, destination.Length].
Returns
Type Description
int

The number of keys written. Returns 0 if no key matches the prefix, the trie is empty, or no space is available starting at destinationIndex.
Exceptions
Type Condition
ArgumentNullException

Thrown when destination or prefix is null.
ArgumentOutOfRangeException

Thrown when destinationIndex is negative or greater than the array length.

CopyTo(Span<string>)

Copies all stored keys in ascending lexicographic order into destination, stopping when the span is full. This is a convenience wrapper that calls CopyMatches(string, Span<string>) with an empty prefix.

Declaration
public int CopyTo(Span<string> destination)
Parameters
Type Name Description
Span<string> destination

The target span to write keys into. If shorter than Count, only the first destination.Length keys are written.
Returns
Type Description
int

The number of keys written. Returns 0 if the trie is empty or the span has length zero.

CopyTo(string[], int)

Copies all stored keys in ascending lexicographic order into the provided array starting at destinationIndex, stopping when the remaining array space is exhausted or all keys have been written.

Declaration
public int CopyTo(string[] destination, int destinationIndex)
Parameters
Type Name Description
string[] destination

The target array to write keys into. Must not be null.
int destinationIndex

The zero-based index in destination at which writing begins. Must be in the range [0, destination.Length].
Returns
Type Description
int

The number of keys written. Returns 0 if the trie is empty or no space is available starting at destinationIndex.
Exceptions
Type Condition
ArgumentNullException

Thrown when destination is null.
ArgumentOutOfRangeException

Thrown when destinationIndex is negative or greater than the array length.

CreateBuilder()

Creates a new fluent builder for configuring and constructing a ScyllaTrie instance. The builder provides a discoverable API for setting node capacity, fixed-capacity mode, case sensitivity, and synchronized wrappers.

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

A new builder instance for configuring ScyllaTrie construction
Remarks
var trie = ScyllaTrie.CreateBuilder()
.WithNodeCapacity(64)
.IgnoreCase()
.FixedCapacity()
.Build();

EnsureCapacity(int, int)

Ensures the internal node and edge arrays can each accommodate at least the specified number of slots without a future resize, growing them immediately if necessary.

Declaration
public void EnsureCapacity(int minNodeCapacity, int minEdgeCapacity)
Parameters
Type Name Description
int minNodeCapacity

The minimum required node-array length. If the current NodeCapacity already meets or exceeds this value, no node-array growth occurs.
int minEdgeCapacity

The minimum required edge-array length. If the current EdgeCapacity already meets or exceeds this value, no edge-array growth occurs.
Exceptions
Type Condition
InvalidOperationException

Thrown when IsFixedCapacity is true and at least one of the requested capacities exceeds the current array size, because fixed-capacity tries may not grow.

TryAdd(string)

Attempts to insert the specified key into the trie, traversing or creating one node per character and marking the final node as a terminal that stores the original key string.

Declaration
public bool TryAdd(string key)
Parameters
Type Name Description
string key

The key to add. Must not be null. An empty string is a valid key; it marks the root node as terminal. If IgnoreCase is active, the characters used for traversal are normalised to upper-case, but the original-casing string is stored on the terminal node and returned by CopyMatches(string, Span<string>).
Returns
Type Description
bool

true if the key was successfully inserted. false in any of these cases:

  • The key already exists in the trie.
  • IsFixedCapacity is true and there are insufficient free node or edge slots to complete the insertion.
Exceptions
Type Condition
ArgumentNullException

Thrown when key is null.

TryRemove(string)

Attempts to remove the specified key from the trie and prune any internal nodes and edges that are no longer reachable by any stored key.

Declaration
public bool TryRemove(string key)
Parameters
Type Name Description
string key

The key to remove. Must not be null. An empty string is a valid key and clears the terminal flag on the root node when present.
Returns
Type Description
bool

true if the key existed and was removed. false if the key does not exist in the trie.
Remarks

After clearing the terminal flag, the method walks back up the ancestor chain and prunes each node that is no longer terminal and has no remaining outgoing edges, unlinking the associated edge from its parent and returning both the node and edge slots to their respective free lists. Keys that share a common prefix with the removed key are not affected. For keys longer than 256 characters, path-tracking arrays are heap-allocated; for shorter keys they are stack-allocated.

Exceptions
Type Condition
ArgumentNullException

Thrown when key is null.

Implements

Extension Methods

See Also

ScyllaTrie<TValue>