A compact auto-enlarging array structure that is intended to be used within other data structures. It should only be used internally in "private" or "protected" members of low-level code. More...

Source file:

/Core/Loyc.Essentials/Collections/Implementations/InternalList.cs

Inheritance diagram for Loyc.Collections.Impl.InternalList< T >:

Remarks

A compact auto-enlarging array structure that is intended to be used within other data structures. It should only be used internally in "private" or "protected" members of low-level code.

An article about this class is available.

InternalList is a struct, not a class, in order to save memory, and for maximum performance, it asserts rather than throwing an exception when an incorrect array index is used. Besides that, it has an InternalArray property that provides access to the internal array. This is useful, for example, when you have a list of structs and you want to change a property of one of them (this is combersome in a standard List{T} because list[i].P = value is illegal in that context, but in InternalList, list.InternalArray[i].P = value is legal.)

For all these reasons one should not expose it in a public API, and it should mainly be used when performance trumps all other concerns.

Passing this structure by value is dangerous because changes to a copy of the structure may or may not be reflected in the original list. It's best not to pass it around at all, but if you must pass it, pass it by reference. Avoid using extension methods on this struct because an extension method will receive a copy of the struct.

Also, do not use the default contructor. Always specify an initial capacity or copy InternalList.Empty so that _array gets a value. This is required because methods such as Add(), Insert() and Resize() assume _array is not null.

InternalList has one nice thing that List(of T) lacks: a Resize method and an equivalent Count setter. Which dork at Microsoft decided no one should be allowed to set the list length directly? This type also provides a handy Last property and a Pop method to respectively get or remove the last item.

Finally, alongside InternalList(T), the static class InternalList comes with some static methods (CopyToNewArray, Insert, RemoveAt, Move) to help manage raw arrays. You might want to use these in a data structure implementation even if you choose not to use InternalList(T) instances.

Public fields
ref T	FirstRef => ref _array[0]

ref T	LastRef => ref _array[_count - 1]

bool ICollection< T >.	IsReadOnly => false

Public static fields
static readonly T[]	EmptyArray = Empty<T>.Array

static readonly InternalList< T >	Empty = new InternalList<T>(Empty<T>.Array, 0)

Properties
int	Count `[get, set]`

bool	IsEmpty `[get]`

int	Capacity `[get, set]`
	Gets or sets the array length. More...

T	First `[get, set]`

T	Last `[get, set]`

T[]	InternalArray `[get]`

T	this[int index] `[get, set]`

T	this[int index, T defaultValue] `[get]`

