visibleSubtreeSize method

int visibleSubtreeSize(TKey key)

Number of currently-visible rows in key's subtree, including key itself. O(1) read off the order buffer's cached subtree sizes.

A visible row with no visible descendants (a leaf, or a collapsed node) returns 1, so getVisibleIndex(key) + visibleSubtreeSize(key) is the visible index just past key's subtree, which is the slot that follows it. That is what drop resolution uses to anchor a gap on a candidate whose sibling index it incremented.

PRECONDITION: key is in the visible order. The cache counts visible rows, so a key that is itself hidden but has visible descendants returns a positive count that is NOT anchored at key, and one that is hidden with nothing visible below it returns 0, which would read as "the slot before key" rather than after it. Callers resolve against rows they have just located in the order.

Implementation

int visibleSubtreeSize(TKey key) {
  _ensureVisibleOrder();
  final nid = _nids[key];
  if (nid == null) {
    return 0;
  }
  assert(
    _order.contains(key),
    "visibleSubtreeSize($key) requires $key to be in the visible order; "
    "the cached count is anchored at the node's own row, so asking about "
    "a hidden node yields a size that belongs to a different slot.",
  );
  return _order.subtreeSizeOf(nid);
}