Enhanced C#
Language of your choice: library documentation

Represents a readonly indexed list in which parts of the index space may be unused or "clear". More...
Represents a readonly indexed list in which parts of the index space may be unused or "clear".
This interface should be implemented by "sparse" data structures that are optimized for lists that have large gaps in them; for example, a sparse data structure with Count == 1000000
might really contain only a few elements, or it could even be completely empty. The Count
of a sparse list tells you the range of valid indexes that you are allowed to read, but since any or all of the space might be empty, it only gives an upper bound, not a lower bound, of the true size of the list.
When you read list[i]
, and i
is within an empty area of the sparse list, a default value is returned, which is normally default(T)
.
As an example, SortedDictionary<int, T>
could be viewed as a sparse list. Assuming the dictionary has no negative integers, you could create a wrapper around SortedDictionary<int, T>
that implements this interface as follows:
Count
returns int.MaxValue
, SortedDictionary
is not a very useful example in practise, though, because it does not provide a way for NextHigherItem and NextLowerItem to work efficiently, and it cannot efficiently support the ISparseList<T> interface. A more useful example is SparseAList{T} in Loyc.Collections.dll, which efficiently implements this interface and ISparseList<T>.
Public Member Functions  
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...  
bool Loyc.Collections.ISparseListSource< T >.IsSet  (  int  index  ) 
Determines whether a value exists at the specified index.
index 
Implemented in Loyc.Collections.SparseAList< T >, and Loyc.Collections.ListSourceAsSparse< T >.
T Loyc.Collections.ISparseListSource< 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.
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 nonempty 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.
Implemented in Loyc.Collections.SparseAList< T >, and Loyc.Collections.ListSourceAsSparse< T >.
T Loyc.Collections.ISparseListSource< 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.
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 nonempty 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.
Implemented in Loyc.Collections.SparseAList< T >, and Loyc.Collections.ListSourceAsSparse< T >.