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

An sorted dictionary that allows multiple values to be associated with a single key. More...


Source file:
Inheritance diagram for Loyc.Collections.BMultiMap< K, V >:
Loyc.Collections.IIndexed< K, BMultiMap< K, V >.ValueList >

Remarks

An sorted dictionary that allows multiple values to be associated with a single key.

The keys must be comparable. By default, the values must also be comparable, but if the values do not support IComparable, you can set the comparison function to (a,b) => 0 to pretend all values are equal. A shorthand way to do this is to call the constructor with parameters of (null, null) which means "use default key comparison and treat all values as equal". If you do this, you should avoid calling this[key].Remove(value) or this[key].Contains(value), or the Remove method in the base class, since these methods will treat any value as a match.

An article about the BList classes is available.

Often when people want to be able to associate multiple values with a single key, they use a Dictionary with values of type List<T>. This approach is very inefficient (in terms of memory use) if most keys are only associated with one or two values; this class solves the problem using a single sorted B+ tree for all keys and all values. It requires, however, that both the keys and values are totally ordered (i.e. are sortable).

By default, keys and values are sorted using Comparer<T>.Default. This will work provided that the keys and values both implement the IComparable<T> interface. If they don't, you can pass custom comparison functions to the constructor instead (one comparison function for keys, and a second one for values).

Since it is derived from BList<T>, this class enjoys the space efficiency of a B+ tree and capabilities of a AListBase<K,V>, although it tends to be slower than Dictionary<K,V>.

Nested classes

struct  ValueList
 Represents the set of values associated with a particular key in a BMultiMap<K,V> collection. More...
 

Properties

ValueList this[K key] [get]
 Gets a collection associated with the specified key. More...
 
IEnumerable< K > Keys [get]
 
IEnumerable< ValueListValues [get]
 Gets a list of collections of ValueList in this object. More...
 
- Properties inherited from Loyc.Collections.IIndexed< K, BMultiMap< K, V >.ValueList >
this[K key] [get]
 Gets the value associated with the specified key. More...
 

Public Member Functions

 BMultiMap (int maxNodeSize)
 
 BMultiMap (int maxLeafSize, int maxInnerSize)
 
 BMultiMap (Func< K, K, int > compareKeys)
 Initializes the map with the specified key-comparer and default value comparer. This constructor can only be used if values are comparible with IComparable<V>. More...
 
 BMultiMap (Func< K, K, int > compareKeys, Func< V, V, int > compareValues)
 Initializes the map with the specified key and value comparers. More...
 
 BMultiMap (Func< K, K, int > compareKeys, Func< V, V, int > compareValues, int maxNodeSize)
 
 BMultiMap (Func< K, K, int > compareKeys, Func< V, V, int > compareValues, int maxLeafSize, int maxInnerSize)
 
bool AddIfUnique (K key, V value)
 Adds a key-value pair if there is not already a pair that compares equal to the new one. More...
 
bool ContainsKey (K key)
 Finds out whether the specified key is present. More...
 
int FirstIndexOf (K key)
 Finds the lowest index of an item with the specified key. More...
 
bool RemoveAny (K key)
 Removes one pair from the collection that matches the specified key. More...
 
int Remove (K key, int maxToRemove)
 Removes up to a specified number of items from the collections that have the specified key. More...
 
int RemoveAll (K key)
 Removes all the items from the collection whose key compares equal to the specified key. More...
 
bool TryGetValue (K key, out V value)
 Finds a value associated with the specified key. More...
 
void Add (K key, V value)
 
int FindLowerBound (K key)
 
int FindLowerBound (K key, out bool found)
 
int FindLowerBound (K key, out V value, out bool found)
 Finds the lowest index of an item that is equal to or greater than the specified item. More...
 
int FindLowerBound (ref K key, out V value, out bool found)
 
int FindUpperBound (K key)
 Finds the index of the first item in the list whose key is greater than the specified key. More...
 
int FindLowerBoundExact (ref K key, out V value, out bool found)
 Does the same thing as IndexOfExact, but with the same set of arguments as FindLowerBound including the value associated with the matching key. More...
 
int IndexOfExact (K key)
 Specialized search function that finds the first index of an item whose key compares equal to the specified key, not only according to the comparison function for this collection, but also according to Object.Equals. This function works properly even if duplicate keys exist in addition that do NOT compare equal according to Object.Equals. More...
 
override long CountSizeInBytes (int sizeOfElement, int sizeOfKey=8)
 

Protected Member Functions

int CompareKeyAndValue (KeyValuePair< K, V > a, KeyValuePair< K, V > b)
 
int CompareKeysOnly (KeyValuePair< K, V > a, KeyValuePair< K, V > b)
 
int UpperBoundCompare (KeyValuePair< K, V > candidate, KeyValuePair< K, V > searchKey)
 

Protected fields

readonly Func< K, K, int > _compareKeys
 
readonly Func< V, V, int > _compareValues
 

Protected static fields

static readonly Func< K, K, int > DefaultKComparison = Comparer<K>.Default.Compare
 
static readonly Func< V, V, int > DefaultVComparison = Comparer<V>.Default.Compare
 
static readonly Func< V, V, int > PretendValuesAreEqual = (a, b) => 0
 
static readonly Func< KeyValuePair< K, V >, KeyValuePair< K, V >, int > DefaultPairComparison
 

Constructor & Destructor Documentation

◆ BMultiMap() [1/2]

Loyc.Collections.BMultiMap< K, V >.BMultiMap ( Func< K, K, int >  compareKeys)
inline

Initializes the map with the specified key-comparer and default value comparer. This constructor can only be used if values are comparible with IComparable<V>.

Parameters
compareKeysKey comparer, or null to use the default key comparer.

