Skip to content

Succinct Trees
Compare
Choose a tag to compare
@Cydhra Cydhra released this 03 Mar 23:39
· 3 commits to master since this release
1.6.0
b90196c

Balanced Parentheses Trees

The crate has a new data structure: Succinct trees using the well-known BP representation.

  • The tree supports tree navigation to parent, children, and siblings, as well as subtree_size and is_ancestor in O(log n)
  • Further, it supports level-tree navigation (i.e. navigation in level-order), also in O(log n)
  • It supports fast depth-first postorder iteration of the entire tree, or individual subtrees.
  • It exposes the usual internal BP helper functions open, close, enclose, and even fwd_search and bwd_search.
  • It is written to support unbalanced parenthesis expressions without panicking on the navigation functions (iterators excluded).

Sparse RsVec

And another new data structure: A sparse bit vector which supports rank1, select1, and rank0 (among the usual convenience features).
It is a thin wrapper around an Elias-Fano vector.

It can be efficiently constructed from a collection of indices of set bits, or from an existing BitVec.

New APIs

Elias Fano

  • Added a rank(i) and select(i) function (the latter being an alias for get(i))
  • Added a delta(i) function, which returns the delta between entries i - 1 and i.
  • Elias Fano construction is a bit over 5% faster

Bit Vectors

  • Added a function append_bits_unchecked which leaves out some housekeeping that append_bit normally does.
  • Added a function unpack_bits(i, n) as a convenient counterpart to the pack_sequence_* constructors. It is an alias for get_bits(i * n, n), and it has an unchecked version too.

Other Fixes

  • small correction in the documentation for rank and select, clarifying the invariant.
Assets 2
Loading