A compact auto-enlarging deque 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. In most cases, you should use DList{T} instead. More...

Source file:

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

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

Remarks

A compact auto-enlarging deque 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. In most cases, you should use DList{T} instead.

This type is implemented with what is commonly called a "circular buffer". There is a single array plus a "start index" and a count. The array may or may not be divided into two "halves", depending on the circumstances. The first element of the DList (returned from this[0] and from the First property) is located at the "start index" of the array; and if the start index + count is greater than the array size, then the end of the DList wraps around to the beginning of the array.

InternalDeque 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 (the one exception is the iterator, which throws in case the collection is modified during enumeration; this is for the sake of DList{T}.)

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. For these and other reasons, one should not expose this struct in a public API, and it should only be used when performance is important.

Also, do not use the default(InternalDList{T}) or the equivalent "default constructor", which only exists because C# requires it. Always specify an initial capacity or copy InternalDeque.Empty so that the internal array gets a value. All methods in this structure assume _array is not null.

This class does not implement IDeque{T} and IList{T} in order to help you not to shoot yourself in the foot. The problem is that any extension methods used with those interfaces that change the list, such as PopLast(), malfunction because the structure is implicitly boxed, producing a shallow copy. By not implementing those interfaces, the extension methods are not available, ensuring you don't accidently box the structure. If you need those interfaces, You can always call AsDList to construct a DList{T} in O(1) time.

You may be curious why InternalList{T}, in contrast, DOES implement IList{T}. It's because there is no way to convert InternalList{T} into a class in O(1) time, so boxing the InternalList{T} is the only fast way to get an instance of IList{T} from it.

Nested classes
class	Enumerator

Public fields
int	_start

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

static readonly InternalDList< T >	Empty = new InternalDList<T>(0)

Properties
T[]	InternalArray `[get]`

int	Capacity `[get, set]`

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

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

int	Count `[get]`

bool	IsReadOnly `[get]`

T	First `[get, set]`

T	Last `[get, set]`

bool	IsEmpty `[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.IHasFirst< out T >
T	First `[get]`
	Gets the first item in the deque. More...

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

Public Member Functions
	InternalDList (int capacity)

	InternalDList (T[] array, int count)

int	Internalize (int index)

int	IncMod (int index)

int	IncMod (int index, int amount)

int	DecMod (int index)

int	DecMod (int index, int amount)

int	IndexOf (T item)

int	IndexOf (T item, int startIndex)

void	PushLast (ICollection< T > items)

void	PushLast (IEnumerable< T > items)

void	PushLast (IReadOnlyCollection< T > items)

void	PushLast (ICollectionAndReadOnly< T > items)

void	PushLast (T item)

void	PushFirst (T item)

void	PopLast (int amount)

void	PopFirst (int amount)

void	AutoRaiseCapacity (int more)

void	AutoRaiseCapacity (int more, int capacityLimit)

void	Insert (int index, T item)

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

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

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

int	InsertRangeHelper (int index, int amount)

void	RemoveAt (int index)

void	RemoveRange (int index, int amount)

bool	TrySet (int index, T value)

T	TryGet (int index, out bool fail)

void	Add (T item)
	An alias for PushLast(). More...

void	Clear ()

void	Resize (int newSize)

bool	Contains (T item)

void	CopyTo (T[] destination, int arrayIndex)

bool	Remove (T item)

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

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

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

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

Enumerator	GetEnumerator ()

Enumerator	GetEnumerator (DList< T > wrapper)

Maybe< T >	TryPopFirst ()

Maybe< T >	TryPeekFirst ()

Maybe< T >	TryPopLast ()

Maybe< T >	TryPeekLast ()

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

int	BinarySearch< K > (K k, Func< T, K, int > compare, bool lowerBound=true)

InternalDList< T >	Clone ()

void	CopyTo (int sourceIndex, T[] destination, int destinationIndex, int subcount)

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

DList< T >	AsDList ()
	Returns a DList{T} wrapped around this list. More...

void	Sort (Comparison< T > comp)

Memory< T >	AsContiguousMemory ()
	Rearranges the collection if necessary so that all elements are in a single contiguous block of memory, then returns that block. More...

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

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

Static Public Member Functions
static int	Min (int x, int y)

Member Function Documentation

void Loyc.Collections.Impl.InternalDList< T >.Add ( T item )

inline

An alias for PushLast().

Memory<T> Loyc.Collections.Impl.InternalDList< T >.AsContiguousMemory ( )

inline

Rearranges the collection if necessary so that all elements are in a single contiguous block of memory, then returns that block.

DList<T> Loyc.Collections.Impl.InternalDList< T >.AsDList ( )

inline

Returns a DList{T} wrapped around this list.

WARNING: in order to run in O(1) time, the two lists (InternalDList and DList) share the same array, but not the same internal state. You must stop using one list after modifying the other, because changes to one list may have strange effects in the other list.

IListSource<T> IListSource<T>. Loyc.Collections.Impl.InternalDList< 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 >.

InternalDList<T> Loyc.Collections.Impl.InternalDList< 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 >.

Remarks

Nested classes

Public fields

Public static fields

Properties

Public Member Functions

Static Public Member Functions

Member Function Documentation