A sparse A-List that implements ISparseList{T}. More...

Source file:

/Core/Loyc.Collections/ALists/SparseAList.cs

Inheritance diagram for Loyc.Collections.SparseAList< T >:

Remarks

A sparse A-List that implements ISparseList{T}.

An article about this class is available.

The sparse A-List is implemented similarly to a normal A-List; the main difference is that leaf nodes have a list of (int, T) pairs rather than a list of T values. The integers represent the relative index of each T value, as an offset from the beginning of the node. This allows an arbitrary amount of empty space to exist between each T value in the list, making it sparse.

SparseAList is a precise sparse list, meaning that you can rely on it to keep track of which indexes are "set" and which are "empty" (the IsSet method tells you which).

TODO: Add support for A-List tree observers (IAListTreeObserver(K,T))

Properties
sealed override T	this[int index] `[get, set]`

Properties inherited from Loyc.Collections.AListBase< T >
new T	First `[get, set]`

new T	Last `[get, set]`

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

Properties inherited from Loyc.Collections.AListBase< K, T >
virtual ListChangingHandler< T, IListSource< T > >	ListChanging
	Event for learning about changes in progress on a list. More...

byte	TreeHeight `[get]`

T	Last `[get]`

T	this[int index] `[get]`

int	ObserverCount `[get]`
	Returns the number of tree observers attached to this list. More...

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.IHasMFirst< T >
new T	First `[get, set]`

Properties inherited from Loyc.Collections.IHasFirst< out T >
T	First `[get]`
	Gets the first item in the deque. More...

Properties inherited from Loyc.Collections.IHasMLast< T >
new T	Last `[get, set]`

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

Properties inherited from Loyc.Collections.IListEx< T >
new int	Count `[get]`

Properties inherited from Loyc.Collections.IArray< T >
new T	this[int index] `[get, set]`
	Gets or sets an element of the array-like collection. More...

Properties inherited from Loyc.Collections.IArraySink< in T >
T	this[int index] `[set]`

Public Member Functions
	SparseAList (IEnumerable< T > items)

	SparseAList (IListSource< T > items)

	SparseAList (ISparseListSource< T > items)

	SparseAList (int maxNodeSize)

	SparseAList (int maxLeafSize, int maxInnerSize)

	SparseAList (SparseAList< T > items, bool keepListChangingHandlers)

sealed override void	Add (T item)

void	AddRange (IEnumerable< T > list)

sealed override void	Insert (int index, T item)

void	InsertRange (int index, SparseAList< T > source)

void	InsertRange (int index, SparseAList< T > source, bool move)

sealed override void	InsertRange (int index, IEnumerable< T > list)

sealed override void	InsertRange (int index, IListSource< T > list)

void	InsertRange (int index, ISparseListSource< T > list)
	Inserts another sparse list into this one. More...

new SparseAList< T >	Clone ()

SparseAList< T >	Clone (bool keepListChangingHandlers)

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

new SparseAList< T >	RemoveSection (int start, int count)

void	Swap (SparseAList< T > other)
	Swaps the contents of two SparseAList{T}s in O(1) time. More...

virtual void	Append (SparseAList< T > other)

virtual void	Append (SparseAList< T > other, bool move)

virtual void	Prepend (SparseAList< T > other)
	Prepends an AList to this list in sublinear time. More...

virtual void	Prepend (SparseAList< T > other, bool move)
	Prepends an AList to this list in sublinear time. More...

sealed override bool	TrySet (int index, T value)

void	ClearSpace (int index, int count=1)
	Unsets the range of indices `index` to `index+count-1` inclusive. If `index + count > Count`, the sparse list shall enlarge `Count` to be equal to `index + count`. More...

void	AddSpace (int count=1)

void	InsertSpace (int index, int count=1)
	Inserts empty space starting at the specified index. More...

bool	IsSet (int index)
	Determines whether a value exists at the specified index. More...

T	NextHigherItem (ref int?index)
	Increases `index` by at least one to reach the next index that is not classified as empty space, and returns the item at that index. More...

T	NextLowerItem (ref int?index)
	Decreases `index` by at least one to reach the next index that is not classified as empty space, and returns the item at that index. More...

override int	IndexOf (T item)
	Finds an index of an item in the list. More...

int	GetRealImmutableCount ()

int	GetRealItemCount ()

new SparseListSourceSlice< T, ISparseListSource< T > >	Slice (int start, int count=int.MaxValue)
	Returns a sub-range of this list. More...

Public Member Functions inherited from Loyc.Collections.AListBase< T >
	AListBase (int maxNodeSize)

	AListBase (int maxLeafSize, int maxInnerSize)

	AListBase (AListBase< T > items, bool keepListChangingHandlers)

void	AddRange (IListSource< T > source)

void	AddRange (AList< T > source)

void	Resize (int newSize)

bool	Contains (T item)
	Returns true if-and-only-if the specified item exists in the list. More...

bool	Remove (T item)
	Finds a specific item and removes it. If duplicates of the item exist, only the first occurrence is removed. More...

AListBase< T >	Clone ()

