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

Internal implementation class. Shared base class of internal nodes for AList<T>, SparseAList<T>, BList<T>, BMultiMap<K,V> and BDictionary<K,V>. More...


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

Remarks

Internal implementation class. Shared base class of internal nodes for AList<T>, SparseAList<T>, BList<T>, BMultiMap<K,V> and BDictionary<K,V>.

Nested classes

struct  Entry
 

Public fields

const int DefaultMaxNodeSize = 32
 

Properties

override bool IsLeaf [get]
 
sealed override int LocalCount [get]
 
int MaxNodeSize [get, set]
 
sealed override uint TotalCount [get]
 
sealed override bool IsFullLeaf [get]
 
override bool IsUndersized [get]
 
override T this[uint index] [get]
 
override int CapacityLeft [get]
 
- Properties inherited from Loyc.Collections.Impl.AListNode< K, T >
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

 AListInnerBase (AListNode< K, T > left, AListNode< K, T > right, int maxNodeSize)
 
int BinarySearchI (uint index)
 Performs a binary search for an index. More...
 
override 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...
 
AListNode< K, T > Child (int i)
 
override void SetAt (uint index, T item, IAListTreeObserver< K, T > tob)
 Sets an item at the specified sub-index. More...
 
override bool RemoveAt (uint index, uint count, IAListTreeObserver< K, T > tob)
 Removes an item at the specified index. More...
 
override void Freeze ()
 
void AutoEnlargeChildren (int more)
 
uint BaseIndexOf (AListNode< K, T > child)
 
int IndexOf (AListNode< K, T > child)
 
override uint GetImmutableCount (bool excludeSparse)
 Diagnostic method. See AListBase<K,T>.GetImmutableCount(). More...
 
- Public Member Functions inherited from Loyc.Collections.Impl.AListNode< K, T >
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 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...
 
virtual uint GetRealItemCount ()
 For sparse lists: counts the number of non-sparse items. More...
 

Protected Member Functions

 AListInnerBase (AListInnerBase< K, T > frozen)
 
 AListInnerBase (AListInnerBase< K, T > original, int localIndex, int localCount, uint baseIndex, int maxNodeSize)
 
 AListInnerBase (AListInnerBase< K, T > original, uint index, uint count, AListBase< K, T > list)
 
void PrepareToInsert (int i, IAListTreeObserver< K, T > tob)
 
void TryToShiftAnItemToSiblingOfLeaf (int i, IAListTreeObserver< K, T > tob)
 
AListInnerBase< K, T > HandleChildSplit (int i, AListNode< K, T > splitLeft, ref AListNode< K, T > splitRight, IAListTreeObserver< K, T > tob)
 Inserts a slot after _children[i], increasing _childCount and replacing [i] and [i+1] with splitLeft and splitRight. Notifies 'tob' of the replacement, and checks whether this node itself needs to split. More...
 
virtual AListInnerBase< K, T > AutoSplit (out AListNode< K, T > splitRight)
 
abstract AListInnerBase< K, T > SplitAt (int divAt, out AListNode< K, T > right)
 Splits this node into two halves More...
 
void AssertValid ()
 
virtual void LLInsert (int i, AListNode< K, T > child, uint indexAdjustment)
 Inserts a child node into _children at index i (resizing _children if necessary), increments _childCount, and adds indexAdjustment to _children[j].Index for all j>i (indexAdjustment can be 0 if i==_childCount). More...
 
void AdjustIndexesAfter (int i, int indexAdjustment)
 
virtual bool HandleUndersizedOrAggregateChanged (int i, IAListTreeObserver< K, T > tob)
 
virtual bool HandleUndersized (int i, IAListTreeObserver< K, T > tob)
 This is called by RemoveAt(), DoSingleOperation() for B+ trees, or by the constructor called by CopySection(), when child [i] drops below its normal size range. We'll either distribute the child's items to its siblings, or transfer ONE item from a sibling to increase the node's size. More...
 
virtual bool LLDelete (int i, bool adjustIndexesAfterI)
 Deletes the child _children[i], shifting all entries afterward to the left, and decrements _childCount. If adjustIndexesAfterI is true, the values of _children[j].Index where j>i are decreased appropriately. More...
 
