Crate bitm 

bitm is the Rust library by Piotr Beling for bit and bitmap (bit vector) manipulation.

Example

use bitm::{BitAccess, BitVec, Rank, ArrayWithRank101111};

let mut b = Box::<[u64]>::with_zeroed_bits(2048);    // b can store 2048 bits
assert_eq!(b.get_bit(100), false);  // b is zeroed so bit at index 100 is not set  
b.set_bit(100);                     // set the bit
assert_eq!(b.get_bit(100), true);   // now it is set
assert_eq!(b.get_bits(99, 5), 0b00010); // 5 bits, beginning from index 99, should be 00010

let (r, ones) = ArrayWithRank101111::build(b);
assert_eq!(ones, 1);        // one bit is set in b
assert_eq!(r.rank(100), 0); // no ones in the first 100 bits of b
assert_eq!(r.rank(101), 1); // 1 one in the first 101 bits of b
assert_eq!(r.rank(999), 1); // 1 one in the first 999 bits of b

Benchmarks

The performance of some of the structures included in bitm can be tested with the cseq_benchmark crate. Its documentation contains benchmark results.

Structs

AdaptiveCombinedSamplingDensity

Specifies adaptive sampling of select values by CombinedSampling.

BinaryRankSearch

A select strategy for RankSelect101111 that does not introduce any overhead (on space or construction speed) and is based on a binary search over ranks.

BitBIterator

Iterator over indices of bits set to 1 (if B is true) or 0 (if B is false) in slice of u64.

BitIterator

Iterator over bits in slice of u64. It yields true for bit 1 and false for 0.

CombinedSampling

Fast select strategy for RankSelect101111 with about 0.39% space overhead.

ConstCombinedSamplingDensity

Specifies a constant sampling of select values by CombinedSampling, given as the base 2 logarithm (which can be calculated by optimal_combined_sampling function). The actual sampling is 2 times denser, but every second sample sometimes cannot be recorded accurately.

RankSelect101111

Returns number of bits set (to one) in content whose length does not exceeds 8. Returns number of bits set (to one) in content whose length does not exceeds 8. The structure that holds bit vector content and ranks structure that takes no more than 3.125% extra space. It can return the number of ones (or zeros) in first index bits of the content (see rank and rank0 method) in O(1) time. In addition, it supports select queries utilizing binary search over ranks (see BinaryRankSearch) or (optionally, at the cost of extra space overhead; about 0.39% with default settings) combined sampling (which is usually faster; see CombinedSampling).

RankSimple

The structure that holds array of bits content and ranks structure that takes no more than 6.25% extra space. It can returns the number of ones in first index bits of the content (see rank method) in O(1) time. Only content with less than 2³² bit ones is supported. Any type that implements the Deref trait with Target = [u64] can be used as a bit vector.

Traits

BitAccess

The trait that is implemented for the array of u64 and extends it with methods for accessing and modifying single bits or arbitrary fragments consisted of few (up to 63) bits.

BitVec

The trait that is implemented for Box<[u64]> and extends it with bit-oriented constructors.

Rank

Trait for rank queries on bit vector. Rank query returns the number of ones (or zeros) in requested number of the first bits.

Select

Trait implemented by the types that support select (one) queries, i.e. can (quickly) find the position of the n-th one in the bitmap.

Select0

Trait implemented by the types that support select zero queries, i.e. can (quickly) find the position of the n-th zero in the bitmap.

Select0ForRank101111

Trait implemented by strategies for select zeros operations for ArrayWithRank101111.

SelectForRank101111

Trait implemented by strategies for select (ones) operations for ArrayWithRank101111.

Functions

bits_to_store

Calculates the minimal number of bits needed to store values from 0 to given max_value.

ceiling_div

Returns ceil of n/d.

get_bits25^⚠

Read at least 25 bits from ptr, beginning from first_bit.

get_bits57^⚠

Read at least 57 bits from ptr, beginning from first_bit.

init_bits25^⚠

Write at least 25 lowest value bits to ptr buffer, beginning from first_bit, using bit-or operation. Appropriate fragment of buffer should be zeroed.

init_bits57^⚠

Write at least 57 lowest value bits to ptr buffer, beginning from first_bit, using bit-or operation. Appropriate fragment of buffer should be zeroed.

n_lowest_bits

Returns the largest how_many-bit number, i.e. 0..01..1 mask with how_many ones. how_many must be in range [0, 63].

n_lowest_bits_0_64

Returns the largest how_many-bit number, i.e. 0..01..1 mask with how_many ones. how_many must be in range [0, 64].

n_lowest_bits_1_64

Returns the largest how_many-bit number, i.e. 0..01..1 mask with how_many ones. how_many must be in range [1, 64].

optimal_combined_sampling

Calculates such a sampling density of select values that provides an approximately constant space overhead (independent of set/unset bits ratio in the vector) of CombinedSampling.

select64

Returns the position of the rank-th (counting from 0) one in the bit representation of n, i.e. the index of the one with the given rank.

set_bits25^⚠

Write desired number, at most 25 lowest value bits to ptr, beginning from first_bit, using bit-or operation. Before write, appropriate fragment of buffer is zeroed by bit-andn with len_mask (which should be of type 0..01..1, with desired number of bit ones). The most significant bits of value should be zeros.

set_bits57^⚠

Write desired number, at most 57 lowest value bits to ptr, beginning from first_bit, using bit-or operation. Before write, appropriate fragment of buffer is zeroed by bit-andn with len_mask (which should be of type 0..01..1, with desired number of bit ones). The most significant bits of value should be zeros.

Type Aliases

ArrayWithRank101111

Alias for backward compatibility. RankSelect101111 with BinaryRankSearch (which does not introduce a space overhead) for select queries.

ArrayWithRankSimple

Alias for backward compatibility.

BitOnesIterator

Iterator over bits set to 1 in slice of u64.

BitZerosIterator

Iterator over bits set to 0 in slice of u64.