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

zerovec/map/
vecs.rs
