NavigableDictionary<TKey, TValue> Class

Definition

Namespace: Bodu.Collections.Generic

Assembly: Bodu.Collections.dll

Package: Bodu.Collections 1.0.0

Source: NavigableDictionary{T,T}.EntryKeyComparer.cs

Represents a key-sorted dictionary augmented with order statistics - an IDictionary<TKey, TValue> that keeps its entries in key comparer order and answers nearest-neighbour ( TryGetFloorEntry(TKey, out KeyValuePair<TKey, TValue>) / TryGetCeilingEntry(TKey, out KeyValuePair<TKey, TValue>) / TryGetHigherEntry(TKey, out KeyValuePair<TKey, TValue>) / TryGetLowerEntry(TKey, out KeyValuePair<TKey, TValue>)), rank/select ( IndexOfKey(TKey) / GetAt(int)), and range-counting queries in O(log n).

public sealed class NavigableDictionary<TKey, TValue> : IDictionary<TKey, TValue>, ICollection<KeyValuePair<TKey, TValue>>, IReadOnlyDictionary<TKey, TValue>, IReadOnlyCollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable where TKey : notnull

Type Parameters

TKey: The type of keys in the dictionary. Keys must not be null.
TValue: The type of values in the dictionary. Values may be null.

Inheritance: object

NavigableDictionary<TKey, TValue>

Implements: IDictionary<TKey, TValue>

ICollection<KeyValuePair<TKey, TValue>>

IReadOnlyDictionary<TKey, TValue>

IReadOnlyCollection<KeyValuePair<TKey, TValue>>

IEnumerable<KeyValuePair<TKey, 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>)

Examples

var quotes = new NavigableDictionary<decimal, string>();
quotes.Add(10.00m, "bid");
quotes.Add(10.25m, "mid");
quotes.Add(10.50m, "ask");

quotes.TryGetFloorEntry(10.30m, out var floor);   // (10.25, "mid") - greatest key <= 10.30
quotes.TryGetCeilingKey(10.30m, out decimal ask); // 10.50 - least key >= 10.30

int rank = quotes.IndexOfKey(10.25m);             // 1 - zero-based rank in key order
var median = quotes.GetAt(quotes.Count / 2);      // (10.25, "mid") - entry with the k-th smallest key
int inBand = quotes.CountInRange(10.00m, 10.30m); // 2 - O(log n), no iteration

Remarks

NavigableDictionary<TKey, TValue> is backed by an order-statistic red-black tree: every node carries the size of its subtree, maintained through all rotations, so positional queries read only size fields on a root-to-node path. The node machinery is the key-value adaptation of the NavigableSet<T> core; see Bodu.Collections/docs/navigable-collections-design.md for the backing-structure decision record.

Compared with SortedDictionary<TKey, TValue>, this type adds rank/select ( IndexOfKey(TKey) is the zero-based rank of a key; GetAt(int) is the entry with the k-th smallest key), O(log n) CountInRange(TKey, TKey), the four nearest-neighbour queries, and cheap Ascending() / Descending() / Range(TKey, TKey) views.

Keys are rejected when null, consistent with the rest of the Bodu collection family; values are unconstrained and may be null. Keys the comparer orders equal are the same key.

This type is not thread-safe.

Constructors

NavigableDictionary()

Initializes a new instance of the NavigableDictionary<TKey, TValue> class using the default comparer.

public NavigableDictionary()

NavigableDictionary(IComparer<TKey>?)

Initializes a new instance of the NavigableDictionary<TKey, TValue> class using the specified comparer.

public NavigableDictionary(IComparer<TKey>? comparer)

Parameters

comparer IComparer<TKey>: The key ordering comparer, or null to use the default comparer.

NavigableDictionary(IEnumerable<KeyValuePair<TKey, TValue>>, IComparer<TKey>?)

Initializes a new instance of the NavigableDictionary<TKey, TValue> class containing the entries from source, bulk-loaded into a balanced tree.

public NavigableDictionary(IEnumerable<KeyValuePair<TKey, TValue>> source, IComparer<TKey>? comparer = null)

Parameters

