pub struct IndexedBits<T: Deref<Target = [u8]>> { /* fields omitted */ }
Bits stored with extra index data for fast rank and select.
Build the index for a sequence of bits.
This is an expensive operation which will examine
all of the data input.
Build an indexed bitvector from some bytes.
This is the same as using Bits::from_bytes
and IndexedBits::build_from_bits
Discard the index and get the original bit sequence storage back.
The number of bits in the storage.
Get the byte at a specific index.
Returns None
for out-of-bounds.
use indexed_bitvec::IndexedBits;
let bits = IndexedBits::build_from_bytes(vec![0xFE, 0xFE], 15).unwrap();
assert_eq!(bits.get(0), Some(true));
assert_eq!(bits.get(7), Some(false));
assert_eq!(bits.get(14), Some(true));
assert_eq!(bits.get(15), None);
Count the set bits (fast O(1)).
use indexed_bitvec::IndexedBits;
let bits = IndexedBits::build_from_bytes(vec![0xFE, 0xFE], 15).unwrap();
assert_eq!(bits.count_ones(), 14);
assert_eq!(bits.count_zeros(), 1);
assert_eq!(bits.count_ones() + bits.count_zeros(), bits.len());
Count the unset bits (fast O(1)).
use indexed_bitvec::IndexedBits;
let bits = IndexedBits::build_from_bytes(vec![0xFE, 0xFE], 15).unwrap();
assert_eq!(bits.count_ones(), 14);
assert_eq!(bits.count_zeros(), 1);
assert_eq!(bits.count_ones() + bits.count_zeros(), bits.len());
Count the set bits before a position in the bits (O(1)).
Returns None
it the index is out of bounds.
use indexed_bitvec::IndexedBits;
let bits = IndexedBits::build_from_bytes(vec![0xFE, 0xFE], 15).unwrap();
assert!((0..bits.len()).all(|idx|
bits.rank_ones(idx).unwrap()
+ bits.rank_zeros(idx).unwrap()
== (idx as u64)));
assert_eq!(bits.rank_ones(7), Some(7));
assert_eq!(bits.rank_zeros(7), Some(0));
assert_eq!(bits.rank_ones(8), Some(7));
assert_eq!(bits.rank_zeros(8), Some(1));
assert_eq!(bits.rank_ones(9), Some(8));
assert_eq!(bits.rank_zeros(9), Some(1));
assert_eq!(bits.rank_ones(15), None);
Count the unset bits before a position in the bits (O(1)).
Returns None
it the index is out of bounds.
use indexed_bitvec::IndexedBits;
let bits = IndexedBits::build_from_bytes(vec![0xFE, 0xFE], 15).unwrap();
assert!((0..bits.len()).all(|idx|
bits.rank_ones(idx).unwrap()
+ bits.rank_zeros(idx).unwrap()
== (idx as u64)));
assert_eq!(bits.rank_ones(7), Some(7));
assert_eq!(bits.rank_zeros(7), Some(0));
assert_eq!(bits.rank_ones(8), Some(7));
assert_eq!(bits.rank_zeros(8), Some(1));
assert_eq!(bits.rank_ones(9), Some(8));
assert_eq!(bits.rank_zeros(9), Some(1));
assert_eq!(bits.rank_ones(15), None);
Find the position of a set bit by its rank (O(log n)).
Returns None
if no suitable bit is found. It is
always the case otherwise that rank_ones(result) == Some(target_rank)
and get(result) == Some(true)
.
use indexed_bitvec::IndexedBits;
let bits = IndexedBits::build_from_bytes(vec![0xFE, 0xFE], 15).unwrap();
assert_eq!(bits.select_ones(6), Some(6));
assert_eq!(bits.select_ones(7), Some(8));
assert_eq!(bits.select_zeros(0), Some(7));
assert_eq!(bits.select_zeros(1), None);
Find the position of an unset bit by its rank (O(log n)).
Returns None
if no suitable bit is found. It is
always the case otherwise that rank_zeros(result) == Some(target_rank)
and get(result) == Some(false)
.
use indexed_bitvec::IndexedBits;
let bits = IndexedBits::build_from_bytes(vec![0xFE, 0xFE], 15).unwrap();
assert_eq!(bits.select_ones(6), Some(6));
assert_eq!(bits.select_ones(7), Some(8));
assert_eq!(bits.select_zeros(0), Some(7));
assert_eq!(bits.select_zeros(1), None);
Performs copy-assignment from source
. Read more
Formats the value using the given formatter. Read more
Serialize this value into the given Serde serializer. Read more
Deserialize this value from the given Serde deserializer. Read more
Creates owned data from borrowed data, usually by cloning. Read more
🔬 This is a nightly-only experimental API. (toowned_clone_into
)
recently added
Uses borrowed data to replace owned data, usually by cloning. Read more
🔬 This is a nightly-only experimental API. (try_from
)
The type returned in the event of a conversion error.
🔬 This is a nightly-only experimental API. (try_from
)
Immutably borrows from an owned value. Read more
Mutably borrows from an owned value. Read more
🔬 This is a nightly-only experimental API. (try_from
)
The type returned in the event of a conversion error.
🔬 This is a nightly-only experimental API. (try_from
)
🔬 This is a nightly-only experimental API. (get_type_id
)
this method will likely be replaced by an associated static