cc_multimap/
lib.rs

1use std::collections::{BTreeMap, HashSet};
2use std::hash::Hash;
3use std::ops::Deref;
4
5#[derive(Debug, Default)]
6pub struct MultiMap<K, V>
7where
8    K: Ord + Eq + Hash,
9    V: Eq + Hash,
10{
11    backing: BTreeMap<K, HashSet<V>>,
12}
13
14impl<K, V> MultiMap<K, V>
15where
16    K: Ord + Eq + Hash,
17    V: Eq + Hash,
18{
19    /// Insert an item into the multimap.
20    pub fn insert(&mut self, key: K, value: V) -> bool {
21        self.backing
22            .entry(key)
23            .or_insert_with(Default::default)
24            .insert(value)
25    }
26
27    /// Remove an item from the multimap.
28    /// Returns true if the item was removed successfully.
29    pub fn remove(&mut self, key: &K, value: &V) -> bool {
30        if let Some(values) = self.backing.get_mut(key) {
31            let only_one_left = values.len() == 1;
32            if !only_one_left {
33                // Operation may be ok: only if value is in values Set.
34                return values.remove(value);
35            }
36            if value
37                != values
38                    .iter()
39                    .next()
40                    .expect("We know there is only one element in collection, tested above; qed")
41            {
42                // Operation failed: value is not the single item in values Set.
43                return false;
44            }
45        } else {
46            // Operation failed: value not found in Map.
47            return false;
48        }
49        // Operation maybe ok: only if value not found in values Set.
50        self.backing.remove(key).is_some()
51    }
52}
53
54impl<K, V> Deref for MultiMap<K, V>
55where
56    K: Ord + Eq + Hash,
57    V: Eq + Hash,
58{
59    type Target = BTreeMap<K, HashSet<V>>;
60
61    fn deref(&self) -> &Self::Target {
62        &self.backing
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn insert_and_get() {
72        let mut map: MultiMap<u8, u32> = MultiMap::default();
73        map.insert(1u8, 3u32);
74        map.insert(2u8, 6u32);
75        map.insert(1u8, 9u32);
76        let set: HashSet<u32> = [3u32, 9u32].iter().cloned().collect();
77        assert_eq!(map.get(&1u8).unwrap(), &set);
78    }
79}
cc_multimap/lib.rs

cc_multimap/
lib.rs
