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
Properties | Public Member Functions | Protected Member Functions | List of all members
Loyc.Collections.AList< T > Class Template Reference

An all-purpose list structure with the following additional features beyond what's offered by List{T}: fast insertion and deletion (O(log N)), batch insertion and deletion, observability, fast cloning, freezability, and fast splitting and joining of large collections. More...


Source file:
Inheritance diagram for Loyc.Collections.AList< T >:
Loyc.Collections.AListBase< T > Loyc.Collections.IListEx< T > Loyc.Collections.IListRangeMethods< T > Loyc.ICloneable< out T > Loyc.Collections.IAddRange< T > Loyc.Collections.IListRangeMethods< T > Loyc.Collections.IArray< T > Loyc.Collections.ICollectionEx< T > Loyc.Collections.IListAndListSource< T > Loyc.Collections.IDeque< T > Loyc.ICloneable< out T > Loyc.Collections.IListAndListSource< T > Loyc.Collections.AListBase< K, T > Loyc.Collections.IndexedAList< T >

Remarks

An all-purpose list structure with the following additional features beyond what's offered by List{T}: fast insertion and deletion (O(log N)), batch insertion and deletion, observability, fast cloning, freezability, and fast splitting and joining of large collections.

An article about this class is available.

Template Parameters
TType of each element in the list

The name "A-List" is short for All-purpose List. It is so named because it has a very large amount of functionality and extension points for further extending this functionality. Essentially, this data structure is jack-of-all-trades, master of none.

Structurally, ALists (like BLists) are very similar to B+trees. They use memory almost as efficiently as arrays, and offer O(log N) insertion and deletion in exchange for a O(log N) indexer, which is distinctly slower than the indexer of List{T}. They use slightly more memory than List{T} for all list sizes.

That said, you should use an AList whenever you know that the list might be large and need insertions or deletions somewhere in the middle. If you expect to do insertions and deletions at random locations, but only occasionally, DList{T} is sometimes a better choice because it has a faster indexer. Both classes provide fast enumeration (O(1) per element), but DList{T} enumerators initialize faster.

Although AList isn't the fastest or smallest data structure for any single task, it is very useful when you need several different capabilities, and there are certain tasks for which it excels; for example, have you ever wanted to remove all items that meet certain criteria from a list? You cannot accomplish this with a foreach loop such as this:

foreach (T item in list) if (MeetsCriteria(item)) list.Remove(item); // Exception occurs! foreach loop cannot continue after Remove()!

When you are using a List{T}, you might try to solve this problem with a reverse for-loop such as this:

for (int i = list.Count - 1; i >= 0; i–) if (MeetsCriteria(list[i])) list.RemoveAt(i);

This works, but it runs in O(N^2) time, so it's very slow if the list is large. The easiest way to solve this problem that is also efficient is to duplicate all the items that you want to keep in a new list:

var list2 = new List<T>(); foreach (T item in list) if (!MeetsCriteria(item)) list2.Add(item); list = list2;

But what if you didn't think of that solution and already wrote the O(N^2) version? There's a lot of code out there already that relies on slow List{T} operations. An easy way to solve performance caused by poor use of List{T} is simply to add "A" in front. AList is pretty much a drop-in replacement for List, so you can convert O(N^2) into faster O(N log N) code simply by using an AList instead of a List.

I like to think of AList as the ultimate novice data structure. Novices like indexed lists, although for many tasks they are not the most efficient choice. AList isn't optimized for any particular task, but it isn't downright slow for any task except IndexOf, so it's very friendly to novices that don't know about all the different types of data structures and how to choose one. Don't worry about it! Just pick AList. It's also a good choice when you're just too busy to think about performance, such as in a scripting environment.

Plus, you can subscribe to the AListBase{K,T}.ListChanging event to find out when the list changes. AList's observability is more lightweight than that of ObservableCollection{T}.

Although single insertions, deletions, and random access require O(log N) time, you can get better performance using any overload of InsertRange or AListBase{K,T}.RemoveRange. These methods require only O(log N + M) time, where M is the number of elements you are inserting, removing or enumerating.

