Struct sucds::bit_vectors::bit_vector::BitVector

pub struct BitVector { /* private fields */ }

Updatable bit vector in a plain format, supporting some utilities such as chunking and predecessor queries.

Examples

use sucds::bit_vectors::BitVector;

let mut bv = BitVector::new();
bv.push_bit(true);
bv.push_bit(false);

assert_eq!(bv.len(), 2);
assert_eq!(bv.get_bit(0), Some(true));

bv.set_bit(0, false)?;
assert_eq!(bv.get_bit(0), Some(false));

Credits

This is a yet another Rust port of succinct::bit_vector.

Implementations

impl BitVector

pub fn new() -> Self

Creates a new empty vector.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::new();
assert_eq!(bv.len(), 0);

pub fn with_capacity(capa: usize) -> Self

Creates a new vector that at least capa bits are reserved.

Arguments

• capa: Number of elements reserved at least.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::with_capacity(40);
assert_eq!(bv.len(), 0);
assert_eq!(bv.capacity(), 64);

pub fn from_bit(bit: bool, len: usize) -> Self

Creates a new vector that stores len bits, where each bit is initialized by bit.

Arguments

• bit: Bit value used for intinialization.
• len: Number of elements.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bit(false, 5);
assert_eq!(bv.len(), 5);
assert_eq!(bv.get_bit(0), Some(false));

pub fn from_bits<I>(bits: I) -> Selfwhere I: IntoIterator<Item = bool>,

Creates a new vector from input bit stream bits.

Arguments

• bits: Bit stream.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([false, true, false]);
assert_eq!(bv.len(), 3);
assert_eq!(bv.get_bit(1), Some(true));

pub fn get_bit(&self, pos: usize) -> Option<bool>

Returns the pos-th bit, or None if out of bounds.

Arguments

• pos: Bit position.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([true, false, false]);
assert_eq!(bv.get_bit(0), Some(true));
assert_eq!(bv.get_bit(1), Some(false));
assert_eq!(bv.get_bit(2), Some(false));
assert_eq!(bv.get_bit(3), None);

pub fn set_bit(&mut self, pos: usize, bit: bool) -> Result<()>

Updates the pos-th bit to bit.

Arguments

• pos: Bit position.
• bit: Bit value set.

Errors

An error is returned if self.len() <= pos.

Examples

use sucds::bit_vectors::BitVector;

let mut bv = BitVector::from_bits([false, true, false]);
bv.set_bit(1, false)?;
assert_eq!(bv.get_bit(1), Some(false));

pub fn push_bit(&mut self, bit: bool)

Pushes bit at the end.

Arguments

• bit: Bit value pushed.

Examples

use sucds::bit_vectors::BitVector;

let mut bv = BitVector::new();
bv.push_bit(true);
bv.push_bit(false);
assert_eq!(bv.len(), 2);

pub fn get_bits(&self, pos: usize, len: usize) -> Option<usize>

Returns the len bits starting at the pos-th bit, or None if

• len is greater than WORD_LEN, or
• self.len() < pos + len.

Arguments

• pos: Bit position.
• len: Number of bits extracted.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([true, false, true, false]);
assert_eq!(bv.get_bits(1, 2), Some(0b10));
assert_eq!(bv.get_bits(2, 3), None);

pub fn set_bits(&mut self, pos: usize, bits: usize, len: usize) -> Result<()>

Updates the len bits starting at the pos-th bit to bits.

Arguments

• pos: Bit position.
• bits: Bit chunk set.
• len: Number of bits of the chunk.

Errors

An error is returned if

• len is greater than WORD_LEN, or
• self.len() < pos + len.

Notes

If bits has active bits other than the lowest len bits, these will be trancated automatically.

Examples

use sucds::bit_vectors::BitVector;

let mut bv = BitVector::from_bit(false, 4);
bv.set_bits(1, 0b11, 2)?;
assert_eq!(bv.get_bits(0, 4), Some(0b0110));

pub fn push_bits(&mut self, bits: usize, len: usize) -> Result<()>

Pushes bits of len bits at the end.

Arguments

• bits: Bit chunk set.
• len: Number of bits of the chunk.

