1use std::{
2 collections::{HashMap, HashSet},
3 hash::{BuildHasher, Hash},
4};
5
6use indexmap::{IndexMap, IndexSet};
7use smallvec::SmallVec;
8
9pub trait Keyed {
10 type Key;
11 type Value;
12
13 fn different_keys<'l>(&'l self, other: &'l Self) -> SmallVec<[&'l Self::Key; 2]>;
14 fn get(&self, key: &Self::Key) -> Option<&Self::Value>;
15 fn contains_key(&self, key: &Self::Key) -> bool {
16 self.get(key).is_some()
17 }
18}
19
20impl<K: Eq + Hash, V: PartialEq, H: BuildHasher> Keyed for HashMap<K, V, H> {
21 type Key = K;
22 type Value = V;
23
24 fn different_keys<'l>(&'l self, other: &'l Self) -> SmallVec<[&'l Self::Key; 2]> {
25 let mut different_keys = SmallVec::new();
26
27 for (key, value) in self.iter() {
28 if let Some(other_value) = other.get(key) {
29 if value != other_value {
30 different_keys.push(key);
31 }
32 } else {
33 different_keys.push(key);
34 }
35 }
36
37 if other.len() != self.len() || !different_keys.is_empty() {
38 for key in other.keys() {
39 if !self.contains_key(key) {
40 different_keys.push(key);
41 }
42 }
43 }
44
45 different_keys
46 }
47
48 fn get(&self, key: &Self::Key) -> Option<&Self::Value> {
49 self.get(key)
50 }
51
52 fn contains_key(&self, key: &Self::Key) -> bool {
53 self.contains_key(key)
54 }
55}
56
57impl<K: Eq + Hash, V: PartialEq, H: BuildHasher> Keyed for IndexMap<K, V, H> {
58 type Key = K;
59 type Value = V;
60
61 fn different_keys<'l>(&'l self, other: &'l Self) -> SmallVec<[&'l Self::Key; 2]> {
62 let mut different_keys = SmallVec::new();
63
64 for (key, value) in self.iter() {
65 if let Some(other_value) = other.get(key) {
66 if value != other_value {
67 different_keys.push(key);
68 }
69 } else {
70 different_keys.push(key);
71 }
72 }
73
74 if other.len() != self.len() || !different_keys.is_empty() {
75 for key in other.keys() {
76 if !self.contains_key(key) {
77 different_keys.push(key);
78 }
79 }
80 }
81
82 different_keys
83 }
84
85 fn get(&self, key: &Self::Key) -> Option<&Self::Value> {
86 self.get(key)
87 }
88
89 fn contains_key(&self, key: &Self::Key) -> bool {
90 self.contains_key(key)
91 }
92}
93
94impl<K: Eq + Hash, H: BuildHasher> Keyed for HashSet<K, H> {
95 type Key = K;
96 type Value = ();
97
98 fn different_keys<'l>(&'l self, other: &'l Self) -> SmallVec<[&'l Self::Key; 2]> {
99 let mut different_keys = SmallVec::new();
100
101 for key in self.iter() {
102 if !other.contains(key) {
103 different_keys.push(key);
104 }
105 }
106
107 if other.len() != self.len() || !different_keys.is_empty() {
108 for key in other.iter() {
109 if !self.contains(key) {
110 different_keys.push(key);
111 }
112 }
113 }
114
115 different_keys
116 }
117
118 fn get(&self, key: &Self::Key) -> Option<&Self::Value> {
119 if self.contains(key) { Some(&()) } else { None }
120 }
121
122 fn contains_key(&self, key: &Self::Key) -> bool {
123 self.contains(key)
124 }
125}
126
127impl<K: Eq + Hash, H: BuildHasher> Keyed for IndexSet<K, H> {
128 type Key = K;
129 type Value = ();
130
131 fn different_keys<'l>(&'l self, other: &'l Self) -> SmallVec<[&'l Self::Key; 2]> {
132 let mut different_keys = SmallVec::new();
133
134 for key in self.iter() {
135 if !other.contains(key) {
136 different_keys.push(key);
137 }
138 }
139
140 if other.len() != self.len() || !different_keys.is_empty() {
141 for key in other.iter() {
142 if !self.contains(key) {
143 different_keys.push(key);
144 }
145 }
146 }
147
148 different_keys
149 }
150
151 fn get(&self, key: &Self::Key) -> Option<&Self::Value> {
152 if self.contains(key) { Some(&()) } else { None }
153 }
154
155 fn contains_key(&self, key: &Self::Key) -> bool {
156 self.contains(key)
157 }
158}
159
160#[cfg(test)]
161mod tests {
162 use super::*;
163
164 fn abc() -> [(&'static str, i32); 3] {
165 [("a", 1), ("b", 2), ("c", 3)]
166 }
167
168 fn abd() -> [(&'static str, i32); 3] {
169 [("a", 1), ("b", 22), ("d", 4)]
170 }
171
172 fn ab() -> [(&'static str, i32); 2] {
173 [("a", 1), ("b", 2)]
174 }
175
176 fn abcde() -> [(&'static str, i32); 5] {
177 [("a", 1), ("b", 2), ("c", 3), ("d", 4), ("e", 5)]
178 }
179
180 fn edcba() -> [(&'static str, i32); 5] {
181 [("e", 5), ("d", 4), ("c", 3), ("b", 2), ("a", 1)]
182 }
183
184 fn assert_diff<T: Keyed>(a: &T, b: &T, expected: &[&T::Key])
185 where
186 T::Key: std::fmt::Debug + PartialEq,
187 {
188 let diffs = a.different_keys(b);
189 assert_eq!(diffs.len(), expected.len());
190 for key in expected {
191 assert!(diffs.contains(key));
192 }
193 }
194
195 #[test]
196 fn test_hash_map_diff() {
197 let map1 = HashMap::from(abc());
198 let map2 = HashMap::from(abd());
199 assert_diff(&map1, &map2, &[&"b", &"c", &"d"]);
200 }
201
202 #[test]
203 fn test_index_map_diff() {
204 let map1 = IndexMap::from(abc());
205 let map2 = IndexMap::from(abd());
206 assert_diff(&map1, &map2, &[&"b", &"c", &"d"]);
207 }
208
209 #[test]
210 fn test_hash_map_equal() {
211 let map1 = HashMap::from(abcde());
212 let map2 = HashMap::from(edcba());
213 assert_diff(&map1, &map2, &[]);
214 }
215
216 #[test]
217 fn test_index_map_equal() {
218 let map1 = IndexMap::from(abcde());
219 let map2 = IndexMap::from(edcba());
220 assert_diff(&map1, &map2, &[]);
221 }
222
223 #[test]
224 fn test_hash_map_add_key() {
225 let map1 = HashMap::from(ab());
226 let map2 = HashMap::from(abc());
227 assert_diff(&map1, &map2, &[&"c"]);
228 }
229
230 #[test]
231 fn test_index_map_add_key() {
232 let map1 = IndexMap::from(ab());
233 let map2 = IndexMap::from(abc());
234 assert_diff(&map1, &map2, &[&"c"]);
235 }
236
237 #[test]
238 fn test_hash_map_remove_key() {
239 let map1 = HashMap::from(abc());
240 let map2 = HashMap::from(ab());
241 assert_diff(&map1, &map2, &[&"c"]);
242 }
243
244 #[test]
245 fn test_index_map_remove_key() {
246 let map1 = IndexMap::from(abc());
247 let map2 = IndexMap::from(ab());
248 assert_diff(&map1, &map2, &[&"c"]);
249 }
250}