Observes changes and builds a table of items in the tree. More...

Source file:

/Core/Loyc.Collections/ALists/AListIndexer.cs

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

Remarks

Observes changes and builds a table of items in the tree.

The IndexedAList<T> class uses one of these objects to speed up methods that search for items in an AList<T> (IndexOf, Contains, and Remove). The amount of speedup is limited by the size of the nodes in the list being indexed; see IndexOfAny.

It is wasteful to use an AListIndexer if the list is small. AListIndexer is designed to accelerate searches in very large lists, and it offers no performance benefit to small lists; to the contrary, it just wastes time and memory in small lists.

It is recommended to use IndexedAList instead of instantiating this class directly.

In general, AListIndexer requires more memory than the list that is being indexed. Specifically, if pointers use P bytes, then AListIndexer itself consumes moderately MORE than X+P*N bytes of memory, where X is the size of the list being indexed, and N is the number of items in the list. Thus, for example, an indexed list of AList<Object> requires approximately three times as much memory as an AList that is not indexed.

Moreover, changing an indexed list takes at least twice as much time, since the indexer must be notified of each change and updates to the index take O(log N) time per update. Batch operations involving X items that take O(log N) time without an indexer (e.g. RemoveRange(i, X)) will take O(X log N) time instead, because the indexer must be notified about each item changed.

Still, these costs are worthwhile in applications that frequently search for items in the list.

Properties
int	ItemCount `[get]`

Public Member Functions
bool?	Attach (AListBase< K, T > list)
	Called when the observer is being attached to an AList. More...

void	Detach (AListBase< K, T > list, AListNode< K, T > root)
	Called when the observer is being detached from an AList. Detach(), unlike Attach(), is not paired with a call to RootChanged. More...

void	RootChanged (AListBase< K, T > list, AListNode< K, T > newRoot, bool clear)
	Called when the root of the tree changes, or when the list is cleared. Also called after Attach(), but not after Detach(). More...

void	ItemAdded (T item, AListLeafBase< K, T > parent)
	Called when an item is added to a leaf node. More...

void	ItemRemoved (T item, AListLeafBase< K, T > parent)
	Called when an item is removed from a leaf node. More...

void	NodeAdded (AListNode< K, T > child, AListInnerBase< K, T > parent)
	Called when a child node is added to an inner node. More...

void	NodeRemoved (AListNode< K, T > child, AListInnerBase< K, T > parent)
	Called when a child node is removed from an inner node. More...

void	RemoveAll (AListNode< K, T > node)
	Called when all children are being removed from a node (leaf or inner) because the node is being split (AddAll will be called afterward for the two replacement nodes). Notifications are not sent for individual children. More...

void	AddAll (AListNode< K, T > node)
	Called when all children are being added to a node (leaf or inner). Notifications are not sent for individual children. More...

void	CheckPoint ()
	Called when a tree modification operation is completed. More...

int	IndexOfAny (T item)
	Returns an index at which the specified item can be found. More...

List< int >	IndexesOf (T item)

void	VerifyCorrectness ()
	Scans the index to verify that it matches the tree that is being indexed. The scan takes O(N log N + N M) time for a list of length N with maximum node size M. More...

long	CountMemory (int sizeOfElement)
	Counts memory used by the index itself (not including the AList nodes) More...

Protected Member Functions
int	ReconstructIndex (T item, AListLeafBase< K, T > leaf)
	Given an item and a leaf that is known to contain a copy of the item, this method returns the index of the item in the tree as a whole. Requires O(M ) More...

Protected static fields
static Func< T, T, int >	CompareTHashCodes = CompareHashCodes<T>

static Func< AListNode< K, T >, AListNode< K, T >, int >	CompareNodeHashCodes = CompareHashCodes<AListNode<K, T>>

static Func< AListLeafBase< K, T >, AListLeafBase< K, T >, int >	CompareLeafHashCodes = CompareHashCodes<AListNode<K, T>>

static Func< AListInnerBase< K, T >, AListInnerBase< K, T >, int >	CompareInnerHashCodes = CompareHashCodes<AListInnerBase<K, T>>

Member Function Documentation

◆ AddAll()

void Loyc.Collections.Impl.AListIndexer< K, T >.AddAll ( AListNode< K, T > node )

inline

Called when all children are being added to a node (leaf or inner). Notifications are not sent for individual children.

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

◆ Attach()

bool? Loyc.Collections.Impl.AListIndexer< K, T >.Attach ( AListBase< K, T > list )

Called when the observer is being attached to an AList.

Parameters

list	The list that the observer is being attached to.

Returns: Return true or false to cause notifications to be sent about all the nodes in the tree, via a depth-first search that calls AddAll for each node in the tree. Return true if you want AddAll to be called for children before their parents (roughly, leaves first). Use False if you want AddAll to be called for inner nodes before their children. If you return null, no notifications are sent except for RootChanged which will be called unconditionally.

If Attach() throws an exception, AListBase<K,T> will cancel the AddObserver() operation and it will not catch the exception.

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

◆ CheckPoint()

void Loyc.Collections.Impl.AListIndexer< K, T >.CheckPoint ( )

inline

Called when a tree modification operation is completed.

This is called after each modification operation (Add, Insert, Remove, Replace, etc.); the list will normally be in a read-only state ("frozen for concurrency") when this method is called, so do not initiate changes from here.

This method can safely throw an exception, and the list class will not swallow it. Note: if there are multiple observers, throwing an exception from one observers will prevent this notification from reaching other observers that have not been notified yet.

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

◆ CountMemory()

