KGy SOFT

CircularSortedListTKey, TValue Class

KGy SOFT Core Libraries Help
Represents a dictionary of key/value pairs that are sorted by key based on the associated IComparerT implementation. The dictionary behaves as list as well, as it has a direct indexed access to the elements through Keys and Values properties or by the ElementAt method. CircularSortedListTKey, TValue is fully compatible with SortedListTKey, TValue, but is generally faster than that.
See the Remarks section for details.
Inheritance Hierarchy

SystemObject
  KGySoft.CollectionsCircularSortedListTKey, TValue

Namespace:  KGySoft.Collections
Assembly:  KGySoft.CoreLibraries (in KGySoft.CoreLibraries.dll) Version: 5.0.0-rc.1
Syntax

[SerializableAttribute]
public class CircularSortedList<TKey, TValue> : IDictionary<TKey, TValue>, 
	ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>, 
	IEnumerable, IList<KeyValuePair<TKey, TValue>>, IDictionary, 
	ICollection, IList, IReadOnlyDictionary<TKey, TValue>, IReadOnlyCollection<KeyValuePair<TKey, TValue>>, 
	IReadOnlyList<KeyValuePair<TKey, TValue>>

Type Parameters

TKey
Type of the keys stored in the sorted list.
TValue
Type of the values stored in the sorted list.

The CircularSortedListTKey, TValue type exposes the following members.

Constructors

  NameDescription
Public methodCircularSortedListTKey, TValue
Creates a new instance of CircularSortedListTKey, TValue with empty capacity and a default comparer.
Public methodCircularSortedListTKey, TValue(IComparerTKey)
Creates a new instance of CircularSortedListTKey, TValue with empty capacity, that uses the specified comparer.
Public methodCircularSortedListTKey, TValue(IDictionaryTKey, TValue, IComparerTKey)
Creates a new instance of CircularSortedListTKey, TValue, that initializes its elements from the provided dictionary, and uses the specified comparer.
Public methodCircularSortedListTKey, TValue(Int32, IComparerTKey)
Creates a new instance of CircularSortedListTKey, TValue, that is empty, and has the specified initial capacity, and uses the specified comparer.
Top
Properties

  NameDescription
Public propertyAsList
Gets the CircularSortedListTKey, TValue cast to an IListT.
Public propertyCapacity
Gets or sets the actual size of the internal storage of held elements.
Public propertyComparer
Gets the IComparerT that is used in the CircularSortedListTKey, TValue.
Public propertyCount
Gets the number of key/value pairs contained in the CircularSortedListTKey, TValue.
Public propertyItem
Gets or sets the value associated with the specified key.
Public propertyKeys
Gets an indexable list containing the keys in the CircularSortedListTKey, TValue, in sorted order.
Public propertyValues
Gets an indexable list containing the values in the CircularSortedListTKey, TValue, in the order of the sorted keys.
Top
Methods

  NameDescription
Public methodAdd
Adds an element with the provided key and value to the CircularSortedListTKey, TValue.
Public methodClear
Removes all items from the CircularSortedListTKey, TValue.
Public methodContainsKey
Determines whether the CircularSortedListTKey, TValue contains an element with the specified key.
Public methodContainsValue
Determines whether the CircularSortedListTKey, TValue contains a specific value.
Public methodElementAt
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodGetEnumerator
Returns an enumerator that iterates through the collection in the order of the sorted keys.
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodIndexOfKey
Searches for the specified key and returns the zero-based index within the entire CircularSortedListTKey, TValue.
Public methodIndexOfValue
Searches for the specified value and returns the zero-based index of the first occurrence within the entire CircularSortedListTKey, TValue.
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodRemove
Removes the element with the specified key from the CircularSortedListTKey, TValue.
Public methodRemoveAt
Removes the element at the specified index of the CircularSortedListTKey, TValue.
Public methodReset
Removes all items from the CircularSortedListTKey, TValue and resets the Capacity to 0.
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Public methodTrimExcess
Sets the capacity to the actual number of elements in the CircularSortedListTKey, TValue, if that number is less than 90 percent of current capacity.
Public methodTryGetValue
Gets the value associated with the specified key.
Top
Extension Methods

  NameDescription
