succinct

compact data structures with fast rank/select for luau

Usage

local succinct = require(...)
local bv = succinct.bitvector_new(1000000)
succinct.bitvector_set(bv, 500, true)
succinct.bitvector_get(bv, 500) -- true
succinct.bitvector_rank(bv, 501) -- count of 1s before index
succinct.bitvector_select(bv, 1) -- index of nth 1-bit
succinct.bitvector_count(bv) -- total 1s
for idx in succinct.bitvector_iter_ones(bv) do ... end
local sa = succinct.sparse_array_new(100000, 8) -- size, value_size
succinct.sparse_array_set(sa, 50000, some_buffer)
succinct.sparse_array_get(sa, 50000) -- buffer or nil
succinct.sparse_array_has(sa, 50000) -- true
succinct.sparse_array_remove(sa, 50000)
for idx, val in succinct.sparse_array_iter(sa) do ... end
local ef = succinct.elias_fano_encode({10, 50, 100, 500}, 500)
succinct.elias_fano_get(ef, 0) -- 10
succinct.elias_fano_contains(ef, 50) -- true
succinct.elias_fano_next_geq(ef, 75) -- index, value >= 75
for idx, val in succinct.elias_fano_iter(ef) do ... end