zerovec/map/
vecs.rs

Help
1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5use crate::ule::*;
6use crate::varzerovec::owned::VarZeroVecOwned;
7use crate::vecs::{FlexZeroSlice, FlexZeroVec, FlexZeroVecOwned, VarZeroVecFormat};
8use crate::{VarZeroSlice, VarZeroVec};
9use crate::{ZeroSlice, ZeroVec};
10use alloc::boxed::Box;
11use alloc::vec::Vec;
12use core::cmp::Ordering;
13use core::mem;
14use core::ops::Range;
15
16/// Trait abstracting over [`ZeroVec`] and [`VarZeroVec`], for use in [`ZeroMap`](super::ZeroMap). **You
17/// should not be implementing or calling this trait directly.**
18///
19/// The T type is the type received by [`Self::zvl_binary_search()`], as well as the one used
20/// for human-readable serialization.
21///
22/// Methods are prefixed with `zvl_*` to avoid clashes with methods on the types themselves
23pub trait ZeroVecLike<T: ?Sized> {
24    /// The type returned by `Self::get()`
25    type GetType: ?Sized + 'static;
26    /// A fully borrowed version of this
27    type SliceVariant: ZeroVecLike<T, GetType = Self::GetType> + ?Sized;
28
29    /// Create a new, empty borrowed variant
30    fn zvl_new_borrowed() -> &'static Self::SliceVariant;
31
32    /// Search for a key in a sorted vector, returns `Ok(index)` if found,
33    /// returns `Err(insert_index)` if not found, where `insert_index` is the
34    /// index where it should be inserted to maintain sort order.
35    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
36    where
37        T: Ord;
38    /// Search for a key within a certain range in a sorted vector.
39    /// Returns `None` if the range is out of bounds, and
40    /// `Ok` or `Err` in the same way as `zvl_binary_search`.
41    /// Indices are returned relative to the start of the range.
42    fn zvl_binary_search_in_range(
43        &self,
44        k: &T,
45        range: Range<usize>,
46    ) -> Option<Result<usize, usize>>
47    where
48        T: Ord;
49
50    /// Search for a key in a sorted vector by a predicate, returns `Ok(index)` if found,
51    /// returns `Err(insert_index)` if not found, where `insert_index` is the
52    /// index where it should be inserted to maintain sort order.
53    fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize>;
54    /// Search for a key within a certain range in a sorted vector by a predicate.
55    /// Returns `None` if the range is out of bounds, and
56    /// `Ok` or `Err` in the same way as `zvl_binary_search`.
57    /// Indices are returned relative to the start of the range.
58    fn zvl_binary_search_in_range_by(
59        &self,
60        predicate: impl FnMut(&T) -> Ordering,
61        range: Range<usize>,
62    ) -> Option<Result<usize, usize>>;
63
64    /// Get element at `index`
65    fn zvl_get(&self, index: usize) -> Option<&Self::GetType>;
66    /// The length of this vector
67    fn zvl_len(&self) -> usize;
68    /// Check if this vector is in ascending order according to `T`s `Ord` impl
69    fn zvl_is_ascending(&self) -> bool
70    where
71        T: Ord,
72    {
73        if let Some(first) = self.zvl_get(0) {
74            let mut prev = first;
75            for i in 1..self.zvl_len() {
76                #[allow(clippy::unwrap_used)] // looping over the valid indices
77                let curr = self.zvl_get(i).unwrap();
78                if Self::get_cmp_get(prev, curr) != Ordering::Less {
79                    return false;
80                }
81                prev = curr;
82            }
83        }
84        true
85    }
86    /// Check if this vector is empty
87    fn zvl_is_empty(&self) -> bool {
88        self.zvl_len() == 0
89    }
90
91    /// Construct a borrowed variant by borrowing from `&self`.
92    ///
93    /// This function behaves like `&'b self -> Self::SliceVariant<'b>`,
94    /// where `'b` is the lifetime of the reference to this object.
95    ///
96    /// Note: We rely on the compiler recognizing `'a` and `'b` as covariant and
97    /// casting `&'b Self<'a>` to `&'b Self<'b>` when this gets called, which works
98    /// out for `ZeroVec` and `VarZeroVec` containers just fine.
99    fn zvl_as_borrowed(&self) -> &Self::SliceVariant;
100
101    /// Compare this type with a `Self::GetType`. This must produce the same result as
102    /// if `g` were converted to `Self`
103    #[inline]
104    fn t_cmp_get(t: &T, g: &Self::GetType) -> Ordering
105    where
106        T: Ord,
107    {
108        Self::zvl_get_as_t(g, |g| t.cmp(g))
109    }
110
111    /// Compare two values of `Self::GetType`. This must produce the same result as
112    /// if both `a` and `b` were converted to `Self`
113    #[inline]
114    fn get_cmp_get(a: &Self::GetType, b: &Self::GetType) -> Ordering
115    where
116        T: Ord,
117    {
118        Self::zvl_get_as_t(a, |a| Self::zvl_get_as_t(b, |b| a.cmp(b)))
119    }
120
121    /// Obtain a reference to T, passed to a closure
122    ///
123    /// This uses a callback because it's not possible to return owned-or-borrowed
124    /// types without GATs
125    ///
126    /// Impls should guarantee that the callback function is be called exactly once.
127    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R;
128}
129
130/// Trait abstracting over [`ZeroVec`] and [`VarZeroVec`], for use in [`ZeroMap`](super::ZeroMap). **You
131/// should not be implementing or calling this trait directly.**
132///
133/// This trait augments [`ZeroVecLike`] with methods allowing for mutation of the underlying
134/// vector for owned vector types.
135///
136/// Methods are prefixed with `zvl_*` to avoid clashes with methods on the types themselves
137pub trait MutableZeroVecLike<'a, T: ?Sized>: ZeroVecLike<T> {
138    /// The type returned by `Self::remove()` and `Self::replace()`
139    type OwnedType;
140
141    /// Insert an element at `index`
142    fn zvl_insert(&mut self, index: usize, value: &T);
143    /// Remove the element at `index` (panicking if nonexistant)
144    fn zvl_remove(&mut self, index: usize) -> Self::OwnedType;
145    /// Replace the element at `index` with another one, returning the old element
146    fn zvl_replace(&mut self, index: usize, value: &T) -> Self::OwnedType;
147    /// Push an element to the end of this vector
148    fn zvl_push(&mut self, value: &T);
149    /// Create a new, empty vector, with given capacity
150    fn zvl_with_capacity(cap: usize) -> Self;
151    /// Remove all elements from the vector
152    fn zvl_clear(&mut self);
153    /// Reserve space for `addl` additional elements
154    fn zvl_reserve(&mut self, addl: usize);
155    /// Applies the permutation such that `before.zvl_get(permutation[i]) == after.zvl_get(i)`.
156    ///
157    /// # Panics
158    /// If `permutation` is not a valid permutation of length `zvl_len()`.
159    fn zvl_permute(&mut self, permutation: &mut [usize]);
160
161    /// Convert an owned value to a borrowed T
162    fn owned_as_t(o: &Self::OwnedType) -> &T;
163
164    /// Construct from the borrowed version of the type
165    ///
166    /// These are useful to ensure serialization parity between borrowed and owned versions
167    fn zvl_from_borrowed(b: &'a Self::SliceVariant) -> Self;
168    /// Extract the inner borrowed variant if possible. Returns `None` if the data is owned.
169    ///
170    /// This function behaves like `&'_ self -> Self::SliceVariant<'a>`,
171    /// where `'a` is the lifetime of this object's borrowed data.
172    ///
173    /// This function is similar to matching the `Borrowed` variant of `ZeroVec`
174    /// or `VarZeroVec`, returning the inner borrowed type.
175    fn zvl_as_borrowed_inner(&self) -> Option<&'a Self::SliceVariant>;
176}
177
178impl<'a, T> ZeroVecLike<T> for ZeroVec<'a, T>
179where
180    T: 'a + AsULE + Copy,
181{
182    type GetType = T::ULE;
183    type SliceVariant = ZeroSlice<T>;
184
185    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
186        ZeroSlice::<T>::new_empty()
187    }
188    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
189    where
190        T: Ord,
191    {
192        ZeroSlice::binary_search(self, k)
193    }
194    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
195    where
196        T: Ord,
197    {
198        let zs: &ZeroSlice<T> = self;
199        zs.zvl_binary_search_in_range(k, range)
200    }
201    fn zvl_binary_search_by(
202        &self,
203        mut predicate: impl FnMut(&T) -> Ordering,
204    ) -> Result<usize, usize> {
205        ZeroSlice::binary_search_by(self, |probe| predicate(&probe))
206    }
207    fn zvl_binary_search_in_range_by(
208        &self,
209        predicate: impl FnMut(&T) -> Ordering,
210        range: Range<usize>,
211    ) -> Option<Result<usize, usize>> {
212        let zs: &ZeroSlice<T> = self;
213        zs.zvl_binary_search_in_range_by(predicate, range)
214    }
215    fn zvl_get(&self, index: usize) -> Option<&T::ULE> {
216        self.get_ule_ref(index)
217    }
218    fn zvl_len(&self) -> usize {
219        ZeroSlice::len(self)
220    }
221    fn zvl_as_borrowed(&self) -> &ZeroSlice<T> {
222        self
223    }
224    #[inline]
225    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
226        f(&T::from_unaligned(*g))
227    }
228}
229
230impl<T> ZeroVecLike<T> for ZeroSlice<T>
231where
232    T: AsULE + Copy,
233{
234    type GetType = T::ULE;
235    type SliceVariant = ZeroSlice<T>;
236
237    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
238        ZeroSlice::<T>::new_empty()
239    }
240    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
241    where
242        T: Ord,
243    {
244        ZeroSlice::binary_search(self, k)
245    }
246    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
247    where
248        T: Ord,
249    {
250        let subslice = self.get_subslice(range)?;
251        Some(ZeroSlice::binary_search(subslice, k))
252    }
253    fn zvl_binary_search_by(
254        &self,
255        mut predicate: impl FnMut(&T) -> Ordering,
256    ) -> Result<usize, usize> {
257        ZeroSlice::binary_search_by(self, |probe| predicate(&probe))
258    }
259    fn zvl_binary_search_in_range_by(
260        &self,
261        mut predicate: impl FnMut(&T) -> Ordering,
262        range: Range<usize>,
263    ) -> Option<Result<usize, usize>> {
264        let subslice = self.get_subslice(range)?;
265        Some(ZeroSlice::binary_search_by(subslice, |probe| {
266            predicate(&probe)
267        }))
268    }
269    fn zvl_get(&self, index: usize) -> Option<&T::ULE> {
270        self.get_ule_ref(index)
271    }
272    fn zvl_len(&self) -> usize {
273        ZeroSlice::len(self)
274    }
275    fn zvl_as_borrowed(&self) -> &ZeroSlice<T> {
276        self
277    }
278
279    #[inline]
280    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
281        f(&T::from_unaligned(*g))
282    }
283}
284
285impl<'a, T> MutableZeroVecLike<'a, T> for ZeroVec<'a, T>
286where
287    T: AsULE + Copy + 'static,
288{
289    type OwnedType = T;
290    fn zvl_insert(&mut self, index: usize, value: &T) {
291        self.with_mut(|v| v.insert(index, value.to_unaligned()))
292    }
293    fn zvl_remove(&mut self, index: usize) -> T {
294        T::from_unaligned(self.with_mut(|v| v.remove(index)))
295    }
296    fn zvl_replace(&mut self, index: usize, value: &T) -> T {
297        #[allow(clippy::indexing_slicing)]
298        let unaligned = self.with_mut(|vec| {
299            debug_assert!(index < vec.len());
300            mem::replace(&mut vec[index], value.to_unaligned())
301        });
302        T::from_unaligned(unaligned)
303    }
304    fn zvl_push(&mut self, value: &T) {
305        self.with_mut(|v| v.push(value.to_unaligned()))
306    }
307    fn zvl_with_capacity(cap: usize) -> Self {
308        if cap == 0 {
309            ZeroVec::new()
310        } else {
311            ZeroVec::new_owned(Vec::with_capacity(cap))
312        }
313    }
314    fn zvl_clear(&mut self) {
315        self.with_mut(|v| v.clear())
316    }
317    fn zvl_reserve(&mut self, addl: usize) {
318        self.with_mut(|v| v.reserve(addl))
319    }
320
321    fn owned_as_t(o: &Self::OwnedType) -> &T {
322        o
323    }
324
325    fn zvl_from_borrowed(b: &'a ZeroSlice<T>) -> Self {
326        b.as_zerovec()
327    }
328    fn zvl_as_borrowed_inner(&self) -> Option<&'a ZeroSlice<T>> {
329        self.as_maybe_borrowed()
330    }
331
332    #[allow(clippy::indexing_slicing)] // documented panic
333    fn zvl_permute(&mut self, permutation: &mut [usize]) {
334        assert_eq!(permutation.len(), self.zvl_len());
335
336        let vec = self.to_mut_slice();
337
338        for cycle_start in 0..permutation.len() {
339            let mut curr = cycle_start;
340            let mut next = permutation[curr];
341
342            while next != cycle_start {
343                vec.swap(curr, next);
344                // Make curr a self-cycle so we don't use it as a cycle_start later
345                permutation[curr] = curr;
346                curr = next;
347                next = permutation[next];
348            }
349            permutation[curr] = curr;
350        }
351    }
352}
353
354impl<'a, T, F> ZeroVecLike<T> for VarZeroVec<'a, T, F>
355where
356    T: VarULE,
357    T: ?Sized,
358    F: VarZeroVecFormat,
359{
360    type GetType = T;
361    type SliceVariant = VarZeroSlice<T, F>;
362
363    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
364        VarZeroSlice::<T, F>::new_empty()
365    }
366    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
367    where
368        T: Ord,
369    {
370        self.binary_search(k)
371    }
372    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
373    where
374        T: Ord,
375    {
376        self.binary_search_in_range(k, range)
377    }
378    fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> {
379        self.binary_search_by(predicate)
380    }
381    fn zvl_binary_search_in_range_by(
382        &self,
383        predicate: impl FnMut(&T) -> Ordering,
384        range: Range<usize>,
385    ) -> Option<Result<usize, usize>> {
386        self.binary_search_in_range_by(predicate, range)
387    }
388    fn zvl_get(&self, index: usize) -> Option<&T> {
389        self.get(index)
390    }
391    fn zvl_len(&self) -> usize {
392        self.len()
393    }
394
395    fn zvl_as_borrowed(&self) -> &VarZeroSlice<T, F> {
396        self.as_slice()
397    }
398
399    #[inline]
400    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
401        f(g)
402    }
403}
404
405impl<T, F> ZeroVecLike<T> for VarZeroSlice<T, F>
406where
407    T: VarULE,
408    T: ?Sized,
409    F: VarZeroVecFormat,
410{
411    type GetType = T;
412    type SliceVariant = VarZeroSlice<T, F>;
413
414    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
415        VarZeroSlice::<T, F>::new_empty()
416    }
417    fn zvl_binary_search(&self, k: &T) -> Result<usize, usize>
418    where
419        T: Ord,
420    {
421        self.binary_search(k)
422    }
423    fn zvl_binary_search_in_range(&self, k: &T, range: Range<usize>) -> Option<Result<usize, usize>>
424    where
425        T: Ord,
426    {
427        self.binary_search_in_range(k, range)
428    }
429    fn zvl_binary_search_by(&self, predicate: impl FnMut(&T) -> Ordering) -> Result<usize, usize> {
430        self.binary_search_by(predicate)
431    }
432    fn zvl_binary_search_in_range_by(
433        &self,
434        predicate: impl FnMut(&T) -> Ordering,
435        range: Range<usize>,
436    ) -> Option<Result<usize, usize>> {
437        self.binary_search_in_range_by(predicate, range)
438    }
439    fn zvl_get(&self, index: usize) -> Option<&T> {
440        self.get(index)
441    }
442    fn zvl_len(&self) -> usize {
443        self.len()
444    }
445
446    fn zvl_as_borrowed(&self) -> &VarZeroSlice<T, F> {
447        self
448    }
449
450    #[inline]
451    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&T) -> R) -> R {
452        f(g)
453    }
454}
455
456impl<'a, T, F> MutableZeroVecLike<'a, T> for VarZeroVec<'a, T, F>
457where
458    T: VarULE,
459    T: ?Sized,
460    F: VarZeroVecFormat,
461{
462    type OwnedType = Box<T>;
463    fn zvl_insert(&mut self, index: usize, value: &T) {
464        self.make_mut().insert(index, value)
465    }
466    fn zvl_remove(&mut self, index: usize) -> Box<T> {
467        let vec = self.make_mut();
468        debug_assert!(index < vec.len());
469        #[allow(clippy::unwrap_used)]
470        let old = vec.get(index).unwrap().to_boxed();
471        vec.remove(index);
472        old
473    }
474    fn zvl_replace(&mut self, index: usize, value: &T) -> Box<T> {
475        let vec = self.make_mut();
476        debug_assert!(index < vec.len());
477        #[allow(clippy::unwrap_used)]
478        let old = vec.get(index).unwrap().to_boxed();
479        vec.replace(index, value);
480        old
481    }
482    fn zvl_push(&mut self, value: &T) {
483        let len = self.len();
484        self.make_mut().insert(len, value)
485    }
486    fn zvl_with_capacity(cap: usize) -> Self {
487        if cap == 0 {
488            VarZeroVec::new()
489        } else {
490            VarZeroVec::Owned(VarZeroVecOwned::with_capacity(cap))
491        }
492    }
493    fn zvl_clear(&mut self) {
494        self.make_mut().clear()
495    }
496    fn zvl_reserve(&mut self, addl: usize) {
497        self.make_mut().reserve(addl)
498    }
499
500    fn owned_as_t(o: &Self::OwnedType) -> &T {
501        o
502    }
503
504    fn zvl_from_borrowed(b: &'a VarZeroSlice<T, F>) -> Self {
505        b.as_varzerovec()
506    }
507    fn zvl_as_borrowed_inner(&self) -> Option<&'a VarZeroSlice<T, F>> {
508        if let VarZeroVec::Borrowed(b) = *self {
509            Some(b)
510        } else {
511            None
512        }
513    }
514
515    #[allow(clippy::unwrap_used)] // documented panic
516    fn zvl_permute(&mut self, permutation: &mut [usize]) {
517        assert_eq!(permutation.len(), self.zvl_len());
518
519        let mut result = VarZeroVecOwned::new();
520        for &i in permutation.iter() {
521            result.push(self.get(i).unwrap());
522        }
523        *self = VarZeroVec::Owned(result);
524    }
525}
526
527impl<'a> ZeroVecLike<usize> for FlexZeroVec<'a> {
528    type GetType = [u8];
529    type SliceVariant = FlexZeroSlice;
530
531    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
532        FlexZeroSlice::new_empty()
533    }
534    fn zvl_binary_search(&self, k: &usize) -> Result<usize, usize> {
535        FlexZeroSlice::binary_search(self, *k)
536    }
537    fn zvl_binary_search_in_range(
538        &self,
539        k: &usize,
540        range: Range<usize>,
541    ) -> Option<Result<usize, usize>> {
542        FlexZeroSlice::binary_search_in_range(self, *k, range)
543    }
544    fn zvl_binary_search_by(
545        &self,
546        mut predicate: impl FnMut(&usize) -> Ordering,
547    ) -> Result<usize, usize> {
548        FlexZeroSlice::binary_search_by(self, |probe| predicate(&probe))
549    }
550    fn zvl_binary_search_in_range_by(
551        &self,
552        mut predicate: impl FnMut(&usize) -> Ordering,
553        range: Range<usize>,
554    ) -> Option<Result<usize, usize>> {
555        FlexZeroSlice::binary_search_in_range_by(self, |probe| predicate(&probe), range)
556    }
557    fn zvl_get(&self, index: usize) -> Option<&[u8]> {
558        self.get_chunk(index)
559    }
560    fn zvl_len(&self) -> usize {
561        FlexZeroSlice::len(self)
562    }
563
564    fn zvl_as_borrowed(&self) -> &FlexZeroSlice {
565        self
566    }
567
568    #[inline]
569    fn zvl_get_as_t<R>(g: &[u8], f: impl FnOnce(&usize) -> R) -> R {
570        f(&crate::chunk_to_usize(g, g.len()))
571    }
572}
573
574impl ZeroVecLike<usize> for FlexZeroSlice {
575    type GetType = [u8];
576    type SliceVariant = FlexZeroSlice;
577
578    fn zvl_new_borrowed() -> &'static Self::SliceVariant {
579        FlexZeroSlice::new_empty()
580    }
581    fn zvl_binary_search(&self, k: &usize) -> Result<usize, usize> {
582        FlexZeroSlice::binary_search(self, *k)
583    }
584    fn zvl_binary_search_in_range(
585        &self,
586        k: &usize,
587        range: Range<usize>,
588    ) -> Option<Result<usize, usize>> {
589        FlexZeroSlice::binary_search_in_range(self, *k, range)
590    }
591    fn zvl_binary_search_by(
592        &self,
593        mut predicate: impl FnMut(&usize) -> Ordering,
594    ) -> Result<usize, usize> {
595        FlexZeroSlice::binary_search_by(self, |probe| predicate(&probe))
596    }
597    fn zvl_binary_search_in_range_by(
598        &self,
599        mut predicate: impl FnMut(&usize) -> Ordering,
600        range: Range<usize>,
601    ) -> Option<Result<usize, usize>> {
602        FlexZeroSlice::binary_search_in_range_by(self, |probe| predicate(&probe), range)
603    }
604    fn zvl_get(&self, index: usize) -> Option<&[u8]> {
605        self.get_chunk(index)
606    }
607    fn zvl_len(&self) -> usize {
608        FlexZeroSlice::len(self)
609    }
610
611    fn zvl_as_borrowed(&self) -> &FlexZeroSlice {
612        self
613    }
614
615    #[inline]
616    fn zvl_get_as_t<R>(g: &Self::GetType, f: impl FnOnce(&usize) -> R) -> R {
617        f(&crate::chunk_to_usize(g, g.len()))
618    }
619}
620
621impl<'a> MutableZeroVecLike<'a, usize> for FlexZeroVec<'a> {
622    type OwnedType = usize;
623    fn zvl_insert(&mut self, index: usize, value: &usize) {
624        self.to_mut().insert(index, *value)
625    }
626    fn zvl_remove(&mut self, index: usize) -> usize {
627        self.to_mut().remove(index)
628    }
629    fn zvl_replace(&mut self, index: usize, value: &usize) -> usize {
630        // TODO(#2028): Make this a single operation instead of two operations.
631        let mutable = self.to_mut();
632        let old_value = mutable.remove(index);
633        mutable.insert(index, *value);
634        old_value
635    }
636    fn zvl_push(&mut self, value: &usize) {
637        self.to_mut().push(*value)
638    }
639    fn zvl_with_capacity(_cap: usize) -> Self {
640        // There is no `FlexZeroVec::with_capacity()` because it is variable-width
641        FlexZeroVec::Owned(FlexZeroVecOwned::new_empty())
642    }
643    fn zvl_clear(&mut self) {
644        self.to_mut().clear()
645    }
646    fn zvl_reserve(&mut self, _addl: usize) {
647        // There is no `FlexZeroVec::reserve()` because it is variable-width
648    }
649
650    fn owned_as_t(o: &Self::OwnedType) -> &usize {
651        o
652    }
653
654    fn zvl_from_borrowed(b: &'a FlexZeroSlice) -> Self {
655        b.as_flexzerovec()
656    }
657    fn zvl_as_borrowed_inner(&self) -> Option<&'a FlexZeroSlice> {
658        if let FlexZeroVec::Borrowed(b) = *self {
659            Some(b)
660        } else {
661            None
662        }
663    }
664
665    #[allow(clippy::unwrap_used)] // documented panic
666    fn zvl_permute(&mut self, permutation: &mut [usize]) {
667        assert_eq!(permutation.len(), self.zvl_len());
668        *self = permutation.iter().map(|&i| self.get(i).unwrap()).collect();
669    }
670}
671
672#[cfg(test)]
673mod test {
674    use super::*;
675
676    #[test]
677    fn test_zerovec_binary_search_in_range() {
678        let zv: ZeroVec<u16> = ZeroVec::from_slice_or_alloc(&[11, 22, 33, 44, 55, 66, 77]);
679
680        // Full range search
681        assert_eq!(zv.zvl_binary_search_in_range(&11, 0..7), Some(Ok(0)));
682        assert_eq!(zv.zvl_binary_search_in_range(&12, 0..7), Some(Err(1)));
683        assert_eq!(zv.zvl_binary_search_in_range(&44, 0..7), Some(Ok(3)));
684        assert_eq!(zv.zvl_binary_search_in_range(&45, 0..7), Some(Err(4)));
685        assert_eq!(zv.zvl_binary_search_in_range(&77, 0..7), Some(Ok(6)));
686        assert_eq!(zv.zvl_binary_search_in_range(&78, 0..7), Some(Err(7)));
687
688        // Out-of-range search
689        assert_eq!(zv.zvl_binary_search_in_range(&44, 0..2), Some(Err(2)));
690        assert_eq!(zv.zvl_binary_search_in_range(&44, 5..7), Some(Err(0)));
691
692        // Offset search
693        assert_eq!(zv.zvl_binary_search_in_range(&44, 2..5), Some(Ok(1)));
694        assert_eq!(zv.zvl_binary_search_in_range(&45, 2..5), Some(Err(2)));
695
696        // Out-of-bounds
697        assert_eq!(zv.zvl_binary_search_in_range(&44, 0..100), None);
698        assert_eq!(zv.zvl_binary_search_in_range(&44, 100..200), None);
699    }
700
701    #[test]
702    fn test_permute() {
703        let mut zv: ZeroVec<u16> = ZeroVec::from_slice_or_alloc(&[11, 22, 33, 44, 55, 66, 77]);
704        let mut permutation = vec![3, 2, 1, 0, 6, 5, 4];
705        zv.zvl_permute(&mut permutation);
706        assert_eq!(&zv, &[44, 33, 22, 11, 77, 66, 55]);
707
708        let mut vzv: VarZeroVec<str> = VarZeroVec::Owned(
709            VarZeroVecOwned::try_from_elements(&["11", "22", "33", "44", "55", "66", "77"])
710                .unwrap(),
711        );
712        let mut permutation = vec![3, 2, 1, 0, 6, 5, 4];
713        vzv.zvl_permute(&mut permutation);
714        assert_eq!(&vzv, &["44", "33", "22", "11", "77", "66", "55"]);
715
716        let mut fzv: FlexZeroVec = [11, 22, 33, 44, 55, 66, 77].into_iter().collect();
717        let mut permutation = vec![3, 2, 1, 0, 6, 5, 4];
718        fzv.zvl_permute(&mut permutation);
719        assert_eq!(
720            fzv.iter().collect::<Vec<_>>(),
721            [44, 33, 22, 11, 77, 66, 55].into_iter().collect::<Vec<_>>()
722        );
723    }
724}
zerovec/map/vecs.rs

zerovec/map/
vecs.rs
