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.IndexedAList< T > Class Template Reference

A simple wrapper around AList that includes an AListIndexer{K,T} that can be used to find items relatively quickly in a large list. When an index is built and the list is large, it accelerates IndexOf(item), Contains(item) and Remove(item). More...


Source file:
Inheritance diagram for Loyc.Collections.IndexedAList< T >:
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 >

Remarks

A simple wrapper around AList that includes an AListIndexer{K,T} that can be used to find items relatively quickly in a large list. When an index is built and the list is large, it accelerates IndexOf(item), Contains(item) and Remove(item).

The IndexOf, AListBase{T}.Remove and AListBase{T}.Contains methods are accelerated by the indexer, but please note that the indexer is expensive in terms of memory usage and CPU time. In total, once the index has been built, IndexedAList typically uses about three times as much memory as a plain AList{T}. Moreover, changing the list takes at least twice as much time, since the indexer must be updated to reflect every change.

An IndexedAList is indexed by default, but if necessary the index can be disabled in the constructor or by settings the IsIndexed property to false.

Properties

bool IsIndexed [get, set]
 Indicates whether the AList is indexed. More...
 
- Properties inherited from Loyc.Collections.AList< T >
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

 IndexedAList (bool createIndexNow)
 
 IndexedAList (IEnumerable< T > items)
 
 IndexedAList (IListSource< T > items)
 
 IndexedAList (int maxLeafSize)
 
 IndexedAList (int maxLeafSize, int maxInnerSize)
 
 IndexedAList (int maxLeafSize, int maxInnerSize, bool createIndexNow)
 
 IndexedAList (AList< T > items, bool keepListChangingHandlers)
 
 IndexedAList (AList< T > items, bool keepListChangingHandlers, bool createIndexNow)
 
override int IndexOf (T item)
 Finds an index of an item in the list. More...
 
List< int > IndexesOf (T item, bool sorted)
 Returns a list of indexes at which the specified item can be found. More...
 
void VerifyCorrectness ()
 
- Public Member Functions inherited from Loyc.Collections.AList< T >
 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)
 
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

void CreateIndex ()
 
- Protected Member Functions inherited from Loyc.Collections.AList< T >
 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

List<int> Loyc.Collections.IndexedAList< T >.IndexesOf ( item,
bool  sorted 
)
inline

Returns a list of indexes at which the specified item can be found.

Parameters
itemItem to find in the list
sortedWhether to sort the list of indexes before returning it.

If IsIndexed is false, an index is created.

override int Loyc.Collections.IndexedAList< T >.IndexOf ( item)
inlinevirtual

Finds an index of an item in the list.

Parameters
itemAn item for which to search.
Returns
An index of the item. If the list contains duplicates of the item, this method does not necessarily return the lowest index of the item.

If IsIndexed is false, an index is created unless the list is short (specifically, an index is created if the root node is not a leaf.)

Reimplemented from Loyc.Collections.AListBase< T >.

Property Documentation

bool Loyc.Collections.IndexedAList< T >.IsIndexed
getset

Indicates whether the AList is indexed.

You can set this property to false to discard the index if it has been built, or set it to true to create a new index if it has not yet been built (which takes O(N log N) where N is the AListBase{K,T}.Count of this list).