Source code
Revision control
Copy as Markdown
Other Tools
// This file is part of ICU4X. For terms of use, please see the file
// called LICENSE at the top level of the ICU4X source tree
use super::*;
use alloc::vec::Vec;
type MapF<K, V> = fn(&(K, V)) -> (&K, &V);
#[inline]
fn map_f<K, V>(input: &(K, V)) -> (&K, &V) {
(&input.0, &input.1)
}
type MapFMut<K, V> = fn(&mut (K, V)) -> (&K, &mut V);
#[inline]
fn map_f_mut<K, V>(input: &mut (K, V)) -> (&K, &mut V) {
(&input.0, &mut input.1)
}
impl<K, V> StoreConstEmpty<K, V> for Vec<(K, V)> {
const EMPTY: Vec<(K, V)> = Vec::new();
}
impl<K, V> Store<K, V> for Vec<(K, V)> {
#[inline]
fn lm_len(&self) -> usize {
self.as_slice().len()
}
#[inline]
fn lm_is_empty(&self) -> bool {
self.as_slice().is_empty()
}
#[inline]
fn lm_get(&self, index: usize) -> Option<(&K, &V)> {
self.as_slice().get(index).map(map_f)
}
#[inline]
fn lm_last(&self) -> Option<(&K, &V)> {
self.as_slice().last().map(map_f)
}
#[inline]
fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize>
where
F: FnMut(&K) -> Ordering,
{
self.as_slice().binary_search_by(|(k, _)| cmp(k))
}
}
impl<K, V> StoreSlice<K, V> for Vec<(K, V)> {
type Slice = [(K, V)];
fn lm_get_range(&self, range: Range<usize>) -> Option<&Self::Slice> {
self.get(range)
}
}
impl<K, V> StoreMut<K, V> for Vec<(K, V)> {
#[inline]
fn lm_with_capacity(capacity: usize) -> Self {
Self::with_capacity(capacity)
}
#[inline]
fn lm_reserve(&mut self, additional: usize) {
self.reserve(additional)
}
#[inline]
fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
self.as_mut_slice().get_mut(index).map(map_f_mut)
}
#[inline]
fn lm_push(&mut self, key: K, value: V) {
self.push((key, value))
}
#[inline]
fn lm_insert(&mut self, index: usize, key: K, value: V) {
self.insert(index, (key, value))
}
#[inline]
fn lm_remove(&mut self, index: usize) -> (K, V) {
self.remove(index)
}
#[inline]
fn lm_clear(&mut self) {
self.clear()
}
}
impl<K: Ord, V> StoreBulkMut<K, V> for Vec<(K, V)> {
#[inline]
fn lm_retain<F>(&mut self, mut predicate: F)
where
F: FnMut(&K, &V) -> bool,
{
self.retain(|(k, v)| predicate(k, v))
}
/// Extends this store with items from an iterator.
///
/// It uses a two-pass (sort + dedup) approach to avoid any potential quadratic costs.
///
/// The asymptotic worst case complexity is O((n + m) log(n + m)), where `n`
/// is the number of elements already in `self` and `m` is the number of elements
/// in the iterator. The best case complexity is O(m), when the input iterator is
/// already sorted, keys aren't duplicated and all keys sort after the existing ones.
#[inline]
fn lm_extend<I>(&mut self, iter: I)
where
I: IntoIterator<Item = (K, V)>,
K: Ord,
{
// First N elements in self that are already sorted and not duplicated.
let mut sorted_len = self.len();
// Use Vec::extend as it has a specialized code for slice and trusted-len iterators.
self.extend(iter);
// `sorted_len` is the length of the sorted run before extension
// window slice `w` is guaranteed to have a length of 2.
#[allow(clippy::indexing_slicing)]
{
// Count new elements that are sorted and non-duplicated.
// Starting from the end of the existing sorted run, if any.
// Thus, start the slice at sorted_len.saturating_sub(1).
sorted_len += self[sorted_len.saturating_sub(1)..]
.windows(2)
.take_while(|w| w[0].0 < w[1].0)
.count();
}
// `windows(2)` only yields `slice len - 1` times, or none if the slice is empty.
// In other words, the first extended element of the slice won't be counted as sorted
// if self was initially empty (sorted_len == 0). We adjust this by adding 1 if the
// original slice was empty but became not empty after extend.
sorted_len += (sorted_len == 0 && !self.is_empty()) as usize;
// If everything was in order, we're done
if sorted_len >= self.len() {
return;
}
// Use stable sort to keep relative order of duplicates.
self.sort_by(|a, b| a.0.cmp(&b.0));
// Deduplicate by keeping the last element of the run in the first slice.
let (dedup, _merged_dup) = partition_dedup_by(self);
sorted_len = dedup.len();
self.truncate(sorted_len);
}
}
/// Moves all but the _last_ of consecutive elements to the end of the slice satisfying
/// equality on K.
///
/// Returns two slices. The first contains no consecutive repeated elements.
/// The second contains all the duplicates in no specified order.
///
/// This is based on std::slice::partition_dedup_by (currently unstable) but retains the
/// _last_ element of the duplicate run in the first slice (instead of first).
#[inline]
#[allow(clippy::type_complexity)]
fn partition_dedup_by<K: Eq, V>(v: &mut [(K, V)]) -> (&mut [(K, V)], &mut [(K, V)]) {
// Although we have a mutable reference to `self`, we cannot make
// *arbitrary* changes. The comparison could panic, so we
// must ensure that the slice is in a valid state at all times.
//
// The way that we handle this is by using swaps; we iterate
// over all the elements, swapping as we go so that at the end
// the elements we wish to keep are in the front, and those we
// wish to reject are at the back. We can then split the slice.
// This operation is still `O(n)`.
//
// Example:
// Assume (K, V) is (char, u8):
//
// We start in this state, where `r` represents "next
// read" and `w` represents "next_write".
//
// r
// | a,0 | b,0 | b,1 | c,0 | d,0 | d,1 |
// w
//
// Comparing self[r] against self[w-1], this is not a duplicate, so
// we swap self[r] and self[w] (no effect as r==w) and then increment both
// r and w, leaving us with:
//
// r
// | a,0 | b,0 | b,1 | c,0 | d,0 | d,0 |
// w
//
// Comparing self[r] against self[w-1], this value is a duplicate,
// we swap self[r] and self[w-1] and then increment `r`:
//
// r
// | a,0 | b,1 | b,0 | c,0 | d,0 | d,1 |
// w
//
// Comparing self[r] against self[w-1], this is not a duplicate,
// so swap self[r] and self[w] and advance r and w:
//
// r
// | a,0 | b,1 | c,0 | b,0 | d,0 | d,1 |
// w
//
// Comparing self[r] against self[w-1], this is not a duplicate,
// so swap self[r] and self[w] and advance r and w:
//
// r
// | a,0 | b,1 | c,0 | d,0 | b,0 | d,1 |
// w
//
// Comparing self[r] against self[w-1], this value is a duplicate,
// we swap self[r] and self[w-1] and then increment `r`:
// r
// | a,0 | b,1 | c,0 | d,1 | b,0 | d,0 |
// w
//
// End of slice, as r > len. Split at w.
if v.len() <= 1 {
return (v, &mut []);
}
let mut read_idx: usize = 1;
let mut write_idx: usize = 1;
while let Some((before_read, [read, ..])) = v.split_at_mut_checked(read_idx) {
// First, `read_idx >= write_idx` is always true as `read_idx` is always incremented
// whereas `write_idx` is only incremented when a distinct element is found.
// Second, before_read is always at least 1 length due to read_idx being initialized to 1.
// Thus it is safe to index before_read with `write_idx - 1`.
#[allow(clippy::indexing_slicing)]
let prev_write = &mut before_read[write_idx - 1];
if read.0 == prev_write.0 {
core::mem::swap(read, prev_write);
} else {
// Equivalent to checking if write_idx == read_idx
if let Some(write) = before_read.get_mut(write_idx) {
core::mem::swap(read, write);
}
write_idx += 1;
}
read_idx += 1;
}
v.split_at_mut(write_idx)
}
impl<K: Ord, V> StoreFromIterable<K, V> for Vec<(K, V)> {
fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
let mut v = Self::new();
v.lm_extend(iter);
v
}
}
impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for Vec<(K, V)> {
type KeyValueIter = core::iter::Map<core::slice::Iter<'a, (K, V)>, MapF<K, V>>;
#[inline]
fn lm_iter(&'a self) -> Self::KeyValueIter {
self.as_slice().iter().map(map_f)
}
}
impl<'a, K: 'a, V: 'a> StoreIterableMut<'a, K, V> for Vec<(K, V)> {
type KeyValueIterMut = core::iter::Map<core::slice::IterMut<'a, (K, V)>, MapFMut<K, V>>;
#[inline]
fn lm_iter_mut(&'a mut self) -> Self::KeyValueIterMut {
self.as_mut_slice().iter_mut().map(map_f_mut)
}
}
impl<K, V> StoreIntoIterator<K, V> for Vec<(K, V)> {
type KeyValueIntoIter = alloc::vec::IntoIter<(K, V)>;
#[inline]
fn lm_into_iter(self) -> Self::KeyValueIntoIter {
IntoIterator::into_iter(self)
}
#[inline]
fn lm_extend_end(&mut self, other: Self) {
self.extend(other)
}
#[inline]
fn lm_extend_start(&mut self, other: Self) {
self.splice(0..0, other);
}
}
impl<K, V> StoreFromIterator<K, V> for Vec<(K, V)> {}
#[test]
fn test_vec_impl() {
crate::testing::check_store_full::<Vec<(u32, u64)>>();
}