1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

//! A multiset backed by a HashMap
use std::collections::HashMap;
use std::hash::Hash;

/// A multiset backed by a HashMap
#[derive(Clone, Eq, PartialEq, Debug)]
pub struct HashMultiSet<T: Hash + Eq> {
    items: HashMap<T, usize>,
    len: usize,
}

impl<T: Hash + Eq> HashMultiSet<T> {
    /// Insert item into the multiset. see `https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.insert`
    pub fn insert(&mut self, value: T) {
        *self.items.entry(value).or_default() += 1;
        self.len += 1;
    }
}

impl<T> Default for HashMultiSet<T>
where
    T: Hash + Eq,
{
    fn default() -> Self {
        Self {
            items: HashMap::default(),
            len: 0,
        }
    }
}

impl<T> FromIterator<T> for HashMultiSet<T>
where
    T: Hash + Eq,
{
    fn from_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut ret = HashMultiSet::default();

        for item in iter {
            ret.insert(item);
        }

        ret
    }
}

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn basic() {
        let mut x = HashMultiSet::default();

        x.insert(1);
        x.insert(2);
        x.insert(2);

        assert_eq!(x, HashMultiSet::from_iter([2, 1, 2]));
    }
}