◆ BMultiMap() [2/2]

Loyc.Collections.BMultiMap< K, V >.BMultiMap ( Func< K, K, int >  compareKeys,
Func< V, V, int >  compareValues 
)
inline

Initializes the map with the specified key and value comparers.

Parameters
compareKeysKey comparer, or null to use the default key comparer.
compareValuesValue comparer, or null to pretend all values are equal. It is useful to use null for this parameter when V does not implement IComparable. However, keep in mind that the Contains() and Remove() methods won't work in the normal way when all values are considered equal!

Member Function Documentation

◆ AddIfUnique()

bool Loyc.Collections.BMultiMap< K, V >.AddIfUnique ( key,
value 
)
inline

Adds a key-value pair if there is not already a pair that compares equal to the new one.

Returns
True if the pair was added, or false if it already existed.

◆ ContainsKey()

bool Loyc.Collections.BMultiMap< K, V >.ContainsKey ( key)
inline

Finds out whether the specified key is present.

Parameters
keyKey to search for
Returns
Returns true if the dictionary contains at least one key- value pair in which the key compares equal to the specified key.

◆ FindLowerBound()

int Loyc.Collections.BMultiMap< K, V >.FindLowerBound ( key,
out V  value,
out bool  found 
)
inline

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

Parameters
keyThe key to find.
valueThe first value associated with the specified key, if the key was found, or default(V) if not.
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 key is greater than the keys of all items in the list.

◆ FindLowerBoundExact()

int Loyc.Collections.BMultiMap< K, V >.FindLowerBoundExact ( ref K  key,
out V  value,
out bool  found 
)
inline

Does the same thing as IndexOfExact, but with the same set of arguments as FindLowerBound including the value associated with the matching key.

Returns
Lowest index of a matching item if found, or the same return value as FindLowerBound if not found.

Referenced by Loyc.Collections.BMultiMap< Loyc.Collections.Impl.AListNode< K, T >, Loyc.Collections.Impl.AListInnerBase< K, T > >.IndexOfExact(), and Loyc.Collections.Impl.AListIndexer< int, T >.ReconstructIndex().

◆ FindUpperBound()

int Loyc.Collections.BMultiMap< K, V >.FindUpperBound ( key)
inline

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

Parameters
keyThe key 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.Collections.BMultiMap< Loyc.Collections.Impl.AListNode< K, T >, Loyc.Collections.Impl.AListInnerBase< K, T > >.Remove().

◆ FirstIndexOf()

int Loyc.Collections.BMultiMap< K, V >.FirstIndexOf ( key)
inline

Finds the lowest index of an item with the specified key.

Parameters
keyKey to search for
Returns
The index of the item that was found, or -1 if there is no such item.

This method is like FindLowerBound except that it returns -1 if the key was not found.

◆ IndexOfExact()

int Loyc.Collections.BMultiMap< K, V >.IndexOfExact ( key)
inline

Specialized search function that finds the first index of an item whose key compares equal to the specified key, not only according to the comparison function for this collection, but also according to Object.Equals. This function works properly even if duplicate keys exist in addition that do NOT compare equal according to Object.Equals.

This method is useful when the items in this collection are sorted by hashcode (which is usually a bad idea, but occasionally useful).

Referenced by Loyc.Collections.Impl.AListIndexer< int, T >.NodeRemoved(), and Loyc.Collections.Impl.AListIndexer< int, T >.VerifyCorrectness().

◆ Remove()

int Loyc.Collections.BMultiMap< K, V >.Remove ( key,
int  maxToRemove 
)
inline

Removes up to a specified number of items from the collections that have the specified key.

Parameters
keyThe key to remove.
maxToRemoveMaximum number of items to remove.
Returns
The number of items removed.

Referenced by Loyc.Collections.BMultiMap< Loyc.Collections.Impl.AListNode< K, T >, Loyc.Collections.Impl.AListInnerBase< K, T > >.RemoveAll().

◆ RemoveAll()

int Loyc.Collections.BMultiMap< K, V >.RemoveAll ( key)
inline

Removes all the items from the collection whose key compares equal to the specified key.

Parameters
keyThe key to remove.
Returns
The number of items removed.

◆ RemoveAny()

bool Loyc.Collections.BMultiMap< K, V >.RemoveAny ( key)
inline

Removes one pair from the collection that matches the specified key.

Returns
True if a pair was removed, or false if the key was not found.

◆ TryGetValue()

bool Loyc.Collections.BMultiMap< K, V >.TryGetValue ( key,
out V  value 
)
inline

Finds a value associated with the specified key.

Parameters
keyKey to find
valueSet to the first (lowest) value associated with the key, or default(V) if the key was not found.
Returns
True if the key was found, false if not.

Referenced by LeMP.Compiler.ProcessArguments().

Member Data Documentation

◆ DefaultPairComparison

readonly Func<KeyValuePair<K, V>, KeyValuePair<K, V>, int> Loyc.Collections.BMultiMap< K, V >.DefaultPairComparison
staticprotected
Initial value:
= (a, b) =>
{
int c = DefaultKComparison(a.Key, b.Key);
if (c != 0)
return c;
return DefaultVComparison(a.Value, b.Value);
}

Property Documentation

◆ this[K key]

ValueList Loyc.Collections.BMultiMap< K, V >.this[K key]
get

Gets a collection associated with the specified key.

Parameters
key
Returns
A synthetic collection associated with the specified key.

This property always succeeds and does not actually search for the key you requested. It returns an object that represents the set of values associated with a key, but those values are not actually retrieved from the collection until you enumerate the collection.

See also
ValueList

◆ Values

IEnumerable<ValueList> Loyc.Collections.BMultiMap< K, V >.Values
get

Gets a list of collections of ValueList in this object.