AList is an excellent choice if you need to make occasional snapshots of the tree. Cloning is fast and memory-efficient, because none of the tree is copied at first. The root node is simply marked as frozen, and nodes are duplicated on-demand as changes are made. Thus, AList can be used as a so-called "persistent" data structure, but it is fairly expensive to clone the tree after every modification. When modifying a tree that was just cloned (remember, AList is really a tree), the leaf node being changed and all of its ancestors must be duplicated. Therefore, it's better if you can arrange to have a high ratio of changes to clones.

AList is also freezable, which is useful if you need to construct a list in a read-only or freezable data structure. You could also freeze the list in order to return a read-only copy of it, which, compared to cloning, has the advantage that no memory allocation is required at the time you return the list. If you need to edit the list later, you can clone the list (the clone can be modified).

As explained in the documentation of AListBase{T}, this class is NOT multithread-safe. Multiple concurrent readers are allowed, as long as the collection is not modified, so frozen instances ARE multithread-safe.

See also
BList{T}, BDictionary{K,V}, DList{T}

Properties

sealed override T this[int index] [get, set]
 
- Properties inherited from Loyc.Collections.AListBase< T >
abstract new T this[int index] [get, set]
 
new T First [get, set]
 
new T Last [get, set]
 
- 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.IDeque< T >
First [get, set]
 Gets the first item in the deque. More...
 
Last [get, set]
 
- Properties inherited from Loyc.Collections.IIsEmpty
bool IsEmpty [get]
 
- Properties inherited from Loyc.Collections.ICount
int Count [get]
 Gets the number of items in the collection. More...
 
- Properties inherited from Loyc.Collections.IArray< T >
new T this[int index] [get, set]
 Gets or sets an element of the array-like collection. More...
 
- Properties inherited from Loyc.Collections.ISinkArray< T >
this[int index] [set]
 

Public Member Functions

 AList (IEnumerable< T > items)
 
 AList (IListSource< T > items)
 
 AList (int maxLeafSize)
 
 AList (int maxLeafSize, int maxInnerSize)
 
 AList (AList< T > items, bool keepListChangingHandlers)
 
sealed override void Add (T item)
 
void AddRange (IEnumerable< T > list)
 
void InsertRange (int index, AList< T > source)
 
void InsertRange (int index, AList< T > source, bool move)
 
sealed override void Insert (int index, T item)
 
sealed override void InsertRange (int index, IEnumerable< T > list)
 
sealed override void InsertRange (int index, IListSource< T > source)
 
sealed override bool TrySet (int index, T value)
 
new AList< T > Clone ()
 
AList< T > Clone (bool keepListChangingHandlers)
 
AList< T > CopySection (int start, int subcount)
 
new AList< T > RemoveSection (int start, int count)
 
void Swap (AList< T > other)
 Swaps the contents of two AList{T}s in O(1) time. More...
 
virtual void Append (AList< T > other)
 
virtual void Append (AList< T > other, bool move)
 Appends another AList to this list in sublinear time. More...
 
virtual void Prepend (AList< T > other)
 Prepends an AList to this list in sublinear time. More...
 
virtual void Prepend (AList< T > other, bool move)
 Prepends an AList to this list in sublinear time. More...
 
void Sort ()
 Uses a specialized "tree quicksort" algorithm to sort this list using Comparer{T}.Default. More...
 
void Sort (Comparer< T > comp)
 Uses a specialized "tree quicksort" algorithm to sort this list using the specified Comparer{T}. More...
 
void Sort (Comparison< T > comp)
 Uses a specialized "tree quicksort" algorithm to sort this list using the specified Comparison{T}. More...
 
void Sort (int start, int subcount, Comparison< T > comp)
 
- Public Member Functions inherited from Loyc.Collections.AListBase< T >
 AListBase (int maxLeafSize)
 
 AListBase (int maxLeafSize, int maxInnerSize)
 
 AListBase (AListBase< T > items, bool keepListChangingHandlers)
 
void AddRange (IListSource< T > source)
 
void AddRange (AList< T > source)
 
void Resize (int newSize)
 
virtual int IndexOf (T item)
 Finds an index of an item in the list. More...
 
bool Contains (T item)
 Returns true if-and-only-if the specified item exists in the list. More...
 
bool Remove (T item)
 Finds a specific item and removes it. If duplicates of the item exist, only the first occurrence is removed. More...
 
