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}
725