Interface IScyllaTrie

Contract for a trie (prefix tree) that stores a set of strings with efficient prefix lookup and lexicographic enumeration. This is the set variant: keys have no associated value. For the key-value map variant see IScyllaTrie<TValue>.

Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
public interface IScyllaTrie : IScyllaCollection
Remarks

Primary use cases: in-game console command registration, tab-completion / autocomplete, prefix existence checks, and ordered enumeration of command names.

Prefix semantics: an empty string is a valid prefix and matches all stored keys. Passing an empty string to ContainsPrefix(string) returns true whenever any key is present. Passing an empty string to CopyMatches(string, Span<string>) copies every key in the trie, equivalent to CopyTo(Span<string>).

Empty-key storage: an empty string is a valid key and may be stored independently of prefix behaviour. After a successful TryAdd(""), the root node becomes terminal.

Case sensitivity: implementations may optionally normalise characters to upper-case (invariant culture) during traversal. When case-insensitive mode is active, keys are stored with their original casing but matched without it. Check the concrete implementation's IgnoreCase property for the active setting.

Lexicographic order: all CopyTo and CopyMatches methods emit keys in ascending lexicographic order determined by the normalised character values stored in the trie's sorted edge lists.

Thread safety: core implementations are unsynchronized. Use AsSynchronized() on the concrete type to obtain a lock-protected wrapper, then check ThreadSafety and SyncRoot as needed.

Methods

Contains(string)

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

Declaration
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 added with TryAdd(string).
Returns
Type Description
bool

true if the trie contains a terminal node reached by traversing every character of key; false otherwise.
Exceptions
Type Condition
ArgumentNullException

Thrown when key is null.

ContainsPrefix(string)

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

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

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

true if any stored key starts with prefix; false when no such key exists or the trie is empty.
Exceptions
Type Condition
ArgumentNullException

Thrown when prefix is null.

CopyMatches(string, Span<string>)

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

Declaration
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 are written.
Returns
Type Description
int

The number of keys written into destination. 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 into destination (starting at destinationIndex) all keys that start with prefix, in ascending lexicographic order, stopping when the remaining array space is exhausted or all matching keys have been written.

Declaration
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 into destination. 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 prefix or destination is null.
ArgumentOutOfRangeException

Thrown when destinationIndex is negative or greater than destination.Length.

CopyTo(Span<string>)

Copies all stored keys in ascending lexicographic order into the provided destination span, stopping when the span is full or all keys have been written.

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

The target span to write keys into. If the span length is smaller than Count, only the first destination.Length keys (in lexicographic order) are written.
Returns
Type Description
int

The number of keys written into destination. 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 destination array starting at destinationIndex, stopping when the remaining array space is exhausted or all keys have been written.

Declaration
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 into destination. 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 destination.Length.

TryAdd(string)

Attempts to insert the specified key into the trie.

Declaration
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 makes the trie root terminal. If the trie is case-insensitive, the key is stored with its original casing but matched in a case-insensitive manner.
Returns
Type Description
bool

true if the key was successfully inserted. false if the key already exists in the trie, or if the trie is operating in fixed-capacity mode and inserting the key would require more nodes or edges than are currently available.
Exceptions
Type Condition
ArgumentNullException

Thrown when key is null.

TryRemove(string)

Attempts to remove the specified key from the trie. After a successful removal, any internal nodes or edges that are no longer reachable by any stored key are pruned and their slots returned to the free list for reuse.

Declaration
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 was found and removed; false if the key does not exist in the trie.
Exceptions
Type Condition
ArgumentNullException

Thrown when key is null.

Extension Methods

See Also

IScyllaTrie<TValue>