Come esercizio per imparare Rust, ho deciso di implementare una libreria Bit Vector, con l'ispirazione da std::vec::Vec per quali metodi fornire.Come restituire una struttura appena creata come riferimento?
Ho il seguente codice:
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))
}
}
Il compilatore si verificano errori ai metodi split_at e split_at_mut: In sostanza mi dice che left e right in entrambi i casi, non vivono abbastanza a lungo per essere restituito come riferimento . Capisco questo, perché sono creati in pila e quindi voglio restituirli come riferimento.
Tuttavia, con il mio disegno è ispirato il std::vec::Vec si può vedere che in the SliceExt trait loro definizioni sono le seguenti:
#[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]);
Suppongo che questo è fatto per convenienza dell'utente finale in quanto piuttosto che fare con i riferimenti che con le scatole.
Penso di poter correggere i miei errori inserendo i vettori bit restituiti in un Box<_>, ma c'è un modo per restituire le strutture create come riferimento?
Come domanda bonus: Funziona se restituisco (BitVector<S>, BitVector<S>), quali sono gli svantaggi di fare questo? Perché il tratto SliceExt non lo fa?
Si prega di produrre un [MCVE]. – Shepmaster
@Shepmaster Non vedo un modo per abbreviare il codice in questione pur mantenendo lo spirito della domanda, vale a dire. che è un vettore bit e come si riferisce a 'std :: vec :: Vec' e al tratto' SliceExt'. – skiwi
Le funzioni 'get',' set', 'capacity' sono irrilevanti. Rimuovi argomenti, tipi generici. Finisci con [questo] (https://play.rust-lang.org/?gist=aa638e102672e09ebcce3098762cf947&version=stable&backtrace=0). – Shepmaster