AListBase< T >	RemoveSection (int start, int count)

new ListSlice< T >	Slice (int start, int length=int.MaxValue)
	Returns a sub-range of this list. More...

Public Member Functions inherited from Loyc.Collections.AListBase< K, T >
void	RemoveAt (int index)

void	RemoveRange (int index, int amount)

int	RemoveAll (Predicate< T > match)
	Removes all the elements that match the conditions defined by the specified predicate. More...

virtual void	Clear ()

IEnumerable< int >	IndexesOf (T item)
	Returns a sequence of integers that represent the locations where a given item appears in the list. More...

virtual IEnumerable< int >	IndexesOf (T item, int minIndex, int maxIndex)

int	FirstIndexOf (T item, int startIndex, EqualityComparer< T >?comparer=null)
	Scans the list starting at startIndex and going upward, and returns the index of an item that matches the first argument. More...

int	LinearScanFor (T item, int startIndex, EqualityComparer< T >?comparer=null)

void	CopyTo (T[] array, int arrayIndex)

Enumerator	GetEnumerator ()

Enumerator	GetEnumerator (int startIndex)

Enumerator	GetEnumerator (int start, int subcount)

Enumerator	GetEnumerator (int start, int subcount, bool startAtEnd)

T	TryGet (int index, out bool fail)

virtual void	Freeze ()
	Prevents further changes to the list. More...

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

int	GetImmutableCount ()
	Diagnostic method. Returns the number of elements of the list that are located in immutable nodes, which will be copied if modified. Used by the test suite. More...

virtual long	CountSizeInBytes (int sizeOfElement, int sizeOfKey=8)
	Tallies the memory use, in bytes, of the entire list including this object, the root node, all child nodes, and all arrays. More...

virtual bool	AddObserver (IAListTreeObserver< K, T > observer)
	Attaches a tree observer to this object. More...

virtual bool	RemoveObserver (IAListTreeObserver< K, T > observer)
	Removes a previously attached tree observer from this list. More...

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

Public Member Functions inherited from Loyc.Collections.ICollectionSource< T >
void	CopyTo (T[] array, int arrayIndex)
	Copies the elements of the collection to an Array, starting at a particular array index. More...

Public Member Functions inherited from Loyc.Collections.ICollectionSink< in T >
void	Clear ()

bool	Remove (T item)

Public Member Functions inherited from Loyc.Collections.IListRangeMethods< in T >
void	RemoveRange (int index, int amount)

Protected Member Functions
	SparseAList (AListBase< int, T > original, AListNode< int, T >?section)

override AListNode< int, T >	NewRootLeaf ()

override void	Clone (out AListBase< T > clone)

override AListBase< T >	cov_RemoveSection (int start, int count)

Protected Member Functions inherited from Loyc.Collections.AListBase< T >
	AListBase (AListBase< int, T > original, AListNode< int, T >?section)

override AListInnerBase< int, T >	SplitRoot (AListNode< int, T > left, AListNode< int, T > right)

void	DetectSizeOverflow (int insertSize)
	Throws OverflowException if inserting the specified number of items would cause Count to overflow. More...

void	BeginInsertRange (int index, IListSource< T > items, int itemsCount)

void	DoneInsertRange (int amountInserted)

void	InsertRange (int index, AListBase< T > source, bool move)

virtual void	Combine (AListBase< T > other, bool move, bool append)

Protected Member Functions inherited from Loyc.Collections.AListBase< K, T >
	AListBase (int maxNodeSize)

	AListBase (int maxLeafSize, int maxInnerSize)

	AListBase (AListBase< K, T > items, bool keepListChangingHandlers)
	Cloning constructor. Does not duplicate the observer (IAListTreeObserver{K,T}), if any, because it may not be cloneable. More...

	AListBase (AListBase< K, T > original, AListNode< K, T >?section)
	This is the constructor that CopySection(), which can be defined by derived classes, should call to create a sublist of a list. Used in conjunction with CopySectionHelper(). More...

abstract AListInnerBase< K, T >	SplitRoot (AListNode< K, T > left, AListNode< K, T > right)

virtual Enumerator	NewEnumerator (uint start, uint firstIndex, uint lastIndex)

void	CheckPoint ()

void	AutoThrow ()

void	AutoCreateOrCloneRoot ()

void	AutoSplit (AListNode< K, T >?splitLeft, AListNode< K, T >?splitRight)

void	HandleChangedOrUndersizedRoot (AListNode< K, T > result)

virtual void	ClearInternal (bool forceClear)
	Clears the tree. More...

void	ThrowIndexOutOfRange ()

AListNode< K, T >	CopySectionHelper (int start, int subcount)
	Together with the AListBase{K,T}.AListBase(AListBase{K,T},AListNode{K,T}) constructor, this method helps implement the CopySection() method in derived classes, by cloning a section of the tree. More...

AListNode< K, T >	CopySectionHelper (uint start, uint subcount)

void	SwapHelper (AListBase< K, T > other, bool swapObservers)
	Swaps two ALists. More...

Additional Inherited Members
Public fields inherited from Loyc.Collections.AListBase< K, T >
int	Count => (int)_count

