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: ?Sized>(&self, k: &Q) -> bool
258    where
259        K: Borrow<Q>,
260        Q: Eq + Hash,
261    {
262        self.inner.contains_key(k)
263    }
264
265    /// Returns the number of elements 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    /// assert_eq!(map.len(), 2);
276    /// ```
277    pub fn len(&self) -> usize {
278        self.inner.len()
279    }
280
281    /// Removes a key from the map, returning the vector of values at
282    /// the key if the key was previously in the map.
283    ///
284    /// The key may be any borrowed form of the map's key type, but Hash and Eq
285    /// on the borrowed form must match those for the key type.
286    ///
287    /// # Examples
288    ///
289    /// ```
290    /// use multimap::MultiMap;
291    ///
292    /// let mut map = MultiMap::new();
293    /// map.insert(1, 42);
294    /// map.insert(1, 1337);
295    /// assert_eq!(map.remove(&1), Some(vec![42, 1337]));
296    /// assert_eq!(map.remove(&1), None);
297    /// ```
298    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<Vec<V>>
299    where
300        K: Borrow<Q>,
301        Q: Eq + Hash,
302    {
303        self.inner.remove(k)
304    }
305
306    /// Returns a reference to the first item in the vector corresponding to
307    /// the key.
308    ///
309    /// The key may be any borrowed form of the map's key type, but Hash and Eq
310    /// on the borrowed form must match those for the key type.
311    ///
312    /// # Examples
313    ///
314    /// ```
315    /// use multimap::MultiMap;
316    ///
317    /// let mut map = MultiMap::new();
318    /// map.insert(1, 42);
319    /// map.insert(1, 1337);
320    /// assert_eq!(map.get(&1), Some(&42));
321    /// ```
322    pub fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
323    where
324        K: Borrow<Q>,
325        Q: Eq + Hash,
326    {
327        self.inner.get(k)?.get(0)
328    }
329
330    /// Returns a mutable reference to the first item in the vector corresponding to
331    /// the key.
332    ///
333    /// The key may be any borrowed form of the map's key type, but Hash and Eq
334    /// on the borrowed form must match those for the key type.
335    ///
336    /// # Examples
337    ///
338    /// ```
339    /// use multimap::MultiMap;
340    ///
341    /// let mut map = MultiMap::new();
342    /// map.insert(1, 42);
343    /// map.insert(1, 1337);
344    /// if let Some(v) = map.get_mut(&1) {
345    ///     *v = 99;
346    /// }
347    /// assert_eq!(map[&1], 99);
348    /// ```
349    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
350    where
351        K: Borrow<Q>,
352        Q: Eq + Hash,
353    {
354        self.inner.get_mut(k)?.get_mut(0)
355    }
356
357    /// Returns a reference to the vector corresponding to the key.
358    ///
359    /// The key may be any borrowed form of the map's key type, but Hash and Eq
360    /// on the borrowed form must match those for the key type.
361    ///
362    /// # Examples
363    ///
364    /// ```
365    /// use multimap::MultiMap;
366    ///
367    /// let mut map = MultiMap::new();
368    /// map.insert(1, 42);
369    /// map.insert(1, 1337);
370    /// assert_eq!(map.get_vec(&1), Some(&vec![42, 1337]));
371    /// ```
372    pub fn get_vec<Q: ?Sized>(&self, k: &Q) -> Option<&Vec<V>>
373    where
374        K: Borrow<Q>,
375        Q: Eq + Hash,
376    {
377        self.inner.get(k)
378    }
379
380    /// Returns a mutable reference to the vector corresponding to the key.
381    ///
382    /// The key may be any borrowed form of the map's key type, but Hash and Eq
383    /// on the borrowed form must match those for the key type.
384    ///
385    /// # Examples
386    ///
387    /// ```
388    /// use multimap::MultiMap;
389    ///
390    /// let mut map = MultiMap::new();
391    /// map.insert(1, 42);
392    /// map.insert(1, 1337);
393    /// if let Some(v) = map.get_vec_mut(&1) {
394    ///     (*v)[0] = 1991;
395    ///     (*v)[1] = 2332;
396    /// }
397    /// assert_eq!(map.get_vec(&1), Some(&vec![1991, 2332]));
398    /// ```
399    pub fn get_vec_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut Vec<V>>
400    where
401        K: Borrow<Q>,
402        Q: Eq + Hash,
403    {
404        self.inner.get_mut(k)
405    }
406
407    /// Returns true if the key is multi-valued.
408    ///
409    /// The key may be any borrowed form of the map's key type, but Hash and Eq
410    /// on the borrowed form must match those for the key type.
411    ///
412    /// # Examples
413    ///
414    /// ```
415    /// use multimap::MultiMap;
416    ///
417    /// let mut map = MultiMap::new();
418    /// map.insert(1, 42);
419    /// map.insert(1, 1337);
420    /// map.insert(2, 2332);
421    ///
422    /// assert_eq!(map.is_vec(&1), true);   // key is multi-valued
423    /// assert_eq!(map.is_vec(&2), false);  // key is single-valued
424    /// assert_eq!(map.is_vec(&3), false);  // key not in map
425    /// ```
426    pub fn is_vec<Q: ?Sized>(&self, k: &Q) -> bool
427    where
428        K: Borrow<Q>,
429        Q: Eq + Hash,
430    {
431        match self.get_vec(k) {
432            Some(val) => val.len() > 1,
433            None => false,
434        }
435    }
436
437    /// Returns the number of elements the map can hold without reallocating.
438    ///
439    /// # Examples
440    ///
441    /// ```
442    /// use multimap::MultiMap;
443    ///
444    /// let map: MultiMap<usize, usize> = MultiMap::new();
445    /// assert!(map.capacity() >= 0);
446    /// ```
447    pub fn capacity(&self) -> usize {
448        self.inner.capacity()
449    }
450
451    /// Returns true if the map contains no elements.
452    ///
453    /// # Examples
454    ///
455    /// ```
456    /// use multimap::MultiMap;
457    ///
458    /// let mut map = MultiMap::new();
459    /// assert!(map.is_empty());
460    /// map.insert(1,42);
461    /// assert!(!map.is_empty());
462    /// ```
463    pub fn is_empty(&self) -> bool {
464        self.inner.is_empty()
465    }
466
467    /// Clears the map, removing all key-value pairs.
468    /// Keeps the allocated memory for reuse.
469    ///
470    /// # Examples
471    ///
472    /// ```
473    /// use multimap::MultiMap;
474    ///
475    /// let mut map = MultiMap::new();
476    /// map.insert(1,42);
477    /// map.clear();
478    /// assert!(map.is_empty());
479    /// ```
480    pub fn clear(&mut self) {
481        self.inner.clear();
482    }
483
484    /// An iterator visiting all keys in arbitrary order.
485    /// Iterator element type is &'a K.
486    ///
487    /// # Examples
488    ///
489    /// ```
490    /// use multimap::MultiMap;
491    ///
492    /// let mut map = MultiMap::new();
493    /// map.insert(1,42);
494    /// map.insert(1,1337);
495    /// map.insert(2,1337);
496    /// map.insert(4,1991);
497    ///
498    /// let mut keys: Vec<_> = map.keys().collect();
499    /// keys.sort();
500    /// assert_eq!(keys, [&1, &2, &4]);
501    /// ```
502    pub fn keys(&'_ self) -> Keys<'_, K, Vec<V>> {
503        self.inner.keys()
504    }
505
506    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
507    /// a reference to the key and the first element in the corresponding key's vector.
508    /// Iterator element type is (&'a K, &'a V).
509    ///
510    /// # Examples
511    ///
512    /// ```
513    /// use multimap::MultiMap;
514    ///
515    /// let mut map = MultiMap::new();
516    /// map.insert(1,42);
517    /// map.insert(1,1337);
518    /// map.insert(3,2332);
519    /// map.insert(4,1991);
520    ///
521    /// let mut pairs: Vec<_> = map.iter().collect();
522    /// pairs.sort_by_key(|p| p.0);
523    /// assert_eq!(pairs, [(&1, &42), (&3, &2332), (&4, &1991)]);
524    /// ```
525    pub fn iter(&self) -> Iter<K, V> {
526        Iter {
527            inner: self.inner.iter(),
528        }
529    }
530
531    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
532    /// a reference to the key and a mutable reference to the first element in the
533    /// corresponding key's vector. Iterator element type is (&'a K, &'a mut V).
534    ///
535    /// # Examples
536    ///
537    /// ```
538    /// use multimap::MultiMap;
539    ///
540    /// let mut map = MultiMap::new();
541    /// map.insert(1,42);
542    /// map.insert(1,1337);
543    /// map.insert(3,2332);
544    /// map.insert(4,1991);
545    ///
546    /// for (_, value) in map.iter_mut() {
547    ///     *value *= *value;
548    /// }
549    ///
550    /// let mut pairs: Vec<_> = map.iter_mut().collect();
551    /// pairs.sort_by_key(|p| p.0);
552    /// assert_eq!(pairs, [(&1, &mut 1764), (&3, &mut 5438224), (&4, &mut 3964081)]);
553    /// ```
554    pub fn iter_mut(&mut self) -> IterMut<K, V> {
555        IterMut {
556            inner: self.inner.iter_mut(),
557        }
558    }
559
560    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
561    /// a reference to the key and the corresponding key's vector.
562    /// Iterator element type is (&'a K, &'a V).
563    ///
564    /// # Examples
565    ///
566    /// ```
567    /// use multimap::MultiMap;
568    ///
569    /// let mut map = MultiMap::new();
570    /// map.insert(1,42);
571    /// map.insert(1,1337);
572    /// map.insert(3,2332);
573    /// map.insert(4,1991);
574    ///
575    /// let mut pairs: Vec<_> = map.iter_all().collect();
576    /// pairs.sort_by_key(|p| p.0);
577    /// assert_eq!(pairs, [(&1, &vec![42, 1337]), (&3, &vec![2332]), (&4, &vec![1991])]);
578    /// ```
579    pub fn iter_all(&self) -> IterAll<K, Vec<V>> {
580        self.inner.iter()
581    }
582
583    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
584    /// a reference to the key and the corresponding key's vector.
585    /// Iterator element type is (&'a K, &'a V).
586    ///
587    /// # Examples
588    ///
589    /// ```
590    /// use multimap::MultiMap;
591    ///
592    /// let mut map = MultiMap::new();
593    /// map.insert(1,42);
594    /// map.insert(1,1337);
595    /// map.insert(3,2332);
596    /// map.insert(4,1991);
597    ///
598    /// for (key, values) in map.iter_all_mut() {
599    ///     for value in values.iter_mut() {
600    ///         *value = 99;
601    ///     }
602    /// }
603    ///
604    /// let mut pairs: Vec<_> = map.iter_all_mut().collect();
605    /// pairs.sort_by_key(|p| p.0);
606    /// assert_eq!(pairs, [(&1, &mut vec![99, 99]), (&3, &mut vec![99]), (&4, &mut vec![99])]);
607    /// ```
608    pub fn iter_all_mut(&mut self) -> IterAllMut<K, Vec<V>> {
609        self.inner.iter_mut()
610    }
611
612    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
613    /// a reference to the key and the first element in the corresponding key's vector.
614    /// Iterator element type is (&'a K, &'a V).
615    ///
616    /// # Examples
617    ///
618    /// ```
619    /// use multimap::MultiMap;
620    ///
621    /// let mut map = MultiMap::new();
622    /// map.insert(1,42);
623    /// map.insert(1,1337);
624    /// map.insert(3,2332);
625    /// map.insert(4,1991);
626    ///
627    /// for (key, value) in map.flat_iter() {
628    ///     println!("key: {:?}, val: {:?}", key, value);
629    /// }
630    /// ```
631    pub fn flat_iter(&self) -> impl Iterator<Item = (&K, &V)> {
632        self.iter_all()
633            .flat_map(|(k, v)| v.iter().map(move |i| (k, i)))
634    }
635
636    /// An iterator visiting all key-value pairs in arbitrary order. The iterator returns
637    /// a reference to the key and the first element in the corresponding key's vector.
638    /// Iterator element type is (&'a K, &'a V).
639    ///
640    /// # Examples
641    ///
642    /// ```
643    /// use multimap::MultiMap;
644    ///
645    /// let mut map = MultiMap::new();
646    /// map.insert(1,42);
647    /// map.insert(1,1337);
648    /// map.insert(3,2332);
649    /// map.insert(4,1991);
650    ///
651    /// for (key, value) in map.flat_iter_mut() {
652    ///     println!("key: {:?}, val: {:?}", key, value);
653    /// }
654    /// ```
655    pub fn flat_iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)> {
656        self.iter_all_mut()
657            .flat_map(|(k, v)| v.iter_mut().map(move |i| (k, i)))
658    }
659
660    /// Gets the specified key's corresponding entry in the map for in-place manipulation.
661    /// It's possible to both manipulate the vector and the 'value' (the first value in the
662    /// vector).
663    ///
664    /// # Examples
665    ///
666    /// ```
667    /// use multimap::MultiMap;
668    ///
669    /// let mut m = MultiMap::new();
670    /// m.insert(1, 42);
671    ///
672    /// {
673    ///     let mut v = m.entry(1).or_insert(43);
674    ///     assert_eq!(v, &42);
675    ///     *v = 44;
676    /// }
677    /// assert_eq!(m.entry(2).or_insert(666), &666);
678    ///
679    /// {
680    ///     let mut v = m.entry(1).or_insert_vec(vec![43]);
681    ///     assert_eq!(v, &vec![44]);
682    ///     v.push(50);
683    /// }
684    /// assert_eq!(m.entry(2).or_insert_vec(vec![667]), &vec![666]);
685    ///
686    /// assert_eq!(m.get_vec(&1), Some(&vec![44, 50]));
687    /// ```
688    pub fn entry(&mut self, k: K) -> Entry<K, V> {
689        use std::collections::hash_map::Entry as HashMapEntry;
690        match self.inner.entry(k) {
691            HashMapEntry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
692            HashMapEntry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
693        }
694    }
695
696    /// Retains only the elements specified by the predicate.
697    ///
698    /// In other words, remove all pairs `(k, v)` such that `f(&k,&mut v)` returns `false`.
699    ///
700    /// # Examples
701    ///
702    /// ```
703    /// use multimap::MultiMap;
704    ///
705    /// let mut m = MultiMap::new();
706    /// m.insert(1, 42);
707    /// m.insert(1, 99);
708    /// m.insert(2, 42);
709    /// m.retain(|&k, &v| { k == 1 && v == 42 });
710    /// assert_eq!(1, m.len());
711    /// assert_eq!(Some(&42), m.get(&1));
712    /// ```
713    pub fn retain<F>(&mut self, mut f: F)
714    where
715        F: FnMut(&K, &V) -> bool,
716    {
717        for (key, vector) in &mut self.inner {
718            vector.retain(|value| f(key, value));
719        }
720        self.inner.retain(|_, v| !v.is_empty());
721    }
722}
723
724impl<'a, K, V, S, Q: ?Sized> Index<&'a Q> for MultiMap<K, V, S>
725where
726    K: Eq + Hash + Borrow<Q>,
727    Q: Eq + Hash,
728    S: BuildHasher,
729{
730    type Output = V;
731
732    fn index(&self, index: &Q) -> &V {
733        self.inner
734            .get(index)
735            .expect("no entry found for key")
736            .first()
737            .expect("no value found for key")
738    }
739}
740
741impl<K, V, S> Debug for MultiMap<K, V, S>
742where
743    K: Eq + Hash + Debug,
744    V: Debug,
745    S: BuildHasher,
746{
747    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
748        f.debug_map().entries(self.iter_all()).finish()
749    }
750}
751
752impl<K, V, S> PartialEq for MultiMap<K, V, S>
753where
754    K: Eq + Hash,
755    V: PartialEq,
756    S: BuildHasher,
757{
758    fn eq(&self, other: &MultiMap<K, V, S>) -> bool {
759        if self.len() != other.len() {
760            return false;
761        }
762
763        self.iter_all()
764            .all(|(key, value)| other.get_vec(key).map_or(false, |v| *value == *v))
765    }
766}
767
768impl<K, V, S> Eq for MultiMap<K, V, S>
769where
770    K: Eq + Hash,
771    V: Eq,
772    S: BuildHasher,
773{
774}
775
776impl<K, V, S> Default for MultiMap<K, V, S>
777where
778    K: Eq + Hash,
779    S: BuildHasher + Default,
780{
781    fn default() -> MultiMap<K, V, S> {
782        MultiMap {
783            inner: Default::default(),
784        }
785    }
786}
787
788impl<K, V, S> FromIterator<(K, V)> for MultiMap<K, V, S>
789where
790    K: Eq + Hash,
791    S: BuildHasher + Default,
792{
793    fn from_iter<T: IntoIterator<Item = (K, V)>>(iterable: T) -> MultiMap<K, V, S> {
794        let iter = iterable.into_iter();
795        let hint = iter.size_hint().0;
796
797        let mut multimap = MultiMap::with_capacity_and_hasher(hint, S::default());
798        for (k, v) in iter {
799            multimap.insert(k, v);
800        }
801
802        multimap
803    }
804}
805
806impl<K, V, S> FromIterator<(K, Vec<V>)> for MultiMap<K, V, S>
807where
808    K: Eq + Hash,
809    V: Clone,
810    S: BuildHasher + Default,
811{
812    fn from_iter<T: IntoIterator<Item = (K, Vec<V>)>>(iterable: T) -> MultiMap<K, V, S> {
813        let iter = iterable.into_iter();
814        let hint = iter.size_hint().0;
815
816        let mut multimap = MultiMap::with_capacity_and_hasher(hint, S::default());
817        for (k, v) in iter {
818            multimap.insert_many_from_slice(k, &v[..])
819        }
820
821        multimap
822    }
823}
824
825impl<'a, K, V, S> IntoIterator for &'a MultiMap<K, V, S>
826where
827    K: Eq + Hash,
828    S: BuildHasher,
829{
830    type Item = (&'a K, &'a Vec<V>);
831    type IntoIter = IterAll<'a, K, Vec<V>>;
832
833    fn into_iter(self) -> IterAll<'a, K, Vec<V>> {
834        self.iter_all()
835    }
836}
837
838impl<'a, K, V, S> IntoIterator for &'a mut MultiMap<K, V, S>
839where
840    K: Eq + Hash,
841    S: BuildHasher,
842{
843    type Item = (&'a K, &'a mut Vec<V>);
844    type IntoIter = IterAllMut<'a, K, Vec<V>>;
845
846    fn into_iter(self) -> IterAllMut<'a, K, Vec<V>> {
847        self.inner.iter_mut()
848    }
849}
850
851impl<K, V, S> IntoIterator for MultiMap<K, V, S>
852where
853    K: Eq + Hash,
854    S: BuildHasher,
855{
856    type Item = (K, Vec<V>);
857    type IntoIter = IntoIter<K, Vec<V>>;
858
859    fn into_iter(self) -> IntoIter<K, Vec<V>> {
860        self.inner.into_iter()
861    }
862}
863
864impl<K, V, S> Extend<(K, V)> for MultiMap<K, V, S>
865where
866    K: Eq + Hash,
867    S: BuildHasher,
868{
869    fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) {
870        for (k, v) in iter {
871            self.insert(k, v);
872        }
873    }
874}
875
876impl<'a, K, V, S> Extend<(&'a K, &'a V)> for MultiMap<K, V, S>
877where
878    K: Eq + Hash + Copy,
879    V: Copy,
880    S: BuildHasher,
881{
882    fn extend<T: IntoIterator<Item = (&'a K, &'a V)>>(&mut self, iter: T) {
883        self.extend(iter.into_iter().map(|(&key, &value)| (key, value)));
884    }
885}
886
887impl<K, V, S> Extend<(K, Vec<V>)> for MultiMap<K, V, S>
888where
889    K: Eq + Hash,
890    S: BuildHasher,
891{
892    fn extend<T: IntoIterator<Item = (K, Vec<V>)>>(&mut self, iter: T) {
893        for (k, values) in iter {
894            match self.entry(k) {
895                Entry::Occupied(mut entry) => {
896                    entry.get_vec_mut().extend(values);
897                }
898                Entry::Vacant(entry) => {
899                    entry.insert_vec(values);
900                }
901            }
902        }
903    }
904}
905
906impl<'a, K, V, S> Extend<(&'a K, &'a Vec<V>)> for MultiMap<K, V, S>
907where
908    K: Eq + Hash + Copy,
909    V: Copy,
910    S: BuildHasher,
911{
912    fn extend<T: IntoIterator<Item = (&'a K, &'a Vec<V>)>>(&mut self, iter: T) {
913        self.extend(
914            iter.into_iter()
915                .map(|(&key, values)| (key, values.to_owned())),
916        );
917    }
918}
919
920#[derive(Clone)]
921pub struct Iter<'a, K: 'a, V: 'a> {
922    inner: IterAll<'a, K, Vec<V>>,
923}
924
925impl<'a, K, V> Iterator for Iter<'a, K, V> {
926    type Item = (&'a K, &'a V);
927
928    fn next(&mut self) -> Option<(&'a K, &'a V)> {
929        let (k, v) = self.inner.next()?;
930        let v = v.first()?;
931        Some((k, v))
932    }
933
934    fn size_hint(&self) -> (usize, Option<usize>) {
935        self.inner.size_hint()
936    }
937}
938
939impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
940    fn len(&self) -> usize {
941        self.inner.len()
942    }
943}
944
945pub struct IterMut<'a, K: 'a, V: 'a> {
946    inner: IterAllMut<'a, K, Vec<V>>,
947}
948
949impl<'a, K, V> Iterator for IterMut<'a, K, V> {
950    type Item = (&'a K, &'a mut V);
951
952    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
953        let (k, v) = self.inner.next()?;
954        let v = v.first_mut()?;
955        Some((k, v))
956    }
957
958    fn size_hint(&self) -> (usize, Option<usize>) {
959        self.inner.size_hint()
960    }
961}
962
963impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
964    fn len(&self) -> usize {
965        self.inner.len()
966    }
967}
968
969#[macro_export]
970/// Create a `MultiMap` from a list of key value pairs
971///
972/// ## Example
973///
974/// ```
975/// # use multimap::MultiMap;
976/// #[macro_use] extern crate multimap;
977/// # fn main(){
978///
979/// let map = multimap!(
980///     "dog" => "husky",
981///     "dog" => "retreaver",
982///     "dog" => "shiba inu",
983///     "cat" => "cat"
984///     );
985/// # }
986///
987/// ```
988macro_rules! multimap{
989    (@replace_with_unit $_t:tt) => { () };
990    (@count $($key:expr),*) => { <[()]>::len(&[$($crate::multimap! { @replace_with_unit $key }),*]) };
991
992    ($($key:expr => $value:expr),* $(,)?)=>{
993        {
994            let mut map = $crate::MultiMap::with_capacity($crate::multimap! { @count $($key),* });
995            $(
996                map.insert($key,$value);
997             )*
998            map
999        }
1000    }
1001}
1002
1003#[cfg(test)]
1004mod tests {
1005    use std::collections::HashMap;
1006    use std::iter::FromIterator;
1007
1008    use super::*;
1009
1010    #[test]
1011    fn create() {
1012        let _: MultiMap<usize, usize> = MultiMap {
1013            inner: HashMap::new(),
1014        };
1015    }
1016
1017    #[test]
1018    fn new() {
1019        let _: MultiMap<usize, usize> = MultiMap::new();
1020    }
1021
1022    #[test]
1023    fn with_capacity() {
1024        let _: MultiMap<usize, usize> = MultiMap::with_capacity(20);
1025    }
1026
1027    #[test]
1028    fn insert() {
1029        let mut m: MultiMap<usize, usize> = MultiMap::new();
1030        m.insert(1, 3);
1031    }
1032
1033    #[test]
1034    fn insert_identical() {
1035        let mut m = MultiMap::new();
1036        m.insert(1, 42);
1037        m.insert(1, 42);
1038        assert_eq!(m.get_vec(&1), Some(&vec![42, 42]));
1039    }
1040
1041    #[test]
1042    fn insert_many() {
1043        let mut m: MultiMap<usize, usize> = MultiMap::new();
1044        m.insert_many(1, vec![3, 4]);
1045        assert_eq!(Some(&vec![3, 4]), m.get_vec(&1));
1046    }
1047
1048    #[test]
1049    fn insert_many_again() {
1050        let mut m: MultiMap<usize, usize> = MultiMap::new();
1051        m.insert(1, 2);
1052        m.insert_many(1, vec![3, 4]);
1053        assert_eq!(Some(&vec![2, 3, 4]), m.get_vec(&1));
1054    }
1055
1056    #[test]
1057    fn insert_many_overlap() {
1058        let mut m: MultiMap<usize, usize> = MultiMap::new();
1059        m.insert_many(1, vec![2, 3]);
1060        m.insert_many(1, vec![3, 4]);
1061        assert_eq!(Some(&vec![2, 3, 3, 4]), m.get_vec(&1));
1062    }
1063
1064    #[test]
1065    fn insert_many_from_slice() {
1066        let mut m: MultiMap<usize, usize> = MultiMap::new();
1067        m.insert_many_from_slice(1, &[3, 4]);
1068        assert_eq!(Some(&vec![3, 4]), m.get_vec(&1));
1069    }
1070
1071    #[test]
1072    fn insert_many_from_slice_again() {
1073        let mut m: MultiMap<usize, usize> = MultiMap::new();
1074        m.insert(1, 2);
1075        m.insert_many_from_slice(1, &[3, 4]);
1076        assert_eq!(Some(&vec![2, 3, 4]), m.get_vec(&1));
1077    }
1078
1079    #[test]
1080    fn insert_existing() {
1081        let mut m: MultiMap<usize, usize> = MultiMap::new();
1082        m.insert(1, 3);
1083        m.insert(1, 4);
1084        assert_eq!(Some(&vec![3, 4]), m.get_vec(&1));
1085    }
1086
1087    #[test]
1088    #[should_panic(expected = "no entry found for key")]
1089    fn index_no_entry() {
1090        let m: MultiMap<usize, usize> = MultiMap::new();
1091        let _ = &m[&1];
1092    }
1093
1094    #[test]
1095    fn index() {
1096        let mut m: MultiMap<usize, usize> = MultiMap::new();
1097        m.insert(1, 41);
1098        m.insert(2, 42);
1099        m.insert(3, 43);
1100        let values = m[&2];
1101        assert_eq!(values, 42);
1102    }
1103
1104    #[test]
1105    #[should_panic(expected = "no value found for key")]
1106    fn index_empty_vec() {
1107        let mut m: MultiMap<usize, usize> = MultiMap::new();
1108        m.insert(1, 42);
1109        m.get_vec_mut(&1).unwrap().clear();
1110        let values = m[&1];
1111        assert_eq!(values, 42);
1112    }
1113
1114    #[test]
1115    fn contains_key_true() {
1116        let mut m: MultiMap<usize, usize> = MultiMap::new();
1117        m.insert(1, 42);
1118        assert!(m.contains_key(&1));
1119    }
1120
1121    #[test]
1122    fn contains_key_false() {
1123        let m: MultiMap<usize, usize> = MultiMap::new();
1124        assert!(!m.contains_key(&1));
1125    }
1126
1127    #[test]
1128    fn len() {
1129        let mut m: MultiMap<usize, usize> = MultiMap::new();
1130        m.insert(1, 42);
1131        m.insert(2, 1337);
1132        m.insert(3, 99);
1133        assert_eq!(m.len(), 3);
1134    }
1135
1136    #[test]
1137    fn remove_not_present() {
1138        let mut m: MultiMap<usize, usize> = MultiMap::new();
1139        let v = m.remove(&1);
1140        assert_eq!(v, None);
1141    }
1142
1143    #[test]
1144    fn remove_present() {
1145        let mut m: MultiMap<usize, usize> = MultiMap::new();
1146        m.insert(1, 42);
1147        let v = m.remove(&1);
1148        assert_eq!(v, Some(vec![42]));
1149    }
1150
1151    #[test]
1152    fn get_not_present() {
1153        let m: MultiMap<usize, usize> = MultiMap::new();
1154        assert_eq!(m.get(&1), None);
1155    }
1156
1157    #[test]
1158    fn get_present() {
1159        let mut m: MultiMap<usize, usize> = MultiMap::new();
1160        m.insert(1, 42);
1161        assert_eq!(m.get(&1), Some(&42));
1162    }
1163
1164    #[test]
1165    fn get_empty() {
1166        let mut m: MultiMap<usize, usize> = MultiMap::new();
1167        m.insert(1, 42);
1168        m.get_vec_mut(&1).and_then(Vec::pop);
1169        assert_eq!(m.get(&1), None);
1170    }
1171
1172    #[test]
1173    fn get_vec_not_present() {
1174        let m: MultiMap<usize, usize> = MultiMap::new();
1175        assert_eq!(m.get_vec(&1), None);
1176    }
1177
1178    #[test]
1179    fn get_vec_present() {
1180        let mut m: MultiMap<usize, usize> = MultiMap::new();
1181        m.insert(1, 42);
1182        m.insert(1, 1337);
1183        assert_eq!(m.get_vec(&1), Some(&vec![42, 1337]));
1184    }
1185
1186    #[test]
1187    fn capacity() {
1188        let m: MultiMap<usize, usize> = MultiMap::with_capacity(20);
1189        assert!(m.capacity() >= 20);
1190    }
1191
1192    #[test]
1193    fn is_empty_true() {
1194        let m: MultiMap<usize, usize> = MultiMap::new();
1195        assert!(m.is_empty());
1196    }
1197
1198    #[test]
1199    fn is_empty_false() {
1200        let mut m: MultiMap<usize, usize> = MultiMap::new();
1201        m.insert(1, 42);
1202        assert!(!m.is_empty());
1203    }
1204
1205    #[test]
1206    fn clear() {
1207        let mut m: MultiMap<usize, usize> = MultiMap::new();
1208        m.insert(1, 42);
1209        m.clear();
1210        assert!(m.is_empty());
1211    }
1212
1213    #[test]
1214    fn get_mut() {
1215        let mut m: MultiMap<usize, usize> = MultiMap::new();
1216        m.insert(1, 42);
1217        if let Some(v) = m.get_mut(&1) {
1218            *v = 1337;
1219        }
1220        assert_eq!(m[&1], 1337)
1221    }
1222
1223    #[test]
1224    fn get_vec_mut() {
1225        let mut m: MultiMap<usize, usize> = MultiMap::new();
1226        m.insert(1, 42);
1227        m.insert(1, 1337);
1228        if let Some(v) = m.get_vec_mut(&1) {
1229            (*v)[0] = 5;
1230            (*v)[1] = 10;
1231        }
1232        assert_eq!(m.get_vec(&1), Some(&vec![5, 10]))
1233    }
1234
1235    #[test]
1236    fn get_mut_empty() {
1237        let mut m: MultiMap<usize, usize> = MultiMap::new();
1238        m.insert(1, 42);
1239        m.get_vec_mut(&1).and_then(Vec::pop);
1240        assert_eq!(m.get_mut(&1), None);
1241    }
1242
1243    #[test]
1244    fn keys() {
1245        let mut m: MultiMap<usize, usize> = MultiMap::new();
1246        m.insert(1, 42);
1247        m.insert(2, 42);
1248        m.insert(4, 42);
1249        m.insert(8, 42);
1250
1251        let keys: Vec<_> = m.keys().cloned().collect();
1252        assert_eq!(keys.len(), 4);
1253        assert!(keys.contains(&1));
1254        assert!(keys.contains(&2));
1255        assert!(keys.contains(&4));
1256        assert!(keys.contains(&8));
1257    }
1258
1259    #[test]
1260    fn iter() {
1261        let mut m: MultiMap<usize, usize> = MultiMap::new();
1262        m.insert(1, 42);
1263        m.insert(1, 42);
1264        m.insert(4, 42);
1265        m.insert(8, 42);
1266
1267        assert!(m.iter().all(|(_, &v)| v == 42));
1268
1269        let mut iter = m.iter();
1270
1271        for _ in iter.by_ref().take(2) {}
1272
1273        assert_eq!(iter.len(), 1);
1274    }
1275
1276    #[test]
1277    fn iter_empty_vec() {
1278        let mut m: MultiMap<usize, usize> = MultiMap::new();
1279        m.insert(42, 42);
1280        m.get_vec_mut(&42).unwrap().clear();
1281
1282        assert!(m.iter().next().is_none());
1283    }
1284
1285    #[test]
1286    fn flat_iter() {
1287        let mut m: MultiMap<usize, usize> = MultiMap::new();
1288        m.insert(1, 42);
1289        m.insert(1, 43);
1290        m.insert(4, 42);
1291        m.insert(8, 42);
1292
1293        let keys = vec![1, 4, 8];
1294
1295        for (key, value) in m.flat_iter() {
1296            assert!(keys.contains(key));
1297
1298            if key == &1 {
1299                assert!(value == &42 || value == &43);
1300            } else {
1301                assert_eq!(value, &42);
1302            }
1303        }
1304    }
1305
1306    #[test]
1307    fn flat_iter_mut() {
1308        let mut m: MultiMap<usize, usize> = MultiMap::new();
1309        m.insert(1, 42);
1310        m.insert(1, 43);
1311        m.insert(4, 42);
1312        m.insert(8, 42);
1313
1314        let keys = vec![1, 4, 8];
1315
1316        for (key, value) in m.flat_iter_mut() {
1317            assert!(keys.contains(key));
1318
1319            if key == &1 {
1320                assert!(value == &42 || value == &43);
1321
1322                *value = 55;
1323                assert_eq!(value, &55);
1324            } else {
1325                assert_eq!(value, &42);
1326
1327                *value = 76;
1328                assert_eq!(value, &76);
1329            }
1330        }
1331    }
1332
1333    #[test]
1334    fn intoiterator_for_reference_type() {
1335        let mut m: MultiMap<usize, usize> = MultiMap::new();
1336        m.insert(1, 42);
1337        m.insert(1, 43);
1338        m.insert(4, 42);
1339        m.insert(8, 42);
1340
1341        let keys = vec![1, 4, 8];
1342
1343        for (key, value) in &m {
1344            assert!(keys.contains(key));
1345
1346            if key == &1 {
1347                assert_eq!(value, &vec![42, 43]);
1348            } else {
1349                assert_eq!(value, &vec![42]);
1350            }
1351        }
1352    }
1353
1354    #[test]
1355    fn intoiterator_for_mutable_reference_type() {
1356        let mut m: MultiMap<usize, usize> = MultiMap::new();
1357        m.insert(1, 42);
1358        m.insert(1, 43);
1359        m.insert(4, 42);
1360        m.insert(8, 42);
1361
1362        let keys = vec![1, 4, 8];
1363
1364        for (key, value) in &mut m {
1365            assert!(keys.contains(key));
1366
1367            if key == &1 {
1368                assert_eq!(value, &vec![42, 43]);
1369                value.push(666);
1370            } else {
1371                assert_eq!(value, &vec![42]);
1372            }
1373        }
1374
1375        assert_eq!(m.get_vec(&1), Some(&vec![42, 43, 666]));
1376    }
1377
1378    #[test]
1379    fn intoiterator_consuming() {
1380        let mut m: MultiMap<usize, usize> = MultiMap::new();
1381        m.insert(1, 42);
1382        m.insert(1, 43);
1383        m.insert(4, 42);
1384        m.insert(8, 42);
1385
1386        let keys = vec![1, 4, 8];
1387
1388        for (key, value) in m {
1389            assert!(keys.contains(&key));
1390
1391            if key == 1 {
1392                assert_eq!(value, vec![42, 43]);
1393            } else {
1394                assert_eq!(value, vec![42]);
1395            }
1396        }
1397    }
1398
1399    #[test]
1400    fn test_fmt_debug() {
1401        let mut map = MultiMap::new();
1402        let empty: MultiMap<i32, i32> = MultiMap::new();
1403
1404        map.insert(1, 2);
1405        map.insert(1, 5);
1406        map.insert(1, -1);
1407        map.insert(3, 4);
1408
1409        let map_str = format!("{:?}", map);
1410
1411        assert!(map_str == "{1: [2, 5, -1], 3: [4]}" || map_str == "{3: [4], 1: [2, 5, -1]}");
1412        assert_eq!(format!("{:?}", empty), "{}");
1413    }
1414
1415    #[test]
1416    fn test_eq() {
1417        let mut m1 = MultiMap::new();
1418        m1.insert(1, 2);
1419        m1.insert(2, 3);
1420        m1.insert(3, 4);
1421        let mut m2 = MultiMap::new();
1422        m2.insert(1, 2);
1423        m2.insert(2, 3);
1424        assert_ne!(m1, m2);
1425        m2.insert(3, 4);
1426        assert_eq!(m1, m2);
1427        m2.insert(3, 4);
1428        assert_ne!(m1, m2);
1429        m1.insert(3, 4);
1430        assert_eq!(m1, m2);
1431    }
1432
1433    #[test]
1434    fn test_eq_empty_key() {
1435        let mut m1 = MultiMap::new();
1436        m1.insert(1, 2);
1437        m1.insert(2, 3);
1438        let mut m2 = MultiMap::new();
1439        m2.insert(1, 2);
1440        m2.insert_many(2, []);
1441        assert_ne!(m1, m2);
1442        m2.insert_many(2, [3]);
1443        assert_eq!(m1, m2);
1444    }
1445
1446    #[test]
1447    fn test_default() {
1448        let _: MultiMap<u8, u8> = Default::default();
1449    }
1450
1451    #[test]
1452    fn test_from_iterator() {
1453        let vals: Vec<(&str, i64)> = vec![("foo", 123), ("bar", 456), ("foo", 789)];
1454        let multimap: MultiMap<&str, i64> = MultiMap::from_iter(vals);
1455
1456        let foo_vals: &Vec<i64> = multimap.get_vec("foo").unwrap();
1457        assert!(foo_vals.contains(&123));
1458        assert!(foo_vals.contains(&789));
1459
1460        let bar_vals: &Vec<i64> = multimap.get_vec("bar").unwrap();
1461        assert!(bar_vals.contains(&456));
1462    }
1463
1464    #[test]
1465    fn test_from_vec_iterator() {
1466        let vals: Vec<(&str, Vec<i64>)> = vec![
1467            ("foo", vec![123, 456]),
1468            ("bar", vec![234]),
1469            ("foobar", vec![567, 678, 789]),
1470            ("bar", vec![12, 23, 34]),
1471        ];
1472
1473        let multimap: MultiMap<&str, i64> = MultiMap::from_iter(vals);
1474
1475        let foo_vals: &Vec<i64> = multimap.get_vec("foo").unwrap();
1476        assert!(foo_vals.contains(&123));
1477        assert!(foo_vals.contains(&456));
1478
1479        let bar_vals: &Vec<i64> = multimap.get_vec("bar").unwrap();
1480        assert!(bar_vals.contains(&234));
1481        assert!(bar_vals.contains(&12));
1482        assert!(bar_vals.contains(&23));
1483        assert!(bar_vals.contains(&34));
1484
1485        let foobar_vals: &Vec<i64> = multimap.get_vec("foobar").unwrap();
1486        assert!(foobar_vals.contains(&567));
1487        assert!(foobar_vals.contains(&678));
1488        assert!(foobar_vals.contains(&789));
1489    }
1490
1491    #[test]
1492    fn test_extend_consuming_hashmap() {
1493        let mut a = MultiMap::new();
1494        a.insert(1, 42);
1495
1496        let mut b = HashMap::new();
1497        b.insert(1, 43);
1498        b.insert(2, 666);
1499
1500        a.extend(b);
1501
1502        assert_eq!(a.len(), 2);
1503        assert_eq!(a.get_vec(&1), Some(&vec![42, 43]));
1504    }
1505
1506    #[test]
1507    fn test_extend_ref_hashmap() {
1508        let mut a = MultiMap::new();
1509        a.insert(1, 42);
1510
1511        let mut b = HashMap::new();
1512        b.insert(1, 43);
1513        b.insert(2, 666);
1514
1515        a.extend(&b);
1516
1517        assert_eq!(a.len(), 2);
1518        assert_eq!(a.get_vec(&1), Some(&vec![42, 43]));
1519        assert_eq!(b.len(), 2);
1520        assert_eq!(b[&1], 43);
1521    }
1522
1523    #[test]
1524    fn test_extend_consuming_multimap() {
1525        let mut a = MultiMap::new();
1526        a.insert(1, 42);
1527
1528        let mut b = MultiMap::new();
1529        b.insert(1, 43);
1530        b.insert(1, 44);
1531        b.insert(2, 666);
1532
1533        a.extend(b);
1534
1535        assert_eq!(a.len(), 2);
1536        assert_eq!(a.get_vec(&1), Some(&vec![42, 43, 44]));
1537    }
1538
1539    #[test]
1540    fn test_extend_ref_multimap() {
1541        let mut a = MultiMap::new();
1542        a.insert(1, 42);
1543
1544        let mut b = MultiMap::new();
1545        b.insert(1, 43);
1546        b.insert(1, 44);
1547        b.insert(2, 666);
1548
1549        a.extend(&b);
1550
1551        assert_eq!(a.len(), 2);
1552        assert_eq!(a.get_vec(&1), Some(&vec![42, 43, 44]));
1553        assert_eq!(b.len(), 2);
1554        assert_eq!(b.get_vec(&1), Some(&vec![43, 44]));
1555    }
1556
1557    #[test]
1558    fn test_entry() {
1559        let mut m = MultiMap::new();
1560        m.insert(1, 42);
1561
1562        {
1563            let v = m.entry(1).or_insert(43);
1564            assert_eq!(v, &42);
1565            *v = 44;
1566        }
1567        assert_eq!(m.entry(2).or_insert(666), &666);
1568
1569        assert_eq!(m[&1], 44);
1570        assert_eq!(m[&2], 666);
1571    }
1572
1573    #[test]
1574    fn test_entry_vec() {
1575        let mut m = MultiMap::new();
1576        m.insert(1, 42);
1577
1578        {
1579            let v = m.entry(1).or_insert_vec(vec![43]);
1580            assert_eq!(v, &vec![42]);
1581            *v.first_mut().unwrap() = 44;
1582        }
1583        assert_eq!(m.entry(2).or_insert_vec(vec![666]), &vec![666]);
1584
1585        assert_eq!(m[&1], 44);
1586        assert_eq!(m[&2], 666);
1587    }
1588
1589    #[test]
1590    fn test_is_vec() {
1591        let mut m = MultiMap::new();
1592        m.insert(1, 42);
1593        m.insert(1, 1337);
1594        m.insert(2, 2332);
1595
1596        assert!(m.is_vec(&1));
1597        assert!(!m.is_vec(&2));
1598        assert!(!m.is_vec(&3));
1599    }
1600
1601    #[test]
1602    fn test_macro() {
1603        let mut manual_map = MultiMap::new();
1604        manual_map.insert("key1", 42);
1605        assert_eq!(manual_map, multimap!("key1" => 42));
1606
1607        manual_map.insert("key1", 1337);
1608        manual_map.insert("key2", 2332);
1609        let macro_map = multimap! {
1610            "key1" =>    42,
1611            "key1" =>  1337,
1612            "key2" =>  2332
1613        };
1614        assert_eq!(manual_map, macro_map);
1615    }
1616
1617    #[test]
1618    fn retain_removes_element() {
1619        let mut m = MultiMap::new();
1620        m.insert(1, 42);
1621        m.insert(1, 99);
1622        m.retain(|&k, &v| k == 1 && v == 42);
1623        assert_eq!(1, m.len());
1624        assert_eq!(Some(&42), m.get(&1));
1625    }
1626
1627    #[test]
1628    fn retain_also_removes_empty_vector() {
1629        let mut m = MultiMap::new();
1630        m.insert(1, 42);
1631        m.insert(1, 99);
1632        m.insert(2, 42);
1633        m.retain(|&k, &v| k == 1 && v == 42);
1634        assert_eq!(1, m.len());
1635        assert_eq!(Some(&42), m.get(&1));
1636    }
1637}
multimap/lib.rs

multimap/
lib.rs
