Trie Class

Definition

Namespace

Bodu.Collections.Generic.Trees

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

Trie.Enumerator.cs

Represents a prefix tree (trie) of string keys and supports efficient prefix queries.

public sealed class Trie : IReadOnlyCollection<string>, IEnumerable<string>, IEnumerable

Inheritance

object

Trie

Implements

IReadOnlyCollection<string>

IEnumerable<string>

IEnumerable

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

ComparableExtensions.AtLeast<T>(T, T, IComparer<T>)

ComparableExtensions.AtMost<T>(T, T, IComparer<T>)

ComparableExtensions.IsEqualTo<T>(T, T, IComparer<T>)

ComparableExtensions.Max<T>(T, T, IComparer<T>)

ComparableExtensions.Min<T>(T, T, IComparer<T>)

Remarks

A Trie stores keys as paths of characters, so membership and prefix operations cost time proportional to the length of the key rather than to the number of stored keys. Character transitions are keyed by the IEqualityComparer<T> supplied at construction, allowing ordinal or case-insensitive matching. The empty string is a valid key.

Enumeration order - through GetEnumerator() or KeysWithPrefix(string) - is unspecified in this version. The trie is not thread-safe for concurrent mutation. For an associative variant that maps keys to values, see Trie<TValue>.

Constructors

Trie()

Initializes a new instance of the Trie class that is empty and uses ordinal character comparison.

public Trie()

Trie(IEnumerable<string>, IEqualityComparer<char>?)

Initializes a new instance of the Trie class containing the specified keys.

public Trie(IEnumerable<string> keys, IEqualityComparer<char>? charComparer = null)

Parameters

keys IEnumerable<string>

The keys to add.

charComparer IEqualityComparer<char>

The comparer used to match characters, or null to use Default.

Exceptions

ArgumentNullException

keys is null, or a key is null.

ArgumentException

A duplicate key is supplied.

Trie(IEqualityComparer<char>?)

Initializes a new instance of the Trie class that is empty and uses the specified character comparer.

public Trie(IEqualityComparer<char>? charComparer)

Parameters

charComparer IEqualityComparer<char>

The comparer used to match characters, or null to use Default.

Properties

Comparer

Gets the comparer used to match characters during key lookup.

public IEqualityComparer<char> Comparer { get; }

Property Value

IEqualityComparer<char>

The character comparer supplied at construction, or the default comparer.

Count

Gets the number of keys stored in the trie.

public int Count { get; }

Property Value

int

The number of stored keys.

Methods

Add(ReadOnlySpan<char>)

Adds the specified key to the trie.

public bool Add(ReadOnlySpan<char> key)

Parameters

key ReadOnlySpan<char>

The key to add.

Returns

bool

true if the key was added; false if it already existed.

Add(string)

Adds the specified key to the trie.

public bool Add(string key)

Parameters

key string

The key to add.

Returns

bool

true if the key was added; false if it already existed.

Exceptions

ArgumentNullException

key is null.

Clear()

Removes all keys from the trie.

public void Clear()

Contains(ReadOnlySpan<char>)

Determines whether the trie contains the specified key.

public bool Contains(ReadOnlySpan<char> key)

Parameters

key ReadOnlySpan<char>

The key to locate.

Returns

bool

true if the key exists; otherwise, false.

Contains(string)

Determines whether the trie contains the specified key.

public bool Contains(string key)

Parameters

key string

The key to locate.

Returns

bool

true if the key exists; otherwise, false.

Exceptions

ArgumentNullException

key is null.

GetEnumerator()

Returns an enumerator that iterates over the keys of the trie.

public Trie.Enumerator GetEnumerator()

Returns

Trie.Enumerator

A struct enumerator that lazily walks the trie's keys and fails fast on modification.

KeysWithPrefix(string)

Returns the keys in the trie that begin with the specified prefix.

public IEnumerable<string> KeysWithPrefix(string prefix)

Parameters

prefix string

The prefix to match.

Returns

IEnumerable<string>

A lazily evaluated sequence of matching keys, in unspecified order.

Remarks

The sequence is fail-fast: it is invalidated by any structural modification of the trie, and continuing to iterate after a modification throws InvalidOperationException.

Exceptions

ArgumentNullException

prefix is null.

InvalidOperationException

The trie was modified after enumeration began.

Remove(ReadOnlySpan<char>)

Removes the specified key from the trie.

public bool Remove(ReadOnlySpan<char> key)

Parameters

key ReadOnlySpan<char>

The key to remove.

Returns

bool

true if the key was found and removed; otherwise, false.

Remove(string)

Removes the specified key from the trie.

public bool Remove(string key)

Parameters

key string

The key to remove.

Returns

bool

true if the key was found and removed; otherwise, false.

Exceptions

ArgumentNullException

key is null.

StartsWith(ReadOnlySpan<char>)

Determines whether any key in the trie begins with the specified prefix.

public bool StartsWith(ReadOnlySpan<char> prefix)

Parameters

prefix ReadOnlySpan<char>

The prefix to test.

Returns

bool

true if at least one key begins with prefix; otherwise, false.

StartsWith(string)

Determines whether any key in the trie begins with the specified prefix.

public bool StartsWith(string prefix)

Parameters

prefix string

The prefix to test.

Returns

bool

true if at least one key begins with prefix; otherwise, false.

Exceptions

ArgumentNullException

prefix is null.

Explicit Interface Implementations

IEnumerable<string>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<string> IEnumerable<string>.GetEnumerator()

Returns

IEnumerator<string>

An enumerator that can be used to iterate through the collection.

IEnumerable.GetEnumerator()

Returns an enumerator that iterates through a collection.

IEnumerator IEnumerable.GetEnumerator()

Returns

IEnumerator

An IEnumerator object that can be used to iterate through the collection.

Applies to

Product	Versions
.NET	8, 10