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

A sparse A-List that implements ISparseList<T>. More...


Source file:
Inheritance diagram for Loyc.Collections.SparseAList< T >:
Loyc.Collections.AListBase< T > Loyc.Collections.ISparseListEx< T > Loyc.Collections.IListEx< T > Loyc.Collections.IListRangeMethods< T > Loyc.Collections.ISparseList< T > Loyc.Collections.IListEx< T > Loyc.Collections.IListAndListSource< T > Loyc.Collections.ICollectionEx< T > Loyc.Collections.IArray< T > Loyc.Collections.IListRangeMethods< T > Loyc.Collections.IAddRange< T > Loyc.Collections.ICount Loyc.Collections.IAddRange< T > Loyc.Collections.ISinkArray< T > Loyc.Collections.IListSource< T > Loyc.Collections.IIsEmpty Loyc.Collections.IAddRange< T > Loyc.Collections.ISinkCollection< T > Loyc.Collections.ICollectionAndReadOnly< T > Loyc.Collections.ICollectionAndReadOnly< T > Loyc.Collections.IListSource< T > Loyc.Collections.IListRangeMethods< T > Loyc.Collections.IArray< T > Loyc.Collections.ICollectionEx< T > Loyc.Collections.IListAndListSource< T > Loyc.Collections.IListAndListSource< T > Loyc.Collections.ISparseListSource< T >

Remarks

A sparse A-List that implements ISparseList<T>.

An article about this class is available.

The sparse A-List is implemented similarly to a normal A-List; the main difference is that leaf nodes have a list of (int, T) pairs rather than a list of T values. The integers represent the relative index of each T value, as an offset from the beginning of the node. This allows an arbitrary amount of empty space to exist between each T value in the list, making it sparse.

SparseAList is a precise sparse list, meaning that you can rely on it to keep track of which indexes are "set" and which are "empty" (the IsSet method tells you which).

TODO: Add support for A-List tree observers (IAListTreeObserver(K,T))

Properties

sealed override T this[int index] [get, set]
 
- 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.IArray< T >
new T this[int index] [get, set]
 Gets or sets an element of the array-like collection. More...
 
- Properties inherited from Loyc.Collections.ISinkArray< T >
this[int index] [set]
 

Public Member Functions

 SparseAList (IEnumerable< T > items)
 
 SparseAList (IListSource< T > items)
 
 SparseAList (ISparseListSource< T > items)
 
 SparseAList (int maxLeafSize)
 
 SparseAList (int maxLeafSize, int maxInnerSize)
 
 SparseAList (SparseAList< T > items, bool keepListChangingHandlers)
 
sealed override void Add (T item)
 
void AddRange (IEnumerable< T > list)
 
sealed override void Insert (int index, T item)
 
void InsertRange (int index, SparseAList< T > source)
 
void InsertRange (int index, SparseAList< T > source, bool move)
 
sealed override void InsertRange (int index, IEnumerable< T > list)
 
sealed override void InsertRange (int index, IListSource< T > list)
 
void InsertRange (int index, ISparseListSource< T > list)
 Inserts another sparse list into this one. More...
 
new SparseAList< T > Clone ()
 
SparseAList< T > Clone (bool keepListChangingHandlers)
 
SparseAList< T > CopySection (int start, int subcount)
 
new SparseAList< T > RemoveSection (int start, int count)
 
void Swap (SparseAList< T > other)
 Swaps the contents of two SparseAList<T>s in O(1) time. More...
 
virtual void Append (SparseAList< T > other)
 
virtual void Append (SparseAList< T > other, bool move)
 
virtual void Prepend (SparseAList< T > other)
 Prepends an AList to this list in sublinear time. More...
 
virtual void Prepend (SparseAList< T > other, bool move)
 Prepends an AList to this list in sublinear time. More...
 
sealed override bool TrySet (int index, T value)
 
void ClearSpace (int index, int count=1)
 Unsets the range of indices index to index+count-1 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...
 
bool IsSet (int index)
 Determines whether a value exists at the specified index. More...
 
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...
 
override int IndexOf (T item)
 
int GetRealImmutableCount ()
 
int GetRealItemCount ()
 
- 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...
 
- Public Member Functions inherited from Loyc.Collections.ICollectionEx< T >
int RemoveAll (Predicate< T > match)
 Removes the all the elements that match the conditions defined by the specified predicate. More...
 
- Public Member Functions inherited from Loyc.Collections.ISinkCollection< T >
void Clear ()
 
bool Remove (T item)
 
- Public Member Functions inherited from Loyc.Collections.IAdd< T >
void Add (T item)
 
- Public Member Functions inherited from Loyc.Collections.IListRangeMethods< T >
void RemoveRange (int index, int amount)
 

Protected Member Functions

 SparseAList (AListBase< int, T > original, AListNode< int, T > section)
 
override AListNode< int, T > NewRootLeaf ()
 
override void Clone (out AListBase< T > clone)
 
override AListBase< T > cov_RemoveSection (int start, int count)
 

Member Function Documentation

void Loyc.Collections.SparseAList< T >.ClearSpace ( int  index,
int  count = 1 
)
inline

Unsets the range of indices index to index+count-1 inclusive. If index + count > Count, the sparse list shall enlarge Count to be equal to index + count.

Exceptions
ArgumentOutOfRangeExceptionindex or count was negative.
OverflowExceptionindex + count overflowed.

Implements Loyc.Collections.ISparseList< T >.

void Loyc.Collections.SparseAList< T >.InsertRange ( int  index,
ISparseListSource< T >  list 
)
inline

Inserts another sparse list into this one.

Implements Loyc.Collections.ISparseListEx< T >.

void Loyc.Collections.SparseAList< T >.InsertSpace ( int  index,
int  count = 1 
)
inline

Inserts empty space starting at the specified index.

Exceptions
OverflowExceptionindex + count overflowed.
ArgumentOutOfRangeExceptionindex or count</c

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.

Implements Loyc.Collections.ISparseList< T >.

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

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.

Implements Loyc.Collections.ISparseListSource< T >.

T Loyc.Collections.SparseAList< T >.NextHigherItem ( ref int?  index)
inline

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.

Implements Loyc.Collections.ISparseListSource< T >.

T Loyc.Collections.SparseAList< T >.NextLowerItem ( ref int?  index)
inline

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.

Implements Loyc.Collections.ISparseListSource< T >.

virtual void Loyc.Collections.SparseAList< T >.Prepend ( SparseAList< T >  other)
inlinevirtual

Prepends an AList to this list in sublinear time.

Parameters
otherA list of items to be added to the front of this list (at index 0).
virtual void Loyc.Collections.SparseAList< T >.Prepend ( SparseAList< T >  other,
bool  move 
)
inlinevirtual

Prepends an AList to this list in sublinear time.

Parameters
otherA list of items to be added to the front of this list (at index 0).
void Loyc.Collections.SparseAList< T >.Swap ( SparseAList< T >  other)
inline

Swaps the contents of two SparseAList<T>s in O(1) time.

Any observers are also swapped.