source IEnumerable<KeyValuePair<TKey, TValue>>: The source entries. Must not be null.
comparer IComparer<TKey>: The key ordering comparer, or null to use the default comparer.

Remarks

The source is sorted by key and built directly into a balanced tree - O(n log n) overall, O(n) after the sort. Comparer-equal duplicate keys are rejected, matching the Dictionary<TKey, TValue> collection-constructor contract.

Exceptions

ArgumentNullException: source is null.
ArgumentException: source contains a null key, or two entries whose keys the comparer orders equal.

Properties

Comparer

Gets the comparer that defines the key ordering.

public IComparer<TKey> Comparer { get; }

Property Value

IComparer<TKey>: The active key ordering comparer.

Count

Gets the number of entries in the dictionary.

public int Count { get; }

Property Value

int: The number of key/value pairs currently stored in the dictionary.

IsReadOnly

Gets a value indicating whether the dictionary is read-only.

public bool IsReadOnly { get; }

Property Value

bool: Always false.

this[TKey]

Gets or sets the value associated with the specified key.

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

Parameters

key TKey: The key of the value to get or set. Must not be null.

Property Value

TValue: The value associated with key.

Remarks

Assigning through the indexer upserts: a new key is inserted at its comparer position, and an existing key has its value overwritten in place. Overwriting a value is not a structural mutation and does not invalidate in-flight enumerators.

Exceptions

ArgumentNullException: key is null.
KeyNotFoundException: The property is read and the dictionary does not contain key.

Keys

Gets a live view of the dictionary's keys in ascending comparer order.

public ICollection<TKey> Keys { get; }

Property Value

ICollection<TKey>: A read-only collection over the current keys, smallest first.

Remarks

The view is live and cached per instance, so repeated reads of Keys do not allocate; enumeration follows ascending key order and is fail-fast against structural mutation.

MaxEntry

Gets the entry with the largest key in the dictionary.

public KeyValuePair<TKey, TValue> MaxEntry { get; }

Property Value

KeyValuePair<TKey, TValue>: The maximum-key entry under the active comparer.

Exceptions

InvalidOperationException: The dictionary is empty.

MinEntry

Gets the entry with the smallest key in the dictionary.

public KeyValuePair<TKey, TValue> MinEntry { get; }

Property Value

KeyValuePair<TKey, TValue>: The minimum-key entry under the active comparer.

Exceptions

InvalidOperationException: The dictionary is empty.

Values

Gets a live view of the dictionary's values in ascending key order.

public ICollection<TValue> Values { get; }

Property Value

ICollection<TValue>: A read-only collection over the current values, ordered by their keys.

Remarks

The view is live and cached per instance, so repeated reads of Values do not allocate; enumeration follows ascending key order and is fail-fast against structural mutation.

Methods

Add(TKey, TValue)

Adds the specified key and value to the dictionary.

public void Add(TKey key, TValue value)

Parameters

key TKey: The key of the entry to add. Must not be null.
value TValue: The value to associate with key.

Remarks

This method follows the strict Add(TKey, TValue) contract and throws on a comparer-equal duplicate key. To insert or overwrite without throwing, assign through the indexer; to add only when absent without throwing, call TryAdd(TKey, TValue).

Exceptions

ArgumentNullException: key is null.
ArgumentException: The dictionary already contains a comparer-equal key.

Ascending()

Returns a live view of the entries in ascending key order.

public IEnumerable<KeyValuePair<TKey, TValue>> Ascending()

Returns

IEnumerable<KeyValuePair<TKey, TValue>>: A lazily evaluated sequence over the current entries, smallest key first.

Remarks

The view is live: each fresh iteration re-resolves against the dictionary's current state, so mutations made after the view was obtained are reflected the next time it is iterated. Within a single iteration the view is fail-fast - any structural mutation causes the next advance to throw InvalidOperationException.

Clear()

Removes all entries from the dictionary.

public void Clear()

ContainsKey(TKey)

Determines whether the dictionary contains an entry with the specified key.

public bool ContainsKey(TKey key)

Parameters

key TKey: The key to locate. Must not be null.

Returns

bool: true if an entry with a comparer-equal key exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

ContainsValue(TValue)

