Loyc.Collections.ISparseList< T > Interface Template Reference

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.Essentials/Collections/Interfaces/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< out T >
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...

Member Function Documentation

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

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

Inserts empty space starting at the specified index.

Exceptions

OverflowException	index + count overflowed.
ArgumentOutOfRangeException	index or count</c 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.

Implemented in Loyc.Collections.SparseAList< T >.