### 8 releases (5 breaking)

0.6.1 | May 1, 2019 |
---|---|

0.6.0 | Apr 10, 2019 |

0.5.0 | Apr 10, 2019 |

0.4.0 | Apr 8, 2019 |

0.1.1 | Apr 6, 2019 |

#**667** in Data structures

**87** downloads per month

**MIT/Apache**

105KB

2K
SLoC

# DEPRECATION WARNING

This library is deprecated. This library has succinct bit vector (FID) and LOUDS implementation.

These implementations are split into distinct libraries.

Use fid-rs and louds-rs instead.

# Succinct.rs

Succinct Data Structures library for Rust.

Master API Docs | Released API Docs | Benchmark Results | Changelog

Succinct.rs is a library to provide succinct data structures with *simple API* and *high performance*.

Currently, **Succinct Bit Vector** and **LOUDS (Level-Order Unary Degree Sequence)** are supported.

## Table of Contents

## Quickstart

To use with Succinct.rs, add the following to your

file:`Cargo .toml`

`[``dependencies``]`
`succinct_rs ``=` `"`0.6`"`

### Succinct Bit Vector Usage

`extern` `crate` succinct_rs`;`
`use` `succinct_rs``::``{`BitString`,` SuccinctBitVectorBuilder`}``;`
`//` Construction -------------------------
`//` `01001` built by `from_bit_string()`
`let` bv `=` `SuccinctBitVectorBuilder``::`from_bit_string`(``BitString``::`new`(``"`0100_1`"``)``)``.``build``(``)``;` `//` Tips: BitString::new() ignores '_'.
`//` `01001` built by `from_length()` and `add_bit()`
`let` bv `=` `SuccinctBitVectorBuilder``::`from_length`(``0``)`
`.``add_bit``(``false``)`
`.``add_bit``(``true``)`
`.``add_bit``(``false``)`
`.``add_bit``(``false``)`
`.``add_bit``(``true``)`
`.``build``(``)``;`
`//` Basic operations ---------------------
`assert_eq!``(`bv`.``access``(``0``)``,` `false``)``;` `//` [0]1001; 0th bit is '0' (false)
`assert_eq!``(`bv`.``access``(``1``)``,` `true``)``;` `//` 0[1]001; 1st bit is '1' (true)
`assert_eq!``(`bv`.``access``(``4``)``,` `true``)``;` `//` 0100[1]; 4th bit is '1' (true)
`assert_eq!``(`bv`.``rank``(``0``)``,` `0``)``;` `//` [0]1001; Range [0, 0] has no '1'
`assert_eq!``(`bv`.``rank``(``3``)``,` `1``)``;` `//` [0100]1; Range [0, 3] has 1 '1'
`assert_eq!``(`bv`.``rank``(``4``)``,` `2``)``;` `//` [01001]; Range [0, 4] has 2 '1's
`assert_eq!``(`bv`.``select``(``0``)``,` `Some``(``0``)``)``;` `//` []01001; Minimum i where range [0, i] has 0 '1's is i=0
`assert_eq!``(`bv`.``select``(``1``)``,` `Some``(``1``)``)``;` `//` 0[1]001; Minimum i where range [0, i] has 1 '1's is i=1
`assert_eq!``(`bv`.``select``(``2``)``,` `Some``(``4``)``)``;` `//` 0100[1]; Minimum i where range [0, i] has 2 '1's is i=4
`assert_eq!``(`bv`.``select``(``3``)``,` `None``)``;` `//` There is no i where range [0, i] has 3 '1's
`//` rank0, select0 -----------------------
`assert_eq!``(`bv`.``rank0``(``0``)``,` `1``)``;` `//` [0]1001; Range [0, 0] has no '0'
`assert_eq!``(`bv`.``rank0``(``3``)``,` `3``)``;` `//` [0100]1; Range [0, 3] has 3 '0's
`assert_eq!``(`bv`.``rank0``(``4``)``,` `3``)``;` `//` [01001]; Range [0, 4] has 3 '0's
`assert_eq!``(`bv`.``select0``(``0``)``,` `Some``(``0``)``)``;` `//` []01001; Minimum i where range [0, i] has 0 '0's is i=0
`assert_eq!``(`bv`.``select0``(``1``)``,` `Some``(``0``)``)``;` `//` [0]1001; Minimum i where range [0, i] has 1 '0's is i=0
`assert_eq!``(`bv`.``select0``(``2``)``,` `Some``(``2``)``)``;` `//` 01[0]01; Minimum i where range [0, i] has 2 '0's is i=2
`assert_eq!``(`bv`.``select0``(``4``)``,` `None``)``;` `//` There is no i where range [0, i] has 4 '0's