AListBase< T > Clone ()
 
AListBase< T > RemoveSection (int start, int count)
 
new ListSlice< T > Slice (int start, int length)
 Returns a sub-range of this list. 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 ()
 
bool Remove (T item)
 
- Public Member Functions inherited from Loyc.Collections.IListRangeMethods< T >
void RemoveRange (int index, int amount)
 

Protected Member Functions

 AList (AListBase< int, T > original, AListNode< int, T > section)
 
override AListNode< int, T > NewRootLeaf ()
 
override void Clone (out AListBase< T > clone)
 
override AListBase< T > cov_RemoveSection (int start, int count)
 
void Sort (uint start, uint subcount, Comparison< T > comp)
 
virtual void SortCore (uint start, uint subcount, Comparison< T > comp)
 
void ForceThaw (uint start, uint subcount)
 
- Protected Member Functions inherited from Loyc.Collections.AListBase< T >
 AListBase (AListBase< int, T > original, AListNode< int, T > section)
 
override AListInnerBase< int, T > SplitRoot (AListNode< int, T > left, AListNode< int, T > right)
 
void DetectSizeOverflow (int insertSize)
 Throws OverflowException if inserting the specified number of items would cause Count to overflow. More...
 
void BeginInsertRange (int index, IListSource< T > items, int itemsCount)
 
void DoneInsertRange (int amountInserted)
 
void InsertRange (int index, AListBase< T > source, bool move)
 
virtual void Combine (AListBase< T > other, bool move, bool append)
 
- 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...
 

Additional Inherited Members

- 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
 
- Events inherited from Loyc.Collections.INotifyListChanging< T >
ListChangingHandler< T > ListChanging
 Occurs when the collection associated with this interface is about to change. More...
 

Member Function Documentation

virtual void Loyc.Collections.AList< T >.Append ( AList< T >  other,
bool  move 
)
inlinevirtual

Appends another AList to this list in sublinear time.

Parameters
otherA list of items to be added to this list.
moveIf this parameter is true, items from the other list are transferred to this list, causing the other list to be cleared. This parameter does not affect the speed of this method itself, but if you use "true" then future modifications to the combined list may be faster. If this parameter is "false" then it will be necessary to freeze the contents of the other list so that both lists can share the same tree nodes. Using "true" instead avoids the freeze operation, which in turn avoids the performance penalty on future modifications.

The default value of the 'move' parameter is false.

When the 'source' list is short, this method doesn't perform any better than a standard AddRange() operation (in fact, the operation is delegated to InsertRange()). However, when 'source' has several hundred or thousand items, the append/prepend operation is performed in roughly O(log N) time where N is the combined list size.

Parts of the tree that end up shared between this list and the other list will be frozen. Frozen parts of the tree must be cloned in order to be modified, which will slow down future operations on the tree. In order to avoid this problem, use move semantics (which clears the other list).

virtual void Loyc.Collections.AList< T >.Prepend ( AList< T >  other)
inlinevirtual

Prepends an AList to this list in sublinear time.

Parameters
otherA list of items to be added to the front of this list (at index 0).
virtual void Loyc.Collections.AList< T >.Prepend ( AList< T >  other,
bool  move 
)
inlinevirtual

Prepends an AList to this list in sublinear time.

Parameters
otherA list of items to be added to the front of this list (at index 0).
void Loyc.Collections.AList< T >.Sort ( )
inline

Uses a specialized "tree quicksort" algorithm to sort this list using Comparer{T}.Default.

void Loyc.Collections.AList< T >.Sort ( Comparer< T >  comp)
inline

Uses a specialized "tree quicksort" algorithm to sort this list using the specified Comparer{T}.

void Loyc.Collections.AList< T >.Sort ( Comparison< T >  comp)
inline

Uses a specialized "tree quicksort" algorithm to sort this list using the specified Comparison{T}.

void Loyc.Collections.AList< T >.Sort ( int  start,
int  subcount,
Comparison< T >  comp 
)
inline
Parameters
startIndex of first item in a range of items to sort.
subcountSize of the range of items to sort.
void Loyc.Collections.AList< T >.Swap ( AList< T >  other)
inline

Swaps the contents of two AList{T}s in O(1) time.

Any observers are also swapped.