Enhanced C#
Language of your choice: library documentation

Documentation moved to ecsharp.net

GitHub doesn't support HTTP redirects, so you'll be redirected in 3 seconds.

 All Classes Namespaces Functions Variables Enumerations Enumerator Properties Events Pages
Nested classes | Properties | Public Member Functions | Protected Member Functions | Protected fields | List of all members
Loyc.Collections.AListBase< K, T > Class Template Referenceabstract

Base class for the indexed tree-based data structures known as AList{T} and BList{T}. More...


Source file:
Inheritance diagram for Loyc.Collections.AListBase< K, T >:
Loyc.Collections.IListSource< out T > Loyc.Collections.INotifyListChanging< T > Loyc.Collections.IListSource< out T > Loyc.Collections.INotifyListChanging< T > Loyc.Collections.AListBase< K, T >.Enumerator Loyc.Collections.AListBase< K, T >.ObserverMgr Loyc.Collections.AListBase< T > Loyc.Collections.BDictionary< K, V > Loyc.Collections.BList< T > Loyc.Collections.AList< T > Loyc.Collections.SparseAList< T > Loyc.Collections.BMultiMap< K, V > Loyc.Collections.IndexedAList< T > Loyc.Collections.BMultiMap< K, V >.ValueList Loyc.Collections.BMultiMap< K, V >.ValueList

Remarks

Base class for the indexed tree-based data structures known as AList{T} and BList{T}.

Manages a collection of IAListTreeObserver{K, T}.

You can read articles about the AList family of data structures online.

AList{T} and BList{T} are excellent data structures to choose if you aren't sure what your requirements are. The main difference between them is that BList is sorted and AList is not. DList{T}, meanwhile, is a simpler data structure with a faster indexer and lower memory requirements. In fact, the leaf nodes of this class are built upon InternalDList{T}.

Classes derived from AListBase typically have the following abilities:

Derived classes provide the following additional capabilities:

As you can see, the A-List family of data structures allows you to accomplish a wide variety of tasks efficiently, so the letter "A" in A-List stands for All-purpose.

A-Lists use memory efficiently because they are similar to B+trees. A-Lists tend to use slightly more memory than List{T} but have lower peak memory usage, because their size never suddenly doubles. A-Lists use much less memory than HashSet{T}, so they are useful for storing large data sets in RAM.

The efficiency of various operations is affected by the maximum sizes of the inner nodes and leaf nodes, which can be set independently when constructing an AList{T} or BList{T}. Generally, larger leaf nodes allow faster indexing but slower insertions and removals. If the list is cloned frequently, smaller inner and leaf nodes will speed up all modifications (insertions, removals, and modification of individual items), although small node sizes suffer increased overhead (higher memory usage and slower indexing). The default inner node size of 16 is usually best for performance, because the binary searches required for lookups will have good locality-of-reference. Small size limits (less than 8) have a high overhead and are not recommended for any purpose except unit testing. The minimum allowed maximum node size is 3.

In general, the tree is structured so that indexing is faster than insertions and removals, even though these three operations have the same scalability, O(log N).

In general, this family of classes is NOT multithread-safe; concurrency support is the only major feature that AListBase lacks. It supports multiple readers concurrently, as long as the collection is not modified, so frozen instances ARE multithread-safe. However, classes derived from AListBase must not be accessed from other threads during any modification. There is a mechanism to detect illegal concurrent access and throw InvalidOperationException if it is detected, but this is not designed to be reliable; its main purpose is to help you find bugs. If concurrent modification is not detected, the AList will probably become corrupted and produce strange exceptions, or fail an assertion (in debug builds).

Although AListBase provides neither concurrent operations nor safety for concurrent modification, the fast-clone feature makes it a useful parallel data structure. Consider, for instance, a document editor that wants to run a spell-check on a background thread, with an AList(of Char) object representing the document. The spell checker cannot access the document if the user might modify it concurrently; luckily, it can be cloned instantly before starting the spell-checking thread. The root of the AList's B+ tree is marked frozen, and when the user modifies the original document, the AList will duplicate a few frozen nodes in order to modify them without crashing the spell-check operation that is running concurrently. You will, of course, have to deal with the fact that the spell-check results apply to an old version of the document, but at least the program won't crash and the user won't be blocked from editing while the spellcheck is running.

The disadvantage of the fast-clone approach is that the immutability of the tree cannot be cancelled. So if the spell-check finishes after a half-second and the user did not modify the document, the tree still remains frozen and will still have to be copied later when the user does modify it. Still, the copying is a pay-as-you-go cost, so the app will stay responsive and the entire tree will not be copied unless you make widespread changes to the collection (e.g. converting the document to all-uppercase.)

Template Parameters
KType of keys that are used to classify items in a tree
TType of each element in the list. The derived class must implement the GetKey method that converts T to K.

TODO:

Nested classes

class  Enumerator
 
class  ObserverMgr
 A multiplexer that is only created for ALists that have two or more attached intances of IAListTreeObserver{K,T}. More...
 

Properties

