Enhanced C#
Language of your choice: library documentation

Documentation moved to ecsharp.net

GitHub doesn't support HTTP redirects, so you'll be redirected in 3 seconds.

 All Classes Namespaces Functions Variables Enumerations Enumerator Properties Events Pages
Public Member Functions | Protected Member Functions | Protected fields | List of all members
Loyc.Collections.BList< T > Class Template Reference

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


Source file:
Inheritance diagram for Loyc.Collections.BList< T >:
Loyc.Collections.AListBase< K, T > Loyc.Collections.IListSource< out T > Loyc.Collections.ICollectionEx< T > Loyc.Collections.IAddRange< T > Loyc.ICloneable< out T > Loyc.Collections.ICount Loyc.Collections.IIsEmpty Loyc.Collections.IAddRange< T > Loyc.Collections.ISinkCollection< T > Loyc.Collections.ICollectionAndReadOnly< T > Loyc.Collections.INotifyListChanging< T > Loyc.Collections.IListSource< out T > Loyc.Collections.INotifyListChanging< T > Loyc.Collections.IListSource< out T > Loyc.Collections.BMultiMap< K, V > Loyc.Collections.BMultiMap< K, V >.ValueList Loyc.Collections.BMultiMap< K, V >.ValueList

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:

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 maxLeafSize)
 
 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)
 Finds the lowest index of an item that is equal to or greater than the specified item. More...
 
int FindLowerBound (T item, out bool found)
 
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 LinearScanFor (T item, int startIndex, EqualityComparer< T > comparer)
 Scans the list starting at startIndex and going upward, and returns the index of an item that matches the first argument. More...
 
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)
 
TryGet (int index, out bool fail)
 Gets the item at the specified index, and does not throw an exception on failure. More...
 
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.ICollectionEx< T >
int RemoveAll (Predicate< T > match)
 Removes the all the elements that match the conditions defined by the specified predicate. More...
 
- Public Member Functions inherited from Loyc.Collections.ISinkCollection< T >
void Clear ()
 

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 Member Functions inherited from Loyc.Collections.AListBase< K, T >
 AListBase (int maxLeafSize)
 
 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...
 
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< 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
 
byte _freezeMode = NotFrozen
 
const byte NotFrozen = 0
 
const byte Frozen = 1
 
const byte FrozenForListChanging = 2
 
const byte FrozenForConcurrency = 3
 

Additional Inherited Members

- Properties inherited from Loyc.Collections.AListBase< K, T >
virtual ListChangingHandler< T > ListChanging
 Event for learning about changes in progress on a list. More...
 
byte TreeHeight [get]
 
int Count [get]
 
bool IsEmpty [get]
 
AListReverseView< K, T > ReverseView [get]
 
this[int index] [get]
 
bool IsFrozen [get]
 
First [get]
 
Last [get]
 
int ObserverCount [get]
 Returns the number of tree observers attached to this list. 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]
 
- Events inherited from Loyc.Collections.INotifyListChanging< T >
ListChangingHandler< T > ListChanging
 Occurs when the collection associated with this interface is about to change. More...
 

Constructor & Destructor Documentation

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

Initializes an empty BList.

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

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

Initializes an empty BList.

Parameters
compareItemsA 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.
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 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&lt;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.

Loyc.Collections.BList< T >.BList ( BList< T >  items,
bool  keepListChangingHandlers 
)
inline
Parameters
itemsA list of items to be cloned.

Member Function Documentation

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

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

Parameters
eA list of items to be added.
Returns
Returns the number of items that were added.
See also
DoRange

Implements Loyc.Collections.IAddRange< T >.

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

Clones a BList.

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

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

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

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

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

Parameters
modeIndicates the operation to perform.
itemAn 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.
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
modeIndicates the operation to perform.
eA 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.
int Loyc.Collections.BList< T >.FindLowerBound ( item)
inline

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

Parameters
itemThe 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.
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.BList< T >.FindUpperBound ( item)
inline

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

Parameters
itemThe 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.
int Loyc.Collections.BList< T >.IndexOf ( item)
inline

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

Parameters
itemItem to find.
Returns
The lower-bound index, or Count if the item is greater than all items in the list.
int Loyc.Collections.BList< T >.IndexOfExact ( 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.

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

Removes a single instance of the specified item.

Implements Loyc.Collections.ISinkCollection< T >.

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

Removes all instances of the specified item.

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

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

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

Parameters
eA list of items to be removed.
Returns
Returns the number of items that were found and removed.
See also
DoRange

Member Data Documentation

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.