| // 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 |
| // (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ). |
| |
| use crate::ule::*; |
| use crate::varzerovec::owned::VarZeroVecOwned; |
| use crate::vecs::{FlexZeroSlice, FlexZeroVec, FlexZeroVecOwned, VarZeroVecFormat}; |
| use crate::{VarZeroSlice, VarZeroVec}; |
| use crate::{ZeroSlice, ZeroVec}; |
| use alloc::boxed::Box; |
| use alloc::vec::Vec; |
| use core::cmp::Ordering; |
| use core::mem; |
| use core::ops::Range; |
| |
| /// Trait abstracting over [`ZeroVec`] and [`VarZeroVec`], for use in [`ZeroMap`](super::ZeroMap). **You |
| /// should not be implementing or calling this trait directly.** |
| /// |
| /// The T type is the type received by [`Self::zvl_binary_search()`], as well as the one used |
| /// for human-readable serialization. |
| /// |
| /// Methods are prefixed with `zvl_*` to avoid clashes with methods on the types themselves |
| pub trait ZeroVecLike<T: ?Sized> { |
| /// The type returned by `Self::get()` |
| type GetType: ?Sized + 'static; |
| /// A fully borrowed version of this |
| type SliceVariant: ZeroVecLike<T, GetType = Self::GetType> + ?Sized; |
| |
| /// Create a new, empty borrowed variant |
| fn zvl_new_borrowed() -> &'static Self::SliceVariant; |
| |
| /// Search for a key in a sorted vector, returns `Ok(index)` if found, |
| /// returns `Err(insert_index)` if not found, where `insert_index` is the |
| /// index where it should be inserted to maintain sort order. |
| fn zvl_binary_search(&self, k: &T) -> Result<usize, usize> |
| where |
| T: Ord; |
| /// Search for a key within a certain range in a sorted vector. |
| /// Returns `None` if the range is out of bounds, and |
| /// `Ok` or `Err` in the same way as `zvl_binary_search`. |
| /// Indices are returned relative to the start of the range. |
| fn zvl_binary_search_in_range( |
| &self, |
| k: &T, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> |
| where |
| T: Ord; |
| |
| /// Search for a key in a sorted vector by a predicate, returns `Ok(index)` if found, |
| /// returns `Err(insert_index)` if not found, where `insert_index` is the |
| /// index where it should be inserted to maintain sort order. |
| fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize>; |
| /// Search for a key within a certain range in a sorted vector by a predicate. |
| /// Returns `None` if the range is out of bounds, and |
| /// `Ok` or `Err` in the same way as `zvl_binary_search`. |
| /// Indices are returned relative to the start of the range. |
| fn zvl_binary_search_in_range_by( |
| &self, |
| predicate: impl FnMut(&T) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>>; |
| |
| /// Get element at `index` |
| fn zvl_get(&self, index: usize) -> Option<&Self::GetType>; |
| /// The length of this vector |
| fn zvl_len(&self) -> usize; |
| /// Check if this vector is in ascending order according to `T`s `Ord` impl |
| fn zvl_is_ascending(&self) -> bool |
| where |
| T: Ord, |
| { |
| if let Some(first) = self.zvl_get(0) { |
| let mut prev = first; |
| for i in 1..self.zvl_len() { |
| #[allow(clippy::unwrap_used)] // looping over the valid indices |
| let curr = self.zvl_get(i).unwrap(); |
| if Self::get_cmp_get(prev, curr) != Ordering::Less { |
| return false; |
| } |
| prev = curr; |
| } |
| } |
| true |
| } |
| /// Check if this vector is empty |
| fn zvl_is_empty(&self) -> bool { |
| self.zvl_len() == 0 |
| } |
| |
| /// Construct a borrowed variant by borrowing from `&self`. |
| /// |
| /// This function behaves like `&'b self -> Self::SliceVariant<'b>`, |
| /// where `'b` is the lifetime of the reference to this object. |
| /// |
| /// Note: We rely on the compiler recognizing `'a` and `'b` as covariant and |
| /// casting `&'b Self<'a>` to `&'b Self<'b>` when this gets called, which works |
| /// out for `ZeroVec` and `VarZeroVec` containers just fine. |
| fn zvl_as_borrowed(&self) -> &Self::SliceVariant; |
| |
| /// Compare this type with a `Self::GetType`. This must produce the same result as |
| /// if `g` were converted to `Self` |
| #[inline] |
| fn t_cmp_get(t: &T, g: &Self::GetType) -> Ordering |
| where |
| T: Ord, |
| { |
| Self::zvl_get_as_t(g, |g| t.cmp(g)) |
| } |
| |
| /// Compare two values of `Self::GetType`. This must produce the same result as |
| /// if both `a` and `b` were converted to `Self` |
| #[inline] |
| fn get_cmp_get(a: &Self::GetType, b: &Self::GetType) -> Ordering |
| where |
| T: Ord, |
| { |
| Self::zvl_get_as_t(a, |a| Self::zvl_get_as_t(b, |b| a.cmp(b))) |
| } |
| |
| /// Obtain a reference to T, passed to a closure |
| /// |
| /// This uses a callback because it's not possible to return owned-or-borrowed |
| /// types without GATs |
| /// |
| /// Impls should guarantee that the callback function is be called exactly once. |
| fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R; |
| } |
| |
| /// Trait abstracting over [`ZeroVec`] and [`VarZeroVec`], for use in [`ZeroMap`](super::ZeroMap). **You |
| /// should not be implementing or calling this trait directly.** |
| /// |
| /// This trait augments [`ZeroVecLike`] with methods allowing for mutation of the underlying |
| /// vector for owned vector types. |
| /// |
| /// Methods are prefixed with `zvl_*` to avoid clashes with methods on the types themselves |
| pub trait MutableZeroVecLike<'a, T: ?Sized>: ZeroVecLike<T> { |
| /// The type returned by `Self::remove()` and `Self::replace()` |
| type OwnedType; |
| |
| /// Insert an element at `index` |
| fn zvl_insert(&mut self, index: usize, value: &T); |
| /// Remove the element at `index` (panicking if nonexistant) |
| fn zvl_remove(&mut self, index: usize) -> Self::OwnedType; |
| /// Replace the element at `index` with another one, returning the old element |
| fn zvl_replace(&mut self, index: usize, value: &T) -> Self::OwnedType; |
| /// Push an element to the end of this vector |
| fn zvl_push(&mut self, value: &T); |
| /// Create a new, empty vector, with given capacity |
| fn zvl_with_capacity(cap: usize) -> Self; |
| /// Remove all elements from the vector |
| fn zvl_clear(&mut self); |
| /// Reserve space for `addl` additional elements |
| fn zvl_reserve(&mut self, addl: usize); |
| /// Applies the permutation such that `before.zvl_get(permutation[i]) == after.zvl_get(i)`. |
| /// |
| /// # Panics |
| /// If `permutation` is not a valid permutation of length `zvl_len()`. |
| fn zvl_permute(&mut self, permutation: &mut [usize]); |
| |
| /// Convert an owned value to a borrowed T |
| fn owned_as_t(o: &Self::OwnedType) -> &T; |
| |
| /// Construct from the borrowed version of the type |
| /// |
| /// These are useful to ensure serialization parity between borrowed and owned versions |
| fn zvl_from_borrowed(b: &'a Self::SliceVariant) -> Self; |
| /// Extract the inner borrowed variant if possible. Returns `None` if the data is owned. |
| /// |
| /// This function behaves like `&'_ self -> Self::SliceVariant<'a>`, |
| /// where `'a` is the lifetime of this object's borrowed data. |
| /// |
| /// This function is similar to matching the `Borrowed` variant of `ZeroVec` |
| /// or `VarZeroVec`, returning the inner borrowed type. |
| fn zvl_as_borrowed_inner(&self) -> Option<&'a Self::SliceVariant>; |
| } |
| |
| impl<'a, T> ZeroVecLike<T> for ZeroVec<'a, T> |
| where |
| T: 'a + AsULE + Copy, |
| { |
| type GetType = T::ULE; |
| type SliceVariant = ZeroSlice<T>; |
| |
| fn zvl_new_borrowed() -> &'static Self::SliceVariant { |
| ZeroSlice::<T>::new_empty() |
| } |
| fn zvl_binary_search(&self, k: &T) -> Result<usize, usize> |
| where |
| T: Ord, |
| { |
| ZeroSlice::binary_search(self, k) |
| } |
| fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>> |
| where |
| T: Ord, |
| { |
| let zs: &ZeroSlice<T> = self; |
| zs.zvl_binary_search_in_range(k, range) |
| } |
| fn zvl_binary_search_by( |
| &self, |
| mut predicate: impl FnMut(&T) -> Ordering, |
| ) -> Result<usize, usize> { |
| ZeroSlice::binary_search_by(self, |probe| predicate(&probe)) |
| } |
| fn zvl_binary_search_in_range_by( |
| &self, |
| predicate: impl FnMut(&T) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| let zs: &ZeroSlice<T> = self; |
| zs.zvl_binary_search_in_range_by(predicate, range) |
| } |
| fn zvl_get(&self, index: usize) -> Option<&T::ULE> { |
| self.get_ule_ref(index) |
| } |
| fn zvl_len(&self) -> usize { |
| ZeroSlice::len(self) |
| } |
| fn zvl_as_borrowed(&self) -> &ZeroSlice<T> { |
| self |
| } |
| #[inline] |
| fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R { |
| f(&T::from_unaligned(*g)) |
| } |
| } |
| |
| impl<T> ZeroVecLike<T> for ZeroSlice<T> |
| where |
| T: AsULE + Copy, |
| { |
| type GetType = T::ULE; |
| type SliceVariant = ZeroSlice<T>; |
| |
| fn zvl_new_borrowed() -> &'static Self::SliceVariant { |
| ZeroSlice::<T>::new_empty() |
| } |
| fn zvl_binary_search(&self, k: &T) -> Result<usize, usize> |
| where |
| T: Ord, |
| { |
| ZeroSlice::binary_search(self, k) |
| } |
| fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>> |
| where |
| T: Ord, |
| { |
| let subslice = self.get_subslice(range)?; |
| Some(ZeroSlice::binary_search(subslice, k)) |
| } |
| fn zvl_binary_search_by( |
| &self, |
| mut predicate: impl FnMut(&T) -> Ordering, |
| ) -> Result<usize, usize> { |
| ZeroSlice::binary_search_by(self, |probe| predicate(&probe)) |
| } |
| fn zvl_binary_search_in_range_by( |
| &self, |
| mut predicate: impl FnMut(&T) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| let subslice = self.get_subslice(range)?; |
| Some(ZeroSlice::binary_search_by(subslice, |probe| { |
| predicate(&probe) |
| })) |
| } |
| fn zvl_get(&self, index: usize) -> Option<&T::ULE> { |
| self.get_ule_ref(index) |
| } |
| fn zvl_len(&self) -> usize { |
| ZeroSlice::len(self) |
| } |
| fn zvl_as_borrowed(&self) -> &ZeroSlice<T> { |
| self |
| } |
| |
| #[inline] |
| fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R { |
| f(&T::from_unaligned(*g)) |
| } |
| } |
| |
| impl<'a, T> MutableZeroVecLike<'a, T> for ZeroVec<'a, T> |
| where |
| T: AsULE + Copy + 'static, |
| { |
| type OwnedType = T; |
| fn zvl_insert(&mut self, index: usize, value: &T) { |
| self.with_mut(|v| v.insert(index, value.to_unaligned())) |
| } |
| fn zvl_remove(&mut self, index: usize) -> T { |
| T::from_unaligned(self.with_mut(|v| v.remove(index))) |
| } |
| fn zvl_replace(&mut self, index: usize, value: &T) -> T { |
| #[allow(clippy::indexing_slicing)] |
| let unaligned = self.with_mut(|vec| { |
| debug_assert!(index < vec.len()); |
| mem::replace(&mut vec[index], value.to_unaligned()) |
| }); |
| T::from_unaligned(unaligned) |
| } |
| fn zvl_push(&mut self, value: &T) { |
| self.with_mut(|v| v.push(value.to_unaligned())) |
| } |
| fn zvl_with_capacity(cap: usize) -> Self { |
| if cap == 0 { |
| ZeroVec::new() |
| } else { |
| ZeroVec::new_owned(Vec::with_capacity(cap)) |
| } |
| } |
| fn zvl_clear(&mut self) { |
| self.with_mut(|v| v.clear()) |
| } |
| fn zvl_reserve(&mut self, addl: usize) { |
| self.with_mut(|v| v.reserve(addl)) |
| } |
| |
| fn owned_as_t(o: &Self::OwnedType) -> &T { |
| o |
| } |
| |
| fn zvl_from_borrowed(b: &'a ZeroSlice<T>) -> Self { |
| b.as_zerovec() |
| } |
| fn zvl_as_borrowed_inner(&self) -> Option<&'a ZeroSlice<T>> { |
| self.as_maybe_borrowed() |
| } |
| |
| #[allow(clippy::indexing_slicing)] // documented panic |
| fn zvl_permute(&mut self, permutation: &mut [usize]) { |
| assert_eq!(permutation.len(), self.zvl_len()); |
| |
| let vec = self.to_mut_slice(); |
| |
| for cycle_start in 0..permutation.len() { |
| let mut curr = cycle_start; |
| let mut next = permutation[curr]; |
| |
| while next != cycle_start { |
| vec.swap(curr, next); |
| // Make curr a self-cycle so we don't use it as a cycle_start later |
| permutation[curr] = curr; |
| curr = next; |
| next = permutation[next]; |
| } |
| permutation[curr] = curr; |
| } |
| } |
| } |
| |
| impl<'a, T, F> ZeroVecLike<T> for VarZeroVec<'a, T, F> |
| where |
| T: VarULE, |
| T: ?Sized, |
| F: VarZeroVecFormat, |
| { |
| type GetType = T; |
| type SliceVariant = VarZeroSlice<T, F>; |
| |
| fn zvl_new_borrowed() -> &'static Self::SliceVariant { |
| VarZeroSlice::<T, F>::new_empty() |
| } |
| fn zvl_binary_search(&self, k: &T) -> Result<usize, usize> |
| where |
| T: Ord, |
| { |
| self.binary_search(k) |
| } |
| fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>> |
| where |
| T: Ord, |
| { |
| self.binary_search_in_range(k, range) |
| } |
| fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> { |
| self.binary_search_by(predicate) |
| } |
| fn zvl_binary_search_in_range_by( |
| &self, |
| predicate: impl FnMut(&T) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| self.binary_search_in_range_by(predicate, range) |
| } |
| fn zvl_get(&self, index: usize) -> Option<&T> { |
| self.get(index) |
| } |
| fn zvl_len(&self) -> usize { |
| self.len() |
| } |
| |
| fn zvl_as_borrowed(&self) -> &VarZeroSlice<T, F> { |
| self.as_slice() |
| } |
| |
| #[inline] |
| fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R { |
| f(g) |
| } |
| } |
| |
| impl<T, F> ZeroVecLike<T> for VarZeroSlice<T, F> |
| where |
| T: VarULE, |
| T: ?Sized, |
| F: VarZeroVecFormat, |
| { |
| type GetType = T; |
| type SliceVariant = VarZeroSlice<T, F>; |
| |
| fn zvl_new_borrowed() -> &'static Self::SliceVariant { |
| VarZeroSlice::<T, F>::new_empty() |
| } |
| fn zvl_binary_search(&self, k: &T) -> Result<usize, usize> |
| where |
| T: Ord, |
| { |
| self.binary_search(k) |
| } |
| fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>> |
| where |
| T: Ord, |
| { |
| self.binary_search_in_range(k, range) |
| } |
| fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> { |
| self.binary_search_by(predicate) |
| } |
| fn zvl_binary_search_in_range_by( |
| &self, |
| predicate: impl FnMut(&T) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| self.binary_search_in_range_by(predicate, range) |
| } |
| fn zvl_get(&self, index: usize) -> Option<&T> { |
| self.get(index) |
| } |
| fn zvl_len(&self) -> usize { |
| self.len() |
| } |
| |
| fn zvl_as_borrowed(&self) -> &VarZeroSlice<T, F> { |
| self |
| } |
| |
| #[inline] |
| fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R { |
| f(g) |
| } |
| } |
| |
| impl<'a, T, F> MutableZeroVecLike<'a, T> for VarZeroVec<'a, T, F> |
| where |
| T: VarULE, |
| T: ?Sized, |
| F: VarZeroVecFormat, |
| { |
| type OwnedType = Box<T>; |
| fn zvl_insert(&mut self, index: usize, value: &T) { |
| self.make_mut().insert(index, value) |
| } |
| fn zvl_remove(&mut self, index: usize) -> Box<T> { |
| let vec = self.make_mut(); |
| debug_assert!(index < vec.len()); |
| #[allow(clippy::unwrap_used)] |
| let old = vec.get(index).unwrap().to_boxed(); |
| vec.remove(index); |
| old |
| } |
| fn zvl_replace(&mut self, index: usize, value: &T) -> Box<T> { |
| let vec = self.make_mut(); |
| debug_assert!(index < vec.len()); |
| #[allow(clippy::unwrap_used)] |
| let old = vec.get(index).unwrap().to_boxed(); |
| vec.replace(index, value); |
| old |
| } |
| fn zvl_push(&mut self, value: &T) { |
| let len = self.len(); |
| self.make_mut().insert(len, value) |
| } |
| fn zvl_with_capacity(cap: usize) -> Self { |
| if cap == 0 { |
| VarZeroVec::new() |
| } else { |
| VarZeroVec::Owned(VarZeroVecOwned::with_capacity(cap)) |
| } |
| } |
| fn zvl_clear(&mut self) { |
| self.make_mut().clear() |
| } |
| fn zvl_reserve(&mut self, addl: usize) { |
| self.make_mut().reserve(addl) |
| } |
| |
| fn owned_as_t(o: &Self::OwnedType) -> &T { |
| o |
| } |
| |
| fn zvl_from_borrowed(b: &'a VarZeroSlice<T, F>) -> Self { |
| b.as_varzerovec() |
| } |
| fn zvl_as_borrowed_inner(&self) -> Option<&'a VarZeroSlice<T, F>> { |
| if let VarZeroVec::Borrowed(b) = *self { |
| Some(b) |
| } else { |
| None |
| } |
| } |
| |
| #[allow(clippy::unwrap_used)] // documented panic |
| fn zvl_permute(&mut self, permutation: &mut [usize]) { |
| assert_eq!(permutation.len(), self.zvl_len()); |
| |
| let mut result = VarZeroVecOwned::new(); |
| for &i in permutation.iter() { |
| result.push(self.get(i).unwrap()); |
| } |
| *self = VarZeroVec::Owned(result); |
| } |
| } |
| |
| impl<'a> ZeroVecLike<usize> for FlexZeroVec<'a> { |
| type GetType = [u8]; |
| type SliceVariant = FlexZeroSlice; |
| |
| fn zvl_new_borrowed() -> &'static Self::SliceVariant { |
| FlexZeroSlice::new_empty() |
| } |
| fn zvl_binary_search(&self, k: &usize) -> Result<usize, usize> { |
| FlexZeroSlice::binary_search(self, *k) |
| } |
| fn zvl_binary_search_in_range( |
| &self, |
| k: &usize, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| FlexZeroSlice::binary_search_in_range(self, *k, range) |
| } |
| fn zvl_binary_search_by( |
| &self, |
| mut predicate: impl FnMut(&usize) -> Ordering, |
| ) -> Result<usize, usize> { |
| FlexZeroSlice::binary_search_by(self, |probe| predicate(&probe)) |
| } |
| fn zvl_binary_search_in_range_by( |
| &self, |
| mut predicate: impl FnMut(&usize) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| FlexZeroSlice::binary_search_in_range_by(self, |probe| predicate(&probe), range) |
| } |
| fn zvl_get(&self, index: usize) -> Option<&[u8]> { |
| self.get_chunk(index) |
| } |
| fn zvl_len(&self) -> usize { |
| FlexZeroSlice::len(self) |
| } |
| |
| fn zvl_as_borrowed(&self) -> &FlexZeroSlice { |
| self |
| } |
| |
| #[inline] |
| fn zvl_get_as_t<R>(g: &[u8], f: impl FnOnce(&usize) -> R) -> R { |
| f(&crate::chunk_to_usize(g, g.len())) |
| } |
| } |
| |
| impl ZeroVecLike<usize> for FlexZeroSlice { |
| type GetType = [u8]; |
| type SliceVariant = FlexZeroSlice; |
| |
| fn zvl_new_borrowed() -> &'static Self::SliceVariant { |
| FlexZeroSlice::new_empty() |
| } |
| fn zvl_binary_search(&self, k: &usize) -> Result<usize, usize> { |
| FlexZeroSlice::binary_search(self, *k) |
| } |
| fn zvl_binary_search_in_range( |
| &self, |
| k: &usize, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| FlexZeroSlice::binary_search_in_range(self, *k, range) |
| } |
| fn zvl_binary_search_by( |
| &self, |
| mut predicate: impl FnMut(&usize) -> Ordering, |
| ) -> Result<usize, usize> { |
| FlexZeroSlice::binary_search_by(self, |probe| predicate(&probe)) |
| } |
| fn zvl_binary_search_in_range_by( |
| &self, |
| mut predicate: impl FnMut(&usize) -> Ordering, |
| range: Range<usize>, |
| ) -> Option<Result<usize, usize>> { |
| FlexZeroSlice::binary_search_in_range_by(self, |probe| predicate(&probe), range) |
| } |
| fn zvl_get(&self, index: usize) -> Option<&[u8]> { |
| self.get_chunk(index) |
| } |
| fn zvl_len(&self) -> usize { |
| FlexZeroSlice::len(self) |
| } |
| |
| fn zvl_as_borrowed(&self) -> &FlexZeroSlice { |
| self |
| } |
| |
| #[inline] |
| fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&usize) -> R) -> R { |
| f(&crate::chunk_to_usize(g, g.len())) |
| } |
| } |
| |
| impl<'a> MutableZeroVecLike<'a, usize> for FlexZeroVec<'a> { |
| type OwnedType = usize; |
| fn zvl_insert(&mut self, index: usize, value: &usize) { |
| self.to_mut().insert(index, *value) |
| } |
| fn zvl_remove(&mut self, index: usize) -> usize { |
| self.to_mut().remove(index) |
| } |
| fn zvl_replace(&mut self, index: usize, value: &usize) -> usize { |
| // TODO(#2028): Make this a single operation instead of two operations. |
| let mutable = self.to_mut(); |
| let old_value = mutable.remove(index); |
| mutable.insert(index, *value); |
| old_value |
| } |
| fn zvl_push(&mut self, value: &usize) { |
| self.to_mut().push(*value) |
| } |
| fn zvl_with_capacity(_cap: usize) -> Self { |
| // There is no `FlexZeroVec::with_capacity()` because it is variable-width |
| FlexZeroVec::Owned(FlexZeroVecOwned::new_empty()) |
| } |
| fn zvl_clear(&mut self) { |
| self.to_mut().clear() |
| } |
| fn zvl_reserve(&mut self, _addl: usize) { |
| // There is no `FlexZeroVec::reserve()` because it is variable-width |
| } |
| |
| fn owned_as_t(o: &Self::OwnedType) -> &usize { |
| o |
| } |
| |
| fn zvl_from_borrowed(b: &'a FlexZeroSlice) -> Self { |
| b.as_flexzerovec() |
| } |
| fn zvl_as_borrowed_inner(&self) -> Option<&'a FlexZeroSlice> { |
| if let FlexZeroVec::Borrowed(b) = *self { |
| Some(b) |
| } else { |
| None |
| } |
| } |
| |
| #[allow(clippy::unwrap_used)] // documented panic |
| fn zvl_permute(&mut self, permutation: &mut [usize]) { |
| assert_eq!(permutation.len(), self.zvl_len()); |
| *self = permutation.iter().map(|&i| self.get(i).unwrap()).collect(); |
| } |
| } |
| |
| #[cfg(test)] |
| mod test { |
| use super::*; |
| |
| #[test] |
| fn test_zerovec_binary_search_in_range() { |
| let zv: ZeroVec<u16> = ZeroVec::from_slice_or_alloc(&[11, 22, 33, 44, 55, 66, 77]); |
| |
| // Full range search |
| assert_eq!(zv.zvl_binary_search_in_range(&11, 0..7), Some(Ok(0))); |
| assert_eq!(zv.zvl_binary_search_in_range(&12, 0..7), Some(Err(1))); |
| assert_eq!(zv.zvl_binary_search_in_range(&44, 0..7), Some(Ok(3))); |
| assert_eq!(zv.zvl_binary_search_in_range(&45, 0..7), Some(Err(4))); |
| assert_eq!(zv.zvl_binary_search_in_range(&77, 0..7), Some(Ok(6))); |
| assert_eq!(zv.zvl_binary_search_in_range(&78, 0..7), Some(Err(7))); |
| |
| // Out-of-range search |
| assert_eq!(zv.zvl_binary_search_in_range(&44, 0..2), Some(Err(2))); |
| assert_eq!(zv.zvl_binary_search_in_range(&44, 5..7), Some(Err(0))); |
| |
| // Offset search |
| assert_eq!(zv.zvl_binary_search_in_range(&44, 2..5), Some(Ok(1))); |
| assert_eq!(zv.zvl_binary_search_in_range(&45, 2..5), Some(Err(2))); |
| |
| // Out-of-bounds |
| assert_eq!(zv.zvl_binary_search_in_range(&44, 0..100), None); |
| assert_eq!(zv.zvl_binary_search_in_range(&44, 100..200), None); |
| } |
| |
| #[test] |
| fn test_permute() { |
| let mut zv: ZeroVec<u16> = ZeroVec::from_slice_or_alloc(&[11, 22, 33, 44, 55, 66, 77]); |
| let mut permutation = vec![3, 2, 1, 0, 6, 5, 4]; |
| zv.zvl_permute(&mut permutation); |
| assert_eq!(&zv, &[44, 33, 22, 11, 77, 66, 55]); |
| |
| let mut vzv: VarZeroVec<str> = VarZeroVec::Owned( |
| VarZeroVecOwned::try_from_elements(&["11", "22", "33", "44", "55", "66", "77"]) |
| .unwrap(), |
| ); |
| let mut permutation = vec![3, 2, 1, 0, 6, 5, 4]; |
| vzv.zvl_permute(&mut permutation); |
| assert_eq!(&vzv, &["44", "33", "22", "11", "77", "66", "55"]); |
| |
| let mut fzv: FlexZeroVec = [11, 22, 33, 44, 55, 66, 77].into_iter().collect(); |
| let mut permutation = vec![3, 2, 1, 0, 6, 5, 4]; |
| fzv.zvl_permute(&mut permutation); |
| assert_eq!( |
| fzv.iter().collect::<Vec<_>>(), |
| [44, 33, 22, 11, 77, 66, 55].into_iter().collect::<Vec<_>>() |
| ); |
| } |
| } |
