Enhanced C#
Language of your choice: library documentation
|
Internal implementation class. Base class for tree nodes in a list class derived from AListBase{T}. These nodes basically form an in-memory B+tree, not necessarily sorted, but structured like a B+tree. That means there are two node types: leaf and inner (internal) nodes. More...
Internal implementation class. Base class for tree nodes in a list class derived from AListBase{T}. These nodes basically form an in-memory B+tree, not necessarily sorted, but structured like a B+tree. That means there are two node types: leaf and inner (internal) nodes.
Indexes that are passed to methods such as Index, this[] and RemoveAt are not range-checked except by assertion. The caller (AList or BList) is expected to ensure indexes are valid.
At the root node level, indexes have the same meaning as they do in AListBase itself. However, below the root node, each node has a "base index" that is subtracted from any index passed to the node. For example, if the root node has two leaf children, and the left one has 20 items, then the right child's base index is 20. When accessing item 23, the subindex 3 is passed to the right child. Note that the right child is not aware of its own base index (the parent node manages the base index); as far as each node is concerned, it manages a collection of items numbered 0 to TotalCount-1.
Indexes are expressed with a uint so that nodes are capable of holding up to uint.MaxValue-1 elements. AList itself doesn't support sizes over int.MaxValue, since it assumes indexes are signed (some protected methods in AList take unsigned indexes, however). It should be possible to support oversize lists in 64-bit machines by writing a derived class based on "uint" or "long" indexes; 32-bit processes, however, don't have enough address space to even hold int.MaxValue bytes.
Before calling any method that modifies a node, it is necessary to call AutoClone() to check if the node is frozen and clone it if necessary. TakeFromRight and TakeFromLeft can be called when one or both nodes are frozen, but will have no effect.
Philosophical note: the kinds of features I'd like to see in Enhanced C# would make it easier to create the AList series of data structures. Each kind of AList is similar yet different and many of the operations of an AList are similar yet different and C# doesn't, I think, provide enough flexibility to handle this variety without smooshing a bunch of different things clumsily into a single class hierarchy and without having to write methods that are in charge of several different operations (e.g. DoSingleOperation). Traits and D-style templates would help make the cod of the AList family of types cleaner and faster.
Properties | |
abstract bool | IsLeaf [get] |
abstract uint | TotalCount [get] |
Gets the total number of (T) items in this node and all children More... | |
abstract int | LocalCount [get] |
Gets the number of items (slots) used this node only. More... | |
abstract bool | IsFullLeaf [get] |
Returns true if the node is full and is a leaf node. More... | |
abstract bool | IsUndersized [get] |
Returns true if the node is undersized, meaning it would prefer to have more immediate children. More... | |
abstract T | this[uint index] [get] |
Gets an item at the specified sub-index. More... | |
bool | IsFrozen [get] |
Returns true if the node is explicitly marked read-only. Conceptually, the node can still be changed, but when any change needs to be made, a clone of the node is created and modified instead. More... | |
abstract int | CapacityLeft [get] |
Public Member Functions | |
virtual AListNode< K, T > | Insert (uint index, T item, out AListNode< K, T > splitRight, IAListTreeObserver< K, T > tob) |
Inserts an item at the specified index. This method can only be called for ALists, since other tree types don't allow insertion at a specific index. More... | |
virtual AListNode< K, T > | InsertRange (uint index, IListSource< T > source, ref int sourceIndex, out AListNode< K, T > splitRight, IAListTreeObserver< K, T > tob) |
Inserts a list of items at the specified index. This method may not insert all items at once, so there is a sourceIndex parameter which points to the next item to be inserted. When sourceIndex reaches source.Count, the insertion is complete. More... | |
abstract T | GetLastItem () |
Gets the last item in the last leaf node (needed by B+ trees, but is also called by AListBase{K,T}.Last). More... | |
abstract void | SetAt (uint index, T item, IAListTreeObserver< K, T > tob) |
Sets an item at the specified sub-index. More... | |
abstract bool | RemoveAt (uint index, uint count, IAListTreeObserver< K, T > tob) |
Removes an item at the specified index. More... | |
abstract void | Freeze () |
abstract AListNode< K, T > | DetachedClone () |
Creates an unfrozen shallow duplicate copy of this node. The child nodes (if this is an inner node) are frozen so that they will require duplication if they are to be modified. The name "DetachedClone" is intended to emphasize that the AListNodeObserver (if any) is not notified, and the clone is effectively independent of the list that it came from. More... | |
abstract AListNode< K, T > | CopySection (uint index, uint count, AListBase< K, T > list) |
Extracts and returns, as fast as possible, a subrange of the list that this node represents. More... | |
abstract uint | GetImmutableCount (bool excludeSparse) |
Diagnostic method. See AListBase{K,T}.GetImmutableCount(). More... | |
virtual uint | GetRealItemCount () |
For sparse lists: counts the number of non-sparse items. More... | |
Static Public Member Functions | |
static bool | AutoClone (ref AListNode< K, T > node, AListInnerBase< K, T > parent, IAListTreeObserver< K, T > tob) |
Checks whether 'node' is frozen and if so, replaces it with an unfrozen copy. More... | |
Protected Member Functions | |
IAListTreeObserver< K, T > | GetObserver (AListBase< K, T > tree) |
Allows derived classes of AListNode to access AListBase._observer. More... | |
bool | HasListChanging (AListBase< K, T > tree) |
Allows derived classes of AListNode to fire the AListBase.ListChanging event. More... | |
void | CallListChanging (AListBase< K, T > tree, ListChangeInfo< T > listChangeInfo) |
Allows derived classes of AListNode to fire the AListBase.ListChanging event properly. More... | |
Static Protected Member Functions | |
static void | Verify (bool condition) |
Same as Assert(), except that the condition expression can have side-effects because it is evaluated even in Release builds. More... | |
Protected fields | |
ushort | _maxNodeSize |
Maximum number of slots in this node More... | |
bool | _isFrozen |
Whether the node is knowingly cloned an therefore frozen. More... | |
byte | _childCount |
Number of children, if this is an inner node. More... | |
|
inlinestatic |
Checks whether 'node' is frozen and if so, replaces it with an unfrozen copy.
node | A node that the caller needs to be unfrozen |
parent | Parent node (used by tob) |
tob | Tree observer (null if none) |
|
inlineprotected |
Allows derived classes of AListNode to fire the AListBase.ListChanging event properly.
|
pure virtual |
Extracts and returns, as fast as possible, a subrange of the list that this node represents.
index | Index to start copying |
count | Number of Ts to copy (must be greater than zero). |
list | List that is making the request. This parameter may be needed by organized trees that need to call list.GetKey(). |
This method may return a size-one inner node that the caller must replace with its child. It will fast-clone any nodes that can be copied in their entirety, including this node itself.
Implemented in Loyc.Collections.Impl.BListLeaf< K, T >.
|
pure virtual |
Creates an unfrozen shallow duplicate copy of this node. The child nodes (if this is an inner node) are frozen so that they will require duplication if they are to be modified. The name "DetachedClone" is intended to emphasize that the AListNodeObserver (if any) is not notified, and the clone is effectively independent of the list that it came from.
Implemented in Loyc.Collections.Impl.SparseAListLeaf< T >, and Loyc.Collections.Impl.BListLeaf< K, T >.
|
pure virtual |
Diagnostic method. See AListBase{K,T}.GetImmutableCount().
excludeSparse | Should be false for normal ALists. If true, the count is of real items only. |
Implemented in Loyc.Collections.Impl.AListInnerBase< K, T >, Loyc.Collections.Impl.SparseAListLeaf< T >, and Loyc.Collections.Impl.AListLeaf< K, T >.
|
pure virtual |
Gets the last item in the last leaf node (needed by B+ trees, but is also called by AListBase{K,T}.Last).
Implemented in Loyc.Collections.Impl.AListInnerBase< K, T >, Loyc.Collections.Impl.AListLeaf< K, T >, and Loyc.Collections.Impl.SparseAListLeaf< T >.
|
inlineprotected |
Allows derived classes of AListNode to access AListBase._observer.
|
inlinevirtual |
For sparse lists: counts the number of non-sparse items.
Reimplemented in Loyc.Collections.Impl.SparseAListLeaf< T >.
|
inlineprotected |
Allows derived classes of AListNode to fire the AListBase.ListChanging event.
|
inlinevirtual |
Inserts an item at the specified index. This method can only be called for ALists, since other tree types don't allow insertion at a specific index.
NotSupportedException | This node does not allow insertion at an arbitrary location (e.g. BList node). |
|
inlinevirtual |
Inserts a list of items at the specified index. This method may not insert all items at once, so there is a sourceIndex parameter which points to the next item to be inserted. When sourceIndex reaches source.Count, the insertion is complete.
index | The index at which to insert the contents of source. Important: if sourceIndex > 0, insertion of the remaining items starts at [index + sourceIndex]. |
This method can only be called for ALists, since other tree types don't allow insertion at a specific index.
NotSupportedException | This node does not allow insertion at an arbitrary location (e.g. BList node). |
|
pure virtual |
Removes an item at the specified index.
When the node is undersized, but is not the root node, the parent will shift an item from a sibling, or discard the node and redistribute its children among existing nodes. If it is the root node, it is only discarded if it is an inner node with a single child (the child becomes the new root node), or it is a leaf node with no children.
Implemented in Loyc.Collections.Impl.AListInnerBase< K, T >, Loyc.Collections.Impl.BListLeaf< K, T >, and Loyc.Collections.Impl.AListLeaf< K, T >.
|
pure virtual |
Sets an item at the specified sub-index.
Currently, this method can be called for all tree types, even though improper use could break the tree invariant (e.g. sorted order of BList).
Implemented in Loyc.Collections.Impl.AListInnerBase< K, T >, and Loyc.Collections.Impl.AListLeaf< K, T >.
|
inlinestaticprotected |
Same as Assert(), except that the condition expression can have side-effects because it is evaluated even in Release builds.
|
protected |
Number of children, if this is an inner node.
Since AListLeaf{T} uses DListInternal, a separate item count is not needed and this counter is always zero. This field logically belongs in AListInnerBase{K,T} but is defined here to ensure that inner nodes are not 4 bytes larger than necessary. This field is "free" if it is declared in the base class, since class sizes are rounded up to the nearest multiple of 4 bytes (8 bytes in 64-bit). The fact that this field is a byte, however, does limit inner node sizes to 255.
|
protected |
Whether the node is knowingly cloned an therefore frozen.
|
protected |
Maximum number of slots in this node
|
get |
Returns true if the node is explicitly marked read-only. Conceptually, the node can still be changed, but when any change needs to be made, a clone of the node is created and modified instead.
When an inner node is frozen, all its children are implicitly frozen, but not actually marked as frozen until the parent is cloned. This allows instantaneous cloning, since only the root node is marked frozen in the beginning.
|
get |
Returns true if the node is full and is a leaf node.
|
get |
Returns true if the node is undersized, meaning it would prefer to have more immediate children.
Referenced by Loyc.Collections.Impl.AListInnerBase< K, T >.HandleUndersized().
|
get |
Gets the number of items (slots) used this node only.
Referenced by Loyc.Collections.Impl.AListInnerBase< K, T >.HandleUndersized().
|
get |
Gets an item at the specified sub-index.
|
get |
Gets the total number of (T) items in this node and all children
Referenced by Loyc.Collections.Impl.AListInnerBase< K, T >.HandleUndersized().