RadixTrie<TValue> Class

Definition

Namespace

Bodu.Collections.Generic.Trees

Assembly

Bodu.Collections.dll

Package

Bodu.Collections 1.0.0

Source

RadixTrie{T}.Enumerator.cs

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

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

Type Parameters

TValue

The type of the values associated with each key.

Inheritance

object

RadixTrie<TValue>

Implements

IReadOnlyCollection<KeyValuePair<string, TValue>>

IEnumerable<KeyValuePair<string, TValue>>

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 RadixTrie<TValue> stores keys as paths of multi-character edge labels: runs of characters with no branching share a single node, so node count is proportional to the number of stored keys rather than to their total length. Insertion splits an edge at the point of divergence and removal re-fuses any single-child pass-through node it leaves behind. Character transitions and label matching are keyed by the IEqualityComparer<T> supplied at construction, allowing ordinal or case-insensitive matching.

The public surface mirrors Trie<TValue> member-for-member, so the two types are drop-in interchangeable; prefer RadixTrie<TValue> when keys share long unbranching runs (URLs, file paths, identifiers). 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

RadixTrie()

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

public RadixTrie()

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

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

public RadixTrie(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.

RadixTrie(IEqualityComparer<char>?)

Initializes a new instance of the RadixTrie<TValue> class that is empty and uses the specified character comparer.

public RadixTrie(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 RadixTrie<TValue>.Enumerator GetEnumerator()

Returns

RadixTrie<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

Product	Versions
.NET	8, 10