An sorted in-memory list that is efficient for all operations and offers indexed access to its list. More...

Source file:

/Core/Loyc.Collections/ALists/BList.cs

Inheritance diagram for Loyc.Collections.BList< T >:

Remarks

An sorted in-memory list that is efficient for all operations and offers indexed access to its list.

An article about the BList classes is available.

When you need a sorted list of items, there's nothing quite like a BList. BList offers numerous features that none of the standard .NET collections can offer:

O(log N) efficiency for all standard list operations (Add, Remove, IndexOf, this[]) plus and O(1) fast cloning and O(1)-per-element enumeration.
Changes can be observed through the AListBase<K,T>.ListChanging event. The performance penalty for this feature is lower than for the standard ObservableCollection{T} class.
Changes to the tree structure can be observed too (see IAListTreeObserver<K,T>).
The list can be frozen with AListBase<K,T>.Freeze, making it read-only.
FindLowerBound and FindUpperBound operations that find the nearest item equal to or greater than a specified item.
A reversed view of the list is available through the AListBase<K,T>.ReverseView property, and the list can be enumerated backwards, also in O(1) time per element..
A BList normally uses less memory than a SortedDictionary<K,V> or a hashtable such as HashSet<T> or Dictionary<K,V>.
Other features inherited from AListBase<T>

Please note, however, that BList<T> is generally slower than Dictionary<K,V> and HashSet<T>, so you should only use it when you need a sorted list of items, or when you need its special features such as FindLowerBound or observability.

Caution: items must not be modified in a way that affects their sort order after they are added to the list. If the list ever stops being sorted, it will malfunction, as it will no longer be possible to find some of the items.

Public Member Functions
	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...

override long	CountSizeInBytes (int sizeOfElement, int sizeOfKey=8)

Public Member Functions inherited from Loyc.Collections.IListSource< T >
IRange< T >	Slice (int start, int count=int.MaxValue)
	Returns a sub-range of 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< 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< T >
void	Clear ()

bool	Remove (T item)

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

void	AddRange (IReadOnlyCollection< T > s)

Protected Member Functions
	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 fields
Func< T, T, int >	_compareItems
	Compares two items. See Comparison<T>. More...

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

Constructor & Destructor Documentation

◆ BList() [1/3]

Loyc.Collections.BList< T >.BList ( )

inline

Initializes an empty BList.

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

◆ BList() [2/3]

Loyc.Collections.BList< T >.BList	(	Func< T, T, int >	compareItems,
		int	maxLeafSize,
		int	maxInnerSize
	)

inline

Initializes an empty BList.

Parameters

compareItems	A method that compares two items and returns -1 if the first item is smaller than the second item, 0 if it is equal, and 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 technical reason (specifically, it is the type required by AListSingleOperation<K,T>.CompareToKey). 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<T> delegate, you must explicitly convert it to a Func delegate with code such as "new Func<T,T,int>(comparisonDelegate)".

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

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

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

References Loyc.Collections.BList< T >._compareItems.

◆ BList() [3/3]

Loyc.Collections.BList< T >.BList	(	BList< T >	items,
		bool	keepListChangingHandlers
	)

inline

Parameters

items A list of items to be cloned.

References Loyc.Collections.BList< T >._compareItems.

Member Function Documentation

◆ AddRange()

int Loyc.Collections.BList< T >.AddRange ( IEnumerable< T > e )

inline

Adds a set of items to the list, one at a time.

Parameters

e	A list of items to be added.

Returns: Returns the number of items that were added.

See also: DoRange

References Loyc.Collections.BList< T >.DoRange().

◆ Clone()

BList<T> Loyc.Collections.BList< T >.Clone ( bool keepListChangingHandlers )

inline

Clones a BList.

Parameters

keepListChangingHandlers If true, ListChanging handlers will be copied from the existing list of items to the new list. Note: if it exists, the NodeObserver is never copied. AListBase<K,T>.ObserverCount will be zero 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 list itself will not be frozen, even if the original list was marked as frozen. Instead, nodes will be copied on demand when you modify the new list.

◆ Contains()

bool Loyc.Collections.BList< T >.Contains ( T item )

inline

Returns true if the list contains the specified item, and false if not.

References Loyc.Collections.BList< T >.IndexOf().

◆ Do()

int Loyc.Collections.BList< T >.Do	(	AListOperation	mode,
		ref T	item
	)

inline

Adds, removes, or replaces an item in the list.

Parameters

mode	Indicates the operation to perform.
item	An item to be added or removed in the list. If the item is passed by reference, and a matching item existed in the tree already, this method returns the old version of the item via this parameter.

