clap_builder/util/
flat_map.rs

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!(
69            self.keys
70                .iter()
71                .enumerate()
72                .find_map(|(i, k)| (k.borrow() == key).then_some(i))
73        );
74        let key = self.keys.remove(index);
75        let value = self.values.remove(index);
76        Some((key, value))
77    }
78
79    pub(crate) fn is_empty(&self) -> bool {
80        self.keys.is_empty()
81    }
82
83    pub(crate) fn entry(&mut self, key: K) -> Entry<'_, K, V> {
84        for (index, existing) in self.keys.iter().enumerate() {
85            if *existing == key {
86                return Entry::Occupied(OccupiedEntry { v: self, index });
87            }
88        }
89        Entry::Vacant(VacantEntry { v: self, key })
90    }
91
92    pub(crate) fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
93    where
94        K: Borrow<Q>,
95        Q: Eq,
96    {
97        for (index, existing) in self.keys.iter().enumerate() {
98            if existing.borrow() == k {
99                return Some(&self.values[index]);
100            }
101        }
102        None
103    }
104
105    pub(crate) fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
106    where
107        K: Borrow<Q>,
108        Q: Eq,
109    {
110        for (index, existing) in self.keys.iter().enumerate() {
111            if existing.borrow() == k {
112                return Some(&mut self.values[index]);
113            }
114        }
115        None
116    }
117
118    pub(crate) fn keys(&self) -> std::slice::Iter<'_, K> {
119        self.keys.iter()
120    }
121
122    pub(crate) fn values(&self) -> std::slice::Iter<'_, V> {
123        self.values.iter()
124    }
125
126    pub(crate) fn iter(&self) -> Iter<'_, K, V> {
127        Iter {
128            keys: self.keys.iter(),
129            values: self.values.iter(),
130        }
131    }
132
133    pub(crate) fn iter_mut(&mut self) -> IterMut<'_, K, V> {
134        IterMut {
135            keys: self.keys.iter_mut(),
136            values: self.values.iter_mut(),
137        }
138    }
139}
140
141impl<K: PartialEq + Eq, V> Default for FlatMap<K, V> {
142    fn default() -> Self {
143        Self {
144            keys: Default::default(),
145            values: Default::default(),
146        }
147    }
148}
149
150pub(crate) enum Entry<'a, K, V> {
151    Vacant(VacantEntry<'a, K, V>),
152    Occupied(OccupiedEntry<'a, K, V>),
153}
154
155impl<'a, K: 'a, V: 'a> Entry<'a, K, V> {
156    pub(crate) fn or_insert(self, default: V) -> &'a mut V {
157        match self {
158            Entry::Occupied(entry) => &mut entry.v.values[entry.index],
159            Entry::Vacant(entry) => {
160                entry.v.keys.push(entry.key);
161                entry.v.values.push(default);
162                entry.v.values.last_mut().unwrap()
163            }
164        }
165    }
166
167    pub(crate) fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
168        match self {
169            Entry::Occupied(entry) => &mut entry.v.values[entry.index],
170            Entry::Vacant(entry) => {
171                entry.v.keys.push(entry.key);
172                entry.v.values.push(default());
173                entry.v.values.last_mut().unwrap()
174            }
175        }
176    }
177}
178
179pub(crate) struct VacantEntry<'a, K, V> {
180    v: &'a mut FlatMap<K, V>,
181    key: K,
182}
183
184pub(crate) struct OccupiedEntry<'a, K, V> {
185    v: &'a mut FlatMap<K, V>,
186    index: usize,
187}
188
189pub(crate) struct Iter<'a, K, V> {
190    keys: std::slice::Iter<'a, K>,
191    values: std::slice::Iter<'a, V>,
192}
193
194impl<'a, K, V> Iterator for Iter<'a, K, V> {
195    type Item = (&'a K, &'a V);
196
197    fn next(&mut self) -> Option<(&'a K, &'a V)> {
198        match self.keys.next() {
199            Some(k) => {
200                let v = self.values.next().unwrap();
201                Some((k, v))
202            }
203            None => None,
204        }
205    }
206    fn size_hint(&self) -> (usize, Option<usize>) {
207        self.keys.size_hint()
208    }
209}
210
211impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
212    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
213        match self.keys.next_back() {
214            Some(k) => {
215                let v = self.values.next_back().unwrap();
216                Some((k, v))
217            }
218            None => None,
219        }
220    }
221}
222
223impl<K, V> ExactSizeIterator for Iter<'_, K, V> {}
224
225pub(crate) struct IterMut<'a, K, V> {
226    keys: std::slice::IterMut<'a, K>,
227    values: std::slice::IterMut<'a, V>,
228}
229
230impl<'a, K, V> Iterator for IterMut<'a, K, V> {
231    type Item = (&'a K, &'a mut V);
232
233    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
234        match self.keys.next() {
235            Some(k) => {
236                let v = self.values.next().unwrap();
237                Some((k, v))
238            }
239            None => None,
240        }
241    }
242    fn size_hint(&self) -> (usize, Option<usize>) {
243        self.keys.size_hint()
244    }
245}
246
247impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
248    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
249        match self.keys.next_back() {
250            Some(k) => {
251                let v = self.values.next_back().unwrap();
252                Some((k, v))
253            }
254            None => None,
255        }
256    }
257}
258
259impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {}
clap_builder/util/flat_map.rs

clap_builder/util/
flat_map.rs
