#[cfg(test)]
mod tests;
use tinyvec::{Array, TinyVec};
use std::convert::{From, Into};
use std::fmt::{self, Debug, Formatter};
use std::iter::FromIterator;
pub type Nibblet = NibbleVec<[u8; 64]>;
#[derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize, Clone, Default)]
pub struct NibbleVec<A: Array<Item = u8>> {
length: usize,
data: TinyVec<A>,
}
impl<A: Array<Item = u8>> NibbleVec<A> {
pub fn new() -> NibbleVec<A> {
NibbleVec {
length: 0,
data: TinyVec::new(),
}
}
#[inline]
pub fn from_byte_vec(vec: Vec<u8>) -> NibbleVec<A> {
let length = 2 * vec.len();
NibbleVec {
length,
data: TinyVec::from_iter(vec),
}
}
#[inline]
pub fn as_bytes(&self) -> &[u8] {
&self.data[..]
}
#[inline]
pub fn into_bytes(self) -> Vec<u8> {
self.data.to_vec()
}
#[inline]
pub fn len(&self) -> usize {
self.length
}
#[inline]
pub fn is_empty(&self) -> bool {
self.data.is_empty()
}
#[inline]
pub fn get(&self, idx: usize) -> u8 {
if idx >= self.length {
panic!(
"NibbleVec index out of bounds: len is {}, index is {}",
self.length, idx
);
}
let vec_idx = idx / 2;
match idx % 2 {
0 => self.data[vec_idx] >> 4,
_ => self.data[vec_idx] & 0x0F,
}
}
#[inline]
pub fn push(&mut self, val: u8) {
if self.length % 2 == 0 {
self.data.push(val << 4);
} else {
let vec_len = self.data.len();
self.data[vec_len - 1] &= 0xF0;
self.data[vec_len - 1] |= val & 0x0F;
}
self.length += 1;
}
pub fn split(&mut self, idx: usize) -> NibbleVec<A> {
if idx > self.length {
panic!(
"attempted to split past vector end. len is {}, index is {}",
self.length, idx
);
} else if idx == self.length {
NibbleVec::new()
} else if idx % 2 == 0 {
self.split_even(idx)
} else {
self.split_odd(idx)
}
}
#[inline]
fn split_odd(&mut self, idx: usize) -> NibbleVec<A> {
let mut tail = NibbleVec::new();
let tail_length = self.length - idx;
let take_last = tail_length % 2 == 1;
self.overlap_copy(
idx / 2,
self.data.len(),
&mut tail.data,
&mut tail.length,
take_last,
);
for _ in (idx / 2 + 1)..self.data.len() {
self.data.pop();
}
self.data[idx / 2] &= 0xF0;
self.length = idx;
tail
}
#[inline]
fn split_even(&mut self, idx: usize) -> NibbleVec<A> {
let half_idx = idx / 2;
let mut tail = NibbleVec::new();
for i in half_idx..self.data.len() {
tail.data.push(self.data[i]);
}
for _ in half_idx..self.data.len() {
self.data.pop();
}
tail.length = self.length - idx;
self.length = idx;
tail
}
#[inline]
fn overlap_copy(
&self,
start: usize,
end: usize,
vec: &mut TinyVec<A>,
length: &mut usize,
include_last: bool,
) {
for i in start..(end - 1) {
let first_half = self.data[i] & 0x0f;
let second_half = self.data[i + 1] >> 4;
vec.push((first_half << 4) | second_half);
*length += 2;
}
if include_last {
let last = self.data[end - 1] & 0x0f;
vec.push(last << 4);
*length += 1;
}
}
#[inline]
pub fn join(mut self, other: &NibbleVec<A>) -> NibbleVec<A> {
if self.length % 2 == 0 {
self.length += other.length;
self.data.extend_from_slice(&other.data);
return self;
}
if other.is_empty() {
return self;
}
self.push(other.get(0));
let take_last = other.len() % 2 == 0;
other.overlap_copy(
0,
other.data.len(),
&mut self.data,
&mut self.length,
take_last,
);
self
}
}
impl<A: Array<Item = u8>> PartialEq<NibbleVec<A>> for NibbleVec<A> {
#[inline]
fn eq(&self, other: &NibbleVec<A>) -> bool {
self.length == other.length && self.data == other.data
}
}
impl<A: Array<Item = u8>> Eq for NibbleVec<A> {}
impl<A: Array<Item = u8>> PartialEq<[u8]> for NibbleVec<A> {
#[inline]
fn eq(&self, other: &[u8]) -> bool {
if other.len() != self.len() {
return false;
}
for (i, x) in other.iter().enumerate() {
if self.get(i) != *x {
return false;
}
}
true
}
}
impl<A: Array<Item = u8>> Debug for NibbleVec<A> {
fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
write!(fmt, "NibbleVec [")?;
if !self.is_empty() {
write!(fmt, "{}", self.get(0))?;
}
for i in 1..self.len() {
write!(fmt, ", {}", self.get(i))?;
}
write!(fmt, "]")
}
}
impl<A: Array<Item = u8>> From<Vec<u8>> for NibbleVec<A> {
#[inline]
fn from(v: Vec<u8>) -> NibbleVec<A> {
NibbleVec::from_byte_vec(v)
}
}
impl<'a, A: Array<Item = u8>> From<&'a [u8]> for NibbleVec<A> {
#[inline]
fn from(v: &[u8]) -> NibbleVec<A> {
NibbleVec::from_byte_vec(v.into())
}
}
impl<A: Array<Item = u8>> Into<Vec<u8>> for NibbleVec<A> {
#[inline]
fn into(self) -> Vec<u8> {
self.data.to_vec()
}
}
impl<'a, A: Array<Item = u8>> Into<Vec<u8>> for &'a NibbleVec<A> {
#[inline]
fn into(self) -> Vec<u8> {
self.data.to_vec()
}
}