Errors

It will return an error if

• len is greater than WORD_LEN.

Notes

If bits has active bits other than the lowest len bits, these will be trancated automatically.

Examples

use sucds::bit_vectors::BitVector;

let mut bv = BitVector::new();
bv.push_bits(0b11, 2)?;
bv.push_bits(0b101, 3)?;
assert_eq!(bv.get_bits(0, 5), Some(0b10111));

pub fn predecessor1(&self, pos: usize) -> Option<usize>

Returns the largest bit position pred such that pred <= pos and the pred-th bit is set, or None if not found or self.len() <= pos.

Arguments

• pos: Bit position.

Complexity

• Linear

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([false, true, false, true]);
assert_eq!(bv.predecessor1(3), Some(3));
assert_eq!(bv.predecessor1(2), Some(1));
assert_eq!(bv.predecessor1(1), Some(1));
assert_eq!(bv.predecessor1(0), None);

pub fn predecessor0(&self, pos: usize) -> Option<usize>

Returns the largest bit position pred such that pred <= pos and the pred-th bit is unset, or None if not found or self.len() <= pos.

Arguments

• pos: Bit position.

Complexity

• Linear

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([true, false, true, false]);
assert_eq!(bv.predecessor0(3), Some(3));
assert_eq!(bv.predecessor0(2), Some(1));
assert_eq!(bv.predecessor0(1), Some(1));
assert_eq!(bv.predecessor0(0), None);

pub fn successor1(&self, pos: usize) -> Option<usize>

Returns the smallest bit position succ such that succ >= pos and the succ-th bit is set, or None if not found or self.len() <= pos.

Arguments

• pos: Bit position.

Complexity

• Linear

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([true, false, true, false]);
assert_eq!(bv.successor1(0), Some(0));
assert_eq!(bv.successor1(1), Some(2));
assert_eq!(bv.successor1(2), Some(2));
assert_eq!(bv.successor1(3), None);

pub fn successor0(&self, pos: usize) -> Option<usize>

Returns the smallest bit position succ such that succ >= pos and the succ-th bit is unset, or None if not found or self.len() <= pos.

Arguments

• pos: Bit position.

Complexity

• Linear

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([false, true, false, true]);
assert_eq!(bv.successor0(0), Some(0));
assert_eq!(bv.successor0(1), Some(2));
assert_eq!(bv.successor0(2), Some(2));
assert_eq!(bv.successor0(3), None);

pub const fn iter(&self) -> Iter<'_>

Creates an iterator for enumerating bits.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([false, true, false]);
let mut it = bv.iter();
assert_eq!(it.next(), Some(false));
assert_eq!(it.next(), Some(true));
assert_eq!(it.next(), Some(false));
assert_eq!(it.next(), None);

pub fn unary_iter(&self, pos: usize) -> UnaryIter<'_>

Creates an iterator for enumerating positions of set bits, starting at bit position pos.

Arguments

• pos: Bit position.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([true, true, false, true]);
let mut it = bv.unary_iter(1);
assert_eq!(it.next(), Some(1));
assert_eq!(it.next(), Some(3));
assert_eq!(it.next(), None);

pub fn get_word64(&self, pos: usize) -> Option<usize>

Returns self.get_bits(pos, 64) but it can extend further self.len(), padding with zeros. If self.len() <= pos, None is returned.

Arguments

• pos: Bit position.

Examples

use sucds::bit_vectors::BitVector;

let bv = BitVector::from_bits([true, false, true, false]);
assert_eq!(bv.get_word64(1), Some(0b10));
assert_eq!(bv.get_bits(1, 64), None);  // out of bounds

pub const fn len(&self) -> usize

Returns the number of bits stored.

pub const fn is_empty(&self) -> bool

Checks if the vector is empty.

pub fn words(&self) -> &[usize]

Gets the slice of raw words.

pub fn capacity(&self) -> usize

Returns the total number of bits it can hold without reallocating.

pub fn num_words(&self) -> usize

Gets the number of words.

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the vector as much as possible.

Trait Implementations

impl Access for BitVector

fn access(&self, pos: usize) -> Option<bool>

Returns the pos-th bit, or None if out of bounds.

