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

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)
	Gets the item at the specified index, and does not throw an exception on failure. More...
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)
	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 ()
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)

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

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.

IRange<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:

IRange<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:

IRange<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.InternalDList< T >.TryGet ( int  index, out bool  fail  )

inline

Gets the item at the specified index, and does not throw an exception on failure.

Parameters

index	An index in the range 0 to Count-1.
fail	A flag that is set on failure.

Returns

The element at the specified index, or default(T) if the index is not valid.

In my original design, the caller could provide a value to return on failure, but this would not allow T to be marked as "out" in C# 4. For the same reason, we cannot have a ref/out T parameter. Instead, the following extension methods are provided:

bool TryGet(int index, ref T value);
T TryGet(int, T defaultValue);

Implements Loyc.Collections.IListSource< out T >.