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

icu_locale_core/shortvec/
litemap.rs
