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:

• /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 = EmptyArray<T>.Value
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]

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)
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 ()
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)
void	Sort (int index, int count, 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...

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

Member Function Documentation

Add()

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

inline

An alias for PushLast().

AsDList()

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.