Struct bio::data_structures::bitenc::BitEnc

pub struct BitEnc { /* private fields */ }

A sequence of bitencoded values.

Space complexity: O(⌈(n * width) / k⌉) * 32 bit, where n is the length of the input sequence and k = 32 - (32 % width) is the number of bits in each 32-bit block that can be used to store values. For values that are not a divider of 32, some bits will remain unused. For example for width = 7 only 4 * 7 = 28 bits are used. Five 7-bit values are stored in 2 blocks.

Implementations

impl BitEnc

pub fn new(width: usize) -> Self

Create a new instance with a given encoding width (e.g. width=2 for using two bits per value). Supports widths up to 8 bits per character, i.e. 1 <= width <= 8.

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;
let bitenc = BitEnc::new(3);

pub fn with_capacity(width: usize, n: usize) -> Self

Create a new instance with a given capacity and encoding width (e.g. width=2 for using two bits per value). Supports widths up to 8 bits per character, i.e. 1 <= width <= 8.

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;

let bitenc = BitEnc::with_capacity(3, 42);

pub fn push(&mut self, value: u8)

Append a character to the current bit-encoding.

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(4);
bitenc.push(0b0000);
bitenc.push(0b1000);
bitenc.push(0b1010);
// The three characters added above are encoded into one u32 entry.
let values: Vec<u8> = bitenc.iter().collect();
assert_eq!(values, [0b0000, 0b1000, 0b1010]);

pub fn push_values(&mut self, n: usize, value: u8)

Append the given value to the encoding n times.

The added values comprise 0 to 1 blocks that need to be filled up from previous steps, 0 to m blocks that are completely filled with the value and 0 to 1 blocks that are only partially filled.

Complexity: O(n)

Example

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(8);
// Width: 8 → 4 values per block
// | __ __ __ __ | Denotes one block with 4 empty slots

bitenc.push_values(5, 0b101010);
// This adds one full and one partial block.
// | 42 42 42 42 | __ __ __ 42 |

let values: Vec<u8> = bitenc.iter().collect();
assert_eq!(values, [42, 42, 42, 42, 42]);

bitenc.push_values(1, 23);
// This only fills up an existing block;
// | 42 42 42 42 | __ __ 23 42 |

let values: Vec<u8> = bitenc.iter().collect();
assert_eq!(values, [42, 42, 42, 42, 42, 23]);

bitenc.push_values(6, 17);
// Fills up the current block, adds a whole new one but does not create a partial block.
// | 42 42 42 42 | 17 17 23 42 | 17 17 17 17 |

let values: Vec<u8> = bitenc.iter().collect();
assert_eq!(values, [42, 42, 42, 42, 42, 23, 17, 17, 17, 17, 17, 17]);

pub fn set(&mut self, i: usize, value: u8)

Replace the current value as position i with the given value.

Complexity: O(1)

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(4);
bitenc.push_values(4, 0b1111);
bitenc.set(2, 0b0000);

let values: Vec<u8> = bitenc.iter().collect();
assert_eq!(values, [0b1111, 0b1111, 0b0000, 0b1111]);

pub fn get(&self, i: usize) -> Option<u8>

Get the value at position i.

Complexity: O(1)

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(4);
for value in 1..=4 {
    bitenc.push(value);
}

let values: Vec<u8> = bitenc.iter().collect();
assert_eq!(values, [0b0001, 0b0010, 0b0011, 0b0100]);

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

Iterate over stored values (values will be unpacked into bytes).

Complexity: O(n), where n is the number of encoded values

Example

use bio::data_structures::bitenc::BitEnc;

// Fill bitenc with 1, 2, 3, and 4.
let mut bitenc = BitEnc::new(4);
for value in 1..=4 {
    bitenc.push(value);
}

// Collect iterator for comparison
let values: Vec<u8> = bitenc.iter().collect();
assert_eq!(values, [0b0001, 0b0010, 0b0011, 0b0100]);

pub fn clear(&mut self)

Clear the sequence.

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(2);
bitenc.push(2);
assert_eq!(bitenc.len(), 1);
bitenc.clear();
assert_eq!(bitenc.len(), 0);

pub fn len(&self) -> usize

👎 Deprecated since 0.33.0:

Please use the more specific nr_blocks and nr_symbols functions instead.

Get the number of symbols encoded.

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(8);
bitenc.push(2);
assert_eq!(bitenc.len(), 1);
bitenc.push(2);
bitenc.push(2);
bitenc.push(2);
assert_eq!(bitenc.len(), 4);
// Add another 2 to create a second block
bitenc.push(2);
assert_eq!(bitenc.len(), 5);

pub fn nr_blocks(&self) -> usize

Get the number of blocks used by the encoding.

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(8);
bitenc.push(2);
assert_eq!(bitenc.nr_blocks(), 1);
// Add enough 2s to completely fill the first block
bitenc.push(2);
bitenc.push(2);
bitenc.push(2);
assert_eq!(bitenc.nr_blocks(), 1);
// Add another 2 to create a second block
bitenc.push(2);
assert_eq!(bitenc.nr_blocks(), 2);

pub fn nr_symbols(&self) -> usize

Get the number of symbols encoded.

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(8);
bitenc.push(2);
assert_eq!(bitenc.nr_symbols(), 1);
bitenc.push(2);
bitenc.push(2);
bitenc.push(2);
assert_eq!(bitenc.nr_symbols(), 4);
bitenc.push(2);
assert_eq!(bitenc.nr_symbols(), 5);

pub fn is_empty(&self) -> bool

Is the encoded sequence empty?

Complexity: O(1)

Example

use bio::data_structures::bitenc::BitEnc;

let mut bitenc = BitEnc::new(2);
assert!(bitenc.is_empty());
bitenc.push(2);
assert!(!bitenc.is_empty());
bitenc.clear();
assert!(bitenc.is_empty());

Trait Implementations

impl<'de> Deserialize<'de> for BitEnc

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl Hash for BitEnc

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H) where
    H: Hasher, 

Feeds a slice of this type into the given Hasher.

impl PartialEq<BitEnc> for BitEnc

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

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

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

This method tests for !=.

impl Serialize for BitEnc

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.

impl Eq for BitEnc

impl StructuralEq for BitEnc

impl StructuralPartialEq for BitEnc