Enhanced C#
Language of your choice: library documentation
Properties | Public Member Functions | Protected Member Functions | Protected fields | Protected static fields | List of all members
Loyc.Collections.BDictionary< K, V > Class Template Reference

An sorted dictionary that is efficient for all operations and offers indexed access to its list of key-value pairs. More...


Source file:
Inheritance diagram for Loyc.Collections.BDictionary< K, V >:

Remarks

An sorted dictionary that is efficient for all operations and offers indexed access to its list of key-value pairs.

An article about the BList classes is available.

The keys must be comparable (ordered); if the type does not implement IComparable or IComparable(T), you must provide a Comparison(T) delegate to perform comparisons.

This class offers the following additional features beyond what's offered by the standard SortedDictionary{T} class: indexed access, a find-nearest- key operation called FindLowerBound (similar to lower_bound in C++), observability, fast cloning, freezability, fast cloning of an arbitrary range of items in a large collection, enumeration of part of the list (not just the entire list), and reverse enumeration, and a few compound operations.

Duplicate keys are not allowed in a BDictionary. If you would like to be able to associate multiple values with a single key, use BMultiMap<K,V> instead.

If you need to store only keys, not values, use BList<K> instead (but note that BList does allow duplicate keys).

Properties

ICollection< K > Keys [get]
 
ICollection< V > Values [get]
 
this[K key] [get, set]
 
this[K key, V defaultValue] [get]
 

Public Member Functions

 BDictionary ()
 Initializes an empty BList. More...
 
 BDictionary (int maxLeafSize)
 
 BDictionary (int maxLeafSize, int maxInnerSize)
 
 BDictionary (Func< K, K, int > compareKeys)
 
 BDictionary (Func< K, K, int > compareKeys, int maxLeafSize)
 
 BDictionary (Func< K, K, int > compareKeys, int maxLeafSize, int maxInnerSize)
 Initializes an empty BDictionary. More...
 
 BDictionary (BDictionary< K, V > items, bool keepListChangingHandlers)
 
void Add (KeyValuePair< K, V > item)
 
int IndexOf (KeyValuePair< K, V > item)
 
bool Contains (KeyValuePair< K, V > item)
 
bool Remove (KeyValuePair< K, V > item)
 
int FindLowerBound (K key)
 Finds the lowest index of an item with a key that is equal to or greater than the specified key. More...
 
int FindLowerBound (K key, out bool found)
 
int FindLowerBound (ref K key)
 
int FindLowerBound (ref K key, out bool found)
 
int IndexOf (K key)
 
int FindUpperBound (K key)
 Finds the index of the first item in the list that is greater than the specified item. More...
 
int FindUpperBound (ref K key)
 
void AddRange (IEnumerable< KeyValuePair< K, V >> e)
 
int RemoveRange (IEnumerable< KeyValuePair< K, V >> e)
 
int RemoveRange (IEnumerable< K > e)
 
void Add (K key, V value)
 
bool ContainsKey (K key)
 
bool Remove (K key)
 
bool TryGetValue (K key, out V value)
 
BDictionary< K, V > Clone ()
 
BDictionary< K, V > Clone (bool keepListChangingHandlers)
 Clones a BDictionary. More...
 
BDictionary< K, V > CopySection (int start, int subcount)
 
BDictionary< K, V > RemoveSection (int start, int count)
 
bool AddIfNotPresent (K key, V value)
 Adds the specified pair only if the key is not already present in the dictionary. More...
 
bool AddIfNotPresent (K key, ref V value)
 
bool AddIfNotPresent (ref K key, ref V value)
 
bool SetAndGetOldValue (K key, ref V value)
 Associates the specified value with the specified key, while getting the old value if one exists. More...
 
bool SetAndGetOldValue (ref K key, ref V value)
 
bool ReplaceIfPresent (K key, V value)
 Replaces the value associated with a specified key, if it already exists in the dictionary. More...
 
bool ReplaceIfPresent (K key, ref V value)
 
bool ReplaceIfPresent (ref K key, ref V value)
 

Protected Member Functions

 BDictionary (BDictionary< K, V > original, AListNode< K, KeyValuePair< K, V >> section)
 
override AListNode< K, KeyValuePair< K, V > > NewRootLeaf ()
 
override AListInnerBase< K, KeyValuePair< K, V > > SplitRoot (AListNode< K, KeyValuePair< K, V >> left, AListNode< K, KeyValuePair< K, V >> right)
 
int CompareToKey (KeyValuePair< K, V > item, K key)
 

Protected fields

Func< K, K, int > _compareKeys
 

Protected static fields

static readonly Func< K, K, int > DefaultComparison = Comparer<K>.Default.Compare
 

