PotentialStorage/test/kv/sorted.test.ts

import { describe, expect, it } from 'vitest'
import fc from 'fast-check'
import { ChunkedSortedMap } from '../../src/kv/sorted.js'

const key = fc.string({ unit: fc.constantFrom('a', 'b', 'c', '/', '0'), minLength: 1, maxLength: 4 })
type Op = { t: 'set'; k: string } | { t: 'del'; k: string } | { t: 'bulk'; ks: string[] }
const op: fc.Arbitrary<Op> = fc.oneof(
  { weight: 5, arbitrary: fc.record({ t: fc.constant('set' as const), k: key }) },
  { weight: 3, arbitrary: fc.record({ t: fc.constant('del' as const), k: key }) },
  { weight: 1, arbitrary: fc.record({ t: fc.constant('bulk' as const), ks: fc.array(key, { minLength: 60, maxLength: 120 }) }) },
)

describe('ChunkedSortedMap (model-based, tiny chunks)', () => {
  it('matches a sorted reference for ranges in both directions', () => {
    fc.assert(
      fc.property(fc.array(op, { maxLength: 80 }), fc.integer({ min: 2, max: 6 }), key, key, (ops, chunk, a, b) => {
        const m = new ChunkedSortedMap<number>(chunk)
        const ref = new Map<string, number>()
        ops.forEach((o, i) => {
          if (o.t === 'set') (m.set(o.k, i), ref.set(o.k, i))
          else if (o.t === 'del') expect(m.delete(o.k)).toBe(ref.delete(o.k))
          else (m.setMany(o.ks.map((k) => [k, i])), o.ks.forEach((k) => ref.set(k, i)))
        })
        const sorted = [...ref.keys()].sort()
        const [gte, lt] = a < b ? [a, b] : [b, a]
        expect(m.size).toBe(ref.size)
        expect([...m.keys({})]).toEqual(sorted)
        expect([...m.keys({ reverse: true })]).toEqual([...sorted].reverse())
        expect([...m.keys({ gte, lt })]).toEqual(sorted.filter((k) => k >= gte && k < lt))
        expect([...m.keys({ gte, lt, reverse: true })]).toEqual(sorted.filter((k) => k >= gte && k < lt).reverse())
        for (const k of sorted) expect(m.get(k)).toBe(ref.get(k))
      }),
      { numRuns: 500 },
    )
  })

  it('iterators resume correctly after mutations between steps', () => {
    fc.assert(
      fc.property(
        fc.uniqueArray(key, { minLength: 1, maxLength: 60 }),
        fc.array(fc.tuple(fc.boolean(), key), { maxLength: 40 }),
        fc.boolean(),
        (initial, muts, reverse) => {
          const m = new ChunkedSortedMap<number>(3)
          initial.forEach((k) => m.set(k, 0))
          const live = new Set(initial)
          const seen: string[] = []
          let step = 0
          for (const k of m.keys({ reverse })) {
            seen.push(k)
            const mut = muts[step++]
            if (mut) {
              const [add, mk] = mut
              if (add) (m.set(mk, 1), live.add(mk))
              else (m.delete(mk), live.delete(mk))
            }
          }
          // Strictly monotone, and every key present throughout the iteration was visited.
          for (let i = 1; i < seen.length; i++) expect(reverse ? seen[i]! < seen[i - 1]! : seen[i]! > seen[i - 1]!).toBe(true)
          const stable = initial.filter((k) => !muts.some(([, mk]) => mk === k))
          for (const k of stable) expect(seen).toContain(k)
        },
      ),
      { numRuns: 500 },
    )
  })
})