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: OccupiedEntry<'_, K, V>) => &mut entry.v.values[entry.index],
158 Entry::Vacant(entry: VacantEntry<'_, K, V>) => {
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: OccupiedEntry<'_, K, V>) => &mut entry.v.values[entry.index],
169 Entry::Vacant(entry: VacantEntry<'_, K, V>) => {
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: &'a K) => {
199 let v: &'a 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: &'a K) => {
214 let v: &'a 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: &'a mut K) => {
235 let v: &'a mut 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: &'a mut K) => {
250 let v: &'a mut 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> {}
259