Properties inherited from Loyc.Collections.ISource< out T >
new int	Count `[get]`
	Gets the number of items in the collection. 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]`

Properties inherited from Loyc.Collections.IIndexed< in K, out V >
V	this[K key] `[get]`
	Gets the value associated with the specified key. More...

Properties inherited from Loyc.Collections.IHasMFirst< T >
new T	First `[get, set]`

Properties inherited from Loyc.Collections.IHasFirst< out T >
T	First `[get]`
	Gets the first item in the deque. More...

Properties inherited from Loyc.Collections.IHasMLast< T >
new T	Last `[get, set]`

Properties inherited from Loyc.Collections.IHasLast< out T >
T	Last `[get]`
	Gets the first item in the collection. More...

Public Member Functions
	InternalList (int capacity)

	InternalList (T[] array, int count)

	InternalList (IEnumerable< T > items)

	InternalList (IEnumerator< T > items)

void	AutoRaiseCapacity (int more, int capacityLimit)

void	Resize (int newSize)

void	Resize (int newSize, bool allowReduceCapacity)
	Makes the list larger or smaller, depending on whether `newSize` is larger or smaller than Count. More...

void	Add (T item)

void	AddRange (IEnumerator< T > items)

void	Insert (int index, T item)

void	InsertRange (int index, ICollectionAndReadOnly< T > items)

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

void	InsertRange (int index, ICollection< T > items)

void	InsertRangeHelper (int index, int spaceNeeded)

void	InsertRange (int index, IEnumerable< T > e)

void	AddRange (IReadOnlyCollection< T > items)

void	AddRange (ICollection< T > items)

void	AddRange (IEnumerable< T > e)

void	AddRange (ICollectionAndReadOnly< T > items)

void	Clear ()
	Clears the list and frees the memory used by the list. Can also be used to initialize a list whose constructor was never called. More...

void	RemoveAt (int index)

void	RemoveRange (int index, int count)

void	Pop ()

InternalList< T >	Clone ()
	Makes a copy of the list with the same capacity More...

InternalList< T >	CloneAndTrim ()
	Makes a copy of the list with Capacity = Count More...

T[]	ToArray ()
	Makes a copy of the list, as an array More...

int	BinarySearch (T lookFor)

int	BinarySearch (T lookFor, Comparer< T > comp)

int	BinarySearch (T lookFor, Comparer< T > comp, bool lowerBound)

int	BinarySearch< K > (K lookFor, Func< T, K, int > func, bool lowerBound)

void	Move (int from, int to)
	Slides the array entry at [from] forward or backward in the list, until it reaches [to]. More...

int	IndexOf (T item)

int	IndexOf (T item, int index)

bool	Contains (T item)
	Returns true if and only if the collection contains the specified item. More...

void	CopyTo (T[] array, int arrayIndex)
	Copies the elements of the collection to an Array, starting at a particular array index. More...

bool	Remove (T item)

System.Collections.IEnumerator System.Collections.IEnumerable.	GetEnumerator ()

IEnumerator< T > IEnumerable< T >.	GetEnumerator ()

InternalList.Enumerator< T >	GetEnumerator ()

T	TryGet (int index, out bool fail)

void	Sort (Comparison< T > comp)

void	Sort (int index, int count, Comparison< T > comp)

IListSource< T > IListSource< T >.	Slice (int start, int count)
	Returns a sub-range of this list. More...

Slice_< T >	Slice (int start, int count=int.MaxValue)
	Returns a sub-range of this list. More...

InternalList< T >	CopySection (int start, int subcount)

Span< T >	AsSpan ()

Memory< T >	AsMemory ()

T[]	AsArray ()

InternalList.Scanner< T >	Scan ()

IScanner< T > IScan< T >.	Scan ()

Public Member Functions inherited from Loyc.Collections.ITryGet< in K, out V >
V	TryGet (K key, out bool fail)
	Gets the item for the specified key or index, and does not throw an exception on failure. More...

Member Function Documentation

void Loyc.Collections.Impl.InternalList< T >.Clear ( )

inline

Clears the list and frees the memory used by the list. Can also be used to initialize a list whose constructor was never called.

InternalList<T> Loyc.Collections.Impl.InternalList< T >.Clone ( )

inline

Makes a copy of the list with the same capacity

Implements Loyc.ICloneable< out T >.

InternalList<T> Loyc.Collections.Impl.InternalList< T >.CloneAndTrim ( )

inline

Makes a copy of the list with Capacity = Count

bool Loyc.Collections.Impl.InternalList< T >.Contains ( T item )

inline

Returns true if and only if the collection contains the specified item.

Parameters

item	Data/object whose presence you want to check for. The collection decides how to test for equality, but it's most common to use EqualityComparer{T}.Default.

Implements Loyc.Collections.IContains< in T >.

void Loyc.Collections.Impl.InternalList< T >.CopyTo	(	T[]	array,
		int	arrayIndex
	)

inline

Copies the elements of the collection to an Array, starting at a particular array index.

It's usually more convenient to call the ToArray() extension method, which calls this method for you.

This method exists for performance reasons (the collection itself can often copy data out faster than an enumerator can).

Exceptions

ArgumentNullException	array is null.
ArgumentOutOfRangeException	arrayIndex is negative.
ArgumentException	The number of elements in the source collection is greater than the available space from arrayIndex to the end of the destination array.

Implements Loyc.Collections.ICollectionSource< T >.

void Loyc.Collections.Impl.InternalList< T >.Move	(	int	from,
		int	to
	)

inline

Slides the array entry at [from] forward or backward in the list, until it reaches [to].

For example, if a list of integers is [0, 1, 2, 3, 4, 5] then Move(4,1) produces the following result: [0, 4, 1, 2, 3, 5].

void Loyc.Collections.Impl.InternalList< T >.Resize	(	int	newSize,
		bool	allowReduceCapacity
	)

inline

Makes the list larger or smaller, depending on whether newSize is larger or smaller than Count.

Parameters

allowReduceCapacity	If this is true, and the new size is smaller than one quarter the current Capacity, the array is reallocated to a smaller size. If this parameter is false, the array is never reallocated when shrinking the list.
newSize	New value of Count. If the Count increases, copies of default(T) are added to the end of the the list; otherwise items are removed from the end of the list.

IListSource<T> IListSource<T>. Loyc.Collections.Impl.InternalList< T >.Slice	(	int	start,
		int	count
	)

inline

Returns a sub-range of this list.

Parameters

start	The new range will start at this index in the current list (this location will be index [0] in the new range).
count	The desired number of elements in the new range, or int.MaxValue to get all elements until the end of the list.

Returns: Returns a sub-range of this range.

Exceptions

ArgumentException The start index was below zero.

The (start, count) range is allowed to be invalid, as long as start is zero or above.

If count is below zero, or if start is above the original Count, the Count of the new slice is set to zero.
if (start + count) is above the original Count, the Count of the new slice is reduced to this.Count - start. Implementation note: do not compute (start + count) because it may overflow. Instead, test whether (count > this.Count - start).

Most collections should use the following implementation:

IListSource<T> IListSource<T>.Slice(int start, int count) { return Slice(start, count); }
public Slice_<T> Slice(int start, int count) { return new Slice_<T>(this, start, count); }

Implements Loyc.Collections.IListSource< out T >.

Slice_<T> Loyc.Collections.Impl.InternalList< T >.Slice	(	int	start,
		int	count = `int.MaxValue`
	)

inline

Returns a sub-range of this list.

Parameters

start	The new range will start at this index in the current list (this location will be index [0] in the new range).
count	The desired number of elements in the new range, or int.MaxValue to get all elements until the end of the list.

Returns: Returns a sub-range of this range.

Exceptions

ArgumentException The start index was below zero.

The (start, count) range is allowed to be invalid, as long as start is zero or above.

If count is below zero, or if start is above the original Count, the Count of the new slice is set to zero.
if (start + count) is above the original Count, the Count of the new slice is reduced to this.Count - start. Implementation note: do not compute (start + count) because it may overflow. Instead, test whether (count > this.Count - start).

Most collections should use the following implementation:

IListSource<T> IListSource<T>.Slice(int start, int count) { return Slice(start, count); }
public Slice_<T> Slice(int start, int count) { return new Slice_<T>(this, start, count); }

Implements Loyc.Collections.IListSource< out T >.

T [] Loyc.Collections.Impl.InternalList< T >.ToArray ( )

inline

Makes a copy of the list, as an array

Property Documentation

int Loyc.Collections.Impl.InternalList< T >.Capacity

getset

Gets or sets the array length.

Changing this property requires O(Count) time and temporary space. Attempting to set the capacity lower than Count has no effect.

Remarks

Public fields

Public static fields

Properties

Public Member Functions

Member Function Documentation

Property Documentation