Enhanced C#
Language of your choice: library documentation
|
Observes changes and builds a table of items in the tree. More...
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... | |
|
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 >.
|
inline |
Called when the observer is being attached to an AList.
list | The list that the observer is being attached to. |
populate | The 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 >.
|
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 >.
|
inline |
Called when the observer is being detached from an AList.
Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.
|
inline |
Returns an index at which the specified item can be found.
item | Item to find. |
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.
|
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 >.
|
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 >.
|
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 >.
|
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 >.
|
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 )
|
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 >.
|
inline |
Called when the root of the tree changes, or when the list is cleared.
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. |
newRoot | The new root (null if the tree is cleared). |
Implements Loyc.Collections.Impl.IAListTreeObserver< K, T >.
|
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.
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.