VisibleOrderBuffer<TKey> class

Maintains the tree's flattened visible order as a dense buffer of nids (not keys), plus a reverse map from nid to visible index for O(1) membership queries.

Also owns the roots list (with order) and the visible-subtree-size cache, both pure functions of structure and visible order, so they belong inside this layer rather than on the controller. The cache satisfies the invariant

_subtreeSizeByNid[nid] == (nid in order ? 1 : 0)
                        + sum over children c of _subtreeSizeByNid[c]

Maintained incrementally on order mutations and parent-change events (subscribed via NodeStore.onParentChanged); rebuilt wholesale by rebuild for bulk paths.

The order buffer (orderNids) is sized independently and grown by doubling on insert. The reverse-index buffer (indexByNid) and the subtree-size buffer are per-nid dense arrays that must be grown in lockstep with every other per-nid array maintained by the controller: call resizeForCapacity from the same path that grows _parentByNid, _depthByNid, and friends.

Does not own the registry; the registry is passed in and used to translate between TKey and nid on the public boundary. Reads parentByNid and childKeysOf via constructor callbacks so the buffer stays decoupled from NodeStore.

Mutating operations invoke the onOrderMutated callback so the owner can invalidate derived caches (e.g. the full-extent prefix sum).

Constructors

VisibleOrderBuffer({required NodeIdRegistry<TKey> registry, required int parentByNid(int nid), required List<TKey>? childKeysOf(TKey key), required void onOrderMutated()})

Properties

debugInsertPerNidCount ↔ int: getter/setter pair
debugInsertSharedChainCount ↔ int: Debug counters for insertAllKeys' two subtree-size bump branches (L25.7): the shared-chain bump for a same-parent run, and the per-nid fallback for a mixed-depth run or a run of roots.
getter/setter pair
debugResetIndexAllCount ↔ int: Number of resetIndexAll invocations over this buffer's lifetime. Perf oracle: an O(nidCapacity) memset per incremental mutation is exactly what the contiguous removal fast path exists to avoid.
getter/setter pair
hashCode → int: The hash code for this object.
no setterinherited
indexByNid → Int32List: Underlying reverse-index buffer. Read-only access for hot loops.
no setter
length → int: Number of entries currently in the visible order.
no setter
orderNids → Int32List: Underlying nid buffer, for read-only access in hot loops. Do not mutate it directly; use the insert and remove methods. Entries beyond length carry stale data from prior mutations.
no setter
roots → List<TKey>: Roots, in order. A live, internally-owned List<TKey> whose reference is stable for this buffer's lifetime, so wrapping it with an UnmodifiableListView produces a view that reflects subsequent mutations.
final
runtimeType → Type: A representation of the runtime type of the object.
no setterinherited

Methods