Public Extension MethodAddRangeKeyValuePairTKey, TValue (Defined by CollectionExtensions.)
Public Extension MethodAsThreadSafeKeyValuePairTKey, TValueOverloaded. (Defined by CollectionExtensions.)
Public Extension MethodAsThreadSafeKeyValuePairTKey, TValueOverloaded. (Defined by ListExtensions.)
Public Extension MethodConvert(Type, CultureInfo)Overloaded.
Converts an Object specified in the obj parameter to the desired targetType.
See the Examples section of the generic ConvertTTarget(Object, CultureInfo) overload for an example.
(Defined by ObjectExtensions.)
Public Extension MethodCode exampleConvertTTarget(CultureInfo)Overloaded.
Converts an Object specified in the obj parameter to the desired TTarget.
(Defined by ObjectExtensions.)
Public Extension MethodForEachKeyValuePairTKey, TValue
Similarly to the List<T>.ForEach method, processes an action on each element of an enumerable collection.
(Defined by EnumerableExtensions.)
Public Extension MethodGetRandomElementKeyValuePairTKey, TValue(Boolean)Overloaded.
Gets a random element from the enumerable source using a new Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodGetRandomElementKeyValuePairTKey, TValue(Random, Boolean)Overloaded.
Gets a random element from the enumerable source using a specified Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodIn (Defined by ObjectExtensions.)
Public Extension MethodIndexOf(FuncObject, Boolean)Overloaded.
Searches for an element in the source enumeration where the specified predicate returns .
(Defined by EnumerableExtensions.)
Public Extension MethodIndexOf(Object)Overloaded.
Searches for an element in the source enumeration.
(Defined by EnumerableExtensions.)
Public Extension MethodIndexOfKeyValuePairTKey, TValue(FuncKeyValuePairTKey, TValue, Boolean)Overloaded.
Searches for an element in the source enumeration where the specified predicate returns .
(Defined by EnumerableExtensions.)
Public Extension MethodIndexOfKeyValuePairTKey, TValue(KeyValuePairTKey, TValue)Overloaded.
Searches for an element in the source enumeration.
(Defined by EnumerableExtensions.)
Public Extension MethodInsertRangeKeyValuePairTKey, TValue (Defined by ListExtensions.)
Public Extension MethodIsNullOrEmptyOverloaded.
Determines whether the specified source is  or empty (has no elements).
(Defined by EnumerableExtensions.)
Public Extension MethodIsNullOrEmptyKeyValuePairTKey, TValueOverloaded.
Determines whether the specified source is  or empty (has no elements).
(Defined by EnumerableExtensions.)
Public Extension MethodRemoveRangeKeyValuePairTKey, TValue
Removes count amount of items from the specified collection at the specified index.
(Defined by ListExtensions.)
Public Extension MethodReplaceRangeKeyValuePairTKey, TValue
Removes count amount of items from the target IListT at the specified index, and inserts the specified collection at the same position. The number of elements in collection can be different from the amount of removed items.
(Defined by ListExtensions.)
Public Extension MethodShuffleKeyValuePairTKey, TValueOverloaded.
Shuffles an enumerable source (randomizes its elements) using a new Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodShuffleKeyValuePairTKey, TValue(Int32)Overloaded.
Shuffles an enumerable source (randomizes its elements) using the provided seed with a new Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodShuffleKeyValuePairTKey, TValue(Random)Overloaded.
Shuffles an enumerable source (randomizes its elements) using a specified Random instance.
(Defined by EnumerableExtensions.)
Public Extension MethodToCircularListKeyValuePairTKey, TValue (Defined by EnumerableExtensions.)
Public Extension MethodTryAdd(Object, Boolean, Boolean)Overloaded.
Tries to add the specified item to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryAddKeyValuePairTKey, TValue(KeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to add the specified item to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryAddRange(IEnumerable, Boolean, Boolean)Overloaded.
Tries to add the specified collection to the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryAddRangeKeyValuePairTKey, TValue(IEnumerableKeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to add the specified collection to the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryClear(Boolean, Boolean)Overloaded.
Tries to remove all elements from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryClearKeyValuePairTKey, TValue(Boolean, Boolean)Overloaded.
Tries to remove all elements from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryConvert(Type, Object)Overloaded.
Tries to convert an Object specified in the obj parameter to the desired targetType.
(Defined by ObjectExtensions.)
Public Extension MethodTryConvert(Type, CultureInfo, Object)Overloaded.
Tries to convert an Object specified in the obj parameter to the desired targetType.
(Defined by ObjectExtensions.)
Public Extension MethodTryConvertTTarget(TTarget)Overloaded.
Tries to convert an Object specified in the obj parameter to the desired TTarget.
See the Examples section of the ConvertTTarget(Object, CultureInfo) method for a related example.
(Defined by ObjectExtensions.)
Public Extension MethodTryConvertTTarget(CultureInfo, TTarget)Overloaded.
Tries to convert an Object specified in the obj parameter to the desired TTarget.
See the Examples section of the ConvertTTarget(Object, CultureInfo) method for a related example.
(Defined by ObjectExtensions.)
Public Extension MethodTryGetElementAt(Int32, Object, Boolean, Boolean)Overloaded.
Tries to get an item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryGetElementAtKeyValuePairTKey, TValue(Int32, KeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to get an item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsert(Int32, Object, Boolean, Boolean)Overloaded.
Tries to insert the specified item at the specified index to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsertKeyValuePairTKey, TValue(Int32, KeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to insert the specified item at the specified index to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsertRange(Int32, IEnumerable, Boolean, Boolean)Overloaded.
Tries to insert the specified collection into the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryInsertRangeKeyValuePairTKey, TValue(Int32, IEnumerableKeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to insert the specified collection into the target collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemove(Object, Boolean, Boolean)Overloaded.
Tries to remove the specified item from to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveKeyValuePairTKey, TValue(KeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to remove the specified item from to the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveAt(Int32, Boolean, Boolean)Overloaded.
Tries to remove an item at the specified index from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveAtKeyValuePairTKey, TValue(Int32, Boolean, Boolean)Overloaded.
Tries to remove an item at the specified index from the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveRange(Int32, Int32, Boolean, Boolean)Overloaded.
Tries to remove count amount of items from the specified collection at the specified index.
(Defined by EnumerableExtensions.)
Public Extension MethodTryRemoveRangeKeyValuePairTKey, TValue(Int32, Int32, Boolean, Boolean)Overloaded.
Tries to remove count amount of items from the specified collection at the specified index.
(Defined by EnumerableExtensions.)
Public Extension MethodTryReplaceRange(Int32, Int32, IEnumerable, Boolean, Boolean)Overloaded.
Tries to remove count amount of items from the target at the specified index, and to insert the specified collection at the same position. The number of elements in collection can be different from the amount of removed items.
(Defined by EnumerableExtensions.)
Public Extension MethodTryReplaceRangeKeyValuePairTKey, TValue(Int32, Int32, IEnumerableKeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to remove count amount of items from the target at the specified index, and to insert the specified collection at the same position. The number of elements in collection can be different from the amount of removed items.
(Defined by EnumerableExtensions.)
Public Extension MethodTrySetElementAt(Int32, Object, Boolean, Boolean)Overloaded.
Tries to set the specified item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Public Extension MethodTrySetElementAtKeyValuePairTKey, TValue(Int32, KeyValuePairTKey, TValue, Boolean, Boolean)Overloaded.
Tries to set the specified item at the specified index in the collection.
(Defined by EnumerableExtensions.)
Top
Remarks

The CircularSortedListTKey, TValue generic class is an array of key/value pairs with O(log n) retrieval, where n is the number of elements in the dictionary. In that regard it is similar to the SortedListTKey, TValue and SortedDictionaryTKey, TValue generic classes. These three classes serve a similar purpose, and all have O(log n) retrieval. Where the three classes differ is in memory use and speed of insertion and removal:

Collection typeBehavior
SortedDictionaryTKey, TValue
SortedListTKey, TValue
  • Store model and memory: Keys and values are stored in separated arrays, which is the most compact storage form among the sorted dictionaries.
  • Insertion and removal: Position of the element is searched with binary search in the array, which in an O(log n) operation. Insertion/removal at the last position has a constant additional cost, so inserting/removing at the and has O(log n) cost, otherwise O(n) cost.
  • Populating from sorted data: Since position of the elements are always checked, adding a new element to the end has always O(log n) cost, though it is faster than in case of a SortedDictionaryTKey, TValue. Though, populating from a reverse ordered data has the worst possible performance, because every already existing elements have to be shifted in the underlying arrays.
  • Enumerating the collection: Really fast, it is actually a traversal of arrays.
CircularSortedListTKey, TValue

Similarly to SortedListTKey, TValue, CircularSortedListTKey, TValue supports efficient indexed retrieval of keys and values through the collections returned by the Keys and Values properties. It is not necessary to regenerate the lists when the properties are accessed, because the lists are just wrappers for the internal arrays of keys and values.

CircularSortedListTKey, TValue is implemented as a pair of CircularListT of key/value pairs, sorted by the key. Each element can be retrieved as a KeyValuePairTKey, TValue object.

Key objects must be immutable as long as they are used as keys in the CircularSortedListTKey, TValue. Every key in a CircularSortedListTKey, TValue must be unique. A key cannot be , but a value can be, if the type of values in the list, TValue, is a reference type, or is a NullableT type.

CircularSortedListTKey, TValue implements IListT as well, so it can be indexed directly when cast to IListT or though the AsList property:

C#
KeyValuePair<int, string> firstItem = myCircularSortedList.AsList[0];
Setting the IList<T>.Item property or using the IList<T>.Insert method throws a NotSupportedException for CircularSortedListTKey, TValue, as the position of an element cannot be set directly, it always depends on the comparer implementation.

CircularSortedListTKey, TValue requires a comparer implementation to sort and to perform comparisons. If comparer is not defined when CircularSortedListTKey, TValue is instantiated by one of the constructors, the comparer will be chosen automatically. When TKey is en enum type, the comparer will be the EnumComparer<TEnum>.Comparer. Otherwise, the default comparer Comparer<T>.Default will be chosen. The default comparer checks whether the key type TKey implements IComparableT and uses that implementation, if available. If not, Comparer<T>.Default checks whether the key type TKey implements IComparable. If the key type TKey does not implement either interface, you can specify an IComparableT implementation in a constructor overload that accepts a comparer parameter.

The capacity of a CircularSortedListTKey, TValue is the number of elements the CircularSortedListTKey, TValue can hold. As elements are added to a CircularSortedListTKey, TValue, the capacity is automatically increased as required by reallocating the internal array. The capacity can be decreased by calling TrimExcess or by setting the Capacity property explicitly. Decreasing the capacity reallocates memory and copies all the elements in the CircularSortedListTKey, TValue.

See Also

Reference