Revision control
Copy as Markdown
Other Tools
// This file is part of ICU4X. For terms of use, please see the file
// called LICENSE at the top level of the ICU4X source tree
use alloc::vec;
use alloc::vec::Vec;
use core::fmt;
use core::iter::FromIterator;
use core::ops::Deref;
use super::FlexZeroSlice;
use super::FlexZeroVec;
/// The fully-owned variant of [`FlexZeroVec`]. Contains all mutation methods.
// Safety invariant: the inner bytes must deref to a valid `FlexZeroSlice`
#[derive(Clone, PartialEq, Eq)]
pub struct FlexZeroVecOwned(Vec<u8>);
impl FlexZeroVecOwned {
/// Creates a new [`FlexZeroVecOwned`] with zero elements.
pub fn new_empty() -> Self {
Self(vec![1])
}
/// Creates a [`FlexZeroVecOwned`] from a [`FlexZeroSlice`].
pub fn from_slice(other: &FlexZeroSlice) -> FlexZeroVecOwned {
// safety: the bytes originate from a valid FlexZeroSlice
Self(other.as_bytes().to_vec())
}
/// Obtains this [`FlexZeroVecOwned`] as a [`FlexZeroSlice`].
pub fn as_slice(&self) -> &FlexZeroSlice {
let slice: &[u8] = &self.0;
unsafe {
// safety: the slice is known to come from a valid parsed FlexZeroSlice
FlexZeroSlice::from_byte_slice_unchecked(slice)
}
}
/// Mutably obtains this `FlexZeroVecOwned` as a [`FlexZeroSlice`].
pub(crate) fn as_mut_slice(&mut self) -> &mut FlexZeroSlice {
let slice: &mut [u8] = &mut self.0;
unsafe {
// safety: the slice is known to come from a valid parsed FlexZeroSlice
FlexZeroSlice::from_byte_slice_mut_unchecked(slice)
}
}
/// Converts this `FlexZeroVecOwned` into a [`FlexZeroVec::Owned`].
#[inline]
pub fn into_flexzerovec(self) -> FlexZeroVec<'static> {
FlexZeroVec::Owned(self)
}
/// Clears all values out of this `FlexZeroVecOwned`.
#[inline]
pub fn clear(&mut self) {
*self = Self::new_empty()
}
/// Appends an item to the end of the vector.
///
/// # Panics
///
/// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
///
/// # Examples
///
/// ```
/// use zerovec::vecs::FlexZeroVec;
///
/// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
/// zv.to_mut().push(33);
/// assert_eq!(zv.to_vec(), vec![22, 44, 66, 33]);
/// ```
pub fn push(&mut self, item: usize) {
let insert_info = self.get_insert_info(item);
self.0.resize(insert_info.new_bytes_len, 0);
let insert_index = insert_info.new_count - 1;
self.as_mut_slice().insert_impl(insert_info, insert_index);
}
/// Inserts an element into the middle of the vector.
///
/// Caution: Both arguments to this function are of type `usize`. Please be careful to pass
/// the index first followed by the value second.
///
/// # Panics
///
/// Panics if `index > len`.
///
/// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
///
/// # Examples
///
/// ```
/// use zerovec::vecs::FlexZeroVec;
///
/// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
/// zv.to_mut().insert(2, 33);
/// assert_eq!(zv.to_vec(), vec![22, 44, 33, 66]);
/// ```
pub fn insert(&mut self, index: usize, item: usize) {
#[allow(clippy::panic)] // panic is documented in function contract
if index > self.len() {
panic!("index {} out of range {}", index, self.len());
}
let insert_info = self.get_insert_info(item);
self.0.resize(insert_info.new_bytes_len, 0);
self.as_mut_slice().insert_impl(insert_info, index);
}
/// Inserts an element into an ascending sorted vector
/// at a position that keeps the vector sorted.
///
/// # Panics
///
/// Panics if inserting the element would require allocating more than `usize::MAX` bytes.
///
/// # Examples
///
/// ```
/// use zerovec::vecs::FlexZeroVecOwned;
///
/// let mut fzv = FlexZeroVecOwned::new_empty();
/// fzv.insert_sorted(10);
/// fzv.insert_sorted(5);
/// fzv.insert_sorted(8);
///
/// assert!(Iterator::eq(fzv.iter(), [5, 8, 10].iter().copied()));
/// ```
pub fn insert_sorted(&mut self, item: usize) {
let index = match self.binary_search(item) {
Ok(i) => i,
Err(i) => i,
};
let insert_info = self.get_insert_info(item);
self.0.resize(insert_info.new_bytes_len, 0);
self.as_mut_slice().insert_impl(insert_info, index);
}
/// Removes and returns the element at the specified index.
///
/// # Panics
///
/// Panics if `index >= len`.
///
/// # Examples
///
/// ```
/// use zerovec::vecs::FlexZeroVec;
///
/// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
/// let removed_item = zv.to_mut().remove(1);
/// assert_eq!(44, removed_item);
/// assert_eq!(zv.to_vec(), vec![22, 66]);
/// ```
pub fn remove(&mut self, index: usize) -> usize {
#[allow(clippy::panic)] // panic is documented in function contract
if index >= self.len() {
panic!("index {} out of range {}", index, self.len());
}
let remove_info = self.get_remove_info(index);
// Safety: `remove_index` is a valid index
let item = unsafe { self.get_unchecked(remove_info.remove_index) };
let new_bytes_len = remove_info.new_bytes_len;
self.as_mut_slice().remove_impl(remove_info);
self.0.truncate(new_bytes_len);
item
}
/// Removes and returns the last element from an ascending sorted vector.
///
/// If the vector is not sorted, use [`FlexZeroVecOwned::remove()`] instead. Calling this
/// function would leave the FlexZeroVec in a safe, well-defined state; however, information
/// may be lost and/or the equality invariant might not hold.
///
/// # Panics
///
/// Panics if `self.is_empty()`.
///
/// # Examples
///
/// ```
/// use zerovec::vecs::FlexZeroVec;
///
/// let mut zv: FlexZeroVec = [22, 44, 66].iter().copied().collect();
/// let popped_item = zv.to_mut().pop_sorted();
/// assert_eq!(66, popped_item);
/// assert_eq!(zv.to_vec(), vec![22, 44]);
/// ```
///
/// Calling this function on a non-ascending vector could cause surprising results:
///
/// ```
/// use zerovec::vecs::FlexZeroVec;
///
/// let mut zv1: FlexZeroVec = [444, 222, 111].iter().copied().collect();
/// let popped_item = zv1.to_mut().pop_sorted();
/// assert_eq!(111, popped_item);
///
/// // Oops!
/// assert_eq!(zv1.to_vec(), vec![188, 222]);
/// ```
pub fn pop_sorted(&mut self) -> usize {
#[allow(clippy::panic)] // panic is documented in function contract
if self.is_empty() {
panic!("cannot pop from an empty vector");
}
let remove_info = self.get_sorted_pop_info();
// Safety: `remove_index` is a valid index
let item = unsafe { self.get_unchecked(remove_info.remove_index) };
let new_bytes_len = remove_info.new_bytes_len;
self.as_mut_slice().remove_impl(remove_info);
self.0.truncate(new_bytes_len);
item
}
}
impl Deref for FlexZeroVecOwned {
type Target = FlexZeroSlice;
fn deref(&self) -> &Self::Target {
self.as_slice()
}
}
impl fmt::Debug for FlexZeroVecOwned {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
write!(f, "{:?}", self.to_vec())
}
}
impl From<&FlexZeroSlice> for FlexZeroVecOwned {
fn from(other: &FlexZeroSlice) -> Self {
Self::from_slice(other)
}
}
impl FromIterator<usize> for FlexZeroVecOwned {
/// Creates a [`FlexZeroVecOwned`] from an iterator of `usize`.
fn from_iter<I>(iter: I) -> Self
where
I: IntoIterator<Item = usize>,
{
let mut result = FlexZeroVecOwned::new_empty();
for item in iter {
result.push(item);
}
result
}
}
#[cfg(test)]
mod test {
use super::*;
fn check_contents(fzv: &FlexZeroSlice, expected: &[usize]) {
assert_eq!(fzv.len(), expected.len(), "len: {fzv:?} != {expected:?}");
assert_eq!(
fzv.is_empty(),
expected.is_empty(),
"is_empty: {fzv:?} != {expected:?}"
);
assert_eq!(
fzv.first(),
expected.first().copied(),
"first: {fzv:?} != {expected:?}"
);
assert_eq!(
fzv.last(),
expected.last().copied(),
"last: {fzv:?} != {expected:?}"
);
for i in 0..(expected.len() + 1) {
assert_eq!(
fzv.get(i),
expected.get(i).copied(),
"@{i}: {fzv:?} != {expected:?}"
);
}
}
#[test]
fn test_basic() {
let mut fzv = FlexZeroVecOwned::new_empty();
assert_eq!(fzv.get_width(), 1);
check_contents(&fzv, &[]);
fzv.push(42);
assert_eq!(fzv.get_width(), 1);
check_contents(&fzv, &[42]);
fzv.push(77);
assert_eq!(fzv.get_width(), 1);
check_contents(&fzv, &[42, 77]);
// Scale up
fzv.push(300);
assert_eq!(fzv.get_width(), 2);
check_contents(&fzv, &[42, 77, 300]);
// Does not need to be sorted
fzv.insert(1, 325);
assert_eq!(fzv.get_width(), 2);
check_contents(&fzv, &[42, 325, 77, 300]);
fzv.remove(3);
assert_eq!(fzv.get_width(), 2);
check_contents(&fzv, &[42, 325, 77]);
// Scale down
fzv.remove(1);
assert_eq!(fzv.get_width(), 1);
check_contents(&fzv, &[42, 77]);
}
#[test]
fn test_build_sorted() {
let nums: &[usize] = &[0, 50, 0, 77, 831, 29, 89182, 931, 0, 77, 712381];
let mut fzv = FlexZeroVecOwned::new_empty();
for num in nums {
fzv.insert_sorted(*num);
}
assert_eq!(fzv.get_width(), 3);
check_contents(&fzv, &[0, 0, 0, 29, 50, 77, 77, 831, 931, 89182, 712381]);
for num in nums {
let index = fzv.binary_search(*num).unwrap();
fzv.remove(index);
}
assert_eq!(fzv.get_width(), 1);
check_contents(&fzv, &[]);
}
}