Enhanced C#
Language of your choice: library documentation
Nested classes | Public fields | Public static fields | Properties | Public Member Functions | Static Public Member Functions | List of all members
Loyc.Collections.Impl.InternalDList< T > Struct Template Reference

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:
Inheritance diagram for Loyc.Collections.Impl.InternalDList< T >:
Loyc.Collections.IListSource< T >


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>.) For these and other reasons, one should not expose it in a public API, and it should only be used when performance is very 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 make List<T> from InternalList<T> in O(1) time; so boxing the InternalList<T> is the only fast way to get an instance of IList<T>.

Nested classes

class  Enumerator

Public fields

int _start

Public static fields

static readonly T[] EmptyArray = EmptyArray<T>.Value
static readonly InternalDList< T > Empty = new InternalDList<T>(0)


T[] InternalArray [get]
int Capacity [get, set]
this[int index] [get, set]
this[int index, T defaultValue] [get]
int Count [get]
bool IsReadOnly [get]
First [get, set]
Last [get, set]
bool IsEmpty [get]

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)
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)
IRange< T > IListSource< T >. Slice (int start, int count)
InternalDList< T > Slice (int start, int subcount)
IEnumerator< T > IEnumerable< T >. GetEnumerator ()
System.Collections.IEnumerator System.Collections.IEnumerable. GetEnumerator ()
IEnumerator< T > GetEnumerator ()
IEnumerator< T > 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)
void Sort (int index, int count, Comparison< T > comp)
- Public Member Functions inherited from Loyc.Collections.IListSource< T >
TryGet (int index, out bool fail)
 Gets the item at the specified index, and does not throw an exception on failure. More...
IRange< T > Slice (int start, int count=int.MaxValue)
 Returns a sub-range of this list. More...

Static Public Member Functions

static int Min (int x, int y)

Member Function Documentation

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

An alias for PushLast().

Referenced by Loyc.Syntax.BaseParserNoBacktracking< Token >.LT().

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

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.