virtual ListChangingHandler< T > ListChanging
 Event for learning about changes in progress on a list. More...
 
byte TreeHeight [get]
 
int Count [get]
 
bool IsEmpty [get]
 
AListReverseView< K, T > ReverseView [get]
 
this[int index] [get]
 
bool IsFrozen [get]
 
First [get]
 
Last [get]
 
int ObserverCount [get]
 Returns the number of tree observers attached to this list. More...
 

Public Member Functions

void RemoveAt (int index)
 
void RemoveRange (int index, int amount)
 
int RemoveAll (Predicate< T > match)
 Removes all the elements that match the conditions defined by the specified predicate. More...
 
virtual void Clear ()
 
IEnumerable< int > IndexesOf (T item)
 Returns a sequence of integers that represent the locations where a given item appears in the list. More...
 
virtual IEnumerable< int > IndexesOf (T item, int minIndex, int maxIndex)
 
int LinearScanFor (T item, int startIndex, EqualityComparer< T > comparer)
 Scans the list starting at startIndex and going upward, and returns the index of an item that matches the first argument. More...
 
void CopyTo (T[] array, int arrayIndex)
 
Enumerator GetEnumerator ()
 
Enumerator GetEnumerator (int startIndex)
 
Enumerator GetEnumerator (int start, int subcount)
 
Enumerator GetEnumerator (int start, int subcount, bool startAtEnd)
 
TryGet (int index, out bool fail)
 Gets the item at the specified index, and does not throw an exception on failure. More...
 
virtual void Freeze ()
 Prevents further changes to the list. More...
 
Slice_< T > Slice (int start, int length)
 Returns a sub-range of this list. More...
 
int GetImmutableCount ()
 Diagnostic method. Returns the number of elements of the list that are located in immutable nodes, which will be copied if modified. Used by the test suite. More...
 
virtual bool AddObserver (IAListTreeObserver< K, T > observer)
 Attaches a tree observer to this object. More...
 
virtual bool RemoveObserver (IAListTreeObserver< K, T > observer)
 Removes a previously attached tree observer from this list. More...
 

Protected Member Functions

 AListBase (int maxLeafSize)
 
 AListBase (int maxLeafSize, int maxInnerSize)
 
 AListBase (AListBase< K, T > items, bool keepListChangingHandlers)
 Cloning constructor. Does not duplicate the observer (IAListTreeObserver{K,T}), if any, because it may not be cloneable. More...
 
 AListBase (AListBase< K, T > original, AListNode< K, T > section)
 This is the constructor that CopySection(), which can be defined by derived classes, should call to create a sublist of a list. Used in conjunction with CopySectionHelper(). More...
 
abstract AListNode< K, T > NewRootLeaf ()
 
abstract AListInnerBase< K, T > SplitRoot (AListNode< K, T > left, AListNode< K, T > right)
 
virtual Enumerator NewEnumerator (uint start, uint firstIndex, uint lastIndex)
 
void CheckPoint ()
 
void AutoThrow ()
 
void AutoCreateOrCloneRoot ()
 
void AutoSplit (AListNode< K, T > splitLeft, AListNode< K, T > splitRight)
 
void HandleChangedOrUndersizedRoot (AListNode< K, T > result)
 
virtual void ClearInternal (bool forceClear)
 Clears the tree. More...
 
AListNode< K, T > CopySectionHelper (int start, int subcount)
 Together with the AListBase{K,T}.AListBase(AListBase{K,T},AListNode{K,T}) constructor, this method helps implement the CopySection() method in derived classes, by cloning a section of the tree. More...
 
AListNode< K, T > CopySectionHelper (uint start, uint subcount)
 
void SwapHelper (AListBase< K, T > other, bool swapObservers)
 Swaps two ALists. More...
 

Protected fields

uint _count
 
ushort _version
 
ushort _maxLeafSize
 
byte _maxInnerSize
 
byte _treeHeight
 
byte _freezeMode = NotFrozen
 
const byte NotFrozen = 0
 
const byte Frozen = 1
 
const byte FrozenForListChanging = 2
 
const byte FrozenForConcurrency = 3
 

Additional Inherited Members

- Events inherited from Loyc.Collections.INotifyListChanging< T >
ListChangingHandler< T > ListChanging
 Occurs when the collection associated with this interface is about to change. More...
 

Constructor & Destructor Documentation

Loyc.Collections.AListBase< K, T >.AListBase ( AListBase< K, T >  items,
bool  keepListChangingHandlers 
)
inlineprotected

Cloning constructor. Does not duplicate the observer (IAListTreeObserver{K,T}), if any, because it may not be cloneable.

Parameters
itemsOriginal list
keepListChangingHandlersWhether to duplicate the delegate for ListChanging; if false, this new object will not include any handlers for the ListChanging event.

This constructor leaves the new clone unfrozen.

Loyc.Collections.AListBase< K, T >.AListBase ( AListBase< K, T >  original,
AListNode< K, T >  section 
)
inlineprotected

This is the constructor that CopySection(), which can be defined by derived classes, should call to create a sublist of a list. Used in conjunction with CopySectionHelper().

