index package:unordered-containers

Given a Hash and a Shift that indicates the level in the tree, compute the index into a Full node or into the bitmap of a BitmapIndexed node.
>>> index 0b0010_0010 0
0b0000_0010
Invariants:
  • Only the lower maxChildren bits of the Bitmap may be set. The remaining upper bits must be 0. (INV2)
  • The array of a BitmapIndexed node stores at least 1 and at most maxChildren - 1 sub-nodes. (INV3)
  • The number of sub-nodes is equal to the number of 1-bits in its Bitmap. (INV4)
  • If a BitmapIndexed node has only one sub-node, this sub-node must be a BitmapIndexed or a Full node. (INV5)
Create a BitmapIndexed or Full node.
This array index is computed by counting the number of 1-bits below the index represented by the mask.
>>> sparseIndex 0b0110_0110 0b0010_0000
2