simple-sds-sbwt 0.3.3

A fork of simple-sds used in the sbwt crate.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

# Simple-sds-sbwt

This is a fork of [simple-sds](https://github.com/jltsiren/simple-sds) used in the sbwt crate.

# Simple succinct data structures

These structures are comparable to those in [SDSL](https://github.com/simongog/sdsl-lite) in performance and scalability.
As the focus is on (relative) simplicity, ugly low-level optimizations are generally avoided.

## Implemented functionality

### Integer vectors

* `RawVector`: A bit array that supports reading, writing, and appending 1-64 bits at a time. Implemented on top of `Vec<u64>`.
  * `RawVectorWriter`: An append-only version of `RawVector` that writes the structure directly to a file.
  * `RawVectorMapper`: An immutable memory-mapped `RawVector`.
* `IntVector`: A bit-packed vector of fixed-width integers implemented on top of `RawVector`. Like `sdsl::int_vector` but also supports stack functionality.
  * `IntVectorWriter`: An append-only version of `IntVector` that writes the structure directly to a file. Like a subset of `sdsl::int_vector_buffer`.
  * `IntVectorMapper`: An immutable memory-mapped `IntVector`.
* `WaveletMatrix`: An immutable vector of fixed-width integers. Similar to `sdsl::wm_int`.
  * Supports `rank()`, `inverse_select()`, `select()`, `predecessor()`, and `successor()` with each item value.
  * Iterators over all items and over items with a specified value.
  * Implemented using a `BitVector` for each level.

### Bitvectors

* `BitVector`: A plain immutable bitvector.
  * Supports `rank()`, `rank_zero()`, `select()`, `select_zero()`, `predecessor()`, and `successor()` queries using optional support structures.
  * Iterators over set bits, unset bits, and all bits.
  * Implemented on top of `RawVector`.
* `RLVector`: A run-length encoded bitvector.
  * Supports `rank()`, `rank_zero()`, `select()`, `select_zero()`, `predecessor()`, and `successor()` queries.
  * Iterators over set bits and all bits.
  * Space-efficient construction with `RLBuilder`.
* `SparseVector`: An Elias-Fano encoded bitvector.
  * Supports `rank()`, `rank_zero()`, `select()`, `select_zero()`, `predecessor()`, and `successor()` queries .
  * Iterators over set bits and all bits.
  * Space-efficient construction with `SparseBuilder`.

## Planned functionality

### Integer vectors

* Mutable memory-mapped vectors.

### Bitvectors

* Versions of `predecessor()` and `successor()` that return values instead of iterators?
* Slice-like functionality based on iterators?

## Notes

* The included `.cargo/config.toml` sets the target CPU to `native`.
* This crate is designed for the x86_64 architecture with the BMI2 instruction set (Intel Haswell / AMD Excavator or later). Some operations may be slow without the POPCNT, LZCNT, TZCNT, and PDEP instructions.
* 64-bit ARM is also supported.
* Unix-like operating system is required for `mmap()`.
* Things may not work if the system is not little-endian or if `usize` is not 64-bit.