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:

/Core/Loyc.Collections/ALists/IndexedAList.cs

Inheritance diagram for Loyc.Collections.IndexedAList< 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.IListEx< T >
new int	Count `[get]`

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

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.IArraySink< T >
T	this[int index] `[set]`

Public Member Functions
	IndexedAList (bool createIndexNow)

	IndexedAList (IEnumerable< T > items)

	IndexedAList (IListSource< T > items)

	IndexedAList (int maxNodeSize)

	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 ()

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

Public Member Functions inherited from Loyc.Collections.AList< T >
	AList (IEnumerable< T > items)

	AList (IListSource< T > items)

	AList (int maxNodeSize)

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

Public Member Functions inherited from Loyc.Collections.IListRangeMethods< T >
void	InsertRange (int index, IEnumerable< T > s)

void	InsertRange (int index, IReadOnlyCollection< T > s)

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)

Member Function Documentation

◆ IndexesOf()

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

inline

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

Parameters

item	Item to find in the list
sorted	Whether to sort the list of indexes before returning it.

If IsIndexed is false, an index is created.

◆ IndexOf()

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

inline

Finds an index of an item in the list.

Parameters

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

References Loyc.Collections.Impl.AListIndexer< K, T >.IndexOfAny().

Property Documentation

◆ IsIndexed

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

Remarks

Properties

Public Member Functions

Protected Member Functions

Member Function Documentation

◆ IndexesOf()

◆ IndexOf()

Property Documentation

◆ IsIndexed