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...
new ISparseListSource< T >	Slice (int start, int count=int.MaxValue)
	Returns a sub-range of this list. Parameters start The new range will start at this index in the current list (this location will be index [0] in the new range). count The desired number of elements in the new range, or int.MaxValue to get all elements until the end of the list. Returns Returns a sub-range of this range. Exceptions ArgumentException The start index was below zero. The (start, count) range is allowed to be invalid, as long as start is zero or above. If count is below zero, or if start is above the original Count, the Count of the new slice is set to zero. if (start + count) is above the original Count, the Count of the new slice is reduced to this.Count - start. Implementation note: do not compute (start + count) because it may overflow. Instead, test whether (count > this.Count - start). Most collections should use the following implementation: IListSource<T> IListSource<T>.Slice(int start, int count) { return Slice(start, count); } public Slice_<T> Slice(int start, int count) { return new Slice_<T>(this, start, count); }
Public Member Functions inherited from Loyc.Collections.ITryGet< in K, out V >
V	TryGet (K key, out bool fail)
	Gets the item for the specified key or index, and does not throw an exception on failure. More...

Additional Inherited Members
Properties inherited from Loyc.Collections.ISource< out T >
new int	Count [get]
	Gets the number of items in the collection. More...
Properties inherited from Loyc.Collections.ICount
int	Count [get]
	Gets the number of items in the collection. More...
Properties inherited from Loyc.Collections.IIsEmpty
bool	IsEmpty [get]
Properties inherited from Loyc.Collections.IIndexed< in K, out V >
V	this[K key] [get]
	Gets the value associated with the specified key. 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 >, Loyc.Collections.SparseListSourceSlice< T, TList >, 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

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 >, Loyc.Collections.SparseListSourceSlice< T, TList >, 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

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 >, Loyc.Collections.SparseListSourceSlice< T, TList >, and Loyc.Collections.ListSourceAsSparse< T >.