Succinct Data Structures for Rust
Rust Other
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
bin
process
src
.VERSION
.gitignore
.travis.yml
Cargo.toml
LICENSE-APACHE
LICENSE-MIT
Makefile
README.md
TODO.md

README.md

Succinct Data Structures for Rust

Build Status Crates.io License: MIT License: Apache 2.0

So far we have:

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

Usage

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

[dependencies]
succinct = "0.4.4"

to your Cargo.toml and

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.