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