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:

/Core/Loyc.Collections/ALists/AListNode.cs

Inheritance diagram for Loyc.Collections.Impl.AListNode< 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

node	A node that the caller needs to be unfrozen
parent	Parent node (used by tob)
tob	Tree 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

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.

◆ 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

sizeOfT	The size to attribute to a slot of type T
sizeOfK	The 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

excludeSparse Should 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,
		T	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

NotSupportedException This 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

index The 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

NotSupportedException This 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,
		T	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

Gets the number of items (slots) used this node only.

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

◆ 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

Gets the total number of (T) items in this node and all children

Referenced by Loyc.Collections.AListBase< K, T >.AListBase(), Loyc.Collections.Impl.AListIndexer< int, T >.CheckPoint(), Loyc.Collections.Impl.AListNode< K, T >.GetRealItemCount(), Loyc.Collections.Impl.AListInnerBase< int, T >.HandleChildSplit(), Loyc.Collections.Impl.AListInnerBase< int, T >.HandleUndersized(), and Loyc.Collections.Impl.AListIndexer< int, T >.VerifyCorrectness().

Remarks

Properties

Public Member Functions

Static Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected fields

Member Function Documentation

◆ AutoClone()

◆ CallListChanging()

◆ CopySection()

◆ CountSizeInBytes()

◆ DetachedClone()

◆ GetImmutableCount()

◆ GetLastItem()

◆ GetObserver()

◆ GetRealItemCount()

◆ HasListChanging()

◆ Insert()

◆ InsertRange()

◆ RemoveAt()

◆ SetAt()

◆ Verify()

Member Data Documentation

◆ _childCount

◆ _isFrozen

◆ _maxNodeSize

Property Documentation

◆ IsFrozen

◆ IsFullLeaf

◆ IsUndersized

◆ LocalCount

◆ this[uint index]

◆ TotalCount