Struct sucds::int_vectors::compact_vector::CompactVector

source ·

pub struct CompactVector { /* private fields */ }

Expand description

Updatable compact vector in which each integer is represented in a fixed number of bits.

Memory usage

$n \lceil \lg u \rceil$ bits for $n$ integers in which a value is in $[0,u)$.

Examples

use sucds::int_vectors::CompactVector;

// Can store integers within 3 bits each.
let mut cv = CompactVector::new(3)?;

cv.push_int(7)?;
cv.push_int(2)?;

assert_eq!(cv.len(), 2);
assert_eq!(cv.get_int(0), Some(7));

cv.set_int(0, 5)?;
assert_eq!(cv.get_int(0), Some(5));

Implementations§

source §

impl CompactVector

source

pub fn new(width: usize) -> Result<Self>

Creates a new empty vector storing integers within width bits each.

Arguments

width: Number of bits used to store an integer.

Errors

An error is returned if width is not in 1..=64.

Examples

use sucds::int_vectors::CompactVector;

let mut cv = CompactVector::new(3)?;
assert_eq!(cv.len(), 0);
assert_eq!(cv.width(), 3);

source

pub fn with_capacity(capa: usize, width: usize) -> Result<Self>

Creates a new vector storing an integer in width bits, where space for storing at least capa integers is reserved.

Arguments

capa: Number of elements reserved at least.
width: Number of bits used to store an integer.

Errors

An error is returned if width is not in 1..=64.

Examples

use sucds::int_vectors::CompactVector;

let mut cv = CompactVector::with_capacity(10, 3)?;

assert_eq!(cv.len(), 0);
assert_eq!(cv.width(), 3);

// Space for storing 21 integers is reserved due to the data structure.
assert_eq!(cv.capacity(), 21);

source

pub fn from_int(val: usize, len: usize, width: usize) -> Result<Self>

Creates a new vector storing an integer in width bits, which stores len values initialized by val.

Arguments

val: Integer value.
len: Number of elements.
width: Number of bits used to store an integer.

Errors

An error is returned if

width is not in 1..=64, or
val cannot be represent in width bits.

Examples

use sucds::int_vectors::CompactVector;

let mut cv = CompactVector::from_int(7, 2, 3)?;
assert_eq!(cv.len(), 2);
assert_eq!(cv.width(), 3);
assert_eq!(cv.get_int(0), Some(7));

source

pub fn from_slice<T>(vals: &[T]) -> Result<Self>where T: ToPrimitive,

Creates a new vector from a slice of integers vals.

The width of each element automatically fits to the maximum value in vals.

Arguments

vals: Slice of integers to be stored.

Errors

An error is returned if vals contains an integer that cannot be cast to usize.

Examples

use sucds::int_vectors::CompactVector;

let mut cv = CompactVector::from_slice(&[7, 2])?;
assert_eq!(cv.len(), 2);
assert_eq!(cv.width(), 3);
assert_eq!(cv.get_int(0), Some(7));

source

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

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

Arguments

pos: Position.

Complexity

Constant

Examples

use sucds::int_vectors::CompactVector;

let cv = CompactVector::from_slice(&[5, 256, 0])?;
assert_eq!(cv.get_int(0), Some(5));
assert_eq!(cv.get_int(1), Some(256));
assert_eq!(cv.get_int(2), Some(0));
assert_eq!(cv.get_int(3), None);

source

pub fn set_int(&mut self, pos: usize, val: usize) -> Result<()>

Sets the pos-th integer to val.

Arguments

pos: Position.
val: Integer value set.

Errors

An error is returned if

pos is out of bounds, or
val cannot be represent in self.width() bits.

Complexity

Constant

Examples

use sucds::int_vectors::CompactVector;

let mut cv = CompactVector::from_int(0, 2, 3)?;
cv.set_int(1, 4)?;
assert_eq!(cv.get_int(1), Some(4));

source

pub fn push_int(&mut self, val: usize) -> Result<()>

Pushes integer val at the end.

Arguments

val: Integer value pushed.

Errors

An error is returned if val cannot be represent in self.width() bits.

Complexity

Constant (Amortized)

Examples

use sucds::int_vectors::CompactVector;

let mut cv = CompactVector::new(3)?;
cv.push_int(2)?;
cv.push_int(1)?;
assert_eq!(cv.len(), 2);

source

pub fn extend(&mut self, vals: I) -> Result<()>where I: IntoIterator<Item = usize>,

Appends integers at the end.

Arguments

vals: Integer stream to be pushed.

Errors

An error is returned if values in vals cannot be represent in self.width() bits.

Complexity

Linear

Examples

use sucds::int_vectors::CompactVector;

let mut cv = CompactVector::new(3)?;
cv.extend([2, 1, 3])?;
assert_eq!(cv.len(), 3);

source

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

Creates an iterator for enumerating integers.

Examples

use sucds::int_vectors::CompactVector;

let cv = CompactVector::from_slice(&[5, 256, 0])?;
let mut it = cv.iter();

assert_eq!(it.next(), Some(5));
assert_eq!(it.next(), Some(256));
assert_eq!(it.next(), Some(0));
assert_eq!(it.next(), None);

source

pub const fn len(&self) -> usize

Gets the number of integers.

source

pub const fn is_empty(&self) -> bool

Checks if the vector is empty.

source

pub fn capacity(&self) -> usize

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

source

pub const fn width(&self) -> usize

Gets the number of bits to represent an integer.

Trait Implementations§

source §

impl Access for CompactVector

source §

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

Returns the pos-th integer, or None if out of bounds (just wrapping Self::get_int()).

Arguments

pos: Position.

Complexity

Constant

Examples

use sucds::int_vectors::{CompactVector, Access};

let cv = CompactVector::from_slice(&[5, 256, 0])?;
assert_eq!(cv.access(0), Some(5));
assert_eq!(cv.access(1), Some(256));
assert_eq!(cv.access(2), Some(0));
assert_eq!(cv.access(3), None);