addKey(TKey key) → void: Appends key's nid to the tail of the order. key must be registered.
bumpFromSelf(int startNid, int delta) → void: Adds delta to the subtree-size cache at startNid and at every ancestor. Stops at kNoParentNid. O(depth).
clear() → void: Zeros length but keeps the order and reverse-index buffers allocated so follow-up inserts can reuse them without realloc. Callers that want the reverse map cleared too must call resetIndexAll separately, since this method does not touch it, nor the subtree-size cache, nor roots. For a full reset use reset.
clearForNid(int nid) → void: Per-nid cache cleanup used by the controller's adopt/release paths. Zeros both the subtree-size slot and the reverse-index slot in one call. Idempotent, so it is safe on already-cleared slots. nid must be in range (callers that only have a key should resolve nid via the registry first).
clearIndexByNid(int nid) → void: Clears the reverse-index slot for nid directly. Used by the controller during nid allocation/release to reset per-nid state.
clearIndexOf(TKey key) → void: Marks key as not visible. Safe on an unregistered key.
contains(TKey key) → bool: Whether key is currently in the visible order.
debugAssertConsistent() → void: Debug-only: asserts the order and reverse-index agree on every live entry, and that the number of non-sentinel reverse-index entries matches length. Wrapped in assert(...) so release builds skip it.
debugAssertSpanIndexed(int fromIndex) → void: Debug-only: verifies order/reverse-index agreement over [fromIndex, length): the O(changed-range) inline check that replaces the full consistency sweep on the incremental-mutation hot path. Live nids must index back to their position; zombie entries (freed nids awaiting a batched sweep) are skipped.
debugAssertSubtreeSizeConsistent() → void: Debug-only: walks the tree and verifies every live nid's subtree-size slot equals the structural definition (own-presence + sum of children's sizes). Wrapped in assert(...) so release builds skip it.
handleParentChanged(int nid, int oldParent, int newParent) → void: Wired up as the subscriber for NodeStore.onParentChanged. Shifts the moved subtree's contribution from the old parent's ancestor chain to the new parent's chain. No-op when oldParent equals newParent, when the moved subtree contributes nothing, or when updates are currently suppressed (e.g. inside rebuild).
indexOf(TKey key) → int: Visible position of key, or kNotVisible if key is not in the order (or not registered). O(1).
insertAllKeys(int index, List<TKey> keys) → void: Inserts the nids of keys at visible position index, preserving their relative order. Each key must be registered.
insertAllKeysAtGaps(List<int> gaps, List<TKey> keys) → void: Inserts keys at the PRE-insert positions gaps, in one pass.
insertKey(int index, TKey key) → void: Inserts key's nid at visible position index. key must be registered.
insertNid(int index, int nid) → void: Inserts nid at visible position index, shifting the suffix right. nid must be live.
keyAt(int i) → TKey: The key at visible position i. Unchecked: i must satisfy 0 <= i < length.
nidAt(int i) → int: The nid at visible position i. Unchecked: i must satisfy 0 <= i < length.
noSuchMethod(Invocation invocation) → dynamic: Invoked when a nonexistent method or property is accessed.
inherited
purgeCompact(Set<TKey> keys) → void: Intention-revealing non-contiguous compaction: clears the removed keys' reverse-index slots, sweeps the order, dropping keys AND any zombie entries whose nid was already released (the zombie protocol documented on removeWhereKeyIn), then rebuilds the reverse index wholesale. The full "non-contiguous removal" protocol in one owner.
rebuild(void build()) → void: Convenience for clear+rebuild paths. Suppresses callbacks, clears the order, runs the closure (which populates via addKey), then rebuilds the reverse-index buffer (since addKey only appends to orderNids and does not write indexByNid) and runs the O(N) post-order subtree-size pass. Owns "clear + fill + finalize all derived state" so the closure body shrinks to just the populate work.
rebuildIndex() → void: Rebuilds indexByNid from the current order buffer. Use after bulk rewrites that leave the reverse map stale.
reindexFrom(int startIndex) → void: Refreshes indexByNid entries for positions in [startIndex, length). Call after inserts at startIndex or after a contiguous removal that shifted the suffix.
removeAt(int index) → void: Removes the entry at visible position index, shifting the suffix left by one.
removeContiguousRange(int start, int endExclusive) → void: Intention-revealing bulk removal of the contiguous range [start, endExclusive): clears each removed entry's reverse-index slot, removes the physical range, and reindexes the shifted suffix. That is the whole contiguous-removal protocol in one owner. Subtree-size cache decrements follow removeRange's suppression contract.
removeRange(int start, int end) → void: Removes entries in [start, end), shifting the suffix left.
removeWhereKeyIn(Set<TKey> keys) → void: Compacts the order by dropping every entry whose key is in keys, or whose nid has been released. Preserves the relative order of kept entries.
reset() → void: Full reset: zeros length and releases the order buffer, the reverse-index buffer, the subtree-size cache buffer back to empty, and clears roots in place (preserving the stable list reference). Used on controller-wide clear.
resetIndexAll() → void: Resets every reverse-index slot to kNotVisible.
resizeForCapacity(int capacity) → void: Grows every per-nid dense array (reverse index + subtree-size cache) to at least capacity. New reverse-index slots are initialised to kNotVisible; new subtree-size slots are initialised to 0. Call from the same code path that grows every other per-nid dense array the controller maintains.
resizeIndex(int capacity) → void: Alias for resizeForCapacity. Both per-nid arrays must stay in lockstep with the registry's capacity, so there is only one growth path.
runWithSubtreeSizeUpdatesSuppressed(void body()) → void: ADVANCED. Suppresses the inlined subtree-size cache callbacks for the closure body. Caller is fully responsible for keeping the subtree-size cache consistent across the body, typically by pre-bumping via bumpFromSelf before the closure runs. Misuse silently corrupts the cache.
subtreeSizeOf(int nid) → int: Per-nid count of currently-visible entries in the subtree rooted at nid, including nid itself when it is in the order. O(1) array read. Returns 0 for nids that are not currently in the order and have no visible descendants, or for freed nids whose slot was reset.
toString() → String: A string representation of this object.
inherited

Operators

operator ==(Object other) → bool: The equality operator.
inherited

Constants

kNotVisible → const int: Sentinel in indexByNid meaning "not currently in the visible order". Freed nids also carry this value so a recycled nid starts invisible.