Crate ransel

The ransel library provides a rank/select API to sets of integers originally due to Guy Jacobson:

Jacobson, G., 1989, October. Space-efficient static trees and graphs. In 30th annual symposium on foundations of computer science (pp. 549-554). IEEE Computer Society.

The beauty of the rank/select API is that it allows many useful operations to be performed over sets of integers (or bitmaps, depending on your point of view), without needing to think about the underlying representation of the set. Indeed, there are many different representations that can be used depending on the expected density and size of the set.

Various forms of this API have been presented (notably Simon Gog’s sdsl-lite), with slightly varying definitions. The definition we use is uniformly 0-based.

Given a set S of non-negative integers over a finite domain, we define:

S.size() is the size of the domain, and is at least 1 greater than the largest element in S.

S.count() is the number of elements in S.

S.rank(x) is the number of elements in S that are strictly less than x. rank_1 is an alias, and rank_0 is the complementary definition: the number of non-negative integers less than x that are not in S (n.b. rank_0 and rank_1 may be defined in terms of each other, with `S.rank_0(x) = x - S.rank_1(x)).

S.select(i) is the i-th smallest element in S, with 0 being the index of the first element.

The API is broken down in to components:

The ImpliedSet trait exposes the size and count operations.

The Rank trait exposes rank and its associated operations.

The Select trait exposes select and its associated operations.

Modules

• bitvec
  A bit vector represented as a vector of 64 bit words.
• intvec
  A module for storing unsigned integers of different widths.
• naive_sparse
  A simple sparse set based on an indexed sorted vector.
• rank
  Traits for sets supporting the rank operation.
• select
  Traits for sets supporting the select operation.
• set
  Traits for implicit set operations.
• sorted
  A simple sparse set based on a sorted vector of elements.
• sparse
  A succinct sparse set representation based on the Okanohara & Sadakane 2007 paper: