1#![forbid(unsafe_code)]
2use std::borrow::Borrow;
70use std::collections::hash_map::{IntoIter, Keys, RandomState};
71use std::collections::HashMap;
72use std::fmt::{self, Debug};
73use std::hash::{BuildHasher, Hash};
74use std::iter::{FromIterator, IntoIterator, Iterator};
75use std::ops::Index;
76
77pub use std::collections::hash_map::Iter as IterAll;
78pub use std::collections::hash_map::IterMut as IterAllMut;
79
80pub use entry::{Entry, OccupiedEntry, VacantEntry};
81
82mod entry;
83
84#[cfg(feature = "serde_impl")]
85pub mod serde;
86
87#[derive(Clone)]
88pub struct MultiMap<K, V, S = RandomState> {
89 inner: HashMap<K, Vec<V>, S>,
90}
91
92impl<K, V> MultiMap<K, V>
93where
94 K: Eq + Hash,
95{
96 pub fn new() -> MultiMap<K, V> {
106 MultiMap {
107 inner: HashMap::new(),
108 }
109 }
110
111 pub fn with_capacity(capacity: usize) -> MultiMap<K, V> {
121 MultiMap {
122 inner: HashMap::with_capacity(capacity),
123 }
124 }
125}
126
127impl<K, V, S> MultiMap<K, V, S>
128where
129 K: Eq + Hash,
130 S: BuildHasher,
131{
132 pub fn with_hasher(hash_builder: S) -> MultiMap<K, V, S> {
144 MultiMap {
145 inner: HashMap::with_hasher(hash_builder),
146 }
147 }
148
149 pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> MultiMap<K, V, S> {
161 MultiMap {
162 inner: HashMap::with_capacity_and_hasher(capacity, hash_builder),
163 }
164 }
165
166 pub fn insert(&mut self, k: K, v: V) {
179 match self.entry(k) {
180 Entry::Occupied(mut entry) => {
181 entry.get_vec_mut().push(v);
182 }
183 Entry::Vacant(entry) => {
184 entry.insert_vec(vec![v]);
185 }
186 }
187 }
188
189 pub fn insert_many<I: IntoIterator<Item = V>>(&mut self, k: K, v: I) {
204 match self.entry(k) {
205 Entry::Occupied(mut entry) => {
206 entry.get_vec_mut().extend(v);
207 }
208 Entry::Vacant(entry) => {
209 entry.insert_vec(v.into_iter().collect::<Vec<_>>());
210 }
211 }
212 }
213
214 pub fn insert_many_from_slice(&mut self, k: K, v: &[V])
229 where
230 V: Clone,
231 {
232 match self.entry(k) {
233 Entry::Occupied(mut entry) => {
234 entry.get_vec_mut().extend_from_slice(v);
235 }
236 Entry::Vacant(entry) => {
237 entry.insert_vec(v.to_vec());
238 }
239 }
240 }
241
242 pub fn contains_key<Q>(&self, k: &Q) -> bool
258 where
259 K: Borrow<Q>,
260 Q: Eq + Hash + ?Sized,
261 {
262 self.inner.contains_key(k)
263 }
264
265 pub fn len(&self) -> usize {
279 self.inner.len()
280 }
281
282 pub fn remove<Q>(&mut self, k: &Q) -> Option<Vec<V>>
300 where
301 K: Borrow<Q>,
302 Q: Eq + Hash + ?Sized,
303 {
304 self.inner.remove(k)
305 }
306
307 pub fn get<Q>(&self, k: &Q) -> Option<&V>
324 where
325 K: Borrow<Q>,
326 Q: Eq + Hash + ?Sized,
327 {
328 self.inner.get(k)?.first()
329 }
330
331 pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
351 where
352 K: Borrow<Q>,
353 Q: Eq + Hash + ?Sized,
354 {
355 self.inner.get_mut(k)?.get_mut(0)
356 }
357
358 pub fn get_vec<Q>(&self, k: &Q) -> Option<&Vec<V>>
374 where
375 K: Borrow<Q>,
376 Q: Eq + Hash + ?Sized,
377 {
378 self.inner.get(k)
379 }
380
381 pub fn get_vec_mut<Q>(&mut self, k: &Q) -> Option<&mut Vec<V>>
401 where
402 K: Borrow<Q>,
403 Q: Eq + Hash + ?Sized,
404 {
405 self.inner.get_mut(k)
406 }
407
408 pub fn is_vec<Q>(&self, k: &Q) -> bool
428 where
429 K: Borrow<Q>,
430 Q: Eq + Hash + ?Sized,
431 {
432 match self.get_vec(k) {
433 Some(val) => val.len() > 1,
434 None => false,
435 }
436 }
437
438 pub fn capacity(&self) -> usize {
449 self.inner.capacity()
450 }
451
452 pub fn is_empty(&self) -> bool {
465 self.inner.is_empty()
466 }
467
468 pub fn clear(&mut self) {
482 self.inner.clear();
483 }
484
485 pub fn keys(&'_ self) -> Keys<'_, K, Vec<V>> {
504 self.inner.keys()
505 }
506
507 pub fn iter(&self) -> Iter<K, V> {
533 Iter {
534 inner: self.inner.iter(),
535 }
536 }
537
538 pub fn iter_mut(&mut self) -> IterMut<K, V> {
568 IterMut {
569 inner: self.inner.iter_mut(),
570 }
571 }
572
573 pub fn iter_all(&self) -> IterAll<K, Vec<V>> {
593 self.inner.iter()
594 }
595
596 pub fn iter_all_mut(&mut self) -> IterAllMut<K, Vec<V>> {
622 self.inner.iter_mut()
623 }
624
625 pub fn flat_iter(&self) -> impl Iterator<Item = (&K, &V)> {
643 self.iter_all()
644 .flat_map(|(k, v)| v.iter().map(move |i| (k, i)))
645 }
646
647 pub fn flat_iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
669 self.iter_all_mut()
670 .flat_map(|(k, v)| v.iter_mut().map(move |i| (k, i)))
671 }
672
673 pub fn entry(&mut self, k: K) -> Entry<K, V> {
702 use std::collections::hash_map::Entry as HashMapEntry;
703 match self.inner.entry(k) {
704 HashMapEntry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
705 HashMapEntry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
706 }
707 }
708
709 pub fn retain<F>(&mut self, mut f: F)
727 where
728 F: FnMut(&K, &V) -> bool,
729 {
730 for (key, vector) in &mut self.inner {
731 vector.retain(|value| f(key, value));
732 }
733 self.inner.retain(|_, v| !v.is_empty());
734 }
735}
736
737impl<K, V, S, Q> Index<&Q> for MultiMap<K, V, S>
738where
739 K: Eq + Hash + Borrow<Q>,
740 Q: Eq + Hash + ?Sized,
741 S: BuildHasher,
742{
743 type Output = V;
744
745 fn index(&self, index: &Q) -> &V {
746 self.inner
747 .get(index)
748 .expect("no entry found for key")
749 .first()
750 .expect("no value found for key")
751 }
752}
753
754impl<K, V, S> Debug for MultiMap<K, V, S>
755where
756 K: Eq + Hash + Debug,
757 V: Debug,
758 S: BuildHasher,
759{
760 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
761 f.debug_map().entries(self.iter_all()).finish()
762 }
763}
764
765impl<K, V, S> PartialEq for MultiMap<K, V, S>
766where
767 K: Eq + Hash,
768 V: PartialEq,
769 S: BuildHasher,
770{
771 fn eq(&self, other: &MultiMap<K, V, S>) -> bool {
772 if self.len() != other.len() {
773 return false;
774 }
775
776 self.iter_all()
777 .all(|(key, value)| other.get_vec(key).is_some_and(|v| *value == *v))
778 }
779}
780
781impl<K, V, S> Eq for MultiMap<K, V, S>
782where
783 K: Eq + Hash,
784 V: Eq,
785 S: BuildHasher,
786{
787}
788
789impl<K, V, S> Default for MultiMap<K, V, S>
790where
791 K: Eq + Hash,
792 S: BuildHasher + Default,
793{
794 fn default() -> MultiMap<K, V, S> {
795 MultiMap {
796 inner: Default::default(),
797 }
798 }
799}
800
801impl<K, V, S> FromIterator<(K, V)> for MultiMap<K, V, S>
802where
803 K: Eq + Hash,
804 S: BuildHasher + Default,
805{
806 fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> MultiMap<K, V, S> {
807 let iter = iterable.into_iter();
808 let hint = iter.size_hint().0;
809
810 let mut multimap = MultiMap::with_capacity_and_hasher(hint, S::default());
811 for (k, v) in iter {
812 multimap.insert(k, v);
813 }
814
815 multimap
816 }
817}
818
819impl<K, V, S> FromIterator<(K, Vec<V>)> for MultiMap<K, V, S>
820where
821 K: Eq + Hash,
822 V: Clone,
823 S: BuildHasher + Default,
824{
825 fn from_iter<T: IntoIterator<Item = (K, Vec<V>)>>(iterable: T) -> MultiMap<K, V, S> {
826 let iter = iterable.into_iter();
827 let hint = iter.size_hint().0;
828
829 let mut multimap = MultiMap::with_capacity_and_hasher(hint, S::default());
830 for (k, v) in iter {
831 multimap.insert_many_from_slice(k, &v[..])
832 }
833
834 multimap
835 }
836}
837
838impl<'a, K, V, S> IntoIterator for &'a MultiMap<K, V, S>
839where
840 K: Eq + Hash,
841 S: BuildHasher,
842{
843 type Item = (&'a K, &'a Vec<V>);
844 type IntoIter = IterAll<'a, K, Vec<V>>;
845
846 fn into_iter(self) -> IterAll<'a, K, Vec<V>> {
847 self.iter_all()
848 }
849}
850
851impl<'a, K, V, S> IntoIterator for &'a mut MultiMap<K, V, S>
852where
853 K: Eq + Hash,
854 S: BuildHasher,
855{
856 type Item = (&'a K, &'a mut Vec<V>);
857 type IntoIter = IterAllMut<'a, K, Vec<V>>;
858
859 fn into_iter(self) -> IterAllMut<'a, K, Vec<V>> {
860 self.inner.iter_mut()
861 }
862}
863
864impl<K, V, S> IntoIterator for MultiMap<K, V, S>
865where
866 K: Eq + Hash,
867 S: BuildHasher,
868{
869 type Item = (K, Vec<V>);
870 type IntoIter = IntoIter<K, Vec<V>>;
871
872 fn into_iter(self) -> IntoIter<K, Vec<V>> {
873 self.inner.into_iter()
874 }
875}
876
877impl<K, V, S> Extend<(K, V)> for MultiMap<K, V, S>
878where
879 K: Eq + Hash,
880 S: BuildHasher,
881{
882 fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
883 for (k, v) in iter {
884 self.insert(k, v);
885 }
886 }
887}
888
889impl<'a, K, V, S> Extend<(&'a K, &'a V)> for MultiMap<K, V, S>
890where
891 K: Eq + Hash + Copy,
892 V: Copy,
893 S: BuildHasher,
894{
895 fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
896 self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
897 }
898}
899
900impl<K, V, S> Extend<(K, Vec<V>)> for MultiMap<K, V, S>
901where
902 K: Eq + Hash,
903 S: BuildHasher,
904{
905 fn extend<T: IntoIterator<Item = (K, Vec<V>)>>(&mut self, iter: T) {
906 for (k, values) in iter {
907 match self.entry(k) {
908 Entry::Occupied(mut entry) => {
909 entry.get_vec_mut().extend(values);
910 }
911 Entry::Vacant(entry) => {
912 entry.insert_vec(values);
913 }
914 }
915 }
916 }
917}
918
919impl<'a, K, V, S> Extend<(&'a K, &'a Vec<V>)> for MultiMap<K, V, S>
920where
921 K: Eq + Hash + Copy,
922 V: Copy,
923 S: BuildHasher,
924{
925 fn extend<T: IntoIterator<Item = (&'a K, &'a Vec<V>)>>(&mut self, iter: T) {
926 self.extend(
927 iter.into_iter()
928 .map(|(&key, values)| (key, values.to_owned())),
929 );
930 }
931}
932
933#[derive(Clone)]
934pub struct Iter<'a, K: 'a, V: 'a> {
935 inner: IterAll<'a, K, Vec<V>>,
936}
937
938impl<'a, K, V> Iterator for Iter<'a, K, V> {
939 type Item = (&'a K, &'a V);
940
941 fn next(&mut self) -> Option<(&'a K, &'a V)> {
942 let (k, v) = self.inner.next()?;
943 let v = v.first()?;
944 Some((k, v))
945 }
946
947 fn size_hint(&self) -> (usize, Option<usize>) {
948 self.inner.size_hint()
949 }
950}
951
952impl<K, V> ExactSizeIterator for Iter<'_, K, V> {
953 fn len(&self) -> usize {
954 self.inner.len()
955 }
956}
957
958pub struct IterMut<'a, K: 'a, V: 'a> {
959 inner: IterAllMut<'a, K, Vec<V>>,
960}
961
962impl<'a, K, V> Iterator for IterMut<'a, K, V> {
963 type Item = (&'a K, &'a mut V);
964
965 fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
966 let (k, v) = self.inner.next()?;
967 let v = v.first_mut()?;
968 Some((k, v))
969 }
970
971 fn size_hint(&self) -> (usize, Option<usize>) {
972 self.inner.size_hint()
973 }
974}
975
976impl<K, V> ExactSizeIterator for IterMut<'_, K, V> {
977 fn len(&self) -> usize {
978 self.inner.len()
979 }
980}
981
982#[macro_export]
983macro_rules! multimap{
1002 (@replace_with_unit $_t:tt) => { () };
1003 (@count $($key:expr),*) => { <[()]>::len(&[$($crate::multimap! { @replace_with_unit $key }),*]) };
1004
1005 ($($key:expr => $value:expr),* $(,)?)=>{
1006 {
1007 let mut map = $crate::MultiMap::with_capacity($crate::multimap! { @count $($key),* });
1008 $(
1009 map.insert($key,$value);
1010 )*
1011 map
1012 }
1013 }
1014}
1015
1016#[cfg(test)]
1017mod tests {
1018 use std::collections::HashMap;
1019 use std::iter::FromIterator;
1020
1021 use super::*;
1022
1023 #[test]
1024 fn create() {
1025 let _: MultiMap<usize, usize> = MultiMap {
1026 inner: HashMap::new(),
1027 };
1028 }
1029
1030 #[test]
1031 fn new() {
1032 let _: MultiMap<usize, usize> = MultiMap::new();
1033 }
1034
1035 #[test]
1036 fn with_capacity() {
1037 let _: MultiMap<usize, usize> = MultiMap::with_capacity(20);
1038 }
1039
1040 #[test]
1041 fn insert() {
1042 let mut m: MultiMap<usize, usize> = MultiMap::new();
1043 m.insert(1, 3);
1044 }
1045
1046 #[test]
1047 fn insert_identical() {
1048 let mut m = MultiMap::new();
1049 m.insert(1, 42);
1050 m.insert(1, 42);
1051 assert_eq!(m.get_vec(&1), Some(&vec![42, 42]));
1052 }
1053
1054 #[test]
1055 fn insert_many() {
1056 let mut m: MultiMap<usize, usize> = MultiMap::new();
1057 m.insert_many(1, vec![3, 4]);
1058 assert_eq!(Some(&vec![3, 4]), m.get_vec(&1));
1059 }
1060
1061 #[test]
1062 fn insert_many_again() {
1063 let mut m: MultiMap<usize, usize> = MultiMap::new();
1064 m.insert(1, 2);
1065 m.insert_many(1, vec![3, 4]);
1066 assert_eq!(Some(&vec![2, 3, 4]), m.get_vec(&1));
1067 }
1068
1069 #[test]
1070 fn insert_many_overlap() {
1071 let mut m: MultiMap<usize, usize> = MultiMap::new();
1072 m.insert_many(1, vec![2, 3]);
1073 m.insert_many(1, vec![3, 4]);
1074 assert_eq!(Some(&vec![2, 3, 3, 4]), m.get_vec(&1));
1075 }
1076
1077 #[test]
1078 fn insert_many_from_slice() {
1079 let mut m: MultiMap<usize, usize> = MultiMap::new();
1080 m.insert_many_from_slice(1, &[3, 4]);
1081 assert_eq!(Some(&vec![3, 4]), m.get_vec(&1));
1082 }
1083
1084 #[test]
1085 fn insert_many_from_slice_again() {
1086 let mut m: MultiMap<usize, usize> = MultiMap::new();
1087 m.insert(1, 2);
1088 m.insert_many_from_slice(1, &[3, 4]);
1089 assert_eq!(Some(&vec![2, 3, 4]), m.get_vec(&1));
1090 }
1091
1092 #[test]
1093 fn insert_existing() {
1094 let mut m: MultiMap<usize, usize> = MultiMap::new();
1095 m.insert(1, 3);
1096 m.insert(1, 4);
1097 assert_eq!(Some(&vec![3, 4]), m.get_vec(&1));
1098 }
1099
1100 #[test]
1101 #[should_panic(expected = "no entry found for key")]
1102 fn index_no_entry() {
1103 let m: MultiMap<usize, usize> = MultiMap::new();
1104 let _ = &m[&1];
1105 }
1106
1107 #[test]
1108 fn index() {
1109 let mut m: MultiMap<usize, usize> = MultiMap::new();
1110 m.insert(1, 41);
1111 m.insert(2, 42);
1112 m.insert(3, 43);
1113 let values = m[&2];
1114 assert_eq!(values, 42);
1115 }
1116
1117 #[test]
1118 #[should_panic(expected = "no value found for key")]
1119 fn index_empty_vec() {
1120 let mut m: MultiMap<usize, usize> = MultiMap::new();
1121 m.insert(1, 42);
1122 m.get_vec_mut(&1).unwrap().clear();
1123 let values = m[&1];
1124 assert_eq!(values, 42);
1125 }
1126
1127 #[test]
1128 fn contains_key_true() {
1129 let mut m: MultiMap<usize, usize> = MultiMap::new();
1130 m.insert(1, 42);
1131 assert!(m.contains_key(&1));
1132 }
1133
1134 #[test]
1135 fn contains_key_false() {
1136 let m: MultiMap<usize, usize> = MultiMap::new();
1137 assert!(!m.contains_key(&1));
1138 }
1139
1140 #[test]
1141 fn len() {
1142 let mut m: MultiMap<usize, usize> = MultiMap::new();
1143 m.insert(1, 42);
1144 m.insert(2, 1337);
1145 m.insert(3, 99);
1146 assert_eq!(m.len(), 3);
1147 }
1148
1149 #[test]
1150 fn remove_not_present() {
1151 let mut m: MultiMap<usize, usize> = MultiMap::new();
1152 let v = m.remove(&1);
1153 assert_eq!(v, None);
1154 }
1155
1156 #[test]
1157 fn remove_present() {
1158 let mut m: MultiMap<usize, usize> = MultiMap::new();
1159 m.insert(1, 42);
1160 let v = m.remove(&1);
1161 assert_eq!(v, Some(vec![42]));
1162 }
1163
1164 #[test]
1165 fn get_not_present() {
1166 let m: MultiMap<usize, usize> = MultiMap::new();
1167 assert_eq!(m.get(&1), None);
1168 }
1169
1170 #[test]
1171 fn get_present() {
1172 let mut m: MultiMap<usize, usize> = MultiMap::new();
1173 m.insert(1, 42);
1174 assert_eq!(m.get(&1), Some(&42));
1175 }
1176
1177 #[test]
1178 fn get_empty() {
1179 let mut m: MultiMap<usize, usize> = MultiMap::new();
1180 m.insert(1, 42);
1181 m.get_vec_mut(&1).and_then(Vec::pop);
1182 assert_eq!(m.get(&1), None);
1183 }
1184
1185 #[test]
1186 fn get_vec_not_present() {
1187 let m: MultiMap<usize, usize> = MultiMap::new();
1188 assert_eq!(m.get_vec(&1), None);
1189 }
1190
1191 #[test]
1192 fn get_vec_present() {
1193 let mut m: MultiMap<usize, usize> = MultiMap::new();
1194 m.insert(1, 42);
1195 m.insert(1, 1337);
1196 assert_eq!(m.get_vec(&1), Some(&vec![42, 1337]));
1197 }
1198
1199 #[test]
1200 fn capacity() {
1201 let m: MultiMap<usize, usize> = MultiMap::with_capacity(20);
1202 assert!(m.capacity() >= 20);
1203 }
1204
1205 #[test]
1206 fn is_empty_true() {
1207 let m: MultiMap<usize, usize> = MultiMap::new();
1208 assert!(m.is_empty());
1209 }
1210
1211 #[test]
1212 fn is_empty_false() {
1213 let mut m: MultiMap<usize, usize> = MultiMap::new();
1214 m.insert(1, 42);
1215 assert!(!m.is_empty());
1216 }
1217
1218 #[test]
1219 fn clear() {
1220 let mut m: MultiMap<usize, usize> = MultiMap::new();
1221 m.insert(1, 42);
1222 m.clear();
1223 assert!(m.is_empty());
1224 }
1225
1226 #[test]
1227 fn get_mut() {
1228 let mut m: MultiMap<usize, usize> = MultiMap::new();
1229 m.insert(1, 42);
1230 if let Some(v) = m.get_mut(&1) {
1231 *v = 1337;
1232 }
1233 assert_eq!(m[&1], 1337)
1234 }
1235
1236 #[test]
1237 fn get_vec_mut() {
1238 let mut m: MultiMap<usize, usize> = MultiMap::new();
1239 m.insert(1, 42);
1240 m.insert(1, 1337);
1241 if let Some(v) = m.get_vec_mut(&1) {
1242 (*v)[0] = 5;
1243 (*v)[1] = 10;
1244 }
1245 assert_eq!(m.get_vec(&1), Some(&vec![5, 10]))
1246 }
1247
1248 #[test]
1249 fn get_mut_empty() {
1250 let mut m: MultiMap<usize, usize> = MultiMap::new();
1251 m.insert(1, 42);
1252 m.get_vec_mut(&1).and_then(Vec::pop);
1253 assert_eq!(m.get_mut(&1), None);
1254 }
1255
1256 #[test]
1257 fn keys() {
1258 let mut m: MultiMap<usize, usize> = MultiMap::new();
1259 m.insert(1, 42);
1260 m.insert(2, 42);
1261 m.insert(4, 42);
1262 m.insert(8, 42);
1263
1264 let keys: Vec<_> = m.keys().cloned().collect();
1265 assert_eq!(keys.len(), 4);
1266 assert!(keys.contains(&1));
1267 assert!(keys.contains(&2));
1268 assert!(keys.contains(&4));
1269 assert!(keys.contains(&8));
1270 }
1271
1272 #[test]
1273 fn iter() {
1274 let mut m: MultiMap<usize, usize> = MultiMap::new();
1275 m.insert(1, 42);
1276 m.insert(1, 42);
1277 m.insert(4, 42);
1278 m.insert(8, 42);
1279
1280 assert!(m.iter().all(|(_, &v)| v == 42));
1281
1282 let mut iter = m.iter();
1283
1284 for _ in iter.by_ref().take(2) {}
1285
1286 assert_eq!(iter.len(), 1);
1287 }
1288
1289 #[test]
1290 fn iter_empty_vec() {
1291 let mut m: MultiMap<usize, usize> = MultiMap::new();
1292 m.insert(42, 42);
1293 m.get_vec_mut(&42).unwrap().clear();
1294
1295 assert!(m.iter().next().is_none());
1296 }
1297
1298 #[test]
1299 fn flat_iter() {
1300 let mut m: MultiMap<usize, usize> = MultiMap::new();
1301 m.insert(1, 42);
1302 m.insert(1, 43);
1303 m.insert(4, 42);
1304 m.insert(8, 42);
1305
1306 let keys = [1, 4, 8];
1307
1308 for (key, value) in m.flat_iter() {
1309 assert!(keys.contains(key));
1310
1311 if key == &1 {
1312 assert!(value == &42 || value == &43);
1313 } else {
1314 assert_eq!(value, &42);
1315 }
1316 }
1317 }
1318
1319 #[test]
1320 fn flat_iter_mut() {
1321 let mut m: MultiMap<usize, usize> = MultiMap::new();
1322 m.insert(1, 42);
1323 m.insert(1, 43);
1324 m.insert(4, 42);
1325 m.insert(8, 42);
1326
1327 let keys = [1, 4, 8];
1328
1329 for (key, value) in m.flat_iter_mut() {
1330 assert!(keys.contains(key));
1331
1332 if key == &1 {
1333 assert!(value == &42 || value == &43);
1334
1335 *value = 55;
1336 assert_eq!(value, &55);
1337 } else {
1338 assert_eq!(value, &42);
1339
1340 *value = 76;
1341 assert_eq!(value, &76);
1342 }
1343 }
1344 }
1345
1346 #[test]
1347 fn intoiterator_for_reference_type() {
1348 let mut m: MultiMap<usize, usize> = MultiMap::new();
1349 m.insert(1, 42);
1350 m.insert(1, 43);
1351 m.insert(4, 42);
1352 m.insert(8, 42);
1353
1354 let keys = [1, 4, 8];
1355
1356 for (key, value) in &m {
1357 assert!(keys.contains(key));
1358
1359 if key == &1 {
1360 assert_eq!(value, &vec![42, 43]);
1361 } else {
1362 assert_eq!(value, &vec![42]);
1363 }
1364 }
1365 }
1366
1367 #[test]
1368 fn intoiterator_for_mutable_reference_type() {
1369 let mut m: MultiMap<usize, usize> = MultiMap::new();
1370 m.insert(1, 42);
1371 m.insert(1, 43);
1372 m.insert(4, 42);
1373 m.insert(8, 42);
1374
1375 let keys = [1, 4, 8];
1376
1377 for (key, value) in &mut m {
1378 assert!(keys.contains(key));
1379
1380 if key == &1 {
1381 assert_eq!(value, &vec![42, 43]);
1382 value.push(666);
1383 } else {
1384 assert_eq!(value, &vec![42]);
1385 }
1386 }
1387
1388 assert_eq!(m.get_vec(&1), Some(&vec![42, 43, 666]));
1389 }
1390
1391 #[test]
1392 fn intoiterator_consuming() {
1393 let mut m: MultiMap<usize, usize> = MultiMap::new();
1394 m.insert(1, 42);
1395 m.insert(1, 43);
1396 m.insert(4, 42);
1397 m.insert(8, 42);
1398
1399 let keys = [1, 4, 8];
1400
1401 for (key, value) in m {
1402 assert!(keys.contains(&key));
1403
1404 if key == 1 {
1405 assert_eq!(value, vec![42, 43]);
1406 } else {
1407 assert_eq!(value, vec![42]);
1408 }
1409 }
1410 }
1411
1412 #[test]
1413 fn test_fmt_debug() {
1414 let mut map = MultiMap::new();
1415 let empty: MultiMap<i32, i32> = MultiMap::new();
1416
1417 map.insert(1, 2);
1418 map.insert(1, 5);
1419 map.insert(1, -1);
1420 map.insert(3, 4);
1421
1422 let map_str = format!("{:?}", map);
1423
1424 assert!(map_str == "{1: [2, 5, -1], 3: [4]}" || map_str == "{3: [4], 1: [2, 5, -1]}");
1425 assert_eq!(format!("{:?}", empty), "{}");
1426 }
1427
1428 #[test]
1429 fn test_eq() {
1430 let mut m1 = MultiMap::new();
1431 m1.insert(1, 2);
1432 m1.insert(2, 3);
1433 m1.insert(3, 4);
1434 let mut m2 = MultiMap::new();
1435 m2.insert(1, 2);
1436 m2.insert(2, 3);
1437 assert_ne!(m1, m2);
1438 m2.insert(3, 4);
1439 assert_eq!(m1, m2);
1440 m2.insert(3, 4);
1441 assert_ne!(m1, m2);
1442 m1.insert(3, 4);
1443 assert_eq!(m1, m2);
1444 }
1445
1446 #[test]
1447 fn test_eq_empty_key() {
1448 let mut m1 = MultiMap::new();
1449 m1.insert(1, 2);
1450 m1.insert(2, 3);
1451 let mut m2 = MultiMap::new();
1452 m2.insert(1, 2);
1453 m2.insert_many(2, []);
1454 assert_ne!(m1, m2);
1455 m2.insert_many(2, [3]);
1456 assert_eq!(m1, m2);
1457 }
1458
1459 #[test]
1460 fn test_default() {
1461 let _: MultiMap<u8, u8> = Default::default();
1462 }
1463
1464 #[test]
1465 fn test_from_iterator() {
1466 let vals: Vec<(&str, i64)> = vec![("foo", 123), ("bar", 456), ("foo", 789)];
1467 let multimap: MultiMap<&str, i64> = MultiMap::from_iter(vals);
1468
1469 let foo_vals: &Vec<i64> = multimap.get_vec("foo").unwrap();
1470 assert!(foo_vals.contains(&123));
1471 assert!(foo_vals.contains(&789));
1472
1473 let bar_vals: &Vec<i64> = multimap.get_vec("bar").unwrap();
1474 assert!(bar_vals.contains(&456));
1475 }
1476
1477 #[test]
1478 fn test_from_vec_iterator() {
1479 let vals: Vec<(&str, Vec<i64>)> = vec![
1480 ("foo", vec![123, 456]),
1481 ("bar", vec![234]),
1482 ("foobar", vec![567, 678, 789]),
1483 ("bar", vec![12, 23, 34]),
1484 ];
1485
1486 let multimap: MultiMap<&str, i64> = MultiMap::from_iter(vals);
1487
1488 let foo_vals: &Vec<i64> = multimap.get_vec("foo").unwrap();
1489 assert!(foo_vals.contains(&123));
1490 assert!(foo_vals.contains(&456));
1491
1492 let bar_vals: &Vec<i64> = multimap.get_vec("bar").unwrap();
1493 assert!(bar_vals.contains(&234));
1494 assert!(bar_vals.contains(&12));
1495 assert!(bar_vals.contains(&23));
1496 assert!(bar_vals.contains(&34));
1497
1498 let foobar_vals: &Vec<i64> = multimap.get_vec("foobar").unwrap();
1499 assert!(foobar_vals.contains(&567));
1500 assert!(foobar_vals.contains(&678));
1501 assert!(foobar_vals.contains(&789));
1502 }
1503
1504 #[test]
1505 fn test_extend_consuming_hashmap() {
1506 let mut a = MultiMap::new();
1507 a.insert(1, 42);
1508
1509 let mut b = HashMap::new();
1510 b.insert(1, 43);
1511 b.insert(2, 666);
1512
1513 a.extend(b);
1514
1515 assert_eq!(a.len(), 2);
1516 assert_eq!(a.get_vec(&1), Some(&vec![42, 43]));
1517 }
1518
1519 #[test]
1520 fn test_extend_ref_hashmap() {
1521 let mut a = MultiMap::new();
1522 a.insert(1, 42);
1523
1524 let mut b = HashMap::new();
1525 b.insert(1, 43);
1526 b.insert(2, 666);
1527
1528 a.extend(&b);
1529
1530 assert_eq!(a.len(), 2);
1531 assert_eq!(a.get_vec(&1), Some(&vec![42, 43]));
1532 assert_eq!(b.len(), 2);
1533 assert_eq!(b[&1], 43);
1534 }
1535
1536 #[test]
1537 fn test_extend_consuming_multimap() {
1538 let mut a = MultiMap::new();
1539 a.insert(1, 42);
1540
1541 let mut b = MultiMap::new();
1542 b.insert(1, 43);
1543 b.insert(1, 44);
1544 b.insert(2, 666);
1545
1546 a.extend(b);
1547
1548 assert_eq!(a.len(), 2);
1549 assert_eq!(a.get_vec(&1), Some(&vec![42, 43, 44]));
1550 }
1551
1552 #[test]
1553 fn test_extend_ref_multimap() {
1554 let mut a = MultiMap::new();
1555 a.insert(1, 42);
1556
1557 let mut b = MultiMap::new();
1558 b.insert(1, 43);
1559 b.insert(1, 44);
1560 b.insert(2, 666);
1561
1562 a.extend(&b);
1563
1564 assert_eq!(a.len(), 2);
1565 assert_eq!(a.get_vec(&1), Some(&vec![42, 43, 44]));
1566 assert_eq!(b.len(), 2);
1567 assert_eq!(b.get_vec(&1), Some(&vec![43, 44]));
1568 }
1569
1570 #[test]
1571 fn test_entry() {
1572 let mut m = MultiMap::new();
1573 m.insert(1, 42);
1574
1575 {
1576 let v = m.entry(1).or_insert(43);
1577 assert_eq!(v, &42);
1578 *v = 44;
1579 }
1580 assert_eq!(m.entry(2).or_insert(666), &666);
1581
1582 assert_eq!(m[&1], 44);
1583 assert_eq!(m[&2], 666);
1584 }
1585
1586 #[test]
1587 fn test_entry_vec() {
1588 let mut m = MultiMap::new();
1589 m.insert(1, 42);
1590
1591 {
1592 let v = m.entry(1).or_insert_vec(vec![43]);
1593 assert_eq!(v, &vec![42]);
1594 *v.first_mut().unwrap() = 44;
1595 }
1596 assert_eq!(m.entry(2).or_insert_vec(vec![666]), &vec![666]);
1597
1598 assert_eq!(m[&1], 44);
1599 assert_eq!(m[&2], 666);
1600 }
1601
1602 #[test]
1603 fn test_is_vec() {
1604 let mut m = MultiMap::new();
1605 m.insert(1, 42);
1606 m.insert(1, 1337);
1607 m.insert(2, 2332);
1608
1609 assert!(m.is_vec(&1));
1610 assert!(!m.is_vec(&2));
1611 assert!(!m.is_vec(&3));
1612 }
1613
1614 #[test]
1615 fn test_macro() {
1616 let mut manual_map = MultiMap::new();
1617 manual_map.insert("key1", 42);
1618 assert_eq!(manual_map, multimap!("key1" => 42));
1619
1620 manual_map.insert("key1", 1337);
1621 manual_map.insert("key2", 2332);
1622 let macro_map = multimap! {
1623 "key1" => 42,
1624 "key1" => 1337,
1625 "key2" => 2332
1626 };
1627 assert_eq!(manual_map, macro_map);
1628 }
1629
1630 #[test]
1631 fn retain_removes_element() {
1632 let mut m = MultiMap::new();
1633 m.insert(1, 42);
1634 m.insert(1, 99);
1635 m.retain(|&k, &v| k == 1 && v == 42);
1636 assert_eq!(1, m.len());
1637 assert_eq!(Some(&42), m.get(&1));
1638 }
1639
1640 #[test]
1641 fn retain_also_removes_empty_vector() {
1642 let mut m = MultiMap::new();
1643 m.insert(1, 42);
1644 m.insert(1, 99);
1645 m.insert(2, 42);
1646 m.retain(|&k, &v| k == 1 && v == 42);
1647 assert_eq!(1, m.len());
1648 assert_eq!(Some(&42), m.get(&1));
1649 }
1650}