Determines whether the dictionary contains an entry with the specified value.

public bool ContainsValue(TValue value)

Parameters

value TValue: The value to locate, which may be null.

Returns

bool: true if at least one entry stores a value equal to value under Default; otherwise, false.

Remarks

This method performs a linear O(n) walk over the entries - values are not indexed. Use ContainsKey(TKey) for the O(log n) key lookup.

CopyTo(KeyValuePair<TKey, TValue>[], int)

Copies the entries to the specified array in ascending key order, starting at arrayIndex.

public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)

Parameters

array KeyValuePair<TKey, TValue>[]: The destination array. Must not be null.
arrayIndex int: The destination start index.

Exceptions

ArgumentNullException: array is null.
ArgumentOutOfRangeException: arrayIndex is negative.
ArgumentException: array does not have enough space starting at arrayIndex.

CountInRange(TKey, TKey)

Returns the number of entries whose keys fall within the inclusive range [lowInclusive, highInclusive].

public int CountInRange(TKey lowInclusive, TKey highInclusive)

Parameters

lowInclusive TKey: The inclusive lower key bound. Must not be null.
highInclusive TKey: The inclusive upper key bound. Must not be null.

Returns

int: The count of stored entries whose keys are no smaller than the lower bound and no larger than the upper bound.

Remarks

Runs in O(log n) as a subtraction of two rank walks; neither bound needs to be present in the dictionary.

Exceptions

ArgumentNullException: lowInclusive or highInclusive is null.
ArgumentException: lowInclusive orders after highInclusive under the active comparer.

Descending()

Returns a live view of the entries in descending key order.

public IEnumerable<KeyValuePair<TKey, TValue>> Descending()

Returns

IEnumerable<KeyValuePair<TKey, TValue>>: A lazily evaluated sequence over the current entries, largest key first.

Remarks

GetAt(int)

Returns the entry at the specified zero-based rank - the entry with the k-th smallest key.

public KeyValuePair<TKey, TValue> GetAt(int rank)

Parameters

rank int: The zero-based rank of the entry to select.

Returns

KeyValuePair<TKey, TValue>: The entry whose key rank is rank.

Remarks

Runs in O(log n) by descending on subtree sizes.

Exceptions

ArgumentOutOfRangeException: rank is negative or greater than or equal to Count.

GetEnumerator()

Returns an enumerator that iterates through the dictionary in ascending key order.

public NavigableDictionary<TKey, TValue>.Enumerator GetEnumerator()

Returns

NavigableDictionary<TKey, TValue>.Enumerator: An NavigableDictionary<TKey, TValue>.Enumerator over the dictionary entries.

IndexOfKey(TKey)

Returns the zero-based rank of key in ascending comparer order.

public int IndexOfKey(TKey key)

Parameters

key TKey: The key to locate. Must not be null.

Returns

int: The number of stored keys smaller than key, or -1 if it is not present.

Remarks

Runs in O(log n) by accumulating subtree sizes along the search path.

Exceptions

ArgumentNullException: key is null.

Range(TKey, TKey)

Returns a live view of the entries whose keys fall within the inclusive range [ lowInclusive, highInclusive] in ascending key order.

public IEnumerable<KeyValuePair<TKey, TValue>> Range(TKey lowInclusive, TKey highInclusive)

Parameters

lowInclusive TKey: The inclusive lower key bound. Must not be null.
highInclusive TKey: The inclusive upper key bound. Must not be null.

Returns

IEnumerable<KeyValuePair<TKey, TValue>>: A lazily evaluated sequence over the in-range entries, smallest key first.

Remarks

The bounds need not be present in the dictionary. The walk descends directly to the first in-range entry and stops past the last, so iterating costs O(log n + k) for k yielded entries.

The view is live over the bound pair: each fresh iteration re-resolves against the dictionary's current state. Within a single iteration the view is fail-fast - any structural mutation causes the next advance to throw InvalidOperationException.

Exceptions

ArgumentNullException: lowInclusive or highInclusive is null.
ArgumentException: lowInclusive orders after highInclusive under the active comparer.

Remove(TKey)

Removes the entry with the specified key from the dictionary.