Member Function Documentation

virtual bool Loyc.Collections.AListBase< K, T >.AddObserver ( IAListTreeObserver< K, T >  observer)
inlinevirtual

Attaches a tree observer to this object.

Returns
True if the observer was added, false if it was already attached.

The tree observer mechanism is much more advanced, and less efficient, than the ListChanging event. You should use that event instead if you can accomplish what you need with it.

Observers cannot be added when the list is frozen, although they can be removed.

This feature can be disabled in a derived class by overriding this method to throw NotSupportedException.

virtual void Loyc.Collections.AListBase< K, T >.ClearInternal ( bool  forceClear)
inlineprotectedvirtual

Clears the tree.

Parameters
forceClearIf true, the list is cleared even if _listChanging throws an exception. If false, _listChanging can cancel the operation by throwing an exception.

If the list is frozen, it is not cleared even if forceClear=true.

AListNode<K, T> Loyc.Collections.AListBase< K, T >.CopySectionHelper ( int  start,
int  subcount 
)
inlineprotected

Together with the AListBase{K,T}.AListBase(AListBase{K,T},AListNode{K,T}) constructor, this method helps implement the CopySection() method in derived classes, by cloning a section of the tree.

virtual void Loyc.Collections.AListBase< K, T >.Freeze ( )
inlinevirtual

Prevents further changes to the list.

After calling this method, any attempt to modify the list will cause a ReadOnlyException to be thrown.

Note: although they will no longer be called, any ListChanging handlers will not be forgotten, because it is possible to clone an unfrozen version of the list while keeping those handlers.

This feature can be disabled in a derived class by overriding this method to throw NotSupportedException.

int Loyc.Collections.AListBase< K, T >.GetImmutableCount ( )
inline

Diagnostic method. Returns the number of elements of the list that are located in immutable nodes, which will be copied if modified. Used by the test suite.

Variable time required. Scans all nodes if none are immutable; stops at the root if the root is immutable.

IEnumerable<int> Loyc.Collections.AListBase< K, T >.IndexesOf ( item)
inline

Returns a sequence of integers that represent the locations where a given item appears in the list.

References Loyc.Collections.AListBase< K, T >.IndexesOf().

Referenced by Loyc.Collections.AListBase< K, T >.IndexesOf().

int Loyc.Collections.AListBase< K, T >.LinearScanFor ( item,
int  startIndex,
EqualityComparer< T >  comparer 
)
inline

Scans the list starting at startIndex and going upward, and returns the index of an item that matches the first argument.

Parameters
itemItem to find
startIndexIndex of first element against which to compare the item.
comparerComparison object (e.g. EqualityComparer{T}.Default.)
Returns
Index of the matching item, or -1 if no matching item was found.
Exceptions
ArgumentOutOfRangeExceptionwhen startIndex > Count
int Loyc.Collections.AListBase< K, T >.RemoveAll ( Predicate< T >  match)
inline

Removes all the elements that match the conditions defined by the specified predicate.

Parameters
matchA lambda that defines the conditions on the elements to remove.
Returns
The number of elements removed from the list.
virtual bool Loyc.Collections.AListBase< K, T >.RemoveObserver ( IAListTreeObserver< K, T >  observer)
inlinevirtual

Removes a previously attached tree observer from this list.

Returns
True if the observer was removed, false if it was not attached.
Slice_<T> Loyc.Collections.AListBase< K, T >.Slice ( int  start,
int  count 
)
inline

Returns a sub-range of this list.

Parameters
startThe new range will start at this index in the current list (this location will be index [0] in the new range).
countThe 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
ArgumentExceptionThe 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:

IRange<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); }

Implements Loyc.Collections.IListSource< out T >.

void Loyc.Collections.AListBase< K, T >.SwapHelper ( AListBase< K, T >  other,
bool  swapObservers 
)
inlineprotected

Swaps two ALists.

Usually, swapping is a useless feature, since usually you can just swap the references to two lists instead of the contents of two lists. This method is provided anyway because AList{T}.Append and AList{T}.Prepend need to be able to swap in-place in some cases.

The derived class must manually swap any additional data members that it defines.

T Loyc.Collections.AListBase< K, T >.TryGet ( int  index,
out bool  fail 
)
inline

Gets the item at the specified index, and does not throw an exception on failure.

Parameters
indexAn index in the range 0 to Count-1.
failA flag that is set on failure.
Returns
The element at the specified index, or default(T) if the index is not valid.

In my original design, the caller could provide a value to return on failure, but this would not allow T to be marked as "out" in C# 4. For the same reason, we cannot have a ref/out T parameter. Instead, the following extension methods are provided:

bool TryGet(int index, ref T value);
T TryGet(int, T defaultValue);

Implements Loyc.Collections.IListSource< out T >.

Property Documentation

virtual ListChangingHandler<T> Loyc.Collections.AListBase< K, T >.ListChanging
addremove

Event for learning about changes in progress on a list.

int Loyc.Collections.AListBase< K, T >.ObserverCount
get

Returns the number of tree observers attached to this list.