- Protected Member Functions inherited from Loyc.Collections.Impl.AListNode< K, T >
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...
 

Protected fields

Entry[] _children
 List of child nodes. Empty children are null. More...
 
const int MaxMaxNodeSize = 0xFF
 
const uint FrozenBit = 0x8000
 
- Protected fields inherited from Loyc.Collections.Impl.AListNode< K, T >
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...
 

Additional Inherited Members

- Static Public Member Functions inherited from Loyc.Collections.Impl.AListNode< K, T >
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...
 
- Static Protected Member Functions inherited from Loyc.Collections.Impl.AListNode< K, T >
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...
 

Member Function Documentation

int Loyc.Collections.Impl.AListInnerBase< K, T >.BinarySearchI ( uint  index)
inline

Performs a binary search for an index.

Optimized. Fastest for power-of-two node sizes. If index is out of range, returns the highest valid index.

override uint Loyc.Collections.Impl.AListInnerBase< K, T >.GetImmutableCount ( bool  excludeSparse)
inlinevirtual

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

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

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

override T Loyc.Collections.Impl.AListInnerBase< K, T >.GetLastItem ( )
inlinevirtual

Gets the last item in the last leaf node (needed by B+ trees, but is also called by AListBase<K,T>.Last).

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

AListInnerBase<K, T> Loyc.Collections.Impl.AListInnerBase< K, T >.HandleChildSplit ( int  i,
AListNode< K, T >  splitLeft,
ref AListNode< K, T >  splitRight,
IAListTreeObserver< K, T >  tob 
)
inlineprotected

Inserts a slot after _children[i], increasing _childCount and replacing [i] and [i+1] with splitLeft and splitRight. Notifies 'tob' of the replacement, and checks whether this node itself needs to split.

Returns
Value of splitLeft to be returned to parent (non-null if splitting)
virtual bool Loyc.Collections.Impl.AListInnerBase< K, T >.HandleUndersized ( int  i,
IAListTreeObserver< K, T >  tob 
)
inlineprotectedvirtual

This is called by RemoveAt(), DoSingleOperation() for B+ trees, or by the constructor called by CopySection(), when child [i] drops below its normal size range. We'll either distribute the child's items to its siblings, or transfer ONE item from a sibling to increase the node's size.

Parameters
iIndex of undersized child
tobObserver to notify about node movements
Returns
True iff this node has become undersized.
virtual bool Loyc.Collections.Impl.AListInnerBase< K, T >.LLDelete ( int  i,
bool  adjustIndexesAfterI 
)
inlineprotectedvirtual

Deletes the child _children[i], shifting all entries afterward to the left, and decrements _childCount. If adjustIndexesAfterI is true, the values of _children[j].Index where j>i are decreased appropriately.

Returns
True if the aggregate value of this node may have changed (organized lists only)

Derived classes can override to add their own bookkeeping.

virtual void Loyc.Collections.Impl.AListInnerBase< K, T >.LLInsert ( int  i,
AListNode< K, T >  child,
uint  indexAdjustment 
)
inlineprotectedvirtual

Inserts a child node into _children at index i (resizing _children if necessary), increments _childCount, and adds indexAdjustment to _children[j].Index for all j>i (indexAdjustment can be 0 if i==_childCount).

Derived classes can override to add their own bookkeeping.

override bool Loyc.Collections.Impl.AListInnerBase< K, T >.RemoveAt ( uint  index,
uint  count,
IAListTreeObserver< K, T >  tob 
)
inlinevirtual

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.

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

override void Loyc.Collections.Impl.AListInnerBase< K, T >.SetAt ( uint  index,
item,
IAListTreeObserver< K, T >  tob 
)
inlinevirtual

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

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

abstract AListInnerBase<K, T> Loyc.Collections.Impl.AListInnerBase< K, T >.SplitAt ( int  divAt,
out AListNode< K, T >  right 
)
protectedpure virtual

Splits this node into two halves

Parameters
divAtIndex into _children where the right half starts
rightAn AListInner node containing the right children
Returns
An AListInner node containing the left children

Member Data Documentation

Entry [] Loyc.Collections.Impl.AListInnerBase< K, T >._children
protected

List of child nodes. Empty children are null.

*** TODO ***: don't increase _children size by 4. Increase it exponentially