long Loyc.Collections.Impl.AListIndexer< K, T >.CountMemory ( int sizeOfElement )

Counts memory used by the index itself (not including the AList nodes)

◆ Detach()

void Loyc.Collections.Impl.AListIndexer< K, T >.Detach	(	AListBase< K, T >	list,
		AListNode< K, T >	root
	)

Called when the observer is being detached from an AList. Detach(), unlike Attach(), is not paired with a call to RootChanged.

Parameters

list	List that is being detached.
root	Root node that is being detached.

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

◆ IndexOfAny()

int Loyc.Collections.Impl.AListIndexer< K, T >.IndexOfAny ( T item )

inline

Returns an index at which the specified item can be found.

Parameters

item	Item to find.

Returns: The index of the item in the list being indexed by this object, or -1 if the item does not exist in the list.

The search takes O(M log^2 N) time, where N is the size of the list and M is the maximum size of nodes in the list. Due to the "M" factor, A-lists with large nodes are searched more slowly than A-lists with small nodes; however, the "log N" part is a base-M logarithm, so you don't actually gain performance by using very small nodes. This is because very small nodes require deeply nested trees, and deep trees are slow. The AListBase<K,T> documentation discusses the effect of node size further.

Referenced by Loyc.Collections.IndexedAList< T >.IndexOf().

◆ ItemAdded()

void Loyc.Collections.Impl.AListIndexer< K, T >.ItemAdded	(	T	item,
		AListLeafBase< K, T >	parent
	)

inline

Called when an item is added to a leaf node.

Note: this may be called as part of a move operation (remove+add)

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

Referenced by Loyc.Collections.Impl.AListIndexer< int, T >.AddAll().

◆ ItemRemoved()

void Loyc.Collections.Impl.AListIndexer< K, T >.ItemRemoved	(	T	item,
		AListLeafBase< K, T >	parent
	)

inline

Called when an item is removed from a leaf node.

Note: this may be called as part of a move operation (remove+add)

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

Referenced by Loyc.Collections.Impl.AListIndexer< int, T >.RemoveAll().

◆ NodeAdded()

void Loyc.Collections.Impl.AListIndexer< K, T >.NodeAdded	(	AListNode< K, T >	child,
		AListInnerBase< K, T >	parent
	)

inline

Called when a child node is added to an inner node.

Note: this may be called as part of a move operation (remove+add)

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

Referenced by Loyc.Collections.Impl.AListIndexer< int, T >.AddAll().

◆ NodeRemoved()

void Loyc.Collections.Impl.AListIndexer< K, T >.NodeRemoved	(	AListNode< K, T >	child,
		AListInnerBase< K, T >	parent
	)

inline

Called when a child node is removed from an inner node.

Note: this may be called as part of a move operation (remove+add)

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

Referenced by Loyc.Collections.Impl.AListIndexer< int, T >.RemoveAll().

◆ ReconstructIndex()

int Loyc.Collections.Impl.AListIndexer< K, T >.ReconstructIndex	(	T	item,
		AListLeafBase< K, T >	leaf
	)

inlineprotected

Given an item and a leaf that is known to contain a copy of the item, this method returns the index of the item in the tree as a whole. Requires O(M )

Referenced by Loyc.Collections.Impl.AListIndexer< int, T >.IndexOfAny().

◆ RemoveAll()

void Loyc.Collections.Impl.AListIndexer< K, T >.RemoveAll ( AListNode< K, T > node )

inline

Called when all children are being removed from a node (leaf or inner) because the node is being split (AddAll will be called afterward for the two replacement nodes). Notifications are not sent for individual children.

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

◆ RootChanged()

void Loyc.Collections.Impl.AListIndexer< K, T >.RootChanged	(	AListBase< K, T >	list,
		AListNode< K, T >	root,
		bool	clear
	)

inline

Called when the root of the tree changes, or when the list is cleared. Also called after Attach(), but not after Detach().

Parameters

clear	true if the root is changing due to a Clear() operation. If this parameter is true, the observer should clear its own state. If this parameter is false but newRoot is null, it means that the list was cleared by removing all the items (rather than by calling Clear() on the list). In that case, if the observer still believes that any items exist in leaf nodes, it means that there is a bookkeeping error somewhere.
list	The list that changed.
root	The new root (null if the tree is cleared).

Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.

◆ VerifyCorrectness()

void Loyc.Collections.Impl.AListIndexer< K, T >.VerifyCorrectness ( )

inline

Scans the index to verify that it matches the tree that is being indexed. The scan takes O(N log N + N M) time for a list of length N with maximum node size M.

Exceptions

InvalidStateException The index is out of sync with the tree.

This could indicate a bug somewhere in the A-list code, but it could also be caused by other rogue code, such as items that change their sort order or hashcode after being added to the collection, an observer that has thrown exceptions when it's not allowed to, or buggy multithreading (modifying a list from two threads at once).

Tree observability is a difficult feature to implement correctly, so this method is called a lot in unit tests to help work out the bugs.

Referenced by Loyc.Collections.IndexedAList< T >.VerifyCorrectness().

Remarks

Properties

Public Member Functions

Protected Member Functions

Protected static fields

Member Function Documentation

◆ AddAll()

◆ Attach()

◆ CheckPoint()

◆ CountMemory()

◆ Detach()

◆ IndexOfAny()

◆ ItemAdded()

◆ ItemRemoved()

◆ NodeAdded()

◆ NodeRemoved()

◆ ReconstructIndex()

◆ RemoveAll()

◆ RootChanged()

◆ VerifyCorrectness()