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

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


Source file:
Inheritance diagram for Loyc.Collections.Impl.AListNode< K, T >:
Loyc.Collections.Impl.AListInnerBase< K, T > Loyc.Collections.Impl.AListLeafBase< K, T >

Remarks

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...
 
abstract long CountSizeInBytes (int sizeOfT, int sizeOfK)
 Tallies the memory use of the current node and all child nodes, with the assumption that each object has a header size of two words (e.g. class Foo {} has a size of 16 bytes per Foo object in a 64-bit process), and arrays have a header size of three words. 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...
 
volatile bool _isFrozen
 Whether the node is knowingly cloned an therefore frozen. More...
 
byte _childCount
 Number of children, if this is an inner node. More...
 

Member Function Documentation

◆ AutoClone()

static bool Loyc.Collections.Impl.AListNode< K, T >.AutoClone ( ref AListNode< K, T >  node,
AListInnerBase< K, T >  parent,
IAListTreeObserver< K, T >  tob 
)
inlinestatic

Checks whether 'node' is frozen and if so, replaces it with an unfrozen copy.

Parameters
nodeA node that the caller needs to be unfrozen
parentParent node (used by tob)
tobTree observer (null if none)
Returns
True if the node was unfrozen

Referenced by Loyc.Collections.Impl.AListInnerBase< int, T >.HandleUndersized(), Loyc.Collections.Impl.AListInnerBase< int, T >.RemoveAt(), and Loyc.Collections.Impl.AListInnerBase< int, T >.SetAt().

◆ CallListChanging()

void Loyc.Collections.Impl.AListNode< K, T >.CallListChanging ( AListBase< K, T >  tree,
ListChangeInfo< T >  listChangeInfo 
)
inlineprotected

Allows derived classes of AListNode to fire the AListBase.ListChanging event properly.

◆ CopySection()

abstract AListNode<K, T> Loyc.Collections.Impl.AListNode< K, T >.CopySection ( uint  index,
uint  count,
AListBase< K, T >  list 
)
pure virtual

Extracts and returns, as fast as possible, a subrange of the list that this node represents.

Parameters
indexIndex to start copying
countNumber of Ts to copy (must be greater than zero).
listList 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.

◆ CountSizeInBytes()

abstract long Loyc.Collections.Impl.AListNode< K, T >.CountSizeInBytes ( int  sizeOfT,
int  sizeOfK 
)
pure virtual

Tallies the memory use of the current node and all child nodes, with the assumption that each object has a header size of two words (e.g. class Foo {} has a size of 16 bytes per Foo object in a 64-bit process), and arrays have a header size of three words.

Parameters
sizeOfTThe size to attribute to a slot of type T
sizeOfKThe size to attribute to a slot of type K

Implemented in Loyc.Collections.Impl.AListInnerBase< K, T >.

◆ DetachedClone()

abstract AListNode<K, T> Loyc.Collections.Impl.AListNode< K, T >.DetachedClone ( )
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.

◆ GetImmutableCount()

abstract uint Loyc.Collections.Impl.AListNode< K, T >.GetImmutableCount ( bool  excludeSparse)
pure virtual

Diagnostic method. See AListBase<K,T>.GetImmutableCount().

Parameters
excludeSparseShould be false for normal ALists. If true, the count is of real items only.

Implemented in Loyc.Collections.Impl.AListInnerBase< K, T >.

◆ GetLastItem()

abstract T Loyc.Collections.Impl.AListNode< K, T >.GetLastItem ( )
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 >.

◆ GetObserver()

IAListTreeObserver<K, T> Loyc.Collections.Impl.AListNode< K, T >.GetObserver ( AListBase< K, T >  tree)
inlineprotected

Allows derived classes of AListNode to access AListBase._observer.

◆ GetRealItemCount()

virtual uint Loyc.Collections.Impl.AListNode< K, T >.GetRealItemCount ( )
inlinevirtual

For sparse lists: counts the number of non-sparse items.

References Loyc.Collections.Impl.AListNode< K, T >.TotalCount.

◆ HasListChanging()

