multimap/
lib.rs

1#![forbid(unsafe_code)]
2// Copyright (c) 2016 multimap developers
3//
4// Licensed under the Apache License, Version 2.0
5// <LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0> or the MIT
6// license <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your
7// option. All files in the project carrying such notice may not be copied,
8// modified, or distributed except according to those terms.
9
10//! A map implementation which allows storing multiple values per key.
11//!
12//! The interface is roughly based on std::collections::HashMap, but is changed
13//! and extended to accomodate the multi-value use case. In fact, MultiMap is
14//! implemented mostly as a thin wrapper around std::collections::HashMap and
15//! stores its values as a std::Vec per key.
16//!
17//! Values are guaranteed to be in insertion order as long as not manually
18//! changed. Keys are not ordered. Multiple idential key-value-pairs can exist
19//! in the MultiMap. A key can exist in the MultiMap with no associated value.
20//!
21//! # Examples
22//!
23//! ```
24//! use multimap::MultiMap;
25//!
26//! // create a new MultiMap. An explicit type signature can be omitted because of the
27//! // type inference.
28//! let mut queries = MultiMap::new();
29//!
30//! // insert some queries.
31//! queries.insert("urls", "http://rust-lang.org");
32//! queries.insert("urls", "http://mozilla.org");
33//! queries.insert("urls", "http://wikipedia.org");
34//! queries.insert("id", "42");
35//! queries.insert("name", "roger");
36//!
37//! // check if there's any urls.
38//! println!("Are there any urls in the multimap? {:?}.",
39//!     if queries.contains_key("urls") {"Yes"} else {"No"} );
40//!
41//! // get the first item in a key's vector.
42//! assert_eq!(queries.get("urls"), Some(&"http://rust-lang.org"));
43//!
44//! // get all the urls.
45//! assert_eq!(queries.get_vec("urls"),
46//!     Some(&vec!["http://rust-lang.org", "http://mozilla.org", "http://wikipedia.org"]));
47//!
48//! // iterate over all keys and the first value in the key's vector.
49//! for (key, value) in queries.iter() {
50//!     println!("key: {:?}, val: {:?}", key, value);
51//! }
52//!
53//! // iterate over all keys and the key's vector.
54//! for (key, values) in queries.iter_all() {
55//!     println!("key: {:?}, values: {:?}", key, values);
56//! }
57//!
58//! // the different methods for getting value(s) from the multimap.
59//! let mut map = MultiMap::new();
60//!
61//! map.insert("key1", 42);
62//! map.insert("key1", 1337);
63//!
64//! assert_eq!(map["key1"], 42);
65//! assert_eq!(map.get("key1"), Some(&42));
66//! assert_eq!(map.get_vec("key1"), Some(&vec![42, 1337]));
67//! ```
68
69use 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    /// Creates an empty MultiMap
97    ///
98    /// # Examples
99    ///
100    /// ```
101    /// use multimap::MultiMap;
102    ///
103    /// let mut map: MultiMap<&str, isize> = MultiMap::new();
104    /// ```
105    pub fn new() -> MultiMap<K, V> {
106        MultiMap {
107            inner: HashMap::new(),
108        }
109    }
110
111    /// Creates an empty multimap with the given initial capacity.
112    ///
113    /// # Examples
114    ///
115    /// ```
116    /// use multimap::MultiMap;
117    ///
118    /// let mut map: MultiMap<&str, isize> = MultiMap::with_capacity(20);
119    /// ```
120    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    /// Creates an empty MultiMap which will use the given hash builder to hash keys.
133    ///
134    /// # Examples
135    ///
136    /// ```
137    /// use multimap::MultiMap;
138    /// use std::collections::hash_map::RandomState;
139    ///
140    /// let s = RandomState::new();
141    /// let mut map: MultiMap<&str, isize> = MultiMap::with_hasher(s);
142    /// ```
143    pub fn with_hasher(hash_builder: S) -> MultiMap<K, V, S> {
144        MultiMap {
145            inner: HashMap::with_hasher(hash_builder),
146        }
147    }
148
149    /// Creates an empty MultiMap with the given intial capacity and hash builder.
150    ///
151    /// # Examples
152    ///
153    /// ```
154    /// use multimap::MultiMap;
155    /// use std::collections::hash_map::RandomState;
156    ///
157    /// let s = RandomState::new();
158    /// let mut map: MultiMap<&str, isize> = MultiMap::with_capacity_and_hasher(20, s);
159    /// ```
160    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    /// Inserts a key-value pair into the multimap. If the key does exist in
167    /// the map then the value is pushed to that key's vector. If the key doesn't
168    /// exist in the map a new vector with the given value is inserted.
169    ///
170    /// # Examples
171    ///
172    /// ```
173    /// use multimap::MultiMap;
174    ///
175    /// let mut map = MultiMap::new();
176    /// map.insert("key", 42);
177    /// ```
178    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    /// Inserts multiple key-value pairs into the multimap. If the key does exist in
190    /// the map then the values are extended into that key's vector. If the key
191    /// doesn't exist in the map a new vector collected from the given values is inserted.
192    ///
193    /// This may be more efficient than inserting values independently.
194    ///
195    /// # Examples
196    ///
197    /// ```
198    /// use multimap::MultiMap;
199    ///
200    /// let mut map = MultiMap::<&str, &usize>::new();
201    /// map.insert_many("key", &[42, 43]);
202    /// ```
203    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    /// Inserts multiple key-value pairs into the multimap. If the key does exist in
215    /// the map then the values are extended into that key's vector. If the key
216    /// doesn't exist in the map a new vector collected from the given values is inserted.
217    ///
218    /// This may be more efficient than inserting values independently.
219    ///
220    /// # Examples
221    ///
222    /// ```
223    /// use multimap::MultiMap;
224    ///
225    /// let mut map = MultiMap::<&str, usize>::new();
226    /// map.insert_many_from_slice("key", &[42, 43]);
227    /// ```
228    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    /// Returns true if the map contains a value for the specified key.
243    ///
244    /// The key may be any borrowed form of the map's key type, but Hash and Eq
245    /// on the borrowed form must match those for the key type.
246    ///
247    /// # Examples
248    ///
249    /// ```
250    /// use multimap::MultiMap;
251    ///
252    /// let mut map = MultiMap::new();
253    /// map.insert(1, 42);
254    /// assert_eq!(map.contains_key(&1), true);
255    /// assert_eq!(map.contains_key(&2), false);
256    /// ```
257    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    /// Returns the number of unique keys in the map.
266    ///
267    /// # Examples
268    ///
269    /// ```
270    /// use multimap::MultiMap;
271    ///
272    /// let mut map = MultiMap::new();
273    /// map.insert(1, 42);
274    /// map.insert(2, 1337);
275    /// map.insert(2, 31337);
276    /// assert_eq!(map.len(), 2);
277    /// ```
278    pub fn len(&self) -> usize {
279        self.inner.len()
280    }
281
282    /// Removes a key from the map, returning the vector of values at
283    /// the key if the key was previously in the map.
284    ///
285    /// The key may be any borrowed form of the map's key type, but Hash and Eq
286    /// on the borrowed form must match those for the key type.
287    ///
288    /// # Examples
289    ///
290    /// ```
291    /// use multimap::MultiMap;
292    ///
293    /// let mut map = MultiMap::new();
294    /// map.insert(1, 42);
295    /// map.insert(1, 1337);
296    /// assert_eq!(map.remove(&1), Some(vec![42, 1337]));
297    /// assert_eq!(map.remove(&1), None);
298    /// ```
299    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    /// Returns a reference to the first item in the vector corresponding to
308    /// the key.
309    ///
310    /// The key may be any borrowed form of the map's key type, but Hash and Eq
311    /// on the borrowed form must match those for the key type.
312    ///
313    /// # Examples
314    ///
315    /// ```
316    /// use multimap::MultiMap;
317    ///
318    /// let mut map = MultiMap::new();
319    /// map.insert(1, 42);
320    /// map.insert(1, 1337);
321    /// assert_eq!(map.get(&1), Some(&42));
322    /// ```
323    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    /// Returns a mutable reference to the first item in the vector corresponding to
332    /// the key.
333    ///
334    /// The key may be any borrowed form of the map's key type, but Hash and Eq
335    /// on the borrowed form must match those for the key type.
336    ///
337    /// # Examples
338    ///
339    /// ```
340    /// use multimap::MultiMap;
341    ///
342    /// let mut map = MultiMap::new();
343    /// map.insert(1, 42);
344    /// map.insert(1, 1337);
345    /// if let Some(v) = map.get_mut(&1) {
346    ///     *v = 99;
347    /// }
348    /// assert_eq!(map[&1], 99);
349    /// ```
350    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    /// Returns a reference to the vector corresponding to the key.
359    ///
360    /// The key may be any borrowed form of the map's key type, but Hash and Eq
361    /// on the borrowed form must match those for the key type.
362    ///
363    /// # Examples
364    ///
365    /// ```
366    /// use multimap::MultiMap;
367    ///
368    /// let mut map = MultiMap::new();
369    /// map.insert(1, 42);
370    /// map.insert(1, 1337);
371    /// assert_eq!(map.get_vec(&1), Some(&vec![42, 1337]));
372    /// ```
373    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    /// Returns a mutable reference to the vector corresponding to the key.
382    ///
383    /// The key may be any borrowed form of the map's key type, but Hash and Eq
384    /// on the borrowed form must match those for the key type.
385    ///
386    /// # Examples
387    ///
388    /// ```
389    /// use multimap::MultiMap;
390    ///
391    /// let mut map = MultiMap::new();
392    /// map.insert(1, 42);
393    /// map.insert(1, 1337);
394    /// if let Some(v) = map.get_vec_mut(&1) {
395    ///     (*v)[0] = 1991;
396    ///     (*v)[1] = 2332;
397    /// }
398    /// assert_eq!(map.get_vec(&1), Some(&vec![1991, 2332]));
399    /// ```
400    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    /// Returns true if the key is multi-valued.
409    ///
410    /// The key may be any borrowed form of the map's key type, but Hash and Eq
411    /// on the borrowed form must match those for the key type.
412    ///
413    /// # Examples
414    ///
415    /// ```
416    /// use multimap::MultiMap;
417    ///
418    /// let mut map = MultiMap::new();
419    /// map.insert(1, 42);
420    /// map.insert(1, 1337);
421    /// map.insert(2, 2332);
422    ///
423    /// assert_eq!(map.is_vec(&1), true);   // key is multi-valued
424    /// assert_eq!(map.is_vec(&2), false);  // key is single-valued
425    /// assert_eq!(map.is_vec(&3), false);  // key not in map
426    /// ```
427    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    /// Returns the number of elements the map can hold without reallocating.
439    ///
440    /// # Examples
441    ///
442    /// ```
443    /// use multimap::MultiMap;
444    ///
445    /// let map: MultiMap<usize, usize> = MultiMap::new();
446    /// assert!(map.capacity() >= 0);
447    /// ```
448    pub fn capacity(&self) -> usize {
449        self.inner.capacity()
450    }
451
452    /// Returns true if the map contains no elements.
453    ///
454    /// # Examples
455    ///
456    /// ```
457    /// use multimap::MultiMap;
458    ///
459    /// let mut map = MultiMap::new();
460    /// assert!(map.is_empty());
461    /// map.insert(1,42);
462    /// assert!(!map.is_empty());
463    /// ```
464    pub fn is_empty(&self) -> bool {
465        self.inner.is_empty()
466    }
467
468    /// Clears the map, removing all key-value pairs.
469    /// Keeps the allocated memory for reuse.
470    ///
471    /// # Examples
472    ///
473    /// ```
474    /// use multimap::MultiMap;
475    ///
476    /// let mut map = MultiMap::new();
477    /// map.insert(1,42);
478    /// map.clear();
479    /// assert!(map.is_empty());
480    /// ```
481    pub fn clear(&mut self) {
482        self.inner.clear();
483    }
484
485    /// An iterator visiting all keys in arbitrary order.
486    /// Iterator element type is &'a K.
487    ///
488    /// # Examples
489    ///
490    /// ```
491    /// use multimap::MultiMap;
492    ///
493    /// let mut map = MultiMap::new();
494    /// map.insert(1,42);
495    /// map.insert(1,1337);
496    /// map.insert(2,1337);
497    /// map.insert(4,1991);
498    ///
499    /// let mut keys: Vec<_> = map.keys().collect();
500    /// keys.sort();
501    /// assert_eq!(keys, [&1, &2, &4]);
502    /// ```
503    pub fn keys(&'_ self) -> Keys<'_, K, Vec<V>> {
504        self.inner.keys()
505    }
506
507    /// An iterator visiting pairs of each key and its first value in arbitrary order.
508    /// The iterator returns
509    /// a reference to the key and the first element in the corresponding key's vector.
510    /// Iterator element type is (&'a K, &'a V).
511    ///
512    /// See [`flat_iter`](Self::flat_iter)
513    /// for visiting all key-value pairs,
514    /// or [`iter_all`](Self::iter_all)
515    /// for visiting each key and its vector of values.
516    ///
517    /// # Examples
518    ///
519    /// ```
520    /// use multimap::MultiMap;
521    ///
522    /// let mut map = MultiMap::new();
523    /// map.insert(1,42);
524    /// map.insert(1,1337);
525    /// map.insert(3,2332);
526    /// map.insert(4,1991);
527    ///
528    /// let mut pairs: Vec<_> = map.iter().collect();
529    /// pairs.sort_by_key(|p| p.0);
530    /// assert_eq!(pairs, [(&1, &42), (&3, &2332), (&4, &1991)]);
531    /// ```
532    pub fn iter(&self) -> Iter<K, V> {
533        Iter {
534            inner: self.inner.iter(),
535        }
536    }
537
538    /// A mutable iterator visiting pairs of each key and its first value
539    /// in arbitrary order. The iterator returns
540    /// a reference to the key and a mutable reference to the first element in the
541    /// corresponding key's vector. Iterator element type is (&'a K, &'a mut V).
542    ///
543    /// See [`flat_iter_mut`](Self::flat_iter_mut)
544    /// for visiting all key-value pairs,
545    /// or [`iter_all_mut`](Self::iter_all_mut)
546    /// for visiting each key and its vector of values.
547    ///
548    /// # Examples
549    ///
550    /// ```
551    /// use multimap::MultiMap;
552    ///
553    /// let mut map = MultiMap::new();
554    /// map.insert(1,42);
555    /// map.insert(1,1337);
556    /// map.insert(3,2332);
557    /// map.insert(4,1991);
558    ///
559    /// for (_, value) in map.iter_mut() {
560    ///     *value *= *value;
561    /// }
562    ///
563    /// let mut pairs: Vec<_> = map.iter_mut().collect();
564    /// pairs.sort_by_key(|p| p.0);
565    /// assert_eq!(pairs, [(&1, &mut 1764), (&3, &mut 5438224), (&4, &mut 3964081)]);
566    /// ```
567    pub fn iter_mut(&mut self) -> IterMut<K, V> {
568        IterMut {
569            inner: self.inner.iter_mut(),
570        }
571    }
572
573    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
574    /// a reference to the key and the corresponding key's vector.
575    /// Iterator element type is (&'a K, &'a V).
576    ///
577    /// # Examples
578    ///
579    /// ```
580    /// use multimap::MultiMap;
581    ///
582    /// let mut map = MultiMap::new();
583    /// map.insert(1,42);
584    /// map.insert(1,1337);
585    /// map.insert(3,2332);
586    /// map.insert(4,1991);
587    ///
588    /// let mut pairs: Vec<_> = map.iter_all().collect();
589    /// pairs.sort_by_key(|p| p.0);
590    /// assert_eq!(pairs, [(&1, &vec![42, 1337]), (&3, &vec![2332]), (&4, &vec![1991])]);
591    /// ```
592    pub fn iter_all(&self) -> IterAll<K, Vec<V>> {
593        self.inner.iter()
594    }
595
596    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
597    /// a reference to the key and the corresponding key's vector.
598    /// Iterator element type is (&'a K, &'a V).
599    ///
600    /// # Examples
601    ///
602    /// ```
603    /// use multimap::MultiMap;
604    ///
605    /// let mut map = MultiMap::new();
606    /// map.insert(1,42);
607    /// map.insert(1,1337);
608    /// map.insert(3,2332);
609    /// map.insert(4,1991);
610    ///
611    /// for (key, values) in map.iter_all_mut() {
612    ///     for value in values.iter_mut() {
613    ///         *value = 99;
614    ///     }
615    /// }
616    ///
617    /// let mut pairs: Vec<_> = map.iter_all_mut().collect();
618    /// pairs.sort_by_key(|p| p.0);
619    /// assert_eq!(pairs, [(&1, &mut vec![99, 99]), (&3, &mut vec![99]), (&4, &mut vec![99])]);
620    /// ```
621    pub fn iter_all_mut(&mut self) -> IterAllMut<K, Vec<V>> {
622        self.inner.iter_mut()
623    }
624
625    /// An iterator visiting all key-value pairs in arbitrary order.
626    ///
627    /// # Examples
628    ///
629    /// ```
630    /// use multimap::MultiMap;
631    ///
632    /// let mut map = MultiMap::new();
633    /// map.insert(1,42);
634    /// map.insert(1,1337);
635    /// map.insert(3,2332);
636    /// map.insert(4,1991);
637    ///
638    /// let mut pairs: Vec<_> = map.flat_iter().collect();
639    /// pairs.sort();
640    /// assert_eq!(pairs, [(&1, &42), (&1, &1337), (&3, &2332), (&4, &1991)]);
641    /// ```
642    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    /// A mutable iterator visiting all key-value pairs in arbitrary order.
648    ///
649    /// # Examples
650    ///
651    /// ```
652    /// use multimap::MultiMap;
653    ///
654    /// let mut map = MultiMap::new();
655    /// map.insert(1,42);
656    /// map.insert(1,1337);
657    /// map.insert(3,2332);
658    /// map.insert(4,1991);
659    ///
660    /// for (key, value) in map.flat_iter_mut() {
661    ///     *value *= key;
662    /// }
663    ///
664    /// let mut pairs: Vec<_> = map.flat_iter().collect();
665    /// pairs.sort();
666    /// assert_eq!(pairs, [(&1, &42), (&1, &1337), (&3, &6996), (&4, &7964)]);
667    /// ```
668    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    /// Gets the specified key's corresponding entry in the map for in-place manipulation.
674    /// It's possible to both manipulate the vector and the 'value' (the first value in the
675    /// vector).
676    ///
677    /// # Examples
678    ///
679    /// ```
680    /// use multimap::MultiMap;
681    ///
682    /// let mut m = MultiMap::new();
683    /// m.insert(1, 42);
684    ///
685    /// {
686    ///     let mut v = m.entry(1).or_insert(43);
687    ///     assert_eq!(v, &42);
688    ///     *v = 44;
689    /// }
690    /// assert_eq!(m.entry(2).or_insert(666), &666);
691    ///
692    /// {
693    ///     let mut v = m.entry(1).or_insert_vec(vec![43]);
694    ///     assert_eq!(v, &vec![44]);
695    ///     v.push(50);
696    /// }
697    /// assert_eq!(m.entry(2).or_insert_vec(vec![667]), &vec![666]);
698    ///
699    /// assert_eq!(m.get_vec(&1), Some(&vec![44, 50]));
700    /// ```
701    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    /// Retains only the elements specified by the predicate.
710    ///
711    /// In other words, remove all pairs `(k, v)` such that `f(&k,&mut v)` returns `false`.
712    ///
713    /// # Examples
714    ///
715    /// ```
716    /// use multimap::MultiMap;
717    ///
718    /// let mut m = MultiMap::new();
719    /// m.insert(1, 42);
720    /// m.insert(1, 99);
721    /// m.insert(2, 42);
722    /// m.retain(|&k, &v| { k == 1 && v == 42 });
723    /// assert_eq!(1, m.len());
724    /// assert_eq!(Some(&42), m.get(&1));
725    /// ```
726    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]
983/// Create a `MultiMap` from a list of key value pairs
984///
985/// ## Example
986///
987/// ```
988/// # use multimap::MultiMap;
989/// #[macro_use] extern crate multimap;
990/// # fn main(){
991///
992/// let map = multimap!(
993///     "dog" => "husky",
994///     "dog" => "retreaver",
995///     "dog" => "shiba inu",
996///     "cat" => "cat"
997///     );
998/// # }
999///
1000/// ```
1001macro_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}
multimap/lib.rs

multimap/
lib.rs
