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:

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

Inheritance diagram for Loyc.Collections.ISparseListSource< 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:

• Count returns int.MaxValue,
• NextHigherItem and NextLowerItem do a linear scan to find the next higher or lower key that exists.
• IsSet(int) returns the result of SortedDictionary<K,V>.ContainsKey, and
• IListSource<T>.TryGet(int, out bool) returns the value retrieved by SortedDictionary<K,V>.TryGetValue, setting 'fail' only if the index is negative.

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

Member Function Documentation

IsSet()

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

NextHigherItem()

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

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

Referenced by Loyc.Collections.LCInterfaces.Items< T >(), and Loyc.Collections.LCInterfaces.NextHigherIndex< T >().

NextLowerItem()

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

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

Referenced by Loyc.Collections.LCInterfaces.NextLowerIndex< T >().