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

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


Source file:
Inheritance diagram for Loyc.Collections.Impl.AListIndexer< K, T >:
Loyc.Collections.Impl.IAListTreeObserver< 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

void Attach (AListBase< K, T > list, Action< bool > populate)
 Called when the observer is being attached to an AList. More...
 
void Detach ()
 Called when the observer is being detached from an AList. More...
 
void RootChanged (AListNode< K, T > newRoot, bool clear)
 Called when the root of the tree changes, or when the list is cleared. More...
 
void ItemAdded (T item, AListLeaf< K, T > parent)
 Called when an item is added to a leaf node. More...
 
void ItemRemoved (T item, AListLeaf< 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). 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...
 

Protected Member Functions

int ReconstructIndex (T item, AListLeaf< 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< AListLeaf< K, T >, AListLeaf< 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

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 >.

void Loyc.Collections.Impl.AListIndexer< K, T >.Attach ( AListBase< K, T >  list,
Action< bool >  populate 
)
inline

Called when the observer is being attached to an AList.

Parameters
listThe list that the observer is being attached to.
populateThe observer can invoke this delegate to cause notifications to be sent about all the nodes in the tree through a depth-first search that calls AddAll for each node in the tree. When calling this delegate, use a parameter of True if you want AddAll to be called for children before parents (roughly, leaves first). Use False if you want AddAll to be called for inner nodes before their children. populate() also calls RootChanged() before scanning the tree.

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 >.

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 >.

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

Called when the observer is being detached from an AList.

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

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

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

Parameters
itemItem 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().

void Loyc.Collections.Impl.AListIndexer< K, T >.ItemAdded ( item,
AListLeaf< 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 >.

void Loyc.Collections.Impl.AListIndexer< K, T >.ItemRemoved ( item,
AListLeaf< 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 >.

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 >.

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 >.

int Loyc.Collections.Impl.AListIndexer< K, T >.ReconstructIndex ( item,
AListLeaf< 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 )

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). Notifications are not sent for individual children.

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

void Loyc.Collections.Impl.AListIndexer< K, T >.RootChanged ( AListNode< K, T >  newRoot,
bool  clear 
)
inline

Called when the root of the tree changes, or when the list is cleared.

Parameters
cleartrue 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.
newRootThe new root (null if the tree is cleared).

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

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
InvalidStateExceptionThe 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().