clap_builder/util/
flat_map.rs

Help
1#![allow(dead_code)]
2
3use std::borrow::Borrow;
4
5/// Flat (Vec) backed map
6///
7/// This preserves insertion order
8#[derive(Clone, Debug, PartialEq, Eq)]
9pub(crate) struct FlatMap<K, V> {
10    keys: Vec<K>,
11    values: Vec<V>,
12}
13
14impl<K: PartialEq + Eq, V> FlatMap<K, V> {
15    pub(crate) fn new() -> Self {
16        Default::default()
17    }
18
19    pub(crate) fn insert(&mut self, key: K, mut value: V) -> Option<V> {
20        for (index, existing) in self.keys.iter().enumerate() {
21            if *existing == key {
22                std::mem::swap(&mut self.values[index], &mut value);
23                return Some(value);
24            }
25        }
26
27        self.insert_unchecked(key, value);
28        None
29    }
30
31    pub(crate) fn insert_unchecked(&mut self, key: K, value: V) {
32        self.keys.push(key);
33        self.values.push(value);
34    }
35
36    pub(crate) fn extend_unchecked(&mut self, iter: impl IntoIterator<Item = (K, V)>) {
37        for (key, value) in iter {
38            self.insert_unchecked(key, value);
39        }
40    }
41
42    pub(crate) fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
43    where
44        K: Borrow<Q>,
45        Q: Eq,
46    {
47        for existing in &self.keys {
48            if existing.borrow() == key {
49                return true;
50            }
51        }
52        false
53    }
54
55    pub(crate) fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V>
56    where
57        K: Borrow<Q>,
58        Q: std::hash::Hash + Eq,
59    {
60        self.remove_entry(key).map(|(_, v)| v)
61    }
62
63    pub(crate) fn remove_entry<Q: ?Sized>(&mut self, key: &Q) -> Option<(K, V)>
64    where
65        K: Borrow<Q>,
66        Q: std::hash::Hash + Eq,
67    {
68        let index = some!(self
69            .keys
70            .iter()
71            .enumerate()
72            .find_map(|(i, k)| (k.borrow() == key).then_some(i)));
73        let key = self.keys.remove(index);
74        let value = self.values.remove(index);
75        Some((key, value))
76    }
77
78    pub(crate) fn is_empty(&self) -> bool {
79        self.keys.is_empty()
80    }
81
82    pub(crate) fn entry(&mut self, key: K) -> Entry<'_, K, V> {
83        for (index, existing) in self.keys.iter().enumerate() {
84            if *existing == key {
85                return Entry::Occupied(OccupiedEntry { v: self, index });
86            }
87        }
88        Entry::Vacant(VacantEntry { v: self, key })
89    }
90
91    pub(crate) fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
92    where
93        K: Borrow<Q>,
94        Q: Eq,
95    {
96        for (index, existing) in self.keys.iter().enumerate() {
97            if existing.borrow() == k {
98                return Some(&self.values[index]);
99            }
100        }
101        None
102    }
103
104    pub(crate) fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
105    where
106        K: Borrow<Q>,
107        Q: Eq,
108    {
109        for (index, existing) in self.keys.iter().enumerate() {
110            if existing.borrow() == k {
111                return Some(&mut self.values[index]);
112            }
113        }
114        None
115    }
116
117    pub(crate) fn keys(&self) -> std::slice::Iter<'_, K> {
118        self.keys.iter()
119    }
120
121    pub(crate) fn values(&self) -> std::slice::Iter<'_, V> {
122        self.values.iter()
123    }
124
125    pub(crate) fn iter(&self) -> Iter<'_, K, V> {
126        Iter {
127            keys: self.keys.iter(),
128            values: self.values.iter(),
129        }
130    }
131
132    pub(crate) fn iter_mut(&mut self) -> IterMut<'_, K, V> {
133        IterMut {
134            keys: self.keys.iter_mut(),
135            values: self.values.iter_mut(),
136        }
137    }
138}
139
140impl<K: PartialEq + Eq, V> Default for FlatMap<K, V> {
141    fn default() -> Self {
142        Self {
143            keys: Default::default(),
144            values: Default::default(),
145        }
146    }
147}
148
149pub(crate) enum Entry<'a, K, V> {
150    Vacant(VacantEntry<'a, K, V>),
151    Occupied(OccupiedEntry<'a, K, V>),
152}
153
154impl<'a, K: 'a, V: 'a> Entry<'a, K, V> {
155    pub(crate) fn or_insert(self, default: V) -> &'a mut V {
156        match self {
157            Entry::Occupied(entry) => &mut entry.v.values[entry.index],
158            Entry::Vacant(entry) => {
159                entry.v.keys.push(entry.key);
160                entry.v.values.push(default);
161                entry.v.values.last_mut().unwrap()
162            }
163        }
164    }
165
166    pub(crate) fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
167        match self {
168            Entry::Occupied(entry) => &mut entry.v.values[entry.index],
169            Entry::Vacant(entry) => {
170                entry.v.keys.push(entry.key);
171                entry.v.values.push(default());
172                entry.v.values.last_mut().unwrap()
173            }
174        }
175    }
176}
177
178pub(crate) struct VacantEntry<'a, K, V> {
179    v: &'a mut FlatMap<K, V>,
180    key: K,
181}
182
183pub(crate) struct OccupiedEntry<'a, K, V> {
184    v: &'a mut FlatMap<K, V>,
185    index: usize,
186}
187
188pub(crate) struct Iter<'a, K, V> {
189    keys: std::slice::Iter<'a, K>,
190    values: std::slice::Iter<'a, V>,
191}
192
193impl<'a, K, V> Iterator for Iter<'a, K, V> {
194    type Item = (&'a K, &'a V);
195
196    fn next(&mut self) -> Option<(&'a K, &'a V)> {
197        match self.keys.next() {
198            Some(k) => {
199                let v = self.values.next().unwrap();
200                Some((k, v))
201            }
202            None => None,
203        }
204    }
205    fn size_hint(&self) -> (usize, Option<usize>) {
206        self.keys.size_hint()
207    }
208}
209
210impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
211    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
212        match self.keys.next_back() {
213            Some(k) => {
214                let v = self.values.next_back().unwrap();
215                Some((k, v))
216            }
217            None => None,
218        }
219    }
220}
221
222impl<K, V> ExactSizeIterator for Iter<'_, K, V> {}
223
224pub(crate) struct IterMut<'a, K, V> {
225    keys: std::slice::IterMut<'a, K>,
226    values: std::slice::IterMut<'a, V>,
227}
228
229impl<'a, K, V> Iterator for IterMut<'a, K, V> {
230    type Item = (&'a K, &'a mut V);
231
232    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
233        match self.keys.next() {
234            Some(k) => {
235                let v = self.values.next().unwrap();
236                Some((k, v))
237            }
238            None => None,
239        }
240    }
241    fn size_hint(&self) -> (usize, Option<usize>) {
242        self.keys.size_hint()
243    }
244}
245
246impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
247    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
248        match self.keys.next_back() {
249            Some(k) => {
250                let v = self.values.next_back().unwrap();
251                Some((k, v))
252            }
253            None => None,
254        }
255    }
256}
257
258impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {}
clap_builder/util/flat_map.rs

clap_builder/util/
flat_map.rs
