Class OrderedDictionary<K, V>
A sorted Dictionary implementation using balanced binary search tree. IEnumerable will enumerate in sorted order.
This may be better than regular Dictionary implementation which can give o(K) in worst case (but O(1) amortized when collisions K is avoided).
Inheritance
OrderedDictionary<K, V>
Assembly: Advanced.Algorithms.dll
Syntax
public class OrderedDictionary<K, V> : IEnumerable<KeyValuePair<K, V>> where K : IComparable
Type Parameters
Name |
Description |
K |
The key datatype.
|
V |
The value datatype.
|
Constructors
OrderedDictionary()
Declaration
public OrderedDictionary()
OrderedDictionary(IEnumerable<KeyValuePair<K, V>>)
Initialize the dictionary with given key value pairs sorted by key.
Time complexity: log(n).
Declaration
public OrderedDictionary(IEnumerable<KeyValuePair<K, V>> sortedKeyValuePairs)
Parameters
Type |
Name |
Description |
IEnumerable<KeyValuePair<K, V>> |
sortedKeyValuePairs |
|
Properties
Count
Declaration
public int Count { get; }
Property Value
Item[K]
Get/set value for given key.
Time complexity: O(log(n)).
Declaration
public V this[K key] { get; set; }
Parameters
Type |
Name |
Description |
K |
key |
|
Property Value
Methods
Add(K, V)
Add a new value for given key.
Time complexity: O(log(n)).
Returns the position (index) of the key in sorted order of this OrderedDictionary.
Declaration
public int Add(K key, V value)
Parameters
Type |
Name |
Description |
K |
key |
|
V |
value |
|
Returns
AsEnumerableDesc()
Declaration
public IEnumerable<KeyValuePair<K, V>> AsEnumerableDesc()
Returns
Type |
Description |
IEnumerable<KeyValuePair<K, V>> |
|
ContainsKey(K)
Does this dictionary contains the given key.
Time complexity: O(log(n)).
Declaration
public bool ContainsKey(K key)
Parameters
Type |
Name |
Description |
K |
key |
The key to check.
|
Returns
Type |
Description |
Boolean |
True if this dictionary contains the given key.
|
ElementAt(Int32)
Time complexity: O(log(n))
Declaration
public KeyValuePair<K, V> ElementAt(int index)
Parameters
Type |
Name |
Description |
Int32 |
index |
|
Returns
Type |
Description |
KeyValuePair<K, V> |
|
GetEnumerator()
Declaration
public IEnumerator<KeyValuePair<K, V>> GetEnumerator()
Returns
Type |
Description |
IEnumerator<KeyValuePair<K, V>> |
|
GetEnumeratorDesc()
Declaration
public IEnumerator<KeyValuePair<K, V>> GetEnumeratorDesc()
Returns
Type |
Description |
IEnumerator<KeyValuePair<K, V>> |
|
IndexOf(K)
Time complexity: O(log(n))
Declaration
public int IndexOf(K key)
Parameters
Type |
Name |
Description |
K |
key |
|
Returns
Max()
Declaration
public KeyValuePair<K, V> Max()
Returns
Type |
Description |
KeyValuePair<K, V> |
|
Min()
Time complexity: O(log(n)).
Declaration
public KeyValuePair<K, V> Min()
Returns
Type |
Description |
KeyValuePair<K, V> |
|
NextHigher(K)
Return the next higher key-value pair after given key in this dictionary.
Time complexity: O(log(n)).
Declaration
public KeyValuePair<K, V> NextHigher(K key)
Parameters
Type |
Name |
Description |
K |
key |
|
Returns
Type |
Description |
KeyValuePair<K, V> |
Null if the given key does'nt exist or next key does'nt exist.
|
NextLower(K)
Return the next lower key-value pair before given key in this dictionary.
Time complexity: O(log(n)).
Declaration
public KeyValuePair<K, V> NextLower(K key)
Parameters
Type |
Name |
Description |
K |
key |
|
Returns
Type |
Description |
KeyValuePair<K, V> |
Null if the given key does'nt exist or previous key does'nt exist.
|
Remove(K)
Remove the given key if it exists.
Time complexity: O(log(n)).
Returns the position (index) of the removed key if removed. Otherwise returns -1.
Declaration
Parameters
Type |
Name |
Description |
K |
key |
|
Returns
RemoveAt(Int32)
Remove the element at given index.
Time complexity: O(log(n)).
Declaration
public KeyValuePair<K, V> RemoveAt(int index)
Parameters
Type |
Name |
Description |
Int32 |
index |
|
Returns
Type |
Description |
KeyValuePair<K, V> |
|