]>
Commit | Line | Data |
---|---|---|
9c376795 FG |
1 | #![allow(dead_code)] |
2 | ||
3 | use std::borrow::Borrow; | |
4 | ||
5 | /// Flat (Vec) backed map | |
6 | /// | |
7 | /// This preserves insertion order | |
8 | #[derive(Clone, Debug, PartialEq, Eq)] | |
9 | pub(crate) struct FlatMap<K, V> { | |
10 | keys: Vec<K>, | |
11 | values: Vec<V>, | |
12 | } | |
13 | ||
14 | impl<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 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 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 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 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 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 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 fn keys(&self) -> std::slice::Iter<'_, K> { | |
118 | self.keys.iter() | |
119 | } | |
120 | ||
121 | pub fn iter(&self) -> Iter<K, V> { | |
122 | Iter { | |
123 | keys: self.keys.iter(), | |
124 | values: self.values.iter(), | |
125 | } | |
126 | } | |
127 | ||
128 | pub 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 | ||
136 | impl<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 | ||
145 | pub enum Entry<'a, K: 'a, V: 'a> { | |
146 | Vacant(VacantEntry<'a, K, V>), | |
147 | Occupied(OccupiedEntry<'a, K, V>), | |
148 | } | |
149 | ||
150 | impl<'a, K: 'a, V: 'a> Entry<'a, K, V> { | |
151 | pub 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 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 | ||
174 | pub struct VacantEntry<'a, K: 'a, V: 'a> { | |
175 | v: &'a mut FlatMap<K, V>, | |
176 | key: K, | |
177 | } | |
178 | ||
179 | pub struct OccupiedEntry<'a, K: 'a, V: 'a> { | |
180 | v: &'a mut FlatMap<K, V>, | |
181 | index: usize, | |
182 | } | |
183 | ||
184 | pub struct Iter<'a, K: 'a, V: 'a> { | |
185 | keys: std::slice::Iter<'a, K>, | |
186 | values: std::slice::Iter<'a, V>, | |
187 | } | |
188 | ||
189 | impl<'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 | ||
206 | impl<'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 | ||
218 | impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {} | |
219 | ||
220 | pub struct IterMut<'a, K: 'a, V: 'a> { | |
221 | keys: std::slice::IterMut<'a, K>, | |
222 | values: std::slice::IterMut<'a, V>, | |
223 | } | |
224 | ||
225 | impl<'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 | ||
242 | impl<'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 | ||
254 | impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {} |