NodeUtil

public func insertAtIndexOfNonFullNodeData<K, V>(
  data : Types.Data<K, V>,
  kvPair : ?(K, V),
  insertIndex : Nat
) : ()

Inserts element at the given index into a non-full leaf node

public func insertRebalancedChild<K, V>(
  children : [var ?Types.Node<K, V>],
  rebalancedChildIndex : Nat,
  leftChildInsert : Types.Node<K, V>,
  rightChildInsert : Types.Node<K, V>
) : ()

Inserts two rebalanced (split) child halves into a non-full array of children.

public func splitChildrenInTwoWithRebalances<K, V>(
  children : [var ?Types.Node<K, V>],
  rebalancedChildIndex : Nat,
  leftChildInsert : Types.Node<K, V>,
  rightChildInsert : Types.Node<K, V>
) : ([var ?Types.Node<K, V>], [var ?Types.Node<K, V>])

Used when splitting the children of an internal node

Takes in the rebalanced child index, as well as both halves of the rebalanced child and splits the children, inserting the left and right child halves appropriately

For more context, see the documentation for the splitArrayAndInsertTwo method in ArrayUtils.mo

public func getKeyIndex<K, V>(
  data : Types.Data<K, V>,
  compare : (K, K) -> Order.Order,
  key : K
) : BS.SearchResult

Helper used to get the key index of of a key within a node

for more, see the BinarySearch.binarySearchNode() documentation

public func minKeysFromOrder(order : Nat) : Nat

public func getMaxKeyValue<K, V>(node : ?Types.Node<K, V>) : (K, V)

public func borrowFromLeftLeafChild<K, V>(children : [var ?Types.Node<K, V>], ofChildIndex : Nat) : ?(K, V)

public func borrowFromRightLeafChild<K, V>(children : [var ?Types.Node<K, V>], ofChildIndex : Nat) : ?(K, V)

public func borrowFromInternalSibling<K, V>(
  children : [var ?Types.Node<K, V>],
  borrowChildIndex : Nat,
  borrowType : InorderBorrowType
) : InternalBorrowResult<K, V>

public func rotateBorrowedKVsAndChildFromSibling<K, V>(
  internalNode : Types.Internal<K, V>,
  parentRotateIndex : Nat,
  borrowedSiblingKVPair : ?(K, V),
  borrowedSiblingChild : ?Types.Node<K, V>,
  internalChildRecipient : Types.Internal<K, V>,
  siblingSide : SiblingSide
)

public func mergeChildrenAndPushDownParent<K, V>(
  leftChild : Types.Internal<K, V>,
  parentKV : ?(K, V),
  rightChild : Types.Internal<K, V>
) : Types.Internal<K, V>