Enhanced C#
Language of your choice: library documentation

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...
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.
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 (nonempty 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 nonempty values; for example, given code like
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 nonnegative 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.
t
and you set this[i] = t
, a sparse list is allowed to return true or false from IsSet(i)
. Clear(i)
, a sparse list is still allowed to return true from IsSet(i)
. 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+count1 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 >  
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 subrange of this list. More...  
void Loyc.Collections.ISparseList< T >.ClearSpace  (  int  index, 
int  count = 1 

) 
Unsets the range of indices index
to index+count1
inclusive. If index + count > Count
, the sparse list shall enlarge Count
to be equal to index + count
.
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.
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. 
Implemented in Loyc.Collections.SparseAList< T >.