Constructor & Destructor Documentation

Initializes an empty BList.

By default, elements of the list will be compared using Comparer<T>.Default.Compare.

Loyc.Collections.BDictionary< K, V >.BDictionary ( Func< K, K, int >  compareKeys,
int  maxLeafSize,
int  maxInnerSize 
)
inline

Initializes an empty BDictionary.

Parameters
compareKeysA method that compares two items and returns a negative number (typically -1) if the first item is smaller than the second item, 0 if it is equal, and a positive number (typically 1) if it is greater.
maxLeafSizeMaximum number of elements to place in a leaf node of the B+ tree.
maxInnerSizeMaximum number of elements to place in an inner node of the B+ tree.

If present, the compareKeys parameter must be a "Func" delegate instead of the more conventional Comparison<T> delegate for an obscure design decision for the benefit of BList<T>. You should not notice any difference between the two, but the stupid .NET type system insists that the two types are not compatible. So, if (for some reason) you already happen to have a Comparison<K> delegate, you must explicitly convert it to a Func delegate with code such as "new Func&lt;K,K,int>(comparisonDelegate)".

If you leave out the compareKeys parameter, Comparer<K>.Default.Compare will be used by default.

See the documentation of AListBase<K,T> for a discussion about node sizes.

An empty BDictionary is created with no root node, so it consumes much less memory than a BDictionary with a single element.

Loyc.Collections.BDictionary< K, V >.BDictionary ( BDictionary< K, V >  items,
bool  keepListChangingHandlers 
)
inline
Parameters
itemsA list of items to be cloned.

Member Function Documentation

bool Loyc.Collections.BDictionary< K, V >.AddIfNotPresent ( key,
value 
)
inline

Adds the specified pair only if the key is not already present in the dictionary.

Parameters
keyKey to search for or add. If this parameter is passed by reference and a matching pair exists already, this method sets it to the existing key instance.
valueValue to search for or add. If this parameter is passed by reference and a matching pair exists already, this method sets it to the existing value.
Returns
True if the new pair was added, false if not.

This method has no effect if the key is already present.

BDictionary<K, V> Loyc.Collections.BDictionary< K, V >.Clone ( bool  keepListChangingHandlers)
inline

Clones a BDictionary.

Parameters
keepListChangingHandlersIf true, ListChanging handlers will be copied from the existing list of items to the new collection. Note: if it exists, the NodeObserver is never copied. AListBase<K,T>.ObserverCount will be 0 in the new list.

Cloning is performed in O(1) time by marking the tree root as frozen and sharing it between the two lists. However, the new dictionary itself will not be frozen, even if the original dictionary was marked as frozen. Instead, nodes will be copied on demand when you modify the new dictionary.

int Loyc.Collections.BDictionary< K, V >.FindLowerBound ( key)
inline

Finds the lowest index of an item with a key that is equal to or greater than the specified key.

Parameters
keyThe key to find. If passed by reference, when this method returns, key is set to the key of the item that was found, or to the next greater item if the item was not found. If the item passed in is higher than all items in the list, it will be left unchanged when this method returns.
foundSet to true if the item was found, false if not.
Returns
The index of the item that was found, or of the next greater item, or Count if the given item is greater than all items in the list.
int Loyc.Collections.BDictionary< K, V >.FindUpperBound ( key)
inline

Finds the index of the first item in the list that is greater than the specified item.

Parameters
keyThe item to find. If passed by reference, when this method returns, item is set to the next greater item than the item you searched for, or left unchanged if there is no greater item.
Returns
The index of the next greater item that was found, or Count if the given item is greater than all items in the list.

Referenced by Loyc.Syntax.LineRemapper.Remap().

bool Loyc.Collections.BDictionary< K, V >.ReplaceIfPresent ( key,
value 
)
inline

Replaces the value associated with a specified key, if it already exists in the dictionary.

Parameters
keyKey to replace. If this parameter is passed by reference and a matching pair existed, this method sets it to the old key instance.
valueNew value to associate with the key. If this parameter is passed by reference and a matching pair existed, this method sets it to the old value.
Returns
True if the key was found and the pair was replaced, false if it was not found.

This method has no effect if the key was not already present.

bool Loyc.Collections.BDictionary< K, V >.SetAndGetOldValue ( key,
ref V  value 
)
inline

Associates the specified value with the specified key, while getting the old value if one exists.

Parameters
keyKey to search for or add. If this parameter is passed by reference and a matching pair existed already, this method sets it to the old key instance.
valueValue to search for or add. If this parameter is passed by reference and a matching pair existed already, this method sets it to the old value.
Returns
True if the new pair was added, false if it was replaced.