Succinct Data Structures for Rust

This library is a very early work in progress. So far we have:

• integer vectors with arbitrary-sized (1- to 64-bit) elements;
• constant-time rank queries; and
• lg lg n-time select queries based on binary search over ranks.

Usage

It’s on crates.io, so you can add

toml [dependencies] succinct = "0.2.0"

to your Cargo.toml and

rust extern crate succinct;

to your crate root.

Credits

• IntVec borrows some implementation techniques from nbitsvec. The main difference is that nbitsvec uses a typenum to put the element size (in bits) as a parameter to the vector type. Also, nbitsvec is likely to be faster.

• Some of the API is inspired by SDSL, a C++ succinct data structures library. It’s much more complete than succinct, and probably more correct and faster too.