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

Source file:

/Core/Loyc.Collections/ALists/BMultiMap.cs

Inheritance diagram for Loyc.Collections.BMultiMap< K, V >:

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< ValueList >	Values `[get]`
	Gets a list of collections of ValueList in this object. More...

Properties inherited from Loyc.Collections.AListBase< K, T >
virtual ListChangingHandler< T, IListSource< T > >	ListChanging
	Event for learning about changes in progress on a list. More...

byte	TreeHeight `[get]`

T	Last `[get]`

T	this[int index] `[get]`

int	ObserverCount `[get]`
	Returns the number of tree observers attached to this list. More...

Properties inherited from Loyc.Collections.ISource< out T >
new int	Count `[get]`
	Gets the number of items in the collection. More...

Properties inherited from Loyc.Collections.ICount
int	Count `[get]`
	Gets the number of items in the collection. More...

Properties inherited from Loyc.Collections.IIsEmpty
bool	IsEmpty `[get]`

Properties inherited from Loyc.Collections.IIndexed< in K, out V >
V	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)
	Tallies the memory use, in bytes, of the entire list including this object, the root node, all child nodes, and all arrays. More...

Public Member Functions inherited from Loyc.Collections.BList< T >
	BList ()
	Initializes an empty BList. More...

	BList (int maxNodeSize)

	BList (int maxLeafSize, int maxInnerSize)

	BList (Func< T, T, int > compareItems)

	BList (Func< T, T, int > compareItems, int maxLeafSize)

	BList (Func< T, T, int > compareItems, int maxLeafSize, int maxInnerSize)
	Initializes an empty BList. More...

	BList (BList< T > items, bool keepListChangingHandlers)

void	Add (T item)

bool	Remove (T item)
	Removes a single instance of the specified item. More...

int	RemoveAll (T item)
	Removes all instances of the specified item. More...

int	Do (AListOperation mode, ref T item)
	Adds, removes, or replaces an item in the list. More...

int	Do (AListOperation mode, T item)

int	AddRange (IEnumerable< T > e)
	Adds a set of items to the list, one at a time. More...

int	RemoveRange (IEnumerable< T > e)
	Removes a set of items from the list, one at a time. More...

int	DoRange (AListOperation mode, IEnumerable< T > e)
	Performs the same operation for each item in a series. Equivalent to calling Do(AListOperation,T) on each item. More...

BList< T >	Clone ()

BList< T >	Clone (bool keepListChangingHandlers)
	Clones a BList. More...

BList< T >	CopySection (int start, int subcount)

BList< T >	RemoveSection (int start, int count)

int	IndexOf (T item)
	Finds the lowest index of an item that is equal to or greater than the specified item. More...

bool	Contains (T item)
	Returns true if the list contains the specified item, and false if not. More...

int	FindLowerBound (T item)

int	FindLowerBound (T item, out bool found)
	Finds the lowest index of an item that is equal to or greater than the specified item. More...

int	FindLowerBound (ref T item)

int	FindLowerBound (ref T item, out bool found)

int	FindUpperBound (T item)
	Finds the index of the first item in the list that is greater than the specified item. More...

int	FindUpperBound (ref T item)

int	IndexOfExact (T item)
	Specialized search function that finds the index of an item that not only compares equal to the specified item according to the comparison function for this collection, but is also equal according to Object.Equals. This function works properly even if duplicate items exist in addition that do NOT compare equal according to Object.Equals. More...

Public Member Functions inherited from Loyc.Collections.AListBase< K, T >
void	RemoveAt (int index)

void	RemoveRange (int index, int amount)

int	RemoveAll (Predicate< T > match)
	Removes all the elements that match the conditions defined by the specified predicate. More...

virtual void	Clear ()

IEnumerable< int >	IndexesOf (T item)
	Returns a sequence of integers that represent the locations where a given item appears in the list. More...

virtual IEnumerable< int >	IndexesOf (T item, int minIndex, int maxIndex)

int	FirstIndexOf (T item, int startIndex, EqualityComparer< T >?comparer=null)
	Scans the list starting at startIndex and going upward, and returns the index of an item that matches the first argument. More...

int	LinearScanFor (T item, int startIndex, EqualityComparer< T >?comparer=null)

void	CopyTo (T[] array, int arrayIndex)

Enumerator	GetEnumerator ()

Enumerator	GetEnumerator (int startIndex)

Enumerator	GetEnumerator (int start, int subcount)

Enumerator	GetEnumerator (int start, int subcount, bool startAtEnd)

T	TryGet (int index, out bool fail)

virtual void	Freeze ()
	Prevents further changes to the list. More...

Slice_< T >	Slice (int start, int length)
	Returns a sub-range of this list. More...

int	GetImmutableCount ()
	Diagnostic method. Returns the number of elements of the list that are located in immutable nodes, which will be copied if modified. Used by the test suite. More...

virtual bool	AddObserver (IAListTreeObserver< K, T > observer)
	Attaches a tree observer to this object. More...

virtual bool	RemoveObserver (IAListTreeObserver< K, T > observer)
	Removes a previously attached tree observer from this list. More...

Public Member Functions inherited from Loyc.Collections.ITryGet< in K, out V >
V	TryGet (K key, out bool fail)
	Gets the item for the specified key or index, and does not throw an exception on failure. More...

Public Member Functions inherited from Loyc.Collections.ICollectionSource< T >
void	CopyTo (T[] array, int arrayIndex)
	Copies the elements of the collection to an Array, starting at a particular array index. More...

Public Member Functions inherited from Loyc.Collections.ICollectionSink< in T >
void	Clear ()

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 Member Functions inherited from Loyc.Collections.BList< T >
	BList (BList< T > original, AListNode< T, T >?section)

override AListNode< T, T >	NewRootLeaf ()

