This question already has answers here:
Closed 2 years ago.
As an exercise to learn Rust I decided to implement a Bit Vector library, with inspiration from std::vec::Vec for which methods to provide.
I have the following code:
extern crate num;
use std::cmp::Eq;
use std::ops::{BitAnd,BitOrAssign,Index,Shl};
use num::{One,Zero,Unsigned,NumCast};
pub trait BitStorage: Sized +
BitAnd<Self, Output = Self> +
BitOrAssign<Self> +
Shl<Self, Output = Self> +
Eq + Zero + One + Unsigned + NumCast + Copy {}
impl<S> BitStorage for S where S: Sized +
BitAnd<S, Output = S> +
BitOrAssign<S> +
Shl<S, Output = S> +
Eq + Zero + One + Unsigned + NumCast + Copy {}
pub struct BitVector<S: BitStorage> {
data: Vec<S>,
capacity: usize,
storage_size: usize
}
impl<S: BitStorage> BitVector<S> {
pub fn with_capacity(capacity: usize) -> BitVector<S> {
let storage_size = std::mem::size_of::<S>() * 8;
let len = (capacity / storage_size) + 1;
BitVector {
data: vec![S::zero(); len],
capacity: capacity,
storage_size: storage_size
}
}
pub fn get(&self, index: usize) -> Option<bool> {
match self.index_in_bounds(index) {
true => Some(self.get_unchecked(index)),
false => None
}
}
pub fn set(&mut self, index: usize, value: bool) {
self.panic_index_bounds(index);
let (data_index, remainder) = self.compute_data_index_and_remainder(index);
let value = if value { S::one() } else { S::zero() };
self.data[data_index] |= value << remainder;
}
pub fn capacity(&self) -> usize {
self.capacity
}
pub fn split_at(&self, index: usize) -> (&BitVector<S>, &BitVector<S>) {
self.panic_index_not_on_storage_bound(index);
let data_index = self.compute_data_index(index);
let (capacity_left, capacity_right) = self.compute_capacities(index);
let (data_left, data_right) = self.data.split_at(data_index);
let left = BitVector {
data: data_left.to_vec(),
capacity: capacity_left,
storage_size: self.storage_size
};
let right = BitVector {
data: data_right.to_vec(),
capacity: capacity_right,
storage_size: self.storage_size
};
(&left, &right)
}
pub fn split_at_mut(&mut self, index: usize) -> (&mut BitVector<S>, &mut BitVector<S>) {
self.panic_index_not_on_storage_bound(index);
let data_index = self.compute_data_index(index);
let (capacity_left, capacity_right) = self.compute_capacities(index);
let (data_left, data_right) = self.data.split_at_mut(data_index);
let mut left = BitVector {
data: data_left.to_vec(),
capacity: capacity_left,
storage_size: self.storage_size
};
let mut right = BitVector {
data: data_right.to_vec(),
capacity: capacity_right,
storage_size: self.storage_size
};
(&mut left, &mut right)
}
#[inline]
fn get_unchecked(&self, index: usize) -> bool {
let (data_index, remainder) = self.compute_data_index_and_remainder(index);
(self.data[data_index] & (S::one() << remainder)) != S::zero()
}
#[inline]
fn compute_data_index_and_remainder(&self, index: usize) -> (usize, S) {
let data_index = self.compute_data_index(index);
let remainder = self.compute_data_remainder(index);
(data_index, remainder)
}
#[inline]
fn compute_data_index(&self, index: usize) -> usize {
index / self.storage_size
}
#[inline]
fn compute_data_remainder(&self, index: usize) -> S {
let remainder = index % self.storage_size;
// we know that remainder is always smaller or equal to the size that S can hold
// for example if S = u8 then remainder <= 2^8 - 1
let remainder: S = num::cast(remainder).unwrap();
remainder
}
#[inline]
fn compute_capacities(&self, index_to_split: usize) -> (usize, usize) {
(index_to_split, self.capacity - index_to_split)
}
#[inline]
fn index_in_bounds(&self, index: usize) -> bool {
index < self.capacity
}
#[inline]
fn panic_index_bounds(&self, index: usize) {
if !self.index_in_bounds(index) {
panic!("Index out of bounds. Length = {}, Index = {}", self.capacity, index);
}
}
#[inline]
fn panic_index_not_on_storage_bound(&self, index: usize) {
if index % self.storage_size != 0 {
panic!("Index not on storage bound. Storage size = {}, Index = {}", self.storage_size, index);
}
}
}
static TRUE: bool = true;
static FALSE: bool = false;
macro_rules! bool_ref {
($cond:expr) => (if $cond { &TRUE } else { &FALSE })
}
impl<S: BitStorage> Index<usize> for BitVector<S> {
type Output = bool;
fn index(&self, index: usize) -> &bool {
self.panic_index_bounds(index);
bool_ref!(self.get_unchecked(index))
}
}
The compiler errors occur at the split_at and split_at_mut methods: They basically tell me that left and right in both cases do not live long enough to be returned as a reference. I understand this, because they are created on the stack and then I want to return them as a reference.
However with my design being inspired by std::vec::Vec you can see that in the SliceExt trait their definitions are as follows:
#[stable(feature = "core", since = "1.6.0")]
fn split_at(&self, mid: usize) -> (&[Self::Item], &[Self::Item]);
#[stable(feature = "core", since = "1.6.0")]
fn split_at_mut(&mut self, mid: usize) -> (&mut [Self::Item], &mut [Self::Item]);
I suppose this is done for end user convenience as they rather deal with references than with boxes.
I think I could fix my errors by putting the returned bit vectors into a Box<_>, but is there a way to return the created structs as a reference?
As a bonus question: It does work if I return (BitVector<S>, BitVector<S>), what are the downsides to doing this? Why does the SliceExt trait not do this?
