icu_locale_core/shortvec/
litemap.rs

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 super::ShortBoxSlice;
6use super::ShortBoxSliceInner;
7#[cfg(feature = "alloc")]
8use super::ShortBoxSliceIntoIter;
9use litemap::store::*;
10
11impl<K, V> StoreConstEmpty<K, V> for ShortBoxSlice<(K, V)> {
12    const EMPTY: ShortBoxSlice<(K, V)> = ShortBoxSlice::new();
13}
14
15impl<K, V> StoreSlice<K, V> for ShortBoxSlice<(K, V)> {
16    type Slice = [(K, V)];
17
18    #[inline]
19    fn lm_get_range(&self, range: core::ops::Range<usize>) -> Option<&Self::Slice> {
20        self.get(range)
21    }
22}
23
24impl<K, V> Store<K, V> for ShortBoxSlice<(K, V)> {
25    #[inline]
26    fn lm_len(&self) -> usize {
27        self.len()
28    }
29
30    #[inline]
31    fn lm_is_empty(&self) -> bool {
32        use ShortBoxSliceInner::*;
33        matches!(self.0, ZeroOne(None))
34    }
35
36    #[inline]
37    fn lm_get(&self, index: usize) -> Option<(&K, &V)> {
38        self.get(index).map(|elt| (&elt.0, &elt.1))
39    }
40
41    #[inline]
42    fn lm_last(&self) -> Option<(&K, &V)> {
43        use ShortBoxSliceInner::*;
44        match self.0 {
45            ZeroOne(ref v) => v.as_ref(),
46            #[cfg(feature = "alloc")]
47            Multi(ref v) => v.last(),
48        }
49        .map(|elt| (&elt.0, &elt.1))
50    }
51
52    #[inline]
53    fn lm_binary_search_by<F>(&self, mut cmp: F) -> Result<usize, usize>
54    where
55        F: FnMut(&K) -> core::cmp::Ordering,
56    {
57        self.binary_search_by(|(k, _)| cmp(k))
58    }
59}
60
61#[cfg(feature = "alloc")]
62impl<K: Ord, V> StoreFromIterable<K, V> for ShortBoxSlice<(K, V)> {
63    fn lm_sort_from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self {
64        alloc::vec::Vec::lm_sort_from_iter(iter).into()
65    }
66}
67
68#[cfg(feature = "alloc")]
69impl<K, V> StoreMut<K, V> for ShortBoxSlice<(K, V)> {
70    fn lm_with_capacity(_capacity: usize) -> Self {
71        ShortBoxSlice::new()
72    }
73
74    fn lm_reserve(&mut self, _additional: usize) {}
75
76    fn lm_get_mut(&mut self, index: usize) -> Option<(&K, &mut V)> {
77        self.get_mut(index).map(|elt| (&elt.0, &mut elt.1))
78    }
79
80    fn lm_push(&mut self, key: K, value: V) {
81        self.push((key, value))
82    }
83
84    fn lm_insert(&mut self, index: usize, key: K, value: V) {
85        self.insert(index, (key, value))
86    }
87
88    fn lm_remove(&mut self, index: usize) -> (K, V) {
89        self.remove(index)
90    }
91
92    fn lm_clear(&mut self) {
93        self.clear();
94    }
95}
96
97#[cfg(feature = "alloc")]
98impl<K: Ord, V> StoreBulkMut<K, V> for ShortBoxSlice<(K, V)> {
99    fn lm_retain<F>(&mut self, mut predicate: F)
100    where
101        F: FnMut(&K, &V) -> bool,
102    {
103        self.retain(|(k, v)| predicate(k, v))
104    }
105
106    fn lm_extend<I>(&mut self, other: I)
107    where
108        I: IntoIterator<Item = (K, V)>,
109    {
110        let mut other = other.into_iter();
111        // Use an Option to hold the first item of the map and move it to
112        // items if there are more items. Meaning that if items is not
113        // empty, first is None.
114        let mut first = None;
115        let mut items = alloc::vec::Vec::new();
116        match core::mem::take(&mut self.0) {
117            ShortBoxSliceInner::ZeroOne(zo) => {
118                first = zo;
119                // Attempt to avoid the items allocation by advancing the iterator
120                // up to two times. If we eventually find a second item, we can
121                // lm_extend the Vec and with the first, next (second) and the rest
122                // of the iterator.
123                while let Some(next) = other.next() {
124                    if let Some(first) = first.take() {
125                        // lm_extend will take care of sorting and deduplicating
126                        // first, next and the rest of the other iterator.
127                        items.lm_extend([first, next].into_iter().chain(other));
128                        break;
129                    }
130                    first = Some(next);
131                }
132            }
133            ShortBoxSliceInner::Multi(existing_items) => {
134                items.reserve_exact(existing_items.len() + other.size_hint().0);
135                // We use a plain extend with existing items, which are already valid and
136                // lm_extend will fold over rest of the iterator sorting and deduplicating as needed.
137                items.extend(existing_items);
138                items.lm_extend(other);
139            }
140        }
141        if items.is_empty() {
142            debug_assert!(items.is_empty());
143            self.0 = ShortBoxSliceInner::ZeroOne(first);
144        } else {
145            debug_assert!(first.is_none());
146            self.0 = ShortBoxSliceInner::Multi(items.into_boxed_slice());
147        }
148    }
149}
150
151impl<'a, K: 'a, V: 'a> StoreIterable<'a, K, V> for ShortBoxSlice<(K, V)> {
152    type KeyValueIter =
153        core::iter::Map<core::slice::Iter<'a, (K, V)>, for<'r> fn(&'r (K, V)) -> (&'r K, &'r V)>;
154
155    fn lm_iter(&'a self) -> Self::KeyValueIter {
156        self.iter().map(|elt| (&elt.0, &elt.1))
157    }
158}
159
160#[cfg(feature = "alloc")]
161impl<K, V> StoreFromIterator<K, V> for ShortBoxSlice<(K, V)> {}
162
163#[cfg(feature = "alloc")]
164impl<'a, K: 'a, V: 'a> StoreIterableMut<'a, K, V> for ShortBoxSlice<(K, V)> {
165    type KeyValueIterMut = core::iter::Map<
166        core::slice::IterMut<'a, (K, V)>,
167        for<'r> fn(&'r mut (K, V)) -> (&'r K, &'r mut V),
168    >;
169
170    fn lm_iter_mut(
171        &'a mut self,
172    ) -> <Self as litemap::store::StoreIterableMut<'a, K, V>>::KeyValueIterMut {
173        self.iter_mut().map(|elt| (&elt.0, &mut elt.1))
174    }
175}
176
177#[cfg(feature = "alloc")]
178impl<K, V> StoreIntoIterator<K, V> for ShortBoxSlice<(K, V)> {
179    type KeyValueIntoIter = ShortBoxSliceIntoIter<(K, V)>;
180
181    fn lm_into_iter(self) -> Self::KeyValueIntoIter {
182        self.into_iter()
183    }
184
185    // leave lm_extend_end as default
186
187    // leave lm_extend_start as default
188}
189
190#[test]
191fn test_short_slice_impl() {
192    litemap::testing::check_store::<ShortBoxSlice<(u32, u64)>>();
193}
194
195#[test]
196fn test_short_slice_impl_full() {
197    litemap::testing::check_store_full::<ShortBoxSlice<(u32, u64)>>();
198}
icu_locale_core/shortvec/litemap.rs

icu_locale_core/shortvec/
litemap.rs
