precomputeStableSubtreeBottoms method

void precomputeStableSubtreeBottoms({ required List<TKey> visibleNodes, required Float64List nodeOffsetsByNid, required Float64List nodeExtentsByNid, })

Precomputes subtree bottom offsets for all visible nodes in O(N).

Uses the same "entering nodes contribute their full estimated extent" logic as the per-candidate fallback, but does it for the entire visible list in three linear passes instead of a per-candidate descent.

Reads layout-space offsets and extents directly from the per-nid arrays passed in. Caller is responsible for ensuring those arrays are fresh.

Implementation

void precomputeStableSubtreeBottoms({
  required List<TKey> visibleNodes,
  required Float64List nodeOffsetsByNid,
  required Float64List nodeExtentsByNid,
}) {
  final n = visibleNodes.length;
  if (n == 0) return;

  if (_depthScratch.length < n) {
    _depthScratch = Int32List(n);
    _subtreeEndIndex = Int32List(n);
    _subtreeBottomByIndex = Float64List(n);
    _stablePrefix = Float64List(n + 1);
  }
  _stablePrefix[0] = 0.0;

  final orderNids = _controller.orderNidsView;

  // Pass A: depths + stable prefix sums.
  for (int i = 0; i < n; i++) {
    final nid = orderNids[i];
    final depth = _controller.depthOfNid(nid);
    _depthScratch[i] = depth;

    final nodeId = visibleNodes[i];
    final anim = _controller.getAnimationState(nodeId);
    final double stableExtent;
    if (anim != null && anim.type == AnimationType.entering) {
      // Use full extent so ancestor push-up doesn't bounce during expand.
      stableExtent = _controller.getEstimatedExtentNid(nid);
    } else {
      stableExtent = nodeExtentsByNid[nid];
    }
    _stablePrefix[i + 1] = _stablePrefix[i] + stableExtent;
  }

  // Pass B: subtree end index for each node using a monotonic depth stack.
  // _indexStack is an Int32List + explicit length; bound is n entries.
  if (_indexStack.length < n) {
    _indexStack = Int32List(n);
  }
  _indexStackLen = 0;
  for (int i = 0; i < n; i++) {
    final depth = _depthScratch[i];
    while (_indexStackLen > 0 &&
        depth <= _depthScratch[_indexStack[_indexStackLen - 1]]) {
      final j = _indexStack[--_indexStackLen];
      _subtreeEndIndex[j] = i - 1;
    }
    _indexStack[_indexStackLen++] = i;
  }
  while (_indexStackLen > 0) {
    final j = _indexStack[--_indexStackLen];
    _subtreeEndIndex[j] = n - 1;
  }

  // Pass C: subtree bottom per node.
  // For each node i: bottom = (node's actual end) + (stable sum of
  // descendants).
  for (int i = 0; i < n; i++) {
    final nid = orderNids[i];
    final actualEnd = nodeOffsetsByNid[nid] + nodeExtentsByNid[nid];
    final end = _subtreeEndIndex[i];
    final descendantStableSum =
        _stablePrefix[end + 1] - _stablePrefix[i + 1];
    _subtreeBottomByIndex[i] = actualEnd + descendantStableSum;
  }
  _lastPrecomputedCount = n;
}