Enhanced C#
Language of your choice: library documentation
Public Member Functions | List of all members
Loyc.Collections.ISparseListSource< T > Interface Template Reference

Represents a read-only indexed list in which parts of the index space may be unused or "clear". More...


Source file:
Inheritance diagram for Loyc.Collections.ISparseListSource< T >:
Loyc.Collections.IListSource< T > Loyc.Collections.ISparseList< T > Loyc.Collections.ListSourceAsSparse< T > Loyc.Collections.ISparseListEx< T > Loyc.Collections.SparseAList< T >

Remarks

Represents a read-only 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:

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

See also
LCExt.AsSparse

Public Member Functions

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

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

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.

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.

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

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.

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

Implemented in Loyc.Collections.SparseAList< T >, and Loyc.Collections.ListSourceAsSparse< T >.