Table of Contents

Trie<TValue> Class

Definition

Namespace
Bodu.Collections.Generic.Trees
Assembly
Bodu.Collections.dll
Package
Bodu.Collections 1.0.0
Source
Trie{TValue}.Enumerator.cs

Represents a prefix tree (trie) that maps string keys to values and supports efficient prefix queries.

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

Type Parameters

TValue

The type of the values associated with each key.

Inheritance
Trie<TValue>
Implements
Inherited Members
Extension Methods

Remarks

A Trie<TValue> stores keys as paths of characters, so operations cost time proportional to the length of the key rather than to the number of stored keys, and it answers prefix questions (StartsWith(string), KeysWithPrefix(string)) without scanning unrelated 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 - whether through GetEnumerator(), KeysWithPrefix(string), or ItemsWithPrefix(string) - is unspecified in this version. The trie is not thread-safe for concurrent mutation.

Constructors

Trie()

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

public Trie()

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

Initializes a new instance of the Trie<TValue> class containing the specified key/value pairs.

public Trie(IEnumerable<KeyValuePair<string, TValue>> items, IEqualityComparer<char>? charComparer = null)

Parameters

items IEnumerable<KeyValuePair<string, TValue>>

The key/value pairs to add.

charComparer IEqualityComparer<char>

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

Exceptions

ArgumentNullException

items is null, or a key is null.

ArgumentException

A duplicate key is supplied.

Trie(IEqualityComparer<char>?)

Initializes a new instance of the Trie<TValue> 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.

this[string]

Gets or sets the value associated with the specified key.

public TValue this[string key] { get; set; }

Parameters

key string

The key whose value is retrieved or assigned.

Property Value

TValue

The value associated with key.

Exceptions

ArgumentNullException

key is null.

KeyNotFoundException

The key does not exist when read.

Methods

Add(ReadOnlySpan<char>, TValue)

Adds the specified key and value to the trie.

public void Add(ReadOnlySpan<char> key, TValue value)

Parameters

key ReadOnlySpan<char>

The key to add.

value TValue

The value to associate with the key.

Exceptions

ArgumentException

The key already exists.

Add(string, TValue)

Adds the specified key and value to the trie.

public void Add(string key, TValue value)

Parameters

key string

The key to add.

value TValue

The value to associate with the key.

Exceptions

ArgumentNullException

key is null.

ArgumentException

The key already exists.

Clear()

Removes all keys from the trie.

public void Clear()

ContainsKey(ReadOnlySpan<char>)

Determines whether the trie contains the specified key.

public bool ContainsKey(ReadOnlySpan<char> key)

Parameters

key ReadOnlySpan<char>

The key to locate.

Returns

bool

true if the key exists; otherwise, false.

ContainsKey(string)

Determines whether the trie contains the specified key.

public bool ContainsKey(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 key/value pairs of the trie.

public Trie<TValue>.Enumerator GetEnumerator()

Returns

Trie<TValue>.Enumerator

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

ItemsWithPrefix(string)

Returns the key/value pairs in the trie whose keys begin with the specified prefix.

public IEnumerable<KeyValuePair<string, TValue>> ItemsWithPrefix(string prefix)

Parameters

prefix string

The prefix to match.

Returns

IEnumerable<KeyValuePair<string, TValue>>

A lazily evaluated sequence of matching key/value pairs, 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.

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.

Set(string, TValue)

Adds or updates the value associated with the specified key.

public void Set(string key, TValue value)

Parameters

key string

The key to add or update.

value TValue

The value to associate with the key.

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.

TryAdd(string, TValue)

Attempts to add the specified key and value to the trie.

public bool TryAdd(string key, TValue value)

Parameters

key string

The key to add.

value TValue

The value to associate with the key.

Returns

bool

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

Exceptions

ArgumentNullException

key is null.

TryGetValue(ReadOnlySpan<char>, out TValue)

Attempts to get the value associated with the specified key.

public bool TryGetValue(ReadOnlySpan<char> key, out TValue value)

Parameters

key ReadOnlySpan<char>

The key to locate.

value TValue

When this method returns, contains the value if found; otherwise, the default value.

Returns

bool

true if the key was found; otherwise, false.

TryGetValue(string, out TValue)

Attempts to get the value associated with the specified key.

public bool TryGetValue(string key, out TValue value)

Parameters

key string

The key to locate.

value TValue

When this method returns, contains the value if found; otherwise, the default value.

Returns

bool

true if the key was found; otherwise, false.

Exceptions

ArgumentNullException

key is null.

Explicit Interface Implementations

IEnumerable<KeyValuePair<string, TValue>>.GetEnumerator()

Returns an enumerator that iterates through the collection.

IEnumerator<KeyValuePair<string, TValue>> IEnumerable<KeyValuePair<string, TValue>>.GetEnumerator()

Returns

IEnumerator<KeyValuePair<string, TValue>>

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

ProductVersions
.NET8, 10