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: OccupiedEntry<'_, K, V>) => &mut entry.v.values[entry.index], |
154 | Entry::Vacant(entry: VacantEntry<'_, K, V>) => { |
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: OccupiedEntry<'_, K, V>) => &mut entry.v.values[entry.index], |
165 | Entry::Vacant(entry: VacantEntry<'_, K, V>) => { |
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: &K) => { |
195 | let v: &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: &K) => { |
210 | let v: &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: &mut K) => { |
231 | let v: &mut 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: &mut K) => { |
246 | let v: &mut 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> {} |
255 | |