Returns: Returns the change in Count: 1 if the item was added, -1 if the item was removed, and 0 if the item replaced an existing item or if nothing happened.

References Loyc.Collections.BList< T >._compareItems.

Referenced by Loyc.Collections.BList< T >.Remove(), and Loyc.Collections.BList< T >.RemoveAll().

◆ DoRange()

int Loyc.Collections.BList< T >.DoRange	(	AListOperation	mode,
		IEnumerable< T >	e
	)

inline

Performs the same operation for each item in a series. Equivalent to calling Do(AListOperation,T) on each item.

Parameters

mode	Indicates the operation to perform.
e	A list of items to act upon.

Returns: Returns the change in Count: positive if items were added, negative if items were removed, and 0 if all items were unchanged or replaced.

References Loyc.Collections.BList< T >._compareItems.

Referenced by Loyc.Collections.BList< T >.AddRange(), and Loyc.Collections.BList< T >.RemoveRange().

◆ FindLowerBound()

int Loyc.Collections.BList< T >.FindLowerBound	(	T	item,
		out bool	found
	)

inline

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

Parameters

item	The item to find. If passed by reference, when this method returns, item is set to 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.

References Loyc.Collections.BList< T >._compareItems.

◆ FindUpperBound()

int Loyc.Collections.BList< T >.FindUpperBound ( T item )

inline

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

Parameters

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

References Loyc.Collections.BList< T >._compareItems.

◆ IndexOf()

int Loyc.Collections.BList< T >.IndexOf ( T item )

inline

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

Parameters

item	Item to find.

Returns: The lower-bound index, or Count if the item is greater than all items in the list.

References Loyc.Collections.BList< T >._compareItems.

Referenced by Loyc.Collections.BList< T >.Contains().

◆ IndexOfExact()

int Loyc.Collections.BList< T >.IndexOfExact ( T item )

inline

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.

This method is useful when the items in this collection are sorted by hashcode, or when they are sorted by key but not sorted by value. In such cases, two items may be equal according to the comparison function but unequal in reality.

Implementation note: this method does a scan across the equal items to find the correct one, unlike the search technique controlled by AListSingleOperation<K,T>.RequireExactMatch, which is not guaranteed to work in case of duplicates.

References Loyc.Collections.BList< T >._compareItems, and Loyc.Collections.BList< T >.FindLowerBound().

◆ Remove()

bool Loyc.Collections.BList< T >.Remove ( T item )

inline

Removes a single instance of the specified item.

References Loyc.Collections.BList< T >.Do().

◆ RemoveAll()

int Loyc.Collections.BList< T >.RemoveAll ( T item )

inline

Removes all instances of the specified item.

Parameters

item	Item to remove

Returns: The number of instances removed (0 if none).

This method is not optimized. It takes twice as long as Remove(T) if there is only one instance, because the tree is searched twice.

References Loyc.Collections.BList< T >.Do().

◆ RemoveRange()

int Loyc.Collections.BList< T >.RemoveRange ( IEnumerable< T > e )

inline

Removes a set of items from the list, one at a time.

Parameters

e	A list of items to be removed.

Returns: Returns the number of items that were found and removed.

See also: DoRange

References Loyc.Collections.BList< T >.DoRange().

Member Data Documentation

◆ _compareItems

Func<T, T, int> Loyc.Collections.BList< T >._compareItems

protected

Compares two items. See Comparison<T>.

Not marked readonly because the derived class constructor for BMultiMap needs to change it.

Referenced by Loyc.Collections.BList< T >.BList(), Loyc.Collections.BList< T >.Do(), Loyc.Collections.BList< T >.DoRange(), Loyc.Collections.BList< T >.FindLowerBound(), Loyc.Collections.BList< T >.FindUpperBound(), Loyc.Collections.BList< T >.IndexOf(), and Loyc.Collections.BList< T >.IndexOfExact().

Remarks

Public Member Functions

Protected Member Functions

Protected fields

Additional Inherited Members

Constructor & Destructor Documentation

◆ BList() [1/3]

◆ BList() [2/3]

◆ BList() [3/3]

Member Function Documentation

◆ AddRange()

◆ Clone()

◆ Contains()

◆ Do()

◆ DoRange()

◆ FindLowerBound()

◆ FindUpperBound()

◆ IndexOf()

◆ IndexOfExact()

◆ Remove()

◆ RemoveAll()

◆ RemoveRange()

Member Data Documentation

◆ _compareItems