public bool Remove(TKey key)

Parameters

key TKey: The key of the entry to remove. Must not be null.

Returns

bool: true if the entry was removed; otherwise, false.

Exceptions

ArgumentNullException: key is null.

Remove(TKey, out TValue)

Removes the entry with the specified key from the dictionary, returning the removed value.

public bool Remove(TKey key, out TValue value)

Parameters

key TKey: The key of the entry to remove. Must not be null.
value TValue: When this method returns true, the value that was associated with key; otherwise, the default value of TValue.

Returns

bool: true if the entry was removed; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryAdd(TKey, TValue)

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

public bool TryAdd(TKey key, TValue value)

Parameters

key TKey: The key of the entry to add. Must not be null.
value TValue: The value to associate with key.

Returns

bool: true if the entry was added; otherwise, false when the dictionary already contains a comparer-equal key. The stored value is left unchanged on a rejected add.

Exceptions

ArgumentNullException: key is null.

TryGetCeilingEntry(TKey, out KeyValuePair<TKey, TValue>)

Attempts to get the entry with the least key greater than or equal to key.

public bool TryGetCeilingEntry(TKey key, out KeyValuePair<TKey, TValue> entry)

Parameters

key TKey: The reference key. Must not be null.
entry KeyValuePair<TKey, TValue>: When this method returns true, the ceiling entry.

Returns

bool: true if a ceiling entry exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetCeilingKey(TKey, out TKey)

Attempts to get the least key greater than or equal to key.

public bool TryGetCeilingKey(TKey key, out TKey ceilingKey)

Parameters

key TKey: The reference key. Must not be null.
ceilingKey TKey: When this method returns true, the ceiling key.

Returns

bool: true if a ceiling key exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetFloorEntry(TKey, out KeyValuePair<TKey, TValue>)

Attempts to get the entry with the greatest key less than or equal to key.

public bool TryGetFloorEntry(TKey key, out KeyValuePair<TKey, TValue> entry)

Parameters

key TKey: The reference key. Must not be null.
entry KeyValuePair<TKey, TValue>: When this method returns true, the floor entry.

Returns

bool: true if a floor entry exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetFloorKey(TKey, out TKey)

Attempts to get the greatest key less than or equal to key.

public bool TryGetFloorKey(TKey key, out TKey floorKey)

Parameters

key TKey: The reference key. Must not be null.
floorKey TKey: When this method returns true, the floor key.

Returns

bool: true if a floor key exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetHigherEntry(TKey, out KeyValuePair<TKey, TValue>)

Attempts to get the entry with the least key strictly greater than key.

public bool TryGetHigherEntry(TKey key, out KeyValuePair<TKey, TValue> entry)

Parameters

key TKey: The reference key. Must not be null.
entry KeyValuePair<TKey, TValue>: When this method returns true, the next-higher entry.

Returns

bool: true if a higher entry exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetHigherKey(TKey, out TKey)

Attempts to get the least key strictly greater than key.

public bool TryGetHigherKey(TKey key, out TKey higherKey)

Parameters

key TKey: The reference key. Must not be null.
higherKey TKey: When this method returns true, the next-higher key.

Returns

bool: true if a higher key exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetLowerEntry(TKey, out KeyValuePair<TKey, TValue>)

Attempts to get the entry with the greatest key strictly less than key.

public bool TryGetLowerEntry(TKey key, out KeyValuePair<TKey, TValue> entry)

Parameters

key TKey: The reference key. Must not be null.
entry KeyValuePair<TKey, TValue>: When this method returns true, the next-lower entry.

Returns

bool: true if a lower entry exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetLowerKey(TKey, out TKey)

Attempts to get the greatest key strictly less than key.

public bool TryGetLowerKey(TKey key, out TKey lowerKey)

Parameters

key TKey: The reference key. Must not be null.
lowerKey TKey: When this method returns true, the next-lower key.

Returns

bool: true if a lower key exists; otherwise, false.

Exceptions

ArgumentNullException: key is null.

TryGetMaxEntry(out KeyValuePair<TKey, TValue>)

Attempts to get the entry with the largest key in the dictionary.

