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

Source file:

/Core/Loyc.Collections/ALists/AListBase.cs

Inheritance diagram for Loyc.Collections.AListBase< K, T >:

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:

Items can always be inserted or removed in O(log N) time (by convention, N refers to the number of items in the list, although it is the Count property that actually returns this number).
Elements can also be accessed by index in O(log N) time.
Scanning the list with an enumerator or foreach loop takes O(1) time per element (plus O(log N) to initialize the enumerator), and it is possible to start enumerating somewhere in the middle of the list.
The list can be frozen with Freeze, making it read-only.
The list can be cloned in O(1) time and space, with incremental copy- on-write semantics. Thus, changing either copy of the tree costs extra time and space in order to duplicate parts of the tree that are changing. A frozen list can be cloned to produce a non-frozen list. In the language of comp-sci techno-babble, A-lists are related to the family of "persistent" data structures, although I could not find a term that describes the form of persistence that A-lists support.
Changes can be observed through the ListChanging event. The performance penalty for this feature is lower than for the standard ObservableCollection{T} class.
Changes to the tree structure can be observed by writing a class that implements IAListTreeObserver{K,T} and calling AddObserver.
A section of the list can be cloned in O(log N) time, although there is no time savings when extracting a small section.
Removing a contiguous group of items takes O(log N + M) time, where M is the number of items being removed.
A reversed view of the list is given by the ReverseView property, and the list can be enumerated backwards, also in O(1) time per element..

Derived classes provide the following additional capabilities:

BList{T} and IndexedAList{T} allow you to find items in O(log N) time. BList is a sorted B+tree, so it achieves this ability through a kind of binary search, while IndexedAList uses a special kind of hashtable maintained in parallel with the tree.
BList{T}.FindLowerBoundallows you to find the closest larger item to an item that is not in the list. For example, if a BList(of int) contains { 1, 3, 9 }, you can search for 5 in order to find 9.
AList{T} allows a contiguous group of items to be inserted in O(log N + M) time, where M is the number of items being inserted.
AList{T} allows you to concatenate two lists in O(log N) time, where N is the size of the combined list, although there is no time savings when combining small lists.
AList{T} has a special sorting algorithm that allows you to sort the list in slightly more than O(N log N) time. This is slower than sorting an array or List{T}, but faster than a quicksort applied directly to AList{T}, which would take O(N log^2 N) time.

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

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

TODO:

Check that all cloning is handled.
Check that all splitting is handled.
Check that all TakeFromLeft/Right is handled.
Check that all leaf changes are handled
Factor out certain calls to indexer to shorten/simplify code
Add a method to install indexer in AList
Write unit tests
Write benchmarks
Try optimizations: _isFrozen in AListNode, _children[0].Index always 0, redundant-if optimization on calls to AutoClone, larger inner nodes

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]`

T	this[int index] `[get]`

bool	IsFrozen `[get]`

T	First `[get]`

T	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)

T	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

items	Original list
keepListChangingHandlers	Whether 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

forceClear If 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 ( T 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	(	T	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

item	Item to find
startIndex	Index of first element against which to compare the item.
comparer	Comparison object (e.g. EqualityComparer{T}.Default.)

Returns: Index of the matching item, or -1 if no matching item was found.

Exceptions

ArgumentOutOfRangeException when 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

match A 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

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:

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

index	An index in the range 0 to Count-1.
fail	A 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.

Documentation moved to ecsharp.net

Remarks

Nested classes

Properties

Public Member Functions

Protected Member Functions

Protected fields

Additional Inherited Members

Constructor & Destructor Documentation

Member Function Documentation

Property Documentation