@zakkster/lite-o1

Zero-GC, O(1) data structures that PROVE their constant. v1.3.0 ships SparseSet (an integer set with O(1) add / has / delete / iterate and an O(1) clear() that zeroes nothing), RingDeque (a fixed-capacity numeric double-ended queue with O(1) push/pop at both ends), UnionFind (a disjoint-set forest with near-O(1) amortized find / union), MonoDeque (a monotonic deque for O(1)-amortized sliding-window min / max), MinStack (a fixed-capacity numeric stack with a worst-case-O(1) running min / max), RandomSet (an integer set with worst-case-O(1) uniform sample / removeRandom), FreqO1 (a worst-case-O(1) LFU frequency structure with O(1) add / increment / peekMin / popMin), BucketQueue (an amortized-O(1) monotone integer priority queue / Dial with O(1) insert / decreaseKey / extractMin), TimerWheel (a worst-case-O(1) bounded simple timing wheel with O(1) schedule / cancel / advance and drain-before-advance), HierarchicalTimerWheel (an amortized-O(1) cascading multi-level timing wheel with a 2^26 delay range), RingLog (a worst-case-O(1) lossy overwrite-oldest ring log whose O(1) push returns the evicted oldest), CuckooMap (a bounded-probe worst-case-O(1)-lookup exact map from general integer keys to numbers via bucketized cuckoo hashing), and SparseTable (a worst-case-O(1)-query STATIC range-minimum / range-maximum table / StaticRMQ) -- plus a throughput-invariance witness that shows the flat cost curve while a native Set, Array.prototype.shift, a naive disjoint-set, a full-window rescan, a full-stack rescan, a Set-iterate-to-the-kth, a frequency-table min-scan, a binary heap, a naive-scan scheduler, a 4-ary heap, a shift-on-full Array log, a naive linear-scan map, or a naive O(len) range-scan decays.

The O(1) toolkit the ecosystem was missing

Almost no JavaScript data-structure library ships the evidence that its Big-O claim survives contact with a real engine -- megamorphic call sites, GC pauses, cache misses, deopts. lite-o1 is a curated, tree-shakeable family of the O(1) structures that actually matter, each zero-GC, each written to teach the trick that buys the constant, and each shipped with a harness that DEMONSTRATES the flat cost curve rather than asserting it. The complexity class IS the product.