override AListInnerBase< T, T >	SplitRoot (AListNode< T, T > left, AListNode< T, T > right)

Protected Member Functions inherited from Loyc.Collections.AListBase< K, T >
	AListBase (int maxNodeSize)

	AListBase (int maxLeafSize, int maxInnerSize)

	AListBase (AListBase< K, T > items, bool keepListChangingHandlers)
	Cloning constructor. Does not duplicate the observer (IAListTreeObserver{K,T}), if any, because it may not be cloneable. More...

	AListBase (AListBase< K, T > original, AListNode< K, T >?section)
	This is the constructor that CopySection(), which can be defined by derived classes, should call to create a sublist of a list. Used in conjunction with CopySectionHelper(). More...

abstract AListInnerBase< K, T >	SplitRoot (AListNode< K, T > left, AListNode< K, T > right)

virtual Enumerator	NewEnumerator (uint start, uint firstIndex, uint lastIndex)

void	CheckPoint ()

void	AutoThrow ()

void	AutoCreateOrCloneRoot ()

void	AutoSplit (AListNode< K, T >?splitLeft, AListNode< K, T >?splitRight)

void	HandleChangedOrUndersizedRoot (AListNode< K, T > result)

virtual void	ClearInternal (bool forceClear)
	Clears the tree. More...

void	ThrowIndexOutOfRange ()

AListNode< K, T >	CopySectionHelper (int start, int subcount)
	Together with the AListBase{K,T}.AListBase(AListBase{K,T},AListNode{K,T}) constructor, this method helps implement the CopySection() method in derived classes, by cloning a section of the tree. More...

AListNode< K, T >	CopySectionHelper (uint start, uint subcount)

void	SwapHelper (AListBase< K, T > other, bool swapObservers)
	Swaps two ALists. More...

Protected fields
readonly Func< K, K, int >	_compareKeys

readonly Func< V, V, int >	_compareValues

Protected fields inherited from Loyc.Collections.BList< T >
Func< T, T, int >	_compareItems
	Compares two items. See Comparison{T}. More...

Protected fields inherited from Loyc.Collections.AListBase< K, T >
uint	_count

ushort	_version

ushort	_maxLeafSize

byte	_maxInnerSize

byte	_treeHeight

FreezeMode	_freezeMode = FreezeMode.NotFrozen

int	BaseClassSizeInBytes => IntPtr.Size * 5 + (IntPtr.Size <= 4 ? 12 : 16)

Protected static fields
static readonly Func< K, K, int >	DefaultKComparison = Comparer<K>.Default.Compare

static readonly Func< V, V, int >	DefaultVComparison = GetDefaultValueComparison()

static readonly Func< V, V, int >	PretendValuesAreEqual = (a, b) => 0

static readonly Func < KeyValuePair< K, V > , KeyValuePair< K, V >, int >	DefaultPairComparison

Additional Inherited Members
Public fields inherited from Loyc.Collections.AListBase< K, T >
int	Count => (int)_count

bool	IsEmpty => _count == 0

T	First => this[0]

bool	IsFrozen => _freezeMode == FreezeMode.Frozen

AListReverseView< K, T >	ReverseView => new AListReverseView<K

Events inherited from Loyc.Collections.INotifyListChanging< T, TCollection >
ListChangingHandler< T, TCollection >	ListChanging
	Occurs when the collection associated with this interface is about to change. More...

Constructor & Destructor Documentation

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

compareKeys Key comparer, or null to use the default key comparer.

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

compareKeys	Key comparer, or null to use the default key comparer.
compareValues	Value 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

bool Loyc.Collections.BMultiMap< K, V >.AddIfUnique	(	K	key,
		V	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.

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

inline

Finds out whether the specified key is present.

Parameters

key	Key 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.

override long Loyc.Collections.BMultiMap< K, V >.CountSizeInBytes	(	int	sizeOfElement,
		int	sizeOfKey = `8`
	)

virtual

Tallies the memory use, in bytes, of the entire list including this object, the root node, all child nodes, and all arrays.

Parameters

sizeOfElement	The size in bytes of a slot of type T
sizeOfKey	The size in bytes of a key slot. This parameter only has an effect in BDictionary{K, V}. In sorted types, T is the combined size of the key and value, while K is the size of the key by itself. But in BMultiMap{K, V}, BList{T}, the key type is T, so this parameter is ignored. Notably, in BMultiMap, a key-value pair is considered to be the key type.

Returns: Number of bytes of heap used.

If T (or K) is a class, the element (or key) size that you pass in should be IntPtr.Size. Do not include memory used by the class objects themselves, because unused slots are counted in the total.

Reimplemented from Loyc.Collections.BList< T >.

int Loyc.Collections.BMultiMap< K, V >.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.

Parameters

key	The key to find.
value	The first value associated with the specified key, if the key was found, or default(V) if not.
found	Set 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.

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.

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

inline

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

Parameters

key	The 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.

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

inline

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

Parameters

key	Key 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.

int Loyc.Collections.BMultiMap< K, V >.IndexOfExact ( K 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).

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

inline

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

Parameters

key	The key to remove.
maxToRemove	Maximum number of items to remove.

Returns: The number of items removed.

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

inline

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

Parameters

key	The key to remove.

Returns: The number of items removed.

References Loyc.Collections.Remove.

bool Loyc.Collections.BMultiMap< K, V >.RemoveAny ( K 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.

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

inline

Finds a value associated with the specified key.

Parameters

key	Key to find
value	Set 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.

Member Data Documentation

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

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

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

get

Gets a list of collections of ValueList in this object.

Remarks

Nested classes

Properties

Public Member Functions

Protected Member Functions

Protected fields

Protected static fields

Additional Inherited Members

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Property Documentation