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 iter(&self) -> Iter<'_, K, V> {
122        Iter {
123            keys: self.keys.iter(),
124            values: self.values.iter(),
125        }
126    }
127
128    pub(crate) fn iter_mut(&mut self) -> IterMut<'_, K, V> {
129        IterMut {
130            keys: self.keys.iter_mut(),
131            values: self.values.iter_mut(),
132        }
133    }
134}
135
136impl<K: PartialEq + Eq, V> Default for FlatMap<K, V> {
137    fn default() -> Self {
138        Self {
139            keys: Default::default(),
140            values: Default::default(),
141        }
142    }
143}
144
145pub(crate) enum Entry<'a, K, V> {
146    Vacant(VacantEntry<'a, K, V>),
147    Occupied(OccupiedEntry<'a, K, V>),
148}
149
150impl<'a, K: 'a, V: 'a> Entry<'a, K, V> {
151    pub(crate) fn or_insert(self, default: V) -> &'a mut V {
152        match self {
153            Entry::Occupied(entry) => &mut entry.v.values[entry.index],
154            Entry::Vacant(entry) => {
155                entry.v.keys.push(entry.key);
156                entry.v.values.push(default);
157                entry.v.values.last_mut().unwrap()
158            }
159        }
160    }
161
162    pub(crate) fn or_insert_with<F: FnOnce() -> V>(self, default: F) -> &'a mut V {
163        match self {
164            Entry::Occupied(entry) => &mut entry.v.values[entry.index],
165            Entry::Vacant(entry) => {
166                entry.v.keys.push(entry.key);
167                entry.v.values.push(default());
168                entry.v.values.last_mut().unwrap()
169            }
170        }
171    }
172}
173
174pub(crate) struct VacantEntry<'a, K, V> {
175    v: &'a mut FlatMap<K, V>,
176    key: K,
177}
178
179pub(crate) struct OccupiedEntry<'a, K, V> {
180    v: &'a mut FlatMap<K, V>,
181    index: usize,
182}
183
184pub(crate) struct Iter<'a, K, V> {
185    keys: std::slice::Iter<'a, K>,
186    values: std::slice::Iter<'a, V>,
187}
188
189impl<'a, K, V> Iterator for Iter<'a, K, V> {
190    type Item = (&'a K, &'a V);
191
192    fn next(&mut self) -> Option<(&'a K, &'a V)> {
193        match self.keys.next() {
194            Some(k) => {
195                let v = self.values.next().unwrap();
196                Some((k, v))
197            }
198            None => None,
199        }
200    }
201    fn size_hint(&self) -> (usize, Option<usize>) {
202        self.keys.size_hint()
203    }
204}
205
206impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
207    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
208        match self.keys.next_back() {
209            Some(k) => {
210                let v = self.values.next_back().unwrap();
211                Some((k, v))
212            }
213            None => None,
214        }
215    }
216}
217
218impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {}
219
220pub(crate) struct IterMut<'a, K, V> {
221    keys: std::slice::IterMut<'a, K>,
222    values: std::slice::IterMut<'a, V>,
223}
224
225impl<'a, K, V> Iterator for IterMut<'a, K, V> {
226    type Item = (&'a K, &'a mut V);
227
228    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
229        match self.keys.next() {
230            Some(k) => {
231                let v = self.values.next().unwrap();
232                Some((k, v))
233            }
234            None => None,
235        }
236    }
237    fn size_hint(&self) -> (usize, Option<usize>) {
238        self.keys.size_hint()
239    }
240}
241
242impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
243    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
244        match self.keys.next_back() {
245            Some(k) => {
246                let v = self.values.next_back().unwrap();
247                Some((k, v))
248            }
249            None => None,
250        }
251    }
252}
253
254impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {}
clap_builder/util/flat_map.rs

clap_builder/util/
flat_map.rs
