]>
Commit | Line | Data |
---|---|---|
17df50a5 | 1 | use std::borrow::Borrow; |
136023e0 | 2 | use std::fmt::Debug; |
136023e0 | 3 | use std::slice::Iter; |
17df50a5 XL |
4 | use std::vec::IntoIter; |
5 | ||
6 | use crate::stable_hasher::{HashStable, StableHasher}; | |
7 | ||
8 | /// A map type implemented as a vector of pairs `K` (key) and `V` (value). | |
9 | /// It currently provides a subset of all the map operations, the rest could be added as needed. | |
10 | #[derive(Clone, Encodable, Decodable, Debug)] | |
11 | pub struct VecMap<K, V>(Vec<(K, V)>); | |
12 | ||
13 | impl<K, V> VecMap<K, V> | |
14 | where | |
136023e0 XL |
15 | K: Debug + PartialEq, |
16 | V: Debug, | |
17df50a5 XL |
17 | { |
18 | pub fn new() -> Self { | |
19 | VecMap(Default::default()) | |
20 | } | |
21 | ||
22 | /// Sets the value of the entry, and returns the entry's old value. | |
23 | pub fn insert(&mut self, k: K, v: V) -> Option<V> { | |
24 | if let Some(elem) = self.0.iter_mut().find(|(key, _)| *key == k) { | |
25 | Some(std::mem::replace(&mut elem.1, v)) | |
26 | } else { | |
27 | self.0.push((k, v)); | |
28 | None | |
29 | } | |
30 | } | |
31 | ||
5e7ed085 FG |
32 | /// Removes the entry from the map and returns the removed value |
33 | pub fn remove(&mut self, k: &K) -> Option<V> { | |
34 | self.0.iter().position(|(k2, _)| k2 == k).map(|pos| self.0.remove(pos).1) | |
35 | } | |
36 | ||
17df50a5 XL |
37 | /// Gets a reference to the value in the entry. |
38 | pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V> | |
39 | where | |
40 | K: Borrow<Q>, | |
41 | Q: Eq, | |
42 | { | |
43 | self.0.iter().find(|(key, _)| k == key.borrow()).map(|elem| &elem.1) | |
44 | } | |
45 | ||
5e7ed085 FG |
46 | /// Gets a mutable reference to the value in the entry. |
47 | pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> | |
48 | where | |
49 | K: Borrow<Q>, | |
50 | Q: Eq, | |
51 | { | |
52 | self.0.iter_mut().find(|(key, _)| k == key.borrow()).map(|elem| &mut elem.1) | |
53 | } | |
54 | ||
136023e0 | 55 | /// Returns the any value corresponding to the supplied predicate filter. |
17df50a5 XL |
56 | /// |
57 | /// The supplied predicate will be applied to each (key, value) pair and it will return a | |
58 | /// reference to the values where the predicate returns `true`. | |
136023e0 | 59 | pub fn any_value_matching(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { |
17df50a5 XL |
60 | self.0.iter().find(|kv| predicate(kv)).map(|elem| &elem.1) |
61 | } | |
62 | ||
136023e0 XL |
63 | /// Returns the value corresponding to the supplied predicate filter. It crashes if there's |
64 | /// more than one matching element. | |
65 | /// | |
66 | /// The supplied predicate will be applied to each (key, value) pair and it will return a | |
67 | /// reference to the value where the predicate returns `true`. | |
68 | pub fn get_value_matching(&self, mut predicate: impl FnMut(&(K, V)) -> bool) -> Option<&V> { | |
69 | let mut filter = self.0.iter().filter(|kv| predicate(kv)); | |
70 | let (_, value) = filter.next()?; | |
71 | // This should return just one element, otherwise it's a bug | |
72 | assert!( | |
73 | filter.next().is_none(), | |
f25598a0 | 74 | "Collection {self:#?} should have just one matching element" |
136023e0 XL |
75 | ); |
76 | Some(value) | |
77 | } | |
78 | ||
17df50a5 XL |
79 | /// Returns `true` if the map contains a value for the specified key. |
80 | /// | |
81 | /// The key may be any borrowed form of the map's key type, | |
82 | /// [`Eq`] on the borrowed form *must* match those for | |
83 | /// the key type. | |
84 | pub fn contains_key<Q: ?Sized>(&self, k: &Q) -> bool | |
85 | where | |
86 | K: Borrow<Q>, | |
87 | Q: Eq, | |
88 | { | |
89 | self.get(k).is_some() | |
90 | } | |
91 | ||
92 | /// Returns `true` if the map contains no elements. | |
93 | pub fn is_empty(&self) -> bool { | |
94 | self.0.is_empty() | |
95 | } | |
96 | ||
97 | pub fn iter(&self) -> Iter<'_, (K, V)> { | |
98 | self.into_iter() | |
99 | } | |
100 | ||
136023e0 | 101 | pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> { |
17df50a5 XL |
102 | self.into_iter() |
103 | } | |
136023e0 XL |
104 | |
105 | pub fn retain(&mut self, f: impl Fn(&(K, V)) -> bool) { | |
106 | self.0.retain(f) | |
107 | } | |
17df50a5 XL |
108 | } |
109 | ||
110 | impl<K, V> Default for VecMap<K, V> { | |
111 | #[inline] | |
112 | fn default() -> Self { | |
113 | Self(Default::default()) | |
114 | } | |
115 | } | |
116 | ||
117 | impl<K, V> From<Vec<(K, V)>> for VecMap<K, V> { | |
118 | fn from(vec: Vec<(K, V)>) -> Self { | |
119 | Self(vec) | |
120 | } | |
121 | } | |
122 | ||
123 | impl<K, V> Into<Vec<(K, V)>> for VecMap<K, V> { | |
124 | fn into(self) -> Vec<(K, V)> { | |
125 | self.0 | |
126 | } | |
127 | } | |
128 | ||
129 | impl<K, V> FromIterator<(K, V)> for VecMap<K, V> { | |
130 | fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { | |
131 | Self(iter.into_iter().collect()) | |
132 | } | |
133 | } | |
134 | ||
135 | impl<'a, K, V> IntoIterator for &'a VecMap<K, V> { | |
136 | type Item = &'a (K, V); | |
137 | type IntoIter = Iter<'a, (K, V)>; | |
138 | ||
139 | #[inline] | |
140 | fn into_iter(self) -> Self::IntoIter { | |
141 | self.0.iter() | |
142 | } | |
143 | } | |
144 | ||
04454e1e | 145 | impl<'a, K: 'a, V: 'a> IntoIterator for &'a mut VecMap<K, V> { |
136023e0 XL |
146 | type Item = (&'a K, &'a mut V); |
147 | type IntoIter = impl Iterator<Item = Self::Item>; | |
17df50a5 XL |
148 | |
149 | #[inline] | |
150 | fn into_iter(self) -> Self::IntoIter { | |
136023e0 | 151 | self.0.iter_mut().map(|(k, v)| (&*k, v)) |
17df50a5 XL |
152 | } |
153 | } | |
154 | ||
155 | impl<K, V> IntoIterator for VecMap<K, V> { | |
156 | type Item = (K, V); | |
157 | type IntoIter = IntoIter<(K, V)>; | |
158 | ||
159 | #[inline] | |
160 | fn into_iter(self) -> Self::IntoIter { | |
161 | self.0.into_iter() | |
162 | } | |
163 | } | |
164 | ||
136023e0 | 165 | impl<K: PartialEq + Debug, V: Debug> Extend<(K, V)> for VecMap<K, V> { |
17df50a5 | 166 | fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) { |
136023e0 XL |
167 | for (k, v) in iter { |
168 | self.insert(k, v); | |
169 | } | |
17df50a5 XL |
170 | } |
171 | ||
136023e0 XL |
172 | fn extend_one(&mut self, (k, v): (K, V)) { |
173 | self.insert(k, v); | |
17df50a5 XL |
174 | } |
175 | ||
176 | fn extend_reserve(&mut self, additional: usize) { | |
177 | self.0.extend_reserve(additional); | |
178 | } | |
179 | } | |
180 | ||
181 | impl<K, V, CTX> HashStable<CTX> for VecMap<K, V> | |
182 | where | |
183 | K: HashStable<CTX> + Eq, | |
184 | V: HashStable<CTX>, | |
185 | { | |
186 | fn hash_stable(&self, hcx: &mut CTX, hasher: &mut StableHasher) { | |
187 | self.0.hash_stable(hcx, hasher) | |
188 | } | |
189 | } | |
190 | ||
191 | #[cfg(test)] | |
192 | mod tests; |