public bool TryGetMaxEntry(out KeyValuePair<TKey, TValue> entry)

Parameters

entry KeyValuePair<TKey, TValue>: When this method returns true, the maximum-key entry.

Returns

bool: true if the dictionary is non-empty; otherwise, false.

TryGetMinEntry(out KeyValuePair<TKey, TValue>)

Attempts to get the entry with the smallest key in the dictionary.

public bool TryGetMinEntry(out KeyValuePair<TKey, TValue> entry)

Parameters

entry KeyValuePair<TKey, TValue>: When this method returns true, the minimum-key entry.

Returns

bool: true if the dictionary is non-empty; otherwise, false.

TryGetValue(TKey, out TValue)

Attempts to retrieve the value associated with the specified key.

public bool TryGetValue(TKey key, out TValue value)

Parameters

key TKey: The key of the value to retrieve. Must not be null.
value TValue: When this method returns true, the value associated with key; otherwise, the default value of TValue.

Returns

bool: true if the dictionary contains an entry with a comparer-equal key; otherwise, false.

Exceptions

ArgumentNullException: key is null.

Explicit Interface Implementations

ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue>)

Adds item via the Add(T) contract.

void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)

Parameters

item KeyValuePair<TKey, TValue>: The key/value pair to add.

Exceptions

ArgumentNullException: item.Key is null.
ArgumentException: The dictionary already contains a comparer-equal key.

ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue>)

Determines whether the dictionary contains an entry matching both the key and the value of item.

bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)

Parameters

item KeyValuePair<TKey, TValue>: The key/value pair to locate.

Returns

bool: true if an entry with a comparer-equal key exists whose value equals item.Value under Default; otherwise, false.

Exceptions

ArgumentNullException: item.Key is null.

ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue>)

Removes the entry matching both the key and the value of item.

bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)

Parameters

item KeyValuePair<TKey, TValue>: The key/value pair to remove.

Returns

bool: true if a matching entry was found and removed; otherwise, false.

Exceptions

ArgumentNullException: item.Key is null.

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

Returns an enumerator that iterates through the collection.

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

Returns

IEnumerator<KeyValuePair<TKey, TValue>>: An enumerator that can be used to iterate through the collection.

IReadOnlyDictionary<TKey, TValue>.Keys

Gets an enumerable collection that contains the keys in the read-only dictionary.

IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys { get; }

Returns

IEnumerable<TKey>: An enumerable collection that contains the keys in the read-only dictionary.

IReadOnlyDictionary<TKey, TValue>.Values

Gets an enumerable collection that contains the values in the read-only dictionary.

IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values { get; }

Returns

IEnumerable<TValue>: An enumerable collection that contains the values in the read-only dictionary.

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

Table of Contents

NavigableDictionary<TKey, TValue> Class

Definition

Type Parameters

Examples

Remarks

Constructors

NavigableDictionary()

NavigableDictionary(IComparer<TKey>?)

Parameters

NavigableDictionary(IEnumerable<KeyValuePair<TKey, TValue>>, IComparer<TKey>?)

Parameters

Remarks

Exceptions

Properties

Comparer

Property Value

Count

Property Value

IsReadOnly

Property Value

this[TKey]

Parameters

Property Value

Remarks

Exceptions

Keys

Property Value

Remarks

MaxEntry

Property Value

Exceptions

MinEntry

Property Value

Exceptions

Values

Property Value

Remarks

Methods

Add(TKey, TValue)

Parameters

Remarks

Exceptions

Ascending()

Returns

Remarks

Clear()

ContainsKey(TKey)

Parameters

Returns

Exceptions

ContainsValue(TValue)

Parameters

Returns

Remarks

CopyTo(KeyValuePair<TKey, TValue>[], int)

Parameters

Exceptions

CountInRange(TKey, TKey)

Parameters

Returns

Remarks

Exceptions

Descending()

Returns

Remarks

GetAt(int)

Parameters

Returns

Remarks

Exceptions

GetEnumerator()

Returns

IndexOfKey(TKey)

Parameters

Returns

Remarks

Exceptions

Range(TKey, TKey)

Parameters