Class SkipListDictionary<K, V>

Namespace

Utils.Collections

Assembly

Utils.Collections.dll

A dictionary whose keys are kept in sorted order using a SkipList<T> as the underlying data structure. All keyed operations run in O(log n) time on average. Iteration yields entries in ascending key order.

public class SkipListDictionary<K, V> : IDictionary<K, V>, ICollection<KeyValuePair<K, V>>, IEnumerable<KeyValuePair<K, V>>, IEnumerable where K : notnull

Type Parameters

K

The type of keys. Must be non-null.

V

The type of values.

Inheritance

object

SkipListDictionary<K, V>

Implements

IDictionary<K, V>

ICollection<KeyValuePair<K, V>>

IEnumerable<KeyValuePair<K, V>>

IEnumerable

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

EnumerableEx.GetValueOrDefault<TKey, TValue>(IDictionary<TKey, TValue>, TKey, TValue)

EnumerableEx.FollowedBy<T>(IEnumerable<T>, params IEnumerable<T>)

EnumerableEx.HasAtLeastElements<T>(IEnumerable<T>, int)

EnumerableEx.HasManyElements<T>(IEnumerable<T>)

EnumerableEx.IsNullOrEmptyCollection<T>(IEnumerable<T>)

EnumerableEx.Pack<T>(IEnumerable<T>)

EnumerableEx.PrecededBy<T>(IEnumerable<T>, params IEnumerable<T>)

EnumerableEx.SkipTake<T>(IEnumerable<T>, int, int)

EnumerableEx.Slice<T>(IEnumerable<T>, params IEnumerable<int>)

EnumerableEx.SlideEnumerateBy<T>(IEnumerable<T>, int, int)

ObjectUtils.ComputeHash<T>(IEnumerable<T>, Func<T, int>)

ObjectUtils.IndexOf<T>(IEnumerable<T>, T)

ObjectUtils.IndexOf<T>(IEnumerable<T>, T, IEqualityComparer<T>)

ObjectUtils.IndexOf<T>(IEnumerable<T>, Func<T, bool>)

DataUtils.ToDbValue(object?)

MathEx.Clamp<T>(T, T, T, IComparer<T>)

FluentExtensions.Failure<T>(T)

FluentExtensions.IsEqualTo<T, CT>(T, CT)

FluentExtensions.IsGreaterOrEqualsThan<T, CT>(T, CT)

FluentExtensions.IsGreaterThan<T, CT>(T, CT)

FluentExtensions.IsIn<T>(T, params T[])

FluentExtensions.IsLowerOrEqualsThan<T, CT>(T, CT)

FluentExtensions.IsLowerThan<T, CT>(T, CT)

FluentExtensions.IsNotIn<T>(T, params T[])

FluentExtensions.IsNotNull<T>(T)

FluentExtensions.IsNull<T>(T)

FluentExtensions.Success<T>(T)

FluentExtensions.Test<T>(T, Func<T, bool>)

ObjectUtils.Between<T>(T, IComparer<T>, T, T)

ObjectUtils.Between<T>(T, IComparer<T>, T, T, bool, bool)

ObjectUtils.DoAsync<T, Result>(T, Func<T, Task<Result>>, Func<Task<Result>>)

ObjectUtils.DoAsync<T, Result>(T, Func<T, Task<Result>>, Result)

ObjectUtils.DoAsync<T, Result>(T, Func<T, Result>, Func<Result>)

ObjectUtils.DoAsync<T, Result>(T, Func<T, Result>, Result)

ObjectUtils.Do<T, Result>(T, Func<T, Result>, Func<Result>)

ObjectUtils.Do<T, Result>(T, Func<T, Result>, Result)

ObjectUtils.In<T>(T, params T[])

ObjectUtils.NotIn<T>(T, params T[])

Validations.ArgMustBe<T>(T, Func<T, bool>, string, string)

Validations.ArgMustNotBe<T>(T, Func<T, bool>, string, string)

Validations.Arg<T>(T, string)

Validations.ValueMustNotBeNull<T>(T, string)

Validations.Variable<T>(T, string)

Remarks

Instance members are not thread-safe. Callers must synchronize access when the same instance is shared between threads, including lookup operations, because the underlying skip list may maintain its adaptive index during a lookup. Keys must not be mutated in a way that changes their ordering or identity under Comparer, because doing so can invalidate the dictionary's logical organization.

Constructors

SkipListDictionary()

Initializes a new instance using the default key comparer and a threshold of 10.

public SkipListDictionary()

SkipListDictionary(IComparer<K>, int)

Initializes a new instance using the specified key comparer and threshold.

public SkipListDictionary(IComparer<K> keyComparer, int threshold = 10)

Parameters

keyComparer IComparer<K>

The comparer used to order keys.

threshold int

The traversal count that must be exceeded before a subsequent unindexed node becomes eligible for promotion. Must be >= 2.

SkipListDictionary(int)

Initializes a new instance using the default key comparer and the specified threshold.

public SkipListDictionary(int threshold)

Parameters

threshold int

