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;
pub trait ZeroVecLike<T: ?Sized> {
type GetType: ?Sized + 'static;
type SliceVariant: ZeroVecLike<T, GetType = Self::GetType> + ?Sized;
fn zvl_new_borrowed() -> &'static Self::SliceVariant;
fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
where
T: Ord;
fn zvl_binary_search_in_range(
&self,
k: &T,
range: Range<usize>,
) -> Option<Result<usize, usize>>
where
T: Ord;
fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize>;
fn zvl_binary_search_in_range_by(
&self,
predicate: impl FnMut(&T) -> Ordering,
range: Range<usize>,
) -> Option<Result<usize, usize>>;
fn zvl_get(&self, index: usize) -> Option<&Self::GetType>;
fn zvl_len(&self) -> usize;
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)] let curr = self.zvl_get(i).unwrap();
if Self::get_cmp_get(prev, curr) != Ordering::Less {
return false;
}
prev = curr;
}
}
true
}
fn zvl_is_empty(&self) -> bool {
self.zvl_len() == 0
}
fn zvl_as_borrowed(&self) -> &Self::SliceVariant;
#[inline]
fn t_cmp_get(t: &T, g: &Self::GetType) -> Ordering
where
T: Ord,
{
Self::zvl_get_as_t(g, |g| t.cmp(g))
}
#[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)))
}
fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R;
}
pub trait MutableZeroVecLike<'a, T: ?Sized>: ZeroVecLike<T> {
type OwnedType;
fn zvl_insert(&mut self, index: usize, value: &T);
fn zvl_remove(&mut self, index: usize) -> Self::OwnedType;
fn zvl_replace(&mut self, index: usize, value: &T) -> Self::OwnedType;
fn zvl_push(&mut self, value: &T);
fn zvl_with_capacity(cap: usize) -> Self;
fn zvl_clear(&mut self);
fn zvl_reserve(&mut self, addl: usize);
fn zvl_permute(&mut self, permutation: &mut [usize]);
fn owned_as_t(o: &Self::OwnedType) -> &T;
fn zvl_from_borrowed(b: &'a Self::SliceVariant) -> Self;
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)] 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);
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)] 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 {
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 {
FlexZeroVec::Owned(FlexZeroVecOwned::new_empty())
}
fn zvl_clear(&mut self) {
self.to_mut().clear()
}
fn zvl_reserve(&mut self, _addl: usize) {
}
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)] 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]);
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)));
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)));
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)));
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<_>>()
);
}
}