Crate bitm

source ·
Expand description

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

Structs

  • ArrayWithRankSelect101111
    The structure that holds array of bits 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 about 0.39% extra space overhead) combined sampling (which is usually faster; see CombinedSampling).
  • ArrayWithRankSimple
    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^32 bit ones is supported.
  • BinaryRankSearch
    A select strategy for ArrayWithRankSelect101111 that does not introduce any overhead (on space or construction speed) and is based on a binary search over ranks.
  • BitBIterator
    Iterator over bits set to 1 (if B is true) or 0 (if B is false) in slice of u64.
  • CombinedSampling
    Fast select strategy for ArrayWithRankSelect101111 with about 0.39% space overhead.

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.
  • 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_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].
  • 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.

Type Aliases