VisibleOrderBuffer<TKey> class

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

Also owns the roots list (with order) and the visible-subtree-size cache — both are pure functions of (structure × 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 TKey ↔ 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

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. Read-only access for hot loops — do not mutate directly; use the insert/remove methods. Entries beyond length carry stale data from prior mutations.
no setter
roots → List<TKey>: Roots (with order). Live, internally-owned List<TKey> — the reference is stable for the lifetime of this buffer instance, 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 — this method does not touch it. Does NOT touch the subtree-size cache or 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 — safe to call 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.
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.
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: Returns the key at visible position i. Unchecked — i must satisfy 0 <= i < length.
nidAt(int i) → int: Returns 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
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.
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: Backwards-compatible alias for resizeForCapacity used by older call sites that grew only the reverse index. Plan B unifies the two growth paths since both per-nid arrays must stay in lockstep with the registry's capacity.
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.
setIndexByNid(int nid, int index) → void: Writes index into the reverse-index slot for nid. nid must be live. Does not touch the order buffer.
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.