Fractional indexing — generate ordered keys that admit insertion between any two existing positions without rebalancing.
Used by cell_item.position to give parent → child membership a stable,
lex-sortable order. Two clients editing the same parent each compute keys
locally; the server applies them with (parent_id, position) as the
primary key. Concurrent inserts that hit the same key surface as a
cell_item_position_taken error; helper-side jitter (a small random
suffix on every generated key) keeps the collision probability negligible
at realistic UX concurrency.
Alphabet: base62 (0-9, A-Z, a-z). '0' is the least
digit; 'z' the greatest. Keys are read as base62 fractions: lex order
over keys equals numeric order over fractions.
Invariants emitted by this generator:
'0'. Without this rule, key + '0' would
lex-equal key for ordering purposes, losing the room-to-insert that
the trailing-'0' extension would otherwise provide.≤ FRACTIONAL_INDEX_LENGTH_MAX. The cap is checked
on both inputs and output: bounds within a few digits of the cap can
push a generated key over it, and the generator throws in that case
rather than emitting an oversized key the wire would reject. In
realistic use keys stay far under 100 chars, so this never fires.Wire vs. emitted invariants: FRACTIONAL_INDEX_REGEX enforces the
alphabet + non-empty contract for any client-supplied position. The
no-trailing-'0' rule is stricter and lives only in this generator;
the wire admits the looser form so a future encoder can sit alongside
this one without a wire-schema bump.
MVP scope — unsupported bracket shapes:
'0…': a long sequence of front-inserts
eventually requires a key lex-less than every '0'-only key.(a, a + '0…0') for any non-empty zero tail: the
no-trailing-'0' invariant means no valid key fits the gap.Both surface as explicit throws. Realistic UX bounds keep emitted keys well under 100 chars after thousands of consecutive front- or back-inserts; consumers that genuinely need the prepend extension should request a negative-prefix scheme.
5 declarations
fractional_index.ts view source
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" import {FRACTIONAL_INDEX_ALPHABET} from '@fuzdev/fuz_util/fractional_index.js'; Base62 alphabet, monotonic in lex order: digits, then upper, then lower.
fractional_index.ts view source
(a: string | null, b: string | null, random?: () => number): string import {fractional_index_between} from '@fuzdev/fuz_util/fractional_index.js'; Returns a key strictly between a and b in lex order.
Either bound may be null (open). Throws when the bracket is invalid
(a >= b lex-wise) or when the gap is structurally too tight to fit
a key under the no-trailing-'0' invariant (only happens with bounds
shaped (a, a + '0…0'); the helper itself never produces those).
Emits a deterministic mid-key, then appends a random jitter suffix.
The deterministic mid is what guarantees lex order; the jitter widens
the keyspace within the slot to defend against concurrent-insert
collisions on the same (prev, next) view.
Pass random to inject a deterministic source for tests; omit for
production (uses Math.random). The callback must honor the standard
[0, 1) contract; jitter_suffix clamps defensively for safety. The
jitter is best-effort collision avoidance, not a security primitive —
the server's cell_item_position_taken error is the load-bearing
safety net.
astring | nullbstring | nullrandom() => numberMath.randomstring Error - if the bracket is invalid (`a >= b`), a bound breaks thefractional_index.ts view source
200 import {FRACTIONAL_INDEX_LENGTH_MAX} from '@fuzdev/fuz_util/fractional_index.js'; Soft length cap on positions, mirrored at the wire. Primarily DOS protection; the algorithm has no inherent length limit but realistic UX bounds keep emitted keys under 100 chars even after thousands of consecutive front- or back-inserts. Inputs above this cap surface as an explicit throw rather than producing oversized output the wire would later reject.
fractional_index.ts view source
RegExp import {FRACTIONAL_INDEX_REGEX} from '@fuzdev/fuz_util/fractional_index.js'; Wire-grammar regex for cell_item.position: at least one base62 digit.
The stricter no-trailing-'0' rule is an invariant of *this* generator,
not the wire. See module docstring §"Wire vs. emitted invariants".
fractional_index.ts view source
(a: string | null, b: string | null, n: number, random?: () => number): string[] import {fractional_indices_between} from '@fuzdev/fuz_util/fractional_index.js'; Generate n strictly-ordered keys between a and b.
Used for batch inserts (paste, bulk-import) so positions don't all collapse onto a single deterministic mid-point. Output is monotonically increasing; equal spacing is not guaranteed (clumping under the same mid is acceptable and rare in practice).
Implemented by recursive bisection: pick the deterministic mid of
(a, b), generate floor(n/2) keys in (a, mid), the mid itself,
and the rest in (mid, b). Each emitted key carries its own jitter.
Atomic on failure: if the bracket is structurally too tight at any
recursion depth, the whole call throws and no partial array is
returned. (Sub-brackets generated by mid_between never have the
tight shape, so this only fires when the *initial* bracket is tight.)
astring | nullbstring | nullnnumberrandom() => numberMath.randomstring[] Error - if `n` is negative or non-integer, or if the initial bracket