bool	IsEmpty => _count == 0

T	First => this[0]

bool	IsFrozen => _freezeMode == FreezeMode.Frozen

AListReverseView< K, T >	ReverseView => new AListReverseView<K

Protected fields inherited from Loyc.Collections.AListBase< K, T >
uint	_count

ushort	_version

ushort	_maxLeafSize

byte	_maxInnerSize

byte	_treeHeight

FreezeMode	_freezeMode = FreezeMode.NotFrozen

int	BaseClassSizeInBytes => IntPtr.Size * 5 + (IntPtr.Size <= 4 ? 12 : 16)

Events inherited from Loyc.Collections.INotifyListChanging< T, TCollection >
ListChangingHandler< T, TCollection >	ListChanging
	Occurs when the collection associated with this interface is about to change. More...

Member Function Documentation

void Loyc.Collections.SparseAList< T >.ClearSpace	(	int	index,
		int	count = `1`
	)

inline

Unsets the range of indices index to index+count-1 inclusive. If index + count > Count, the sparse list shall enlarge Count to be equal to index + count.

Exceptions

ArgumentOutOfRangeException	`index` or `count` was negative.
OverflowException	`index + count` overflowed.

Implements Loyc.Collections.ISparseList< T >.

override int Loyc.Collections.SparseAList< T >.IndexOf ( T item )

inlinevirtual

Finds an index of an item in the list.

Parameters

item	An item for which to search.

Returns: An index of the item.

The default implementation simply calls AListBase{K,T}.LinearScanFor. This method is called by Remove and Contains.

Reimplemented from Loyc.Collections.AListBase< T >.

void Loyc.Collections.SparseAList< T >.InsertRange	(	int	index,
		ISparseListSource< T >	list
	)

inline

Inserts another sparse list into this one.

Implements Loyc.Collections.ISparseListEx< T >.

void Loyc.Collections.SparseAList< T >.InsertSpace	(	int	index,
		int	count = `1`
	)

inline

Inserts empty space starting at the specified index.

Exceptions

OverflowException	`index + count` overflowed.
ArgumentOutOfRangeException	`index` or `count` was negative. If `index > Count`, this method may throw: if, for this kind of list, setting this[i] for some invalid i>=0 throws `ArgumentOutOfRangeException`, then so too does this method throw. If you want the list to be enlarged instead, call `Clear(index, 0)` first, since the contract of Clear() requires it not to throw in the same situation.

Implements Loyc.Collections.ISparseList< T >.

bool Loyc.Collections.SparseAList< T >.IsSet ( int index )

inline

Determines whether a value exists at the specified index.

Parameters

index

Returns: true if a value is assigned at the specified index, or false if index is part of an empty space, or is outside the range of indexes that exist.

Implements Loyc.Collections.ISparseListSource< T >.

T Loyc.Collections.SparseAList< T >.NextHigherItem ( ref int? index )

inline

Increases index by at least one to reach the next index that is not classified as empty space, and returns the item at that index.

Parameters

index This parameter is increased by at least one, and perhaps more than one so that it refers to an index where there is a value. If index is null upon entering this method, the first non-empty space in the list is found. If there are no values at higher indexes, if the list is empty or if index + 1 >= Count, index is null when the method returns.

This method must skip over all indexes i for which IsSet(i) returns false, and return the next index for which IsSet(i) returns true. This method must accept any integer as input, including invalid indexes.

Implements Loyc.Collections.ISparseListSource< T >.

T Loyc.Collections.SparseAList< T >.NextLowerItem ( ref int? index )

inline

Decreases index by at least one to reach the next index that is not classified as empty space, and returns the item at that index.

Parameters

index This parameter is increased by at least one, and perhaps more than one so that it refers to an index where there is a value. If index is null upon entering this method, the last non-empty space in the list is found. If there are no values at lower indexes, if the list is empty or if index is 0 or less, index is null when the method returns.

This method must skip over all indexes i for which IsSet(i) returns false, and return the next index for which IsSet(i) returns true. This method must accept any integer as input, including invalid indexes.

Implements Loyc.Collections.ISparseListSource< T >.

virtual void Loyc.Collections.SparseAList< T >.Prepend ( SparseAList< T > other )

inlinevirtual

Prepends an AList to this list in sublinear time.

Parameters

other A list of items to be added to the front of this list (at index 0).

virtual void Loyc.Collections.SparseAList< T >.Prepend	(	SparseAList< T >	other,
		bool	move
	)

inlinevirtual

Prepends an AList to this list in sublinear time.

Parameters

other A list of items to be added to the front of this list (at index 0).

new SparseListSourceSlice<T, ISparseListSource<T> > Loyc.Collections.SparseAList< T >.Slice	(	int	start,
		int	count = `int.MaxValue`
	)

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

void Loyc.Collections.SparseAList< T >.Swap ( SparseAList< T > other )

inline

Swaps the contents of two SparseAList{T}s in O(1) time.

Any observers are also swapped.

Remarks

Properties

Public Member Functions

Protected Member Functions

Additional Inherited Members

Member Function Documentation