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.

Contains static methods to help manage raw arrays with even less overhead than InternalList<T>.

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. For all these reasons one should not expose it in a public API, and it should only 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.

The methods of this class are used by some data structures that contain arrays but, for whatever reason, don't use InternalList<T>. These methods are also used by InternalList(T) itself.

Nested classes
struct	Enumerator

Public fields
bool ICollection< T >.	IsReadOnly => false

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

static readonly InternalList< T >	Empty = new InternalList<T>(EmptyArray<T>.Value, 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]`

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)

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

T	TryGet (int index, out bool fail)

void	Sort (Comparison< T > comp)

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

IRange< T > IListSource< T >.	Slice (int start, int count)

Slice_< T >	Slice (int start, int count=int.MaxValue)

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

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.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.IListRangeMethods< T >
void	InsertRange (int index, IEnumerable< T > s)

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

void	RemoveRange (int index, int amount)

Static Public Member Functions
static InternalList< T >	AsInternalList< T > (this T[] array)
	Converts an array to InternalList (exists to help infer type params) More...

static InternalList< T >	AsInternalList< T > (this T[] array, int count)

static T[]	CopyToNewArray< T > (T[] _array, int _count, int newCapacity)

static T[]	CopyToNewArray< T > (T[] array)

static void	Fill< T > (T[] array, T value)

static void	Fill< T > (T[] array, int start, int count, T value)

static int	BinarySearch< T > (T[] array, int count, T k, Comparer< T > comp, bool lowerBound)

static int	BinarySearch< T, K > (T[] _array, int _count, K k, Func< T, K, int > compare, bool lowerBound)
	Performs a binary search with a custom comparison function. More...

static int	BinarySearchByIndex< Anything > (Anything data, int count, Func< int, Anything, int > compare, bool lowerBound)
	A binary search function that knows nothing about the list being searched. More...

static int	NextLargerSize (int than)
	As an alternative to the typical enlarging pattern of doubling the array size when it overflows, this function proposes a 75% size increase instead (100% when the array is small), while ensuring that the array length stays even. More...

static int	NextLargerSize (int than, int capacityLimit)
	Same as NextLargerSize(int), but allows you to specify a capacity limit, to avoid wasting memory when a collection has a known maximum size. More...

static T[]	Insert< T > (int index, T item, T[] array, int count)

static T[]	InsertRangeHelper< T > (int index, int spaceNeeded, T[] array, int count)

static T[]	AutoRaiseCapacity< T > (T[] array, int count, int more, int capacityLimit)

static int	RemoveAt< T > (int index, T[] array, int count)

static int	RemoveAt< T > (int index, int removeCount, T[] array, int count)

static void	Move< T > (T[] array, int from, int to)

static void	Sort< T > (T[] array, int index, int count, Comparison< T > comp)
	Performs a quicksort using a Comparison function. More...

static void	InsertionSort< T > (T[] array, int index, int count, Comparison< T > comp)
	Performs an insertion sort. More...

static bool	AllEqual< T > (this InternalList< T > a, InternalList< T > b)

static bool	AllEqual< T > (T[] a, T[] b, int count)

Member Function Documentation

◆ AsInternalList< T >()

static InternalList<T> Loyc.Collections.Impl.InternalList< T >.AsInternalList< T > ( this T[] array )

inlinestatic

Converts an array to InternalList (exists to help infer type params)

◆ BinarySearch< T, K >()

static int Loyc.Collections.Impl.InternalList< T >.BinarySearch< T, K >	(	T[]	_array,
		int	_count,
		K	k,
		Func< T, K, int >	compare,
		bool	lowerBound
	)

inlinestatic

Performs a binary search with a custom comparison function.

Parameters

_array	Array to search
_count	Number of elements used in the array
k	A key to compare with elements of the array
compare	Lambda function that knows how to compare Ts with Ks (T and K can be the same). It is passed a series of elements from the array. It must return 0 if the element has the desired value, 1 if the supplied element is higher than desired, and -1 if it is lower than desired.
lowerBound	Whether to find the "lower bound" in case there are duplicates in the list. If duplicates exist of the search key k, the lowest index of a matching duplicate is returned. This search mode may be slightly slower when a match exists.

Returns: The index of the matching array entry, if found. If no exact match was found, this method returns the bitwise complement of an insertion location that would preserve the order.

// The first 6 elements are sorted. The seventh is invalid, // and must be excluded from the binary search. int[] array = new int[] { 0, 10, 20, 30, 40, 50, -1 }; // The result will be 2, because array[2] == 20. int a = InternalList.BinarySearch(array, 6, i => i.CompareTo(20)); // The result will be ~2, which equals -3, because index 2 would // be the correct place to insert 17 to preserve the sort order. int b = InternalList.BinarySearch(array, 6, i => i.CompareTo(17));

◆ BinarySearchByIndex< Anything >()

static int Loyc.Collections.Impl.InternalList< T >.BinarySearchByIndex< Anything >	(	Anything	data,
		int	count,
		Func< int, Anything, int >	compare,
		bool	lowerBound
	)

inlinestatic

A binary search function that knows nothing about the list being searched.

Template Parameters

Anything Any data type relevant to the caller.

Parameters

data	State information to be passed to compare()
count	Number of items in the list being searched
compare	Comparison method that is given the current index to examine and the state parameter "data".
lowerBound	Whether to find the "lower bound" in case there are duplicates in the list. If duplicates exist of the search key k exist, the lowest index of a matching duplicate is returned. This search mode may be slightly slower when a match exists.

Returns: The index of the matching index, if found. If no exact match was found, this method returns the bitwise complement of an insertion location that would preserve the sort order.

◆ Clear()

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.

Referenced by Loyc.Syntax.AbstractTriviaInjector< Token >.RunCore().

◆ Clone()

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

inline

Makes a copy of the list with the same capacity

◆ CloneAndTrim()

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

inline

Makes a copy of the list with Capacity = Count

◆ CopyTo()

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

◆ InsertionSort< T >()

static void Loyc.Collections.Impl.InternalList< T >.InsertionSort< T >	(	T[]	array,
		int	index,
		int	count,
		Comparison< T >	comp
	)

inlinestatic

Performs an insertion sort.

The insertion sort is a stable sort algorithm that is slow in general (O(N^2)). It should be used only when (a) the list to be sorted is short (less than about 20 elements) or (b) the list is very nearly sorted already.

See also: ListExt.InsertionSort

◆ Move()

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

Referenced by Loyc.Collections.Impl.InternalList< Loyc.Collections.Impl.IAListTreeObserver< K, T > >.Move().

◆ NextLargerSize() [1/2]

static int Loyc.Collections.Impl.InternalList< T >.NextLargerSize ( int than )

inlinestatic

As an alternative to the typical enlarging pattern of doubling the array size when it overflows, this function proposes a 75% size increase instead (100% when the array is small), while ensuring that the array length stays even.

With a seed of 0, 2, or 4: 0, 2, 4, 8, 16, 30, 54, 96, 170, 298, 522...
With a seed of 1: 1, 2, 4, 8, 16, 30, 54, 96, 170, 298, 522...
With a seed of 3: 3, 6, 12, 22, 40, 72, 128, 226, 396...
With a seed of 5: 5, 10, 18, 32, 58, 102, 180, 316, 554...
With a seed of 7: 7, 14, 26, 46, 82, 144, 254, 446, 782...

75% size increases require 23.9% more allocations than size doubling (1.75 to the 1.239th power is about 2.0), but memory utilization is increased. With size doubling, the average list uses 2/3 of its entries, but with this resizing pattern, the average list uses 72.72% of its entries. The average size of a list is 8.3% lower. Originally I used 50% size increases, but they required 71% more allocations, which seemed like too much.

Referenced by Loyc.Collections.Impl.InternalList< Loyc.Collections.Impl.IAListTreeObserver< K, T > >.NextLargerSize().

◆ NextLargerSize() [2/2]

static int Loyc.Collections.Impl.InternalList< T >.NextLargerSize	(	int	than,
		int	capacityLimit
	)

inlinestatic

Same as NextLargerSize(int), but allows you to specify a capacity limit, to avoid wasting memory when a collection has a known maximum size.

Parameters

than	Return value will be larger than this number.
capacityLimit	Maximum value to return. This parameter is ignored if it than >= capacityLimit.

Returns: Produces the same result as NextLargerSize(int) unless the return value would be near capacityLimit (and capacityLimit

than). If the return value would be more than capacityLimit,

capacityLimit is returned instead. If the return value would be slightly less than capacityLimit (within 20%) then capacityLimit is returned, to ensure that another reallocation will not be required later.

◆ Resize()

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.

◆ Sort< T >()

static void Loyc.Collections.Impl.InternalList< T >.Sort< T >	(	T[]	array,
		int	index,
		int	count,
		Comparison< T >	comp
	)

inlinestatic

Performs a quicksort using a Comparison function.

Normally one uses Array.Sort for sorting arrays. This method exists because there is no Array.Sort overload that accepts both a Comparison and a range (index, count), nor does the .NET framework provide access to its internal adapter that converts Comparison to IComparer.

This quicksort algorithm uses a best-of-three pivot so that it remains performant (fast) if the input is already sorted. It is designed to perform reasonably well in case the data contains many duplicates (not verified). It is also designed to avoid using excessive stack space if a worst-case input occurs that requires O(N^2) time.

◆ ToArray()

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

inline

Makes a copy of the list, as an array

Property Documentation

◆ Capacity

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.

Referenced by Loyc.Collections.Impl.InternalList< Loyc.Collections.Impl.IAListTreeObserver< K, T > >.Resize().

Remarks

Nested classes

Public fields

Public static fields

Properties

Public Member Functions

Static Public Member Functions

Member Function Documentation

◆ AsInternalList< T >()

◆ BinarySearch< T, K >()

◆ BinarySearchByIndex< Anything >()

◆ Clear()

◆ Clone()

◆ CloneAndTrim()

◆ CopyTo()

◆ InsertionSort< T >()

◆ Move()

◆ NextLargerSize() [1/2]

◆ NextLargerSize() [2/2]

◆ Resize()

◆ Sort< T >()

◆ ToArray()

Property Documentation

◆ Capacity