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

Source file:

/Core/Loyc.Collections/ALists/BDictionary.cs

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]`

V	this[K key] `[get, set]`

V	this[K key, V defaultValue] `[get]`

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

Properties inherited from Loyc.Collections.IDictionaryEx< K, V >
new V	this[K key] `[get, set]`

new ICollection< K >	Keys `[get]`

new ICollection< V >	Values `[get]`

Properties inherited from Loyc.Collections.IIndexedSink< in K, in V >
V	this[K key] `[set]`

Properties inherited from Loyc.Collections.IMIndexed< in K, V >
new V	this[K key] `[get, set]`
	Gets the value associated with the specified key. More...

Public Member Functions
	BDictionary ()
	Initializes an empty BList. More...

	BDictionary (int maxNodeSize)

	BDictionary (int maxLeafSize, int maxInnerSize)

	BDictionary (Func< K, K, int > compareKeys)

	BDictionary (Func< K, K, int > compareKeys, int maxNodeSize)

	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)

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

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	AddRange (IEnumerable< KeyValuePair< K, V >> e, DictEditMode mode)
	Merges the contents of the specified sequence into this map. More...

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)

Maybe< V >	GetAndRemove (K key)
	TODO: TEST THIS!! More...

bool	GetAndEdit (ref K key, ref V value, DictEditMode mode)
	Combines a get and change operation into a single method call. You rarely need to call this method directly; the following extension methods are based on it: DictionaryExt.SwapIfPresent, DictionaryExt.AddIfNotPresent, DictionaryExt.AddOrGetExisting, DictionaryExt.ReplaceIfPresent, DictionaryExt.SetAndGet. More...

bool	AddIfNotPresent (K key, ref V value)

bool	TryAdd (K key, ref V value)

bool	AddIfNotPresent (ref K key, ref V value)
	Add a pair if it is not alredy present, or get its value if it is. More...

bool	TryAdd (ref K key, ref V value)

bool	AddIfNotPresent (ref KeyValuePair< K, V > pair)

bool	SetAndGetOldValue (ref K key, ref V value)

bool	GetAndSet (ref K key, ref V value)
	Associates the specified value with the specified key, while getting the old value if one exists. More...

bool	SetAndGet (ref K key, ref V value)

bool	SetAndGetOldValue (K key, ref V value)

bool	SetAndGetOldValue (ref KeyValuePair< K, V > pair)

bool	ReplaceIfPresent (ref KeyValuePair< K, V > pair)

bool	ReplaceIfPresent (K key, ref V value)

bool	ReplaceIfPresent (ref K key, ref V value)
	Replaces the value associated with a specified key, if it already exists in the dictionary. More...

override long	CountSizeInBytes (int sizeOfPair, 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.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.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.IContains< in T >
bool	Contains (T item)
	Returns true if and only if the collection contains the specified item. More...

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

bool	Remove (T item)

Public Member Functions inherited from Loyc.Collections.IAdd< in T >
void	Add (T item)

Public Member Functions inherited from Loyc.Collections.IAddRange< in T >
void	AddRange (IEnumerable< T > e)

void	AddRange (IReadOnlyCollection< T > s)

Public Member Functions inherited from Loyc.Collections.IDictionaryEx< K, V >
new void	Clear ()

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 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
Func< K, K, int >	_compareKeys

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 >	DefaultComparison = Comparer<K>.Default.Compare

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.BDictionary< K, V >.BDictionary ( )

inline

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

compareKeys	A 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.
maxLeafSize	Maximum number of elements to place in a leaf node of the B+ tree.
maxInnerSize	Maximum 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<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

items A list of items to be cloned.

Member Function Documentation

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

inline

Add a pair if it is not alredy present, or get its value if it is.

Returns: True if the pair was added, false if it was retrieved.

int Loyc.Collections.BDictionary< K, V >.AddRange	(	IEnumerable< KeyValuePair< K, V >>	data,
		DictEditMode	mode
	)

inline

Merges the contents of the specified sequence into this map.

Parameters

data	Pairs to merge in. Duplicates are allowed; if the `ReplaceIfPresent` bit is set in `mode`, later values take priority over earlier values, otherwise earlier values take priority.
mode	Specifies how to combine the collections.

Returns: The number of pairs that did not already exist in the collection. if the AddIfNotPresent bit is set on mode, this is the number of new pairs added.

See also: DictionaryExt.AddRange{K, V}(IDictionary{K, V}, IEnumerable{KeyValuePair{K, V}})

Implements Loyc.Collections.IDictionaryEx< K, V >.

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

inline

Clones a BDictionary.

Parameters

keepListChangingHandlers If 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.

override long Loyc.Collections.BDictionary< 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.AListBase< K, T >.

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

inline

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

Parameters

key	The 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.
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 item is greater than all items in the list.

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

inline

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

Parameters

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

bool Loyc.Collections.BDictionary< K, V >.GetAndEdit	(	ref K	key,
		ref V	value,
		DictEditMode	mode
	)

inline

Combines a get and change operation into a single method call. You rarely need to call this method directly; the following extension methods are based on it: DictionaryExt.SwapIfPresent, DictionaryExt.AddIfNotPresent, DictionaryExt.AddOrGetExisting, DictionaryExt.ReplaceIfPresent, DictionaryExt.SetAndGet.

Parameters

key	Specifies the key that you want to search for in the map. Some implementations will update the key with the version of it found in the dictionary (although the new key is "equal" to the old key, it may be a different object); otherwise the key is left unchanged.
value	If the key is found, the old value is saved in this parameter. Otherwise, it is left unchanged.
mode	The specific behavior of this method depends on this. See DictEditMode to understand its effect.

Returns: True if the pair's key ALREADY existed, false if not.

This method exists because some collections can optimize certain combinations of operations, avoiding the two traversals through the data structure that would be required by the IDictionary interface.

This method shall not throw when the key is null, unless the AddIfNotPresent bit is set in mode and the dictionary does not support a null key.

See also: DictionaryExt.AddIfNotPresent

Implements Loyc.Collections.IDictionaryEx< K, V >.

Maybe<V> Loyc.Collections.BDictionary< K, V >.GetAndRemove ( K key )

inline

TODO: TEST THIS!!

Implements Loyc.Collections.IDictionaryEx< K, V >.

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

inline

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

Parameters

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

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

inline

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

Parameters

key	Key to find. If a matching key existed, this method changes this parameter to the old stored key.
value	Value to associate with the key. On exit, this is changed to the old value or left unchanged if the key was not found.

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.

Remarks

Properties

Public Member Functions

Protected Member Functions

Protected fields

Protected static fields

Additional Inherited Members

Constructor & Destructor Documentation

Member Function Documentation