Struct sucds::bit_vector::BitVector

pub struct BitVector { /* private fields */ }

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

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

Examples

use sucds::BitVector;

let bv = BitVector::from_bits(&[true, false, false, true]);

assert_eq!(bv.get_bit(0), true);
assert_eq!(bv.get_bit(1), false);
assert_eq!(bv.get_bit(2), false);
assert_eq!(bv.get_bit(3), true);

assert_eq!(bv.predecessor1(2), Some(0));
assert_eq!(bv.predecessor0(2), Some(2));
assert_eq!(bv.successor1(1), Some(3));
assert_eq!(bv.successor0(1), Some(1));

let mut bytes = vec![];
let size = bv.serialize_into(&mut bytes).unwrap();
let other = BitVector::deserialize_from(&bytes[..]).unwrap();
assert_eq!(bv, other);
assert_eq!(size, bytes.len());
assert_eq!(size, bv.size_in_bytes());

Implementations

impl BitVector

pub fn new() -> Self

Creates a new empty BitVector.

pub fn with_len(len: usize) -> Self

Creates a new BitVector of len bits.

pub fn with_capacity(capa: usize) -> Self

Creates a new BitVector that capa bits are reserved.

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

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

Arguments

• writer: std::io::Write variable.

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

Deserializes the data structure from the reader.

Arguments

• reader: std::io::Read variable.

pub fn size_in_bytes(&self) -> usize

Returns the number of bytes to serialize the data structure.

pub fn from_bits<'a, I>(bits: I) -> Self where
    I: IntoIterator<Item = &'a bool>, 

Creates a new BitVector from input bitset bits.

Arguments

• bits: List of bits.

Examples

use sucds::BitVector;

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

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

Gets the pos-th bit.

Arguments

• pos: Bit position.

Examples

use sucds::BitVector;

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

pub fn set_bit(&mut self, pos: usize, bit: bool)

Sets the pos-th bit to bit.

Arguments

• pos: Bit position.
• bit: Set bit.

Examples

use sucds::BitVector;

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

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

Pushes bit at the end.

Arguments

• bit: Pushed bit.

Examples

use sucds::BitVector;

let mut bv = BitVector::new();
bv.push_bit(true);
bv.push_bit(false);
assert_eq!(bv.get_bit(0), true);
assert_eq!(bv.get_bit(1), false);

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

Gets the len bits starting at the pos-th bit.

Arguments

• pos: Starting bit position.
• len: Number of bits.

Examples

use sucds::BitVector;

let bv = BitVector::from_bits(&[true, false, true, false, true]);
assert_eq!(bv.get_bits(1, 4), 0b1010);

pub fn set_bits(&mut self, pos: usize, bits: usize, len: usize)

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

Arguments

• pos: Starting bit position.
• bits: Set bits.
• len: Number of bits.

Examples

use sucds::BitVector;

let mut bv = BitVector::with_len(5);
bv.set_bits(1, 0b1010, 4);
assert_eq!(bv.get_bits(1, 4), 0b1010);

pub fn push_bits(&mut self, bits: usize, len: usize)

Pushes bits of len bits at the end.

Arguments

• bits: Pushed bits.
• len: Number of bits.

Examples

use sucds::BitVector;

let mut bv = BitVector::new();
bv.push_bits(0b1, 1);
bv.push_bits(0b1010, 4);
assert_eq!(bv.get_bits(1, 4), 0b1010);

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

Gets the largest bit position pred such that pred <= pos and the pred-th bit is set. If not found, None is returned.

Arguments

• pos: Bit position.

Examples

use sucds::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 successor1(&self, pos: usize) -> Option<usize>

Gets the smallest bit position succ such that succ >= pos and the succ-th bit is set. If not found, None is returned.

Arguments

• pos: Bit position.

Examples

use sucds::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 predecessor0(&self, pos: usize) -> Option<usize>

Gets the largest bit position pred such that pred <= pos and the pred-th bit is not set. If not found, None is returned.

Arguments

• pos: Bit position.

Examples

use sucds::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 successor0(&self, pos: usize) -> Option<usize>

Gets the smallest bit position succ such that succ >= pos and the succ-th bit is not set. If not found, None is returned.

Arguments

• pos: Bit position.

Examples

use sucds::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 fn unary_iter(&self, pos: usize) -> UnaryIterator<'_>

Creates an iterator for enumerating positions of set bits.

Examples

use sucds::BitVector;

let bv = BitVector::from_bits(&[false, true, false, false, true]);
let mut it = bv.unary_iter(1);

assert_eq!(it.next(), Some(1));
assert_eq!(it.next(), Some(4));
assert_eq!(it.next(), None);

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

Gets get_bits(pos, 64) but it can extend further len(), padding with zeros.

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

Gets the slice of raw words.

pub fn num_words(&self) -> usize

Gets the number of words.

pub const fn len(&self) -> usize

Gets the number of bits.

pub const fn is_empty(&self) -> bool

Checks if the vector is empty.

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the vector as much as possible.

Trait Implementations

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 PartialEq<BitVector> 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: &BitVector) -> bool

This method tests for !=.

impl Eq for BitVector

impl StructuralEq for BitVector

impl StructuralPartialEq for BitVector