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 | |
5 | use crate::ule::*; |
6 | use crate::varzerovec::owned::VarZeroVecOwned; |
7 | use crate::vecs::{FlexZeroSlice, FlexZeroVec, FlexZeroVecOwned, VarZeroVecFormat}; |
8 | use crate::{VarZeroSlice, VarZeroVec}; |
9 | use crate::{ZeroSlice, ZeroVec}; |
10 | use alloc::boxed::Box; |
11 | use alloc::vec::Vec; |
12 | use core::cmp::Ordering; |
13 | use core::mem; |
14 | use 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 |
23 | pub 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 |
137 | pub 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 | |
178 | impl<'a, T> ZeroVecLike<T> for ZeroVec<'a, T> |
179 | where |
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 | |
230 | impl<T> ZeroVecLike<T> for ZeroSlice<T> |
231 | where |
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 | |
285 | impl<'a, T> MutableZeroVecLike<'a, T> for ZeroVec<'a, T> |
286 | where |
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 | |
354 | impl<'a, T, F> ZeroVecLike<T> for VarZeroVec<'a, T, F> |
355 | where |
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 | |
405 | impl<T, F> ZeroVecLike<T> for VarZeroSlice<T, F> |
406 | where |
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 | |
456 | impl<'a, T, F> MutableZeroVecLike<'a, T> for VarZeroVec<'a, T, F> |
457 | where |
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 | |
527 | impl<'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 | |
574 | impl 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 | |
621 | impl<'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)] |
673 | mod 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 | |