The traversal count that must be exceeded before a subsequent unindexed node becomes eligible for promotion. Must be >= 2.

Properties

Comparer

Gets the comparer that defines key ordering and identity.

public IComparer<K> Comparer { get; }

Property Value

IComparer<K>

Count

Gets the number of elements contained in the ICollection<T>.

public int Count { get; }

Property Value

int

The number of elements contained in the ICollection<T>.

IsReadOnly

Gets a value indicating whether the ICollection<T> is read-only.

public bool IsReadOnly { get; }

Property Value

bool

true if the ICollection<T> is read-only; otherwise, false.

this[K]

Gets or sets the element with the specified key.

public V this[K key] { get; set; }

Parameters

key K

The key of the element to get or set.

Property Value

V

The element with the specified key.

Exceptions

ArgumentNullException

key is null.

KeyNotFoundException

The property is retrieved and key is not found.

NotSupportedException

The property is set and the IDictionary<TKey, TValue> is read-only.

Keys

Gets the cached, read-only live view of keys. Its enumerators fail fast on dictionary content changes.

public ICollection<K> Keys { get; }

Property Value

ICollection<K>

Values

Gets the cached, read-only live view of values. Its enumerators fail fast on dictionary content changes.

public ICollection<V> Values { get; }

Property Value

ICollection<V>

Methods

Add(KeyValuePair<K, V>)

Adds an item to the ICollection<T>.

public void Add(KeyValuePair<K, V> item)

Parameters

item KeyValuePair<K, V>

The object to add to the ICollection<T>.

Exceptions

NotSupportedException

The ICollection<T> is read-only.

Add(K, V)

Adds an element with the provided key and value to the IDictionary<TKey, TValue>.

public void Add(K key, V value)

Parameters

key K

The object to use as the key of the element to add.

value V

The object to use as the value of the element to add.

Exceptions

ArgumentNullException

key is null.

ArgumentException

An element with the same key already exists in the IDictionary<TKey, TValue>.

NotSupportedException

The IDictionary<TKey, TValue> is read-only.

Clear()

Removes all items from the ICollection<T>.

public void Clear()

Exceptions

NotSupportedException

The ICollection<T> is read-only.

Contains(KeyValuePair<K, V>)

Determines whether the ICollection<T> contains a specific value.

public bool Contains(KeyValuePair<K, V> item)

Parameters

item KeyValuePair<K, V>

The object to locate in the ICollection<T>.

Returns

bool

true if item is found in the ICollection<T>; otherwise, false.

ContainsKey(K)

Determines whether the IDictionary<TKey, TValue> contains an element with the specified key.

public bool ContainsKey(K key)

Parameters

key K

The key to locate in the IDictionary<TKey, TValue>.

Returns

bool

true if the IDictionary<TKey, TValue> contains an element with the key; otherwise, false.

Exceptions

ArgumentNullException

key is null.

CopyTo(KeyValuePair<K, V>[], int)

Copies the elements of the ICollection<T> to an Array, starting at a particular Array index.

public void CopyTo(KeyValuePair<K, V>[] array, int arrayIndex)

Parameters

array KeyValuePair<K, V>[]

The one-dimensional Array that is the destination of the elements copied from ICollection<T>. The Array must have zero-based indexing.

arrayIndex int

The zero-based index in array at which copying begins.

Exceptions

ArgumentNullException

array is null.

ArgumentOutOfRangeException

arrayIndex is less than 0.

ArgumentException

The number of elements in the source ICollection<T> is greater than the available space from arrayIndex to the end of the destination array.

GetEnumerator()

Returns an enumerator that iterates through the collection.

public IEnumerator<KeyValuePair<K, V>> GetEnumerator()

Returns

IEnumerator<KeyValuePair<K, V>>

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

Remove(KeyValuePair<K, V>)

Removes the first occurrence of a specific object from the ICollection<T>.

public bool Remove(KeyValuePair<K, V> item)

Parameters

item KeyValuePair<K, V>

The object to remove from the ICollection<T>.

Returns

bool

true if item was successfully removed from the ICollection<T>; otherwise, false. This method also returns false if item is not found in the original ICollection<T>.

Exceptions

NotSupportedException

The ICollection<T> is read-only.

Remove(K)

Removes the element with the specified key from the IDictionary<TKey, TValue>.

public bool Remove(K key)

Parameters

key K

The key of the element to remove.

Returns

bool

true if the element is successfully removed; otherwise, false. This method also returns false if key was not found in the original IDictionary<TKey, TValue>.

Exceptions

ArgumentNullException

key is null.

NotSupportedException

The IDictionary<TKey, TValue> is read-only.

TryGetValue(K, out V)

Gets the value associated with the specified key.

public bool TryGetValue(K key, out V value)

Parameters

key K

The key whose value to get.

value V

When this method returns, the value associated with the specified key, if the key is found; otherwise, the default value for the type of the value parameter. This parameter is passed uninitialized.

Returns

bool

true if the object that implements IDictionary<TKey, TValue> contains an element with the specified key; otherwise, false.

Exceptions

ArgumentNullException

key is null.