Arguments

• pos: Bit position.

Examples

use sucds::bit_vectors::{BitVector, Access};

let bv = BitVector::from_bits([true, false, false]);
assert_eq!(bv.access(0), Some(true));
assert_eq!(bv.access(1), Some(false));
assert_eq!(bv.access(2), Some(false));
assert_eq!(bv.access(3), None);

impl Build for BitVector

fn build_from_bits<I>( bits: I, _with_rank: bool, _with_select1: bool, _with_select0: bool ) -> Result<Self>where I: IntoIterator<Item = bool>, Self: Sized,

Creates a new vector from input bit stream bits.

Arguments

• bits: Bit stream.
• with_rank: Dummy.
• with_select1: Dummy.
• with_select0: Dummy.

Errors

Never.

impl Clone for BitVector

fn clone(&self) -> BitVector

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for BitVector

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for BitVector

fn default() -> BitVector

Returns the “default value” for a type.

impl Extend<bool> for BitVector

fn extend<I>(&mut self, bits: I)where I: IntoIterator<Item = bool>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl NumBits for BitVector

fn num_bits(&self) -> usize

Returns the number of bits stored (just wrapping Self::len()).

fn num_ones(&self) -> usize

Returns the number of bits set.

Notes on complexity

It is performed by linear scan in $O(u)$ time.

fn num_zeros(&self) -> usize

Returns the number of bits unset.

impl PartialEq for BitVector

fn eq(&self, other: &BitVector) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Rank for BitVector

fn rank1(&self, pos: usize) -> Option<usize>

Returns the number of ones from the 0-th bit to the pos-1-th bit, or None if self.len() < pos.

Complexity

• Linear

Examples

use sucds::bit_vectors::{BitVector, Rank};

let bv = BitVector::from_bits([true, false, false, true]);
assert_eq!(bv.rank1(1), Some(1));
assert_eq!(bv.rank1(2), Some(1));
assert_eq!(bv.rank1(3), Some(1));
assert_eq!(bv.rank1(4), Some(2));
assert_eq!(bv.rank1(5), None);

fn rank0(&self, pos: usize) -> Option<usize>

Returns the number of zeros from the 0-th bit to the pos-1-th bit, or None if self.len() < pos.

Complexity

• Linear

Examples

use sucds::bit_vectors::{BitVector, Rank};

let bv = BitVector::from_bits([true, false, false, true]);
assert_eq!(bv.rank0(1), Some(0));
assert_eq!(bv.rank0(2), Some(1));
assert_eq!(bv.rank0(3), Some(2));
assert_eq!(bv.rank0(4), Some(2));
assert_eq!(bv.rank0(5), None);

impl Select for BitVector

fn select1(&self, k: usize) -> Option<usize>

Searches the position of the k-th bit set, or None if k is no less than the number of ones.

Complexity

• Linear

Examples

use sucds::bit_vectors::{BitVector, Select};

let bv = BitVector::from_bits([true, false, false, true]);
assert_eq!(bv.select1(0), Some(0));
assert_eq!(bv.select1(1), Some(3));
assert_eq!(bv.select1(2), None);

fn select0(&self, k: usize) -> Option<usize>

Searches the position of the k-th bit unset, or None if k is no less than the number of zeros.

Complexity

• Linear

Examples

use sucds::bit_vectors::{BitVector, Select};

let bv = BitVector::from_bits([true, false, false, true]);
assert_eq!(bv.select0(0), Some(1));
assert_eq!(bv.select0(1), Some(2));
assert_eq!(bv.select0(2), None);

impl Serializable for BitVector

fn serialize_into<W: Write>(&self, writer: W) -> Result<usize>

Serializes the data structure into the writer, returning the number of serialized bytes.

fn deserialize_from<R: Read>(reader: R) -> Result<Self>

Deserializes the data structure from the reader.

fn size_in_bytes(&self) -> usize

Returns the number of bytes to serialize the data structure.

fn size_of() -> Option<usize>

Returns the size of a primitive type in bytes (if the type is so).

impl Eq for BitVector

impl StructuralEq for BitVector

impl StructuralPartialEq for BitVector