IndexedList

npm install @derivation/indexed-list

IndexedList<NodeId, X> is an immutable list with efficient insertions and deletions anywhere in the order, but it also allows efficiently finding the positional index of an item given its ID. NodeIds are derived from the Xs.

This is useful when you need a list with:

• stable identities,
• frequent insertions between existing items,
• cheap order comparisons.

It does this by assigning each node a bigint label and maintaining two ranked, sorted maps:

• id -> { label, value }
• label -> id

Part of what makes this efficient is that the label space isn't dense. For N items, the label space is O(n^2).

Labels may need to be reassigned if you do a lot of insertions in the same place, but there's a smart strategy to minimize reassignments.

Efficient insertions here means amortized O(log n) time observed, but potentially O(log^2 n) theoretically.

Usage

const list = IndexedList.create({
  compareIds: (a, b) => (a < b ? -1 : a > b ? 1 : 0),
  xToNodeId: (value: { id: bigint; text: string }) => value.id,
});

const [withAlpha, alphaId] = list.append({ id: 10n, text: "alpha" });
const [withBoth] = withAlpha.insertAfter(alphaId, { id: 20n, text: "beta" });

Partial persistence safety

IndexedList is safe to use in a partially persistent way. This means that updates never happen in place and you can query historical versions, but you must always have linear history. Don't try to go back and modify historical versions (it'll work, but it may perform poorly).