Represents a sparse list that allows insertion and removal of items and empty spaces. In a sparse list, some spaces can be "clear" meaning that they have no value. More...

Source file:

/Core/Loyc.Interfaces/Collections/ISparseList.cs

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

Remarks

Represents a sparse list that allows insertion and removal of items and empty spaces. In a sparse list, some spaces can be "clear" meaning that they have no value.

Template Parameters

T

Classes that implement this interface should be designed so that large empty spaces in the list consume no memory, or very little memory. Furthermore, insertions and removals at random indexes should take no more than O(M) amortized time to complete, where M is the number of elements actually set (non-empty spaces), and Count >= M. (Sparse lists do not have to keep track of M itself, though, so there is no property to retrieve this value).

This interface has special methods for creating empty spaces: ClearSpace(int, int) and InsertSpace(int, int). The implementation can treat all other insertions and changes as non-empty values; for example, given code like

ISparseList<T> list = ...;
foreach (int i in Enumerable.Range(1000))
    list.Add(default(T));

A sparse list is allowed to treat the last 1000 items as "clear" (saving memory) or "set" (allocating memory) depending on how it is implemented. Since the .NET framework does not allow fast bitwise comparisons of a generic T (in other words, there is no fast, generic way to compare a T value with default(T)), implementations will typically treat the last 1000 items as "set" and unnecessarily allocate memory for them. Blame Microsoft.

This interface has no method to insert another sparse list into the current one, but ISparseListEx<T> does.

A sparse list is allowed to behave like IAutoSizeArray<T> when setting an invalid non-negative index. When you set this[i] where i >= 0, the Count may automatically increase to i + 1 if necessary, or the setter may throw ArgumentOutOfRangeException. Even if the setter succeeds, the getter of this[i] may still throw ArgumentOutOfRangeException when i is an invalid index.

The indexer (this[i]) returns a default value, typically default(T), when the specified index is valid but clear.

Sparse list implementations do not have to perfectly track which spaces are clear and which spaces are set; in particular, implementations are allowed to return true from IsSet for any valid index.

If the default value is t and you set this[i] = t, a sparse list is allowed to return true or false from IsSet(i).
After you call Clear(i), a sparse list is still allowed to return true from IsSet(i).
After you set this[i] = v where v is not the default value, IsSet(i) must return true.

The purpose of this freedom is to permit implementations that use arrays of T[] for regions that are mostly filled. For example, if 95 out of 100 indexes in a certain region are filled, an implementation may decide it is more efficient to use an array that discards information about the empty spaces.

On the other hand, some implementations are precise, and will always report that IsSet(i)==false after you call Clear(i) or InsertSpace(i).

Public Member Functions
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	InsertSpace (int index, int count=1)
	Inserts empty space starting at the specified index. More...

Public Member Functions inherited from Loyc.Collections.ISparseListSource< T >
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...

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

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

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.IContains< T >
bool	Contains (T item)
	Returns true if and only if the collection contains the specified item. More...

Member Function Documentation

◆ ClearSpace()

void Loyc.Collections.ISparseList< T >.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.

Exceptions

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

Implemented in Loyc.Collections.SparseAList< T >.

◆ InsertSpace()

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

Inserts empty space starting at the specified index.