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 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
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 enum Entry<'a, K: 'a, V: 'a> {
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 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
174pub struct VacantEntry<'a, K: 'a, V: 'a> {
175 v: &'a mut FlatMap<K, V>,
176 key: K,
177}
178
179pub struct OccupiedEntry<'a, K: 'a, V: 'a> {
180 v: &'a mut FlatMap<K, V>,
181 index: usize,
182}
183
184pub struct Iter<'a, K: 'a, V: 'a> {
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: &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
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: &K) => {
210 let v: &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 struct IterMut<'a, K: 'a, V: 'a> {
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: &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
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: &mut K) => {
246 let v: &mut 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> {}
255