v1.3.0 ships thirteen members. SparseSet, the textbook O(1) integer set (a dense + sparse array pair) whose clear() runs in O(1) by resetting a count and zeroing nothing at all. RingDeque, a fixed-capacity double-ended queue of numbers over one circular Float64Array -- O(1) push/pop at both ends, the zero-GC answer to the Array.prototype.shift O(n) trap. UnionFind, a disjoint-set forest over two Uint32Array columns -- near-O(1) amortized find / union via path halving + union by size, the family's first amortized-honesty member. MonoDeque, a monotonic deque over two parallel Float64Array columns -- O(1)-amortized sliding-window min / max, the zero-GC answer to the full-window-rescan O(W) trap. MinStack, a fixed-capacity numeric stack over two parallel Float64Array columns (value + a running-extreme prefix) -- WORST-CASE O(1) push/pop plus a running min / max, no amortization asterisk. RandomSet, SparseSet's substrate plus WORST-CASE O(1) uniform sample() / removeRandom() -- the zero-GC answer to the Array.from(set)[k] O(n)-plus-allocation trap. FreqO1, a WORST-CASE O(1) frequency structure over a private bucket forest -- add / increment / peekMin / popMin, the standalone primitive behind O(1) LFU eviction, the zero-GC answer to the scan-all-counts-for-the-minimum O(n) trap. BucketQueue, an AMORTIZED O(1) monotone integer priority queue ("Dial") over private key columns + a static per-priority bucket array -- insert / decreaseKey / extractMin, the standalone primitive behind Dial's algorithm, the zero-GC answer to a binary heap's O(log n) per op when priorities are small bounded integers. And TimerWheel, a WORST-CASE O(1) bounded "simple" timing wheel (Varghese-Lauck) over private id columns + a static per-slot FIFO ring -- schedule / cancel / drainDue / advance, the standalone primitive behind O(1) timer scheduling, the zero-GC answer to a binary-heap timer queue's O(log n) per op (and a linear scan's O(n) per tick) when the delay horizon is bounded. And HierarchicalTimerWheel, an AMORTIZED O(1) CASCADING multi-level timing wheel (the Linux tvec shape: 1x256 + 3x64, delay range 2^26) over the same substrate plus a Float64 expiry column -- schedule / cancel / drainDue / advance, TimerWheel's sibling for a delay horizon too wide for one rotation, cascading coarse timers down to finer levels by index (zero allocation) and wearing an honest max-single-op cascade spike. And RingLog, a WORST-CASE O(1) LOSSY overwrite-oldest ring log over one circular Float64Array -- "keep the last N": push never blocks and never throws on full, it OVERWRITES the oldest entry and RETURNS it (RingDeque's substrate with its full-push policy INVERTED), the zero-GC answer to the push-then-shift-on-full Array log's O(n) trap. And CuckooMap, a bounded-probe WORST-CASE O(1)-lookup exact map from GENERAL INTEGER keys (|k| <= 2^53) to numbers over a bucketized cuckoo table (2 tables x 4 slots, get / has / delete probe at most 8 slots) -- the family's first general-key exact dictionary, O(capacity) space over a sparse / large integer key domain (vs SparseSet's O(universe) dense one), whose amortized set wears an honest in-place re-seed spike, the zero-GC answer to a general hash map's average-case-only lookup and its GC. And SparseTable, a WORST-CASE O(1)-QUERY STATIC range-minimum / range-maximum table (the idempotent-operation sparse table / "StaticRMQ") over two immutable Float64Array columns (a source copy + a flat n*(K+1) table) -- the family's FIRST static build-once / immutable member: build once, then answer the min OR max over any range [l, r] in worst-case O(1) (a floor-log2 + two table reads + one compare), the zero-GC answer to a naive O(len) range-scan (the O(n log n) build + table space are a disclosed co-headline). They share no mutable module state, so a bundler that imports one drops the others.

npm install @zakkster/lite-o1

import { SparseSet } from '@zakkster/lite-o1';

// Universe [0, 100000); at most 10000 entries live at once.
const live = new SparseSet(100000, 10000);

live.add(42);
live.add(7);
live.add(42);           // idempotent -- still size 2

live.has(42);           // -> true
live.has(999);          // -> false (absent, never a throw)
live.has(-1);           // -> false (a bad key is absent; null is not zero)

live.delete(7);         // -> true (swaps the last dense entry into the hole)
live.size;              // -> 1

for (const k of live) console.log(k);   // 42   (insertion order, alloc-free)

live.clear();           // O(1): resets the count, touches NEITHER backing array
live.size;              // -> 0

Every op above is O(1) worst-case and allocates zero bytes after construction. The witness harness (npm run witness) proves SparseSet holds its ops/ms from n=1e3 to n=1e7 while a native Set falls off a cliff.

Table of contents

• Why this exists
• What you get
• How SparseSet works
• API reference
  • SparseSet
  • Constants
• The O(1) Witness
• RingDeque
  • How RingDeque works
  • RingDeque API reference
• UnionFind
  • How UnionFind works
  • UnionFind API reference
• MonoDeque
  • How MonoDeque works
  • MonoDeque API reference
• MinStack
  • How MinStack works
  • MinStack API reference
• RandomSet
  • How RandomSet works
  • RandomSet API reference
• FreqO1
  • How FreqO1 works
  • FreqO1 API reference
• BucketQueue
  • How BucketQueue works
  • BucketQueue API reference
• TimerWheel
  • How TimerWheel works
  • TimerWheel API reference
• HierarchicalTimerWheel
  • How HierarchicalTimerWheel works
  • HierarchicalTimerWheel API reference
• RingLog
  • RingLog API reference
• CuckooMap
  • CuckooMap API reference
• SparseTable
  • SparseTable API reference
• Composability with the ecosystem
• Zero-GC design notes
• Design decisions worth knowing
• Testing
• What this is not
• Ecosystem
• License

Why this exists

Two problems no small library solves at once for integer sets on a hot path:

1. The Big-O claim is never proven. A library says "O(1)" and you take it on faith. But a real engine can turn a nominal O(1) into something that decays with n: a hash set's buckets scatter across an ever-larger table until every lookup is a cache miss. lite-o1's analytical anchor is throughput invariance -- ops/ms that stays FLAT as n grows across orders of magnitude. That flat line IS the proof of the constant, and the shipped witness reports it as a number and a shape, against a built-in Set foil on the identical sweep.

2. The clear() trap. Emptying a set by zeroing its store is O(n) -- fine once, ruinous in a per-frame loop that refills and clears an ECS component set or a visited-mask every tick. SparseSet's cross-checked membership (sparse[k] < n && dense[sparse[k]] === k) makes clear() a single n = 0: the stale sparse pointers are simply ignored because the cross-check rejects them. Nothing is zeroed, so clearing 10 million entries costs the same as clearing one.

Existing options: a native Set (arbitrary keys, but a hash table that decays and an O(n) clear), a plain Array of flags (O(1) set/test but O(n) clear and O(universe) iterate), or roll-your-own (and get the delete-swap back-pointer wrong). lite-o1 is the zero-GC primitive for a dense integer domain, with the proof attached.

What you get

• SparseSet(universe, capacity?) -- a zero-GC O(1) integer set over [0, universe), holding at most capacity live members (default capacity = universe). The hot surface is five ops plus two getters:
  • add(k) -- insert (idempotent). O(1). Throws a [lite-o1] error on a bad key or when full.
  • has(k) -- membership test. O(1). A bad key (negative, fractional, NaN, null, >= universe) is absent -- never a throw.
  • delete(k) -- remove by swapping the last dense entry into the hole and fixing its back-pointer. O(1). Returns true iff present.
  • clear() -- empty in O(1): resets the live count, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate present keys in insertion order, alloc-free.
  • size / capacity -- getters.
• RingDeque(capacity) -- a zero-GC O(1) fixed-capacity double-ended queue of numbers over one circular Float64Array. Capacity rounds up to the next power of two. The hot surface is eight ops plus two getters:
  • pushFront(v) / pushBack(v) -- push at either end. O(1). Throw a [lite-o1] error when full (a byte-identical no-op) or on a non-clean value.
  • popFront() / popBack() -- remove + return from either end. O(1). Return undefined on empty -- never a throw.
  • peekFront() / peekBack() -- read either end without removing. O(1). undefined on empty.
  • clear() -- empty in O(1): resets head + count, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate live elements front -> back, alloc-free.
  • size / capacity -- getters (capacity reports the rounded power of two).
• UnionFind(n) -- a zero-GC near-O(1) (amortized alpha(n)) disjoint-set forest over two Uint32Array columns (parent + subtree size), fixed element count n (elements are [0, n)). The hot surface is four ops plus two getters and two O(n) scan primitives:
  • find(x) -- the root of x's component. O(1)-amortized. Path halving flattens the walk in place. Throws a [lite-o1] error on a bad element.
  • union(a, b) -- merge two components (union by size). O(1)-amortized. Returns true iff a real merge happened.
  • connected(a, b) / componentSize(x) -- same-component test / component size. O(1)-amortized.
  • count / capacity -- getters (count is the live component count, maintained in O(1); capacity is the fixed n).
  • reset() -- re-singleton every element. O(n) (the honest exception; allocates nothing, but is a bulk op, not a per-op hot path).
  • forEachRoots(fn) / roots() -- visit the current roots; forEachRoots is an O(n) alloc-free scan, roots() is an allocating generator.
• MonoDeque(capacity, kind) -- a zero-GC O(1)-amortized monotonic deque for sliding-window min / max over two parallel Float64Array columns (value + monotonic seq). kind ('min' | 'max') is frozen at construction; capacity rounds up to the next power of two. The hot surface is four ops plus three getters:
  • push(v) -- assign the next monotonic seq, pop dominated back entries, append. O(1)-amortized. Returns the assigned seq. Throws a [lite-o1] error when full (a byte-identical no-op), on a non-clean value, or past seq 2^53.
  • evictOlderThan(seq) -- drop front entries the caller has slid past (stored seq <= the given seq). O(1)-amortized. Throws on a non-number / NaN seq.
  • value() / frontSeq() -- the current window extreme (front value) and its seq. O(1). undefined on empty -- never a throw.
  • kind / size / capacity -- getters (kind is the frozen 'min'/'max'; capacity reports the rounded power of two).
  • clear() -- empty in O(1): resets head + count + the seq counter, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate live entries front -> back (O(k)); forEach is alloc-free, [Symbol.iterator] allocates a [value, seq] tuple per step by protocol.
• MinStack(capacity, kind) -- a zero-GC WORST-CASE O(1) fixed-capacity numeric stack that also reports the running min / max over two parallel Float64Array columns (value + a running-extreme prefix). kind ('min' | 'max') is frozen at construction; capacity is EXACT (not rounded). The hot surface is four ops plus three getters:
  • push(v) -- push onto the top, carrying the running extreme in one compare. O(1) worst-case. Returns this. Throws a [lite-o1] error when full (a byte-identical no-op) or on a non-clean value.
  • pop() / peek() -- remove / read the top value. O(1). Return undefined on empty -- never a throw.
  • extreme() -- the current min / max (per kind) of every live element, a single prefix read. O(1) worst-case. undefined on empty.
  • kind / size / capacity -- getters (kind is the frozen 'min'/'max'; capacity is the exact constructed integer).
  • clear() -- empty in O(1): resets the top pointer, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate live elements top -> bottom (pop order, O(k)); forEach is alloc-free, [Symbol.iterator] allocates a {value, done} per step by protocol.
• RandomSet(universe, capacity?, seed?) -- a zero-GC O(1) integer set (SparseSet's dense + sparse substrate, duplicated verbatim) that ALSO samples a uniform-random live member in WORST-CASE O(1). seed (default 0x9e3779b1) is a per-instance RNG word. The hot surface is the SparseSet surface plus two random ops:
  • add(k) / has(k) / delete(k) / clear() / forEach(fn) / [Symbol.iterator] / size / capacity -- identical to SparseSet (same fail-closed + never-throw-query contract).
  • sample() -- a uniform-random live member WITHOUT removing it (a pure peek; it advances the RNG). O(1) worst-case. undefined on empty -- never a throw.
  • removeRandom() -- remove + return a uniform-random live member (the same swap-last delete uses). O(1) worst-case. undefined on empty -- never a throw.
• FreqO1(universe, capacity?, maxFreq?) -- a zero-GC WORST-CASE O(1) frequency structure over a private Uint32Array node + bucket forest: the standalone primitive behind O(1) LFU eviction. maxFreq (default 2**32 - 2) is the frequency ceiling. The hot surface is six ops plus four getters:
  • add(k) -- ensure k is tracked at frequency 1 if absent (idempotent no-op if present; does NOT bump). O(1). Throws a [lite-o1] error on a bad key or when full.
  • increment(k) -- record one access (insert at 1 if absent, else freq += 1). O(1) worst-case. Throws on a bad key, when full, or past maxFrequency.
  • frequencyOf(k) -- k's frequency, or 0 if absent / bad. O(1). Never a throw (0 = not tracked).
  • has(k) -- membership. O(1). A bad key is absent -- never a throw.
  • peekMin() / popMin() -- read / remove the least-frequently-used key (lowest count; FIFO tie-break). O(1) worst-case. undefined on empty -- never a throw.
  • clear() -- empty in O(1): resets the count + the bucket pool, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate live keys in dense storage order (forEach alloc-free, fn is (key, frequency, freq); the iterator allocates per protocol).
  • size / capacity / universe / maxFrequency -- getters.
• BucketQueue(universe, ceiling, capacity?) -- a zero-GC AMORTIZED O(1) monotone integer priority queue ("Dial") over private Uint32Array key columns + a static per-priority bucket array: the standalone primitive behind Dial's algorithm. ceiling is the inclusive max priority (space is O(ceiling)). The hot surface is six ops plus five getters:
  • insert(k, p) -- insert k at priority p. O(1). Idempotent no-op if k is present. Throws a [lite-o1] error on a bad key / priority, a priority below the cursor, or when full.
  • decreaseKey(k, newPrio) -- lower k's priority. O(1). No-op if k is absent or newPrio is not a strict decrease. Throws on a bad key / priority or a newPrio below the cursor.
  • extractMin() -- remove + return the min-priority key (FIFO tie-break); advances the monotone cursor. O(1) amortized. undefined on empty -- never a throw.
  • peekMin() -- the min-priority key without removing it. O(1) amortized. undefined on empty.
  • priorityOf(k) -- k's priority, or -1 if absent / bad. O(1). Never a throw (-1 is the not-tracked sentinel; priority 0 is a real priority).
  • has(k) -- membership. O(1). A bad key is absent -- never a throw.
  • clear() -- empty in O(1): resets the count + the cursor, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate live keys in dense storage order (forEach alloc-free, fn is (key, priority, queue); the iterator allocates per protocol).
  • size / capacity / universe / ceiling / cursor -- getters.
• TimerWheel(universe, slots, capacity?) -- a zero-GC WORST-CASE O(1) bounded "simple" timing wheel (Varghese-Lauck) over private Uint32Array id columns + a static per-slot FIFO ring: the standalone primitive behind O(1) timer scheduling. slots rounds up to a power of two and caps the delay range at slots - 1 (space is O(slots) -- the bounded-delay-range honesty note). The hot surface is five ops plus five getters:
  • schedule(id, delay) -- file id into slot (now + delay) & MASK. O(1). Idempotent no-op if id is present (reschedule = cancel then schedule). Throws a [lite-o1] error on a bad id, a delay >= slots, or when full.
  • cancel(id) -- unlink id from its slot FIFO + swap-remove. O(1). Returns true iff it was scheduled; a bad / absent id returns false -- never a throw.
  • drainDue(fn) -- fire + remove exactly the timers present in the due slot (slot[now & MASK]) at entry, calling fn(id, wheel) in FIFO order. O(due). SNAPSHOT semantics: a timer (re)scheduled during a callback defers to a later drain (a self-reschedule at delay 0 fires once, then defers), and a timer canceled before it fires does not fire. Re-entrant schedule / cancel / clear from a callback are supported; re-entrant advance() throws (it would strand the un-fired due timers).
  • advance(ticks = 1) -- step the clock. O(1) for advance(1), O(k) for advance(k). FAIL-CLOSED: throws [lite-o1] if a slot being left behind is undrained (drain-before-advance), if called from inside a drainDue callback (an in-flight drain), or if the 2^53 tick ceiling is hit -- each a byte-identical no-op.
  • has(id) -- membership. O(1). A bad id is absent -- never a throw.
  • clear() -- empty in O(1): resets the count + the tick clock, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate live timers in dense storage order (forEach alloc-free, fn is (id, slot, wheel); the iterator allocates per protocol).
  • size / capacity / universe / slots / now -- getters.
• HierarchicalTimerWheel(universe, capacity?) -- a zero-GC AMORTIZED O(1) CASCADING multi-level timing wheel (the Linux tvec shape: 1x256 + 3x64, delay range 2^26) over the same substrate as TimerWheel plus a Float64 expiry column: TimerWheel's sibling for a wider bounded delay horizon. The surface mirrors TimerWheel -- schedule(id, delay) (delay in [0, 2^26)), cancel(id), drainDue(fn), advance(ticks = 1), has(id), clear(), forEach(fn) (fn is (id, expiry, wheel)), [Symbol.iterator], and getters size / capacity / universe / now / maxDelay (2^26 - 1). As the clock advances, coarse timers CASCADE down to finer levels by index (zero allocation); a level-wrap advance(1) is O(bucket) -- the amortized-O(1) cascade SPIKE. Re-entrant schedule / cancel / clear from a callback are supported; re-entrant advance() throws. Fails closed: a bad id / a delay >= 2^26 / a NEW id past capacity throw [lite-o1] as a byte-identical no-op; drain-before-advance is enforced.
• RingLog(capacity) -- a zero-GC WORST-CASE O(1) fixed-capacity LOSSY overwrite-oldest ring log of numbers over one circular Float64Array ("keep the last N"). Capacity rounds up to the next power of two. The hot surface is four ops plus three getters:
  • push(v) -- append v as the newest entry. O(1) worst-case. Returns the EVICTED oldest value when the log was full (v overwrote it), or undefined while still filling. NEVER throws when full (it overwrites); throws a [lite-o1] error on a non-clean value (a byte-identical no-op).
  • get(i) -- the entry at oldest-relative index i (0 oldest .. size-1 newest). O(1). undefined out of range / non-integer -- never a throw.
  • oldest() / newest() -- read the oldest / newest entry without removing it. O(1). undefined on empty -- never a throw.
  • clear() -- empty in O(1): resets head + count, zeroes no store.
  • forEach(fn) / [Symbol.iterator] -- iterate live entries oldest -> newest (forEach alloc-free, fn is (value, index, log); the iterator allocates per protocol).
  • size / capacity / isFull -- getters (capacity reports the rounded power of two; isFull is size === capacity). There is deliberately NO popOldest / drain -- a RingLog is a window you READ, not a queue you consume (reach for RingDeque to drain / fail closed).
• CuckooMap(capacity, seed?) -- a zero-GC bounded-probe exact map from GENERAL INTEGER keys (|k| <= 2^53, Number.isSafeInteger) to numbers, over a bucketized cuckoo table (2 tables x 4 slots) plus a Uint8Array occupancy signal + two Float64Array columns. Capacity rounds up so the request fits under a 0.90 load ceiling. The hot surface is four ops plus four getters:
  • set(k, v) -- insert or update. AMORTIZED O(1). Returns this. An update of a present key overwrites the value (no eviction). Throws a [lite-o1] error (a byte-identical no-op) on a bad key (not a safe integer) or value (not a number / NaN), and fail-closed at the 0.90 ceiling or when an eviction chain + one in-place O(capacity) re-seed cannot place a new key.
  • get(k) -- the value bound to k, or undefined if absent / not a safe integer. WORST-CASE O(1) -- at most 8 slot reads. Never throws.
  • has(k) -- membership. WORST-CASE O(1). A bad key is absent -- never a throw.
  • delete(k) -- remove k (clears its occupancy byte). WORST-CASE O(1). Returns true iff present. Never throws.
  • clear() -- empty in O(capacity): zeroes the occupancy signal (a Uint8Array fill), leaves the columns as stale, unreachable numbers.
  • forEach(fn) / [Symbol.iterator] -- iterate live entries in dense slot order (forEach alloc-free, fn is (key, value, map); the iterator allocates a [key, value] tuple per step by protocol).
  • size / capacity / seed / load -- getters (capacity is the usable capacity; seed is the current uint32 hash seed; load is size / capacity). 0 is a legal key and any finite number a legal value -- emptiness is the occupancy byte, never a 0 sentinel.
• SparseTable(source, kind) -- a zero-GC WORST-CASE O(1)-QUERY STATIC range-minimum / range-maximum table (StaticRMQ) over two immutable Float64Array columns (a source copy + a flat n*(K+1) table, K = floor(log2 n)). kind ('min' | 'max') is frozen at construction; the source (a real Array of numbers or any numeric TypedArray) is COPIED at build, so a later mutation of the caller's array cannot invalidate a query. The suite's FIRST static build-once / immutable member. The hot surface is two ops plus two getters (NO mutators, NO clear -- immutable):
  • query(l, r) -- the extreme (min or max, per kind) over the inclusive range [l, r]. WORST-CASE O(1): a floor-log2 (via clz32) + two table reads + one compare, independent of the range width. A bad l / r (out of range, l > r) returns undefined -- never throws.
  • at(i) -- the single source element at index i, or undefined out of range / non-integer. O(1). Never throws.
  • forEach(fn) / [Symbol.iterator] -- iterate the source values in index order (forEach alloc-free, fn is (value, index, table); the iterator allocates per protocol).
  • length / kind -- getters (number of source elements; the frozen 'min' | 'max'). The O(n log n) build + n*(floor(log2 n)+1)-cell table space are a DISCLOSED co-headline paid once at construction, excluded from the per-op claim.
• VERSION -- the package version string.
• The O(1) Witness (npm run witness) -- an offline harness that times a fixed batch of each member's hot op across an n-sweep, reports ops/ms + a flatness ratio (SparseSet vs a native Set, RingDeque vs Array.prototype.shift, UnionFind vs a naive disjoint-set, MonoDeque vs a full-window rescan, MinStack vs a full-stack rescan, RandomSet vs a Set iterate-to-the-kth, FreqO1 vs a frequency-table min-scan, BucketQueue vs a binary min-heap, TimerWheel vs a naive-scan scheduler, HierarchicalTimerWheel vs a 4-ary min-heap, RingLog vs a push-then-shift-on-full Array log, CuckooMap vs a naive O(n) linear-scan map, SparseTable vs a naive O(len) range-scan), and fails if the constant regressed.

Full types ship in O1.d.ts. Tree-shakeable named exports (sideEffects: false) -- import only what you use.

How SparseSet works

A SparseSet holds two Uint32Arrays and a live count n:

• dense (capacity-sized) -- dense[i] is the i-th member key, packed into [0, n) in insertion order. This is what iteration walks.
• sparse (universe-sized) -- sparse[k] is the index into dense where key k lives. It is only VALID when the cross-check holds.

Membership is a cross-checked double indirection:

has(k)  ==  sparse[k] < n  &&  dense[sparse[k]] === k

That second half is the whole trick. sparse is never cleared, so it is full of stale pointers from previous fills. A stale pointer either aims past the live prefix (sparse[k] >= n, rejected) or into a slot now holding a different key (dense[sparse[k]] !== k, rejected). Either way, a key that is not a member reads as absent -- so:

• clear() is n = 0. Every prior key now fails sparse[k] < n. No store is touched; clearing 10M entries is O(1).
• add(k) appends: dense[n] = k; sparse[k] = n; n++. Idempotent because the cross-check catches a re-add.
• delete(k) fills the hole with the last live entry so dense stays packed: move dense[n-1] into dense[sparse[k]], fix that moved key's sparse back-pointer, then n--. O(1), no shifting.

Because dense is packed and contiguous, iteration is a linear scan over [0, n) -- cache-friendly and alloc-free. Because sparse is a flat typed array indexed by the key, lookup is two dependent loads with no hashing and no pointer chase. That layout is why the witness stays flat where a hash set decays.

The cost of the constant is memory: sparse is sized to the whole universe (4 bytes per possible key), whether or not a key is ever added. SparseSet is the right tool when the universe is a known, bounded integer range (entity ids, node indices, small key spaces), not for sparse keys over a huge or unbounded domain.

API reference

SparseSet

new SparseSet(universe: number, capacity?: number)

• universe -- the exclusive key ceiling; valid keys are integers in [0, universe). An integer in [1, 2^32]. Sizes the sparse array.
• capacity -- the maximum number of live members at once. An integer in [1, universe]. Defaults to universe. Sizes the dense array.

The constructor validates both up front and throws a [lite-o1]-tagged RangeError on a non-integer or out-of-range argument (fail closed). All scratch is allocated here; every method afterward allocates nothing.

add(k: number): this        // insert (idempotent); throws on a bad key or when full
has(k: number): boolean     // membership; a bad key is absent, never a throw
delete(k: number): boolean  // remove via swap-the-last; true iff k was present
clear(): void               // O(1) empty; zeroes no store
forEach(fn: (key: number, set: SparseSet) => void): void   // insertion order, alloc-free
[Symbol.iterator](): IterableIterator<number>              // insertion order
get size: number            // live member count
get capacity: number        // max live members as constructed

• add(k) throws [lite-o1] key out of universe ... for a key that is not an integer in [0, universe) (this includes -1, 1.5, NaN, null, and k === universe), and [lite-o1] SparseSet full ... when a NEW key would exceed capacity. Re-adding a present key when full is a no-op, never a throw.
• has(k) / delete(k) never throw: a bad key is simply absent (has returns false, delete returns false). null is rejected as null, never coerced to key 0 -- has(null) is false even when 0 is a member.

Constants

| Constant | Value | Meaning | | ---------- | --------- | -------------------------------------------------- | | VERSION | '1.3.0' | Package version string. |

Contract bounds (validated, not exported):

| Bound | Rule | | ------------------- | ------------------------------------------------ | | SparseSet universe| integer in [1, 2^32] | | SparseSet capacity| integer in [1, universe], default universe | | SparseSet valid key | integer in [0, universe) | | RingDeque capacity| integer in [1, 2^31], rounded up to a power of two | | RingDeque value | typeof 'number' and not NaN (+/-Infinity OK) | | UnionFind n | integer in [1, 2^32-1] | | UnionFind element | integer in [0, n) | | MonoDeque capacity| integer in [1, 2^31], rounded up to a power of two | | MonoDeque kind | 'min' or 'max' (frozen at construction) | | MonoDeque value | typeof 'number' and not NaN (+/-Infinity OK) | | MonoDeque seq ceiling | MAX_SEQ = 2^53 (push past it throws) | | MinStack capacity | integer in [1, 2^31], EXACT (NOT rounded) | | MinStack kind | 'min' or 'max' (frozen at construction) | | MinStack value | typeof 'number' and not NaN (+/-Infinity OK) | | RandomSet universe| integer in [1, 2^32] | | RandomSet capacity| integer in [1, universe], default universe | | RandomSet seed | any integer (coerced to uint32), default 0x9e3779b1 | | RandomSet valid key | integer in [0, universe) | | FreqO1 universe | integer in [1, 2^32] | | FreqO1 capacity | integer in [1, universe], default universe | | FreqO1 maxFreq | integer in [1, 2^32-2], default 2^32-2 | | FreqO1 valid key | integer in [0, universe) | | BucketQueue universe | integer in [1, 2^32] | | BucketQueue ceiling | integer in [0, 2^31-1] (inclusive max priority; space O(ceiling)) | | BucketQueue capacity | integer in [1, universe], default universe | | BucketQueue valid key | integer in [0, universe) | | BucketQueue valid priority | integer in [0, ceiling], and >= cursor (monotone) | | TimerWheel universe | integer in [1, 2^32] | | TimerWheel slots | integer in [1, 2^31], rounded up to a power of two (delay range O(slots)) | | TimerWheel capacity | integer in [1, universe], default universe | | TimerWheel valid id | integer in [0, universe) | | TimerWheel valid delay | integer in [0, slots-1] | | TimerWheel now ceiling | TW_MAX_TICK = 2^53 (advance past it throws) | | HierarchicalTimerWheel universe | integer in [1, 2^32] | | HierarchicalTimerWheel capacity | integer in [1, universe], default universe | | HierarchicalTimerWheel valid id | integer in [0, universe) | | HierarchicalTimerWheel valid delay | integer in [0, 2^26) (maxDelay = 2^26 - 1; delay range O(1) via 4 levels) | | HierarchicalTimerWheel now ceiling | 2^53 (advance past it throws) | | RingLog capacity | integer in [1, 2^31], rounded up to a power of two | | RingLog value | typeof 'number' and not NaN (+/-Infinity OK) | | RingLog get(i) index | integer in [0, size) (oldest-relative; out of range -> undefined) | | CuckooMap capacity| integer in [1, 2^30], rounded up so the request fits under the 0.90 load ceiling (getter reports the usable capacity) | | CuckooMap seed | OPTIONAL uint32 (integer in [0, 2^32)); defaults deterministically from the table size | | CuckooMap valid key | safe integer, |k| <= 2^53 (Number.isSafeInteger) -- 0 and negatives legal, -0 aliases 0 | | CuckooMap value | typeof 'number' and not NaN (+/-Infinity OK) | | SparseTable source| a real Array of numbers or a numeric TypedArray, length integer in [1, 2^26] (COPIED at build; immutable) | | SparseTable element | typeof 'number' and not NaN (+/-Infinity OK) -- a bad element throws at construction, byte-identical no-op | | SparseTable kind | 'min' or 'max', frozen at construction | | SparseTable query(l, r) | l, r integers in [0, length) with l <= r (else -> undefined, never throws) |

The O(1) Witness

The analytical anchor: ops/ms that stays flat as n grows is the proof of O(1). npm run witness fills a SparseSet of size n and times a fixed batch (1e6) of the membership op at each n in a geometric sweep [1e3, 1e4, 1e5, 1e6, 1e7], with two warm-ups and the median of 9 reps to reject a loaded-runner stall. It runs a native Set foil on the identical key sweep -- the thing a working programmer reaches for by default -- and reports both curves plus a flatness ratio (opsPerMs(last) / opsPerMs(first)):

  n         SparseSet ops/ms   Set ops/ms   ratio
  --------  ----------------   ----------   -----
  1e3             ~378483.23    ~169062.91   ~2.24x   <- L1 micro-case (shown, not gated)
  1e4             ~401472.12    ~114038.09   ~3.52x
  1e6             ~404626.17     ~44210.86   ~9.15x
  1e7             ~402030.25     ~19032.79  ~21.12x   <- memory wall (shown, not gated)

  SparseSet flatness (n=1e4..1e6):  ~1.00   (gate >= 0.70)
  Set foil  flatness (n=1e4..1e6):  ~0.39   (gate <= 0.55)
  min SparseSet/Set ratio (n=1e4..1e6): ~3.5x   (gate >= 1.50x)

SparseSet's contiguous typed-array layout streams flat -- its ops/ms barely moves from n=1e3 to n=1e7 -- while the Set's hash table scatters across an ever-larger backing store until each lookup is a cache miss, so its ops/ms falls ~9x across the sweep and SparseSet's lead grows with n (2x to 21x). Honest gate domain: ops/ms is a hardware signal, so the two unrepresentative endpoints are displayed but excluded from the gate -- n=1e3 is a pure-L1 micro-case that turbo-spikes (an unstable flatness denominator), and n=1e7 is the memory wall, where the 8*n-byte arrays exceed cache and you measure DRAM latency rather than the algorithm. The gate is computed over the steady, cache-resident window 1e4 <= n <= 1e6 and fails the build if SparseSet flatness drops below 0.70, the foil fails to decay below 0.55, or the ratio falls under 1.5x at any gated size -- so a regression that quietly ruins the constant fails as loudly as a broken test. (Absolute ops/ms is machine-specific; reproduce on your own hardware.)

RingDeque

The second member: a fixed-capacity double-ended queue of numbers over one circular Float64Array. Push and pop at BOTH ends are O(1) worst-case and allocate zero bytes -- the zero-GC answer to the Array.prototype.shift / unshift O(n) trap, where every element re-indexes on each end operation.

import { RingDeque } from '@zakkster/lite-o1';

// Requested 1000 -> capacity rounds UP to the next power of two (1024).
const q = new RingDeque(1000);
q.capacity;              // -> 1024

q.pushBack(1);
q.pushBack(2);
q.pushFront(0);         // [0, 1, 2]

q.peekFront();          // -> 0
q.peekBack();           // -> 2

q.popFront();           // -> 0  (FIFO with pushBack)
q.popBack();            // -> 2  (LIFO with pushBack)
q.size;                 // -> 1

for (const v of q) console.log(v);   // 1   (front -> back, alloc-free)

q.pushBack(Infinity);   // OK: +/-Infinity are clean numbers
// q.pushBack(NaN);     // throws [lite-o1]: NaN is rejected
// q.pushBack('3');     // throws [lite-o1]: not a number

q.clear();              // O(1): resets head + count, touches NO store
q.popFront();           // -> undefined  (empty never throws)

Every op is O(1) worst-case and zero-allocation after construction. pop* / peek* on an empty ring return undefined (never throw); the sentinel is unambiguous because every stored value is a real number. A push on a full ring throws a [lite-o1] error as a byte-identical no-op -- fail closed, no silent drop or overwrite. The witness harness proves RingDeque's FIFO churn holds its ops/ms while Array.prototype.shift collapses as n grows.

How RingDeque works

A RingDeque holds one Float64Array (the ring), a head (the index of the front element), and a count (how many elements are live). The physical slot for logical offset i from the front is:

store[(head + i) & MASK]      MASK = capacity - 1

Because capacity is a power of two, the modulo that wraps the index is a single bitwise & MASK -- no branch, no division. The requested capacity rounds UP to the next power of two (so new RingDeque(1000) gives capacity 1024), and the capacity getter reports that rounded value.

• pushBack(v) writes store[(head + count) & MASK] = v; count++.
• pushFront(v) moves the head back one slot (head = (head - 1) & MASK, where int32 -1 & MASK === MASK wraps off slot 0 to the top), writes store[head] = v, then count++.
• popFront() reads store[head], advances head = (head + 1) & MASK, count--.
• popBack() does count-- and reads store[(head + count) & MASK].

Using head + count (not a head/tail pair) makes "full" a single test (count === capacity) and "empty" a single test (count === 0), with no ambiguous head === tail state to disambiguate.

• clear() is head = 0; count = 0. The store is left byte-identical. The stale numbers are unreachable (every read is bounded by count) and retain no references (they are numbers), so there is nothing to zero -- clearing a full ring costs the same as clearing an empty one. This is the same teachable gem as SparseSet's cross-checked clear.

The cost of the constant is the value domain: a Float64Array holds numbers only. To queue objects, queue their integer handles / indices and keep the payloads in a parallel column or @zakkster/lite-arena.

RingDeque API reference

new RingDeque(capacity: number)   // capacity rounds up to the next power of two

• capacity -- the requested maximum number of live elements; an integer in [1, 2^31]. Rounded UP to the next power of two (>= requested); the capacity getter reports the rounded value. The constructor throws a [lite-o1]-tagged RangeError on a non-integer, out-of-range, or non-number argument (typeof-guarded before any coercion, so a Symbol / BigInt fails closed rather than crashing raw).

pushFront(v: number): this        // push at the front; throws when full / on a bad value
pushBack(v: number): this         // push at the back;  throws when full / on a bad value
popFront(): number | undefined    // remove + return the front; undefined on empty
popBack(): number | undefined     // remove + return the back;  undefined on empty
peekFront(): number | undefined   // read the front; undefined on empty
peekBack(): number | undefined    // read the back;  undefined on empty
clear(): void                     // O(1) empty; zeroes no store
forEach(fn: (value: number, index: number, deque: RingDeque) => void): void  // front -> back
[Symbol.iterator](): IterableIterator<number>                                 // front -> back
get size: number                  // live element count
get capacity: number              // max elements (power-of-two, rounded up)

• pushFront(v) / pushBack(v) throw [lite-o1] RingDeque full ... when the ring is at capacity (a byte-identical no-op -- store + head + count unchanged), and [lite-o1] RingDeque value must be a number ... on a value that is not a clean number. A value is clean iff typeof v === 'number' AND it is not NaN; +Infinity / -Infinity are accepted, while null, undefined, strings, Symbols, BigInts, objects, and NaN are rejected. The typeof guard runs first so a Symbol / BigInt never reaches arithmetic.
• popFront() / popBack() / peekFront() / peekBack() never throw: an empty ring returns undefined. Because every stored value is a real number, undefined unambiguously means "empty".

Reach for RingDeque when you need FIFO / LIFO / sliding-window push-pop at O(1) with zero per-op allocation over a bounded numeric domain (ring buffers, bounded work queues, rolling windows). Avoid it when you need to queue non-numbers (queue their handles instead), or need the queue to grow past a bound you cannot set up front (it fails closed on a full push rather than resizing). See GUIDE.md for the full reach-for / avoid / measure-it.

UnionFind

The third member: a disjoint-set (union-find) forest over two Uint32Array columns (parent + subtree size), fixed element count n. find / union / connected / componentSize are near-O(1) amortized (inverse Ackermann alpha(n) <= ~4) and allocate zero bytes -- the family's amortized-honesty member, and the zero-GC answer to a naive disjoint-set whose find degrades to O(n) as its trees deepen.

import { UnionFind } from '@zakkster/lite-o1';

// A forest of 10 singletons: elements 0..9, each its own component.
const uf = new UnionFind(10);
uf.count;               // -> 10  (live component count, maintained in O(1))
uf.capacity;            // -> 10  (the fixed universe n)

uf.union(0, 1);         // -> true  (a real merge)
uf.union(1, 2);         // -> true  (2 joins {0,1})
uf.union(0, 2);         // -> false (already connected -- no-op)
uf.count;               // -> 8

uf.connected(0, 2);     // -> true
uf.connected(0, 5);     // -> false
uf.componentSize(1);    // -> 3   ({0,1,2})
uf.find(2);             // -> the component root (path-halved on the way)

// uf.find(10);         // throws [lite-o1]: element out of [0, 10)
// uf.find(1.5);        // throws [lite-o1]: not an integer element
// uf.union(0, Symbol());// throws [lite-o1]: fail-closed, never a raw TypeError

uf.reset();             // O(n): re-singleton every element (the honest exception)
uf.count;               // -> 10

Every query / merge above is O(1)-amortized and zero-allocation after construction. Fail closed: a bad element (non-integer, out of [0, n), NaN, null, a Symbol, a BigInt) throws a [lite-o1] error -- never a raw TypeError, and null is never coerced to element 0. The witness harness proves UnionFind's amortized find holds its ops/ms while a naive disjoint-set (no path compression, no union-by-size) collapses as n grows.

How UnionFind works

A UnionFind holds two Uint32Arrays and a live component count:

• parent -- parent[i] is i's parent in its tree; i is a ROOT iff parent[i] === i. Two elements are in the same component iff they reach the same root.
• size -- size[root] is the number of elements in that tree. It drives union-by-size AND answers componentSize for free.

The two near-constant tricks are both applied:

• Path halving on find. Walking x up to its root, every other node is repointed at its grandparent:

  while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }

  The tree flattens as a side effect of querying it. This is ITERATIVE -- no recursion, no stack array -- so the hot body allocates nothing (full compression would need a second pass or a stack; halving gets the same amortized bound in one alloc-free pass).

• Union by size. union attaches the smaller-rooted tree under the larger (if (size[ra] < size[rb]) swap; parent[rb] = ra; size[ra] += size[rb]), so a tree never grows taller than log n before halving flattens it. count is decremented exactly once per REAL merge (never a scan), and union returns true iff it actually merged.

Together these bound any single op at O(alpha(n)) AMORTIZED. Honesty: a single find is NOT worst-case O(1) -- an adversarial chain that has not yet been halved is O(depth). The guarantee is amortized alpha(n) (effectively a small constant), and the witness proves the amortized throughput stays flat while a naive disjoint-set foil (no compression, no union-by-size -> a degenerate chain) decays toward O(n).

reset() (re-singleton everything) and forEachRoots(fn) (visit every root) are the O(n) exceptions: there is no cross-check trick to make them O(1) because every element's parent must actually be read / rewritten. They still allocate nothing (a single bulk pass over the existing arrays), but they are bulk ops, not per-op hot paths -- reset() is named reset(), not clear(), precisely to flag that different cost class.

The cost of the constant is memory: two n-sized Uint32Array columns, allocated eagerly at construction. UnionFind is the right tool when elements are a known, bounded integer range and you merge groups incrementally -- not for a huge / unbounded or non-integer element domain.

UnionFind API reference

new UnionFind(n: number)   // n elements [0, n); n an integer in [1, 2^32-1]

• n -- the fixed element count; valid elements are integers in [0, n). An integer in [1, 2^32-1]. Sizes both Uint32Array columns. The constructor throws a [lite-o1]-tagged RangeError on a non-integer / out-of-range / non-number argument (Number.isInteger never coerces, so a Symbol / BigInt fails closed rather than crashing raw). All scratch is allocated here; every method afterward allocates nothing (except roots()).

find(x: number): number              // component root; O(1)-amortized (path halving)
union(a: number, b: number): boolean // merge (union by size); true iff a real merge
connected(a: number, b: number): boolean // same-component test; O(1)-amortized
componentSize(x: number): number     // size of x's component; O(1)-amortized
reset(): void                        // O(n): re-singleton every element (allocates nothing)
forEachRoots(fn: (root: number, uf: UnionFind) => void): void  // O(n) alloc-free scan
roots(): IterableIterator<number>    // O(n) scan; ALLOCATES a generator per protocol
get count: number                    // live component count (maintained in O(1))
get capacity: number                 // the fixed element universe n

• find / union / connected / componentSize throw [lite-o1] node out of range [0, n): ... for an element that is not an integer in [0, n) (this includes -1, 1.5, NaN, null, x === n, a Symbol, and a BigInt). The typeof guard runs BEFORE the coercing >>>, so a Symbol / BigInt never reaches arithmetic. null is rejected as null, never coerced to element 0.
• union(a, b) returns true iff a and b were in DIFFERENT components (a real merge, count drops by one); false if already joined (a no-op). union(x, x) is always false.
• reset() / forEachRoots() / roots() are O(n), NOT per-op hot paths. reset() and forEachRoots() allocate nothing; roots() allocates a generator + a {value, done} per step by protocol -- use forEachRoots for the alloc-free scan. There is no public size getter (it would collide with the live-element-count meaning size has on the other members); use count (live components) and capacity (fixed universe).

Reach for UnionFind when you track "which things are in the same group" over a fixed integer element set and merge groups incrementally (connected components, Kruskal MST, percolation, cycle detection, equivalence classes) at near-constant amortized cost with zero per-op allocation. Avoid it when you need to SPLIT / un-merge (union-find is merge-only; reset() re-singletons everything in O(n)), your elements are not a bounded integer range, or you are on a strict per-op WORST-CASE budget (a single find is amortized alpha(n), not worst-case O(1)). See GUIDE.md for the full reach-for / avoid / measure-it.

MonoDeque

The fourth member: a monotonic deque for sliding-window minimum / maximum over two parallel Float64Array columns (value + monotonic seq). push / evictOlderThan are O(1) amortized and allocate zero bytes -- the family's second amortized-honesty member, and the zero-GC answer to the naive rolling-extreme that rescans the whole window each step (O(W) per element).

import { MonoDeque } from '@zakkster/lite-o1';

// A sliding-window MINIMUM over a numeric stream; window width W = 3.
const lo = new MonoDeque(8, 'min');   // kind frozen; capacity rounds up (8 stays 8)
const W = 3;

const stream = [5, 3, 8, 1, 9, 2];
for (const x of stream) {
  const seq = lo.push(x);        // returns this element's monotonic seq
  lo.evictOlderThan(seq - W);    // slide: drop everything older than the last W
  console.log('min of last', W, '=', lo.value());
}
// -> 5, 3, 3, 1, 1, 1

lo.kind;                 // -> 'min'  (frozen at construction)
lo.value();              // -> 1      (current window minimum, O(1))
lo.frontSeq();           // -> the seq of that minimum

// lo.push(NaN);         // throws [lite-o1]: NaN is rejected (+/-Infinity accepted)
// lo.push(Symbol());    // throws [lite-o1]: fail-closed, never a raw TypeError

lo.clear();              // O(1): resets head + count + the seq counter (seq restarts at 0)
lo.value();              // -> undefined  (empty never throws)

Every push / evictOlderThan is O(1)-amortized and zero-allocation after construction; value() / frontSeq() are O(1) front reads that return undefined on empty (never throw). A push on a full ring throws a [lite-o1] error as a byte-identical no-op -- fail closed, no silent drop. For BOTH the min and the max of the same stream, run two MonoDeques (kind is frozen per instance). The witness harness proves MonoDeque's amortized push holds its ops/ms while a full-window rescan collapses as the window grows:

  W         MonoDeque ops/ms   naive ops/ms   ratio
  --------  ----------------   ------------   -----
  1e3             ~53420.94       ~3378.68   ~15.81x
  1e4             ~48449.81        ~254.91  ~190.06x
  1e5             ~51320.65         ~30.12 ~1703.67x

  MonoDeque flatness (last/first): ~0.96   (gate >= 0.70)
  naive foil flatness (last/first): ~0.01   (gate <= 0.55)
  min MonoDeque/naive ratio:        ~15.81x  (gate >= 1.50x)
  MAX single push (O(W) pop-storm, W=1e5): ~0.043 ms   vs typical O(1) push: ~0.0002 ms   (amortized, not worst-case)

MonoDeque's amortized push streams flat across the window sweep while the naive rescan collapses ~100x per order of magnitude (its ratio blows from ~16x to ~1700x). The MAX-single-op line is the amortized-honesty bar: a deliberate O(W) pop-storm is a tall ~0.043 ms spike beside the ~0.0002 ms typical push -- a single push is worst-case O(k), amortized O(1), and the witness shows both. (Absolute ops/ms is machine-specific; reproduce on your own hardware.)

How MonoDeque works

A MonoDeque holds two parallel Float64Arrays in a head + count power-of-two ring (the same substrate as RingDeque): a value column and a seq column, where seq is a monotonically increasing insertion number.

The monotone invariant is the whole trick. For a 'min' deque, push(v) first pops every back entry whose value is >= v:

while (count > 0 && backValue >= v) count--;   // drop dominated entries

Any entry >= v can never again be the window minimum while v is in the window (v is smaller and stays at least as long), so it is redundant -- dropped. What remains is STRICTLY INCREASING front -> back, so the front is always the window minimum and value() is a single O(1) read. ('max' is the mirror: pop while <= v, strictly decreasing, front is the maximum.) The seqs stay strictly increasing front -> back because insertion order is FIFO.

• push(v) assigns seq = nextSeq++, pops the dominated back run, appends (v, seq), and returns seq.
• evictOlderThan(seq) drops front entries whose stored seq <= the given seq -- the caller's window slide.
• value() / frontSeq() read the front (value, seq); undefined on empty.
• clear() is head = 0; count = 0; nextSeq = 0. The store is left byte-identical (numbers retain no references, so there is nothing to zero) and the seq counter restarts.

The window is caller-driven -- a primitive, not a policy. The deque owns the monotone invariant; the caller owns which seqs are still in the window. evictOlderThan(seq - W) gives a count window; evicting by a stored timestamp seq gives a time window; one MonoDeque serves any rule without baking in a policy it cannot know.

Amortized, not worst-case. A single push can pop a whole dominated run -- O(k) in the worst case. But every element is pushed once and popped at most once, so the pops charged across a run of pushes total at most that run's length: amortized O(1). The witness proves it against a naive O(W)-window-rescan foil AND prints the MAX single-op time (a deliberate O(W) pop-storm) beside a typical O(1) push, so a hidden worst-case spike shows as a tall bar even though the amortized line stays flat.

The cost of the constant is the value domain (numbers only, like RingDeque) and a seq ceiling: seqs live in a Float64Array slot, so a push whose seq would pass MAX_SEQ = 2^53 throws rather than lose integer precision -- clear() (which resets the counter) is the way to reuse a very long-lived instance.

MonoDeque API reference

new MonoDeque(capacity: number, kind: 'min' | 'max')   // capacity rounds up to a power of two

• capacity -- the maximum number of simultaneously-live entries; an integer in [1, 2^31]. Rounded UP to the next power of two; the capacity getter reports the rounded value. The constructor throws a [lite-o1]-tagged RangeError on a non-integer / out-of-range / non-number argument (typeof-guarded before any coercion).
• kind -- 'min' or 'max', FROZEN at construction (one monotone invariant per instance). Anything else throws [lite-o1].

push(v: number): number              // append (assign seq); amortized O(1); throws when full / bad value / seq > 2^53
evictOlderThan(seq: number): void    // drop front entries with stored seq <= seq; amortized O(1)
value(): number | undefined          // current window extreme (front value); undefined on empty
frontSeq(): number | undefined       // seq of the current extreme; undefined on empty
clear(): void                        // O(1) empty; resets head + count + the seq counter; zeroes no store
forEach(fn: (value: number, seq: number, deque: MonoDeque) => void): void  // front -> back, alloc-free
[Symbol.iterator](): IterableIterator<[number, number]>                    // front -> back [value, seq] tuples
get kind: 'min' | 'max'              // the frozen monotone invariant
get size: number                     // live entry count
get capacity: number                 // max simultaneously-live entries (power-of-two, rounded up)

• push(v) throws [lite-o1] MonoDeque full ... when the ring is at capacity (a byte-identical no-op -- both stores + head + count + the seq counter unchanged), [lite-o1] MonoDeque value must be a number ... on a value that is not a clean number (typeof v === 'number' AND not NaN; +/-Infinity accepted; the typeof guard runs first so a Symbol / BigInt never reaches arithmetic), and [lite-o1] MonoDeque seq ceiling 2^53 reached ... past MAX_SEQ. It returns the seq it assigned.
• evictOlderThan(seq) throws [lite-o1] on a non-number / NaN seq (typeof-guarded). A threshold below the oldest live seq (or negative) is a no-op.
• value() / frontSeq() never throw: an empty deque returns undefined. Because every stored value is a real number, undefined unambiguously means "empty".

Reach for MonoDeque when you need the MIN or MAX of a sliding window over a numeric stream at O(1) amortized with zero per-op allocation (rolling extrema, envelope / peak detection, stock-span, bounded-window statistics) and you were about to rescan the window each step. Avoid it when you need BOTH extremes of one window (run two instances -- kind is frozen), arbitrary order statistics or a window SUM (a monotonic deque only answers the extreme), or you are on a strict per-op WORST-CASE budget (a single push is O(k), amortized O(1)). See GUIDE.md for the full reach-for / avoid / measure-it.

MinStack

The fifth member: a fixed-capacity numeric stack that also reports the current minimum or maximum of every live element in WORST-CASE O(1) -- no amortization asterisk -- over two parallel Float64Array columns (value + a running-extreme prefix). Where MonoDeque answers a moving WINDOW, MinStack answers the whole live STACK, and it does so with a strict per-op bound: push never pops a run, so there is no worst-case spike to hide.

import { MinStack } from '@zakkster/lite-o1';

// A LIFO stack of numbers that always knows its current minimum, in O(1).
const s = new MinStack(1000, 'min');   // kind frozen; capacity EXACT (stays 1000)

s.push(5);   s.extreme();   // -> 5
s.push(3);   s.extreme();   // -> 3
s.push(9);   s.extreme();   // -> 3   (9 does not beat 3)
s.push(1);   s.extreme();   // -> 1

s.peek();                   // -> 1   (the top value)
s.pop();     s.extreme();   // -> 3   (popped 1; the prior minimum is restored, O(1))
s.pop();     s.extreme();   // -> 3   (popped 9)

s.kind;                     // -> 'min'  (frozen at construction)
s.size;                     // -> 2

// s.push(NaN);             // throws [lite-o1]: NaN is rejected (+/-Infinity accepted)
// s.push(Symbol());        // throws [lite-o1]: fail-closed, never a raw TypeError

s.clear();                  // O(1): resets the top pointer (touches no store)
s.extreme();                // -> undefined  (empty never throws)

Every push / pop / peek / extreme is WORST-CASE O(1) and zero-allocation after construction; pop() / peek() / extreme() return undefined on empty (never throw). A push on a full stack throws a [lite-o1] error as a byte-identical no-op -- fail closed, no silent drop. For BOTH the min and the max of the same stack, run two MinStacks (kind is frozen per instance). The witness harness proves MinStack's extreme() holds its ops/ms while a full-stack rescan collapses as the stack grows:

  depth     MinStack ops/ms    naive ops/ms   ratio
  --------  ----------------   ------------   -----
  1e3            ~154047.60       ~2458.17   ~62.67x   <- L1 micro-case (shown, not gated)
  1e4            ~127020.42        ~268.89  ~472.39x
  1e5            ~126057.05         ~20.83 ~6051.49x

  MinStack flatness (depth >= 1e4): ~1.00   (gate >= 0.70)
  naive foil flatness (last/first): ~0.10   (gate <= 0.55)
  min MinStack/naive ratio:         ~425x   (gate >= 1.50x)

MinStack's extreme() streams flat across the depth sweep while the naive rescan collapses ~10x per order of magnitude. The feed is strictly DECREASING -- every push rewrites the running extreme, MinStack's own worst case -- and the line still stays flat, because a rewrite is the same one compare + two writes as a carry-forward. There is deliberately NO MAX-single-op line here (unlike MonoDeque): MinStack never pops a run, so there is no amortized pop-storm to expose -- the flat line IS the worst-case claim. The depth=1e3 point is a pure-L1 micro-case that turbo-spikes as the flatness denominator, so it is displayed but excluded from the gate (the same steady-window discipline SparseSet uses; the 0.70 floor is unchanged, only the domain is pinned). (Absolute ops/ms is machine-specific; reproduce on your own hardware.)

How MinStack works

A MinStack holds two parallel Float64Arrays and a top pointer n: a value column and an ext column, where ext[i] is the extreme (min or max, per `ki