### LOUDS Usage

`extern` `crate` succinct_rs`;`
`use` `succinct_rs``::``{`BitString`,` LoudsBuilder`,` LoudsIndex`,` LoudsNodeNum`}``;`
`//` Construct from LBS.
`let` bs `=` `BitString``::`new`(``"`10_1110_10_0_1110_0_0_10_110_0_0_0`"``)``;`
`let` louds `=` `LoudsBuilder``::`from_bit_string`(`bs`)``.``build``(``)``;`
`//` LoudsNodeNum <-> LoudsIndex
`let` node8 `=` `LoudsNodeNum``::`new`(``8``)``;`
`let` index11 `=` louds`.``node_num_to_index``(``&`node8`)``;`
`assert_eq!``(`louds`.``index_to_node_num``(``&`index11`)``,` node8`)``;`
`//` Search for children.
`assert_eq!``(`louds`.``parent_to_children``(``&`node8`)``,` `vec!``(``LoudsIndex``::`new`(``17``)``,` `LoudsIndex``::`new`(``18``)``)``)``;`
`//` Search for parent.
`assert_eq!``(`louds`.``child_to_parent``(``&`index11`)``,` `LoudsNodeNum``::`new`(``4``)``)``;`

## Features

**Arbitrary length support with minimum working memory**: Succinct.rs provides virtually*arbitrary size*of data structures. There are carefully designed to use as small memory space as possible.**Simple public APIs**: Each data structures almost only have very basic operations for the data structure.

, for example, has only`succinct`SuccinctBitVector`::`

,`access``(``)`

, and`rank``(``)`

.`select``(``)`**Latest benchmark results are always accessible**: Succinct.rs is continuously benchmarked in Travis CI using Criterion.rs. Graphical benchmark results are published here.

### Succinct Bit Vector Complexity

When the length of a

is `SuccinctBitVector`*N*:

build() | access() | rank() | select() | |
---|---|---|---|---|

Time-complexity | O(N) |
O(1) |
O(1) |
O(log N) |

Space-complexity | N + o(N) |
0 |
O(log N) |
O(log N) |

(Actually,

's time-complexity can be `select``(``)`*O(1)* with complex implementation but Succinct.rs, like many other libraries, uses binary search of

's result).`rank``(``)`

### LOUDS Complexity

When the number of nodes in the tree represented as LOUDS is *N*:

build() | node_num_to_index() | index_to_node_num() | child_to_parent() | parent_to_children() | |
---|---|---|---|---|---|

Time-complexity | O(N) |
O(log N) |
O(1) |
O(1) |
O( max(log N, max num of children a node has) ) |

Space-complexity | N + o(N) |
O(log N) |
O(log N) |
O(log N) |
O( max(log N, max num of children a node has) ) |

(

and `node_num_to_index``(``)`

use rank(). `child_to_parent``(``)`

and `index_to_node_num``(``)`

use select()).`parent_to_children``(``)`

## Versions

Succinct.rs uses semantic versioning.

Since current major version is *0*, minor version update might involve breaking public API change (although it is carefully avoided).

### Rust Version Supports

Succinct.rs is continuously tested with these Rust versions in Travis CI:

- 1.33.0
- Latest stable version
- Beta version
- Nightly build

So it expectedly works with Rust 1.33.0 and any newer versions.

Older versions may also work, but are not tested or guaranteed.

## Roadmap

Succinct.rs has plan to provide these succinct data structures.

- Succinct Bit Vector
**(done)** - LOUDS
**(doing)**- Find out efficient API sets by applying LOUDS to Trie implementation.

- SuRF

## Contributing

Any kind of pull requests are appreciated.

Currently, there are not many rules for contribution. But at least your pull requests must pass Travis CI.

## License

Succinct.rs is dual licensed under the Apache 2.0 license and the MIT license.