bool Loyc.Collections.Impl.AListNode< K, T >.HasListChanging ( AListBase< K, T >  tree)
inlineprotected

Allows derived classes of AListNode to fire the AListBase.ListChanging event.

◆ Insert()

virtual AListNode<K, T> Loyc.Collections.Impl.AListNode< K, T >.Insert ( uint  index,
item,
out AListNode< K, T >  splitRight,
IAListTreeObserver< K, T >  tob 
)
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.

Returns
Returns null if the insert completed normally. If the node split in half, the return value is the left side, and splitRight is set to the right side.
Exceptions
NotSupportedExceptionThis node does not allow insertion at an arbitrary location (e.g. BList node).

◆ InsertRange()

virtual AListNode<K, T> Loyc.Collections.Impl.AListNode< K, T >.InsertRange ( uint  index,
IListSource< T >  source,
ref int  sourceIndex,
out AListNode< K, T >  splitRight,
IAListTreeObserver< K, T >  tob 
)
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.

Parameters
indexThe index at which to insert the contents of source. Important: if sourceIndex > 0, insertion of the remaining items starts at [index + sourceIndex].
Returns
Returns non-null if the node is split, as explained in the documentation of Insert.

This method can only be called for ALists, since other tree types don't allow insertion at a specific index.

Exceptions
NotSupportedExceptionThis node does not allow insertion at an arbitrary location (e.g. BList node).

◆ RemoveAt()

abstract bool Loyc.Collections.Impl.AListNode< K, T >.RemoveAt ( uint  index,
uint  count,
IAListTreeObserver< K, T >  tob 
)
pure virtual

Removes an item at the specified index.

Returns
Returns true if the node is undersized after the removal, or if this is an organized tree and the removal caused the aggregate key (highest key in a B+tree) to change.

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

◆ SetAt()

abstract void Loyc.Collections.Impl.AListNode< K, T >.SetAt ( uint  index,
item,
IAListTreeObserver< K, T >  tob 
)
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 >.

◆ Verify()

static void Loyc.Collections.Impl.AListNode< K, T >.Verify ( bool  condition)
inlinestaticprotected

Same as Assert(), except that the condition expression can have side-effects because it is evaluated even in Release builds.

Member Data Documentation

◆ _childCount

byte Loyc.Collections.Impl.AListNode< K, T >._childCount
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.

Referenced by Loyc.Collections.Impl.AListInnerBase< int, T >.GetImmutableCount(), Loyc.Collections.Impl.AListInnerBase< int, T >.LLDelete(), and Loyc.Collections.Impl.AListInnerBase< int, T >.LLInsert().

◆ _isFrozen

volatile bool Loyc.Collections.Impl.AListNode< K, T >._isFrozen
protected

Whether the node is knowingly cloned an therefore frozen.

◆ _maxNodeSize

ushort Loyc.Collections.Impl.AListNode< K, T >._maxNodeSize
protected

Maximum number of slots in this node

Property Documentation

◆ IsFrozen

bool Loyc.Collections.Impl.AListNode< K, T >.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.

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.

Referenced by Loyc.Collections.Impl.AListInnerBase< int, T >.GetImmutableCount(), Loyc.Collections.Impl.AListInnerBase< int, T >.HandleUndersized(), Loyc.Collections.Impl.AListInnerBase< int, T >.RemoveAt(), and Loyc.Collections.Impl.AListInnerBase< int, T >.SetAt().

◆ IsFullLeaf

abstract bool Loyc.Collections.Impl.AListNode< K, T >.IsFullLeaf
get

Returns true if the node is full and is a leaf node.

◆ IsUndersized

abstract bool Loyc.Collections.Impl.AListNode< K, T >.IsUndersized
get

Returns true if the node is undersized, meaning it would prefer to have more immediate children.

◆ LocalCount

abstract int Loyc.Collections.Impl.AListNode< K, T >.LocalCount
get

◆ this[uint index]

abstract T Loyc.Collections.Impl.AListNode< K, T >.this[uint index]
get

Gets an item at the specified sub-index.

◆ TotalCount

abstract uint Loyc.Collections.Impl.AListNode< K, T >.TotalCount
get