MultiSet

A multiset is a set that allows for multiple occurrences of the same element. It is similar to a list, but it does not allow for duplicate elements. We will use multiset that has keys in sorted order

Rust Implementation

In Rust, we can implement a multiset using a BTreeMap to store the elements and their counts. The BTreeMap will maintain the sorted order of the elements, allowing us to efficiently get the smallest and largest elements. The BTreeMap isn’t prone to collisions blowup (HashMap is prone), so it is a good choice for implementing a multiset.

use std::clone::Clone;
use std::iter::FromIterator;
use std::collections::BTreeMap;


#[derive(Debug, Default)]
pub struct MultiSet<T> {
    elems: BTreeMap<T, usize>,
}

impl<T: Ord + Clone> MultiSet<T> {
    pub fn new() -> Self {
        MultiSet {
            elems: BTreeMap::new(),
        }
    }

    pub fn insert(&mut self, el: T) {
        *self.elems.entry(el).or_insert(0) += 1;
    }

    pub fn remove(&mut self, el: &T) -> bool {
        if let Some(count) = self.elems.get_mut(el) {
            if *count > 1 {
                *count -= 1;
            } else {
                self.elems.remove(el);
            }
            true
        } else {
            false
        }
    }

    pub fn remove_all(&mut self, el: &T) -> bool {
        if self.elems.remove(el).is_some() {
            true
        } else {
            false
        }
    }

    pub fn contains(&self, el: &T) -> bool {
        self.elems.contains_key(el)
    }

    pub fn first(&self) -> Option<T> {
        self.elems.keys().next().cloned()
    }

    pub fn last(&self) -> Option<T> {
        self.elems.keys().next_back().cloned()
    }

    pub fn iter(&self) -> impl Iterator<Item = (&T, &usize)> {
        self.elems.iter()
    }

    pub fn into_iter(self) -> impl Iterator<Item = (T, usize)> {
        self.elems.into_iter()
    }

    pub fn iter_mut(&mut self) -> impl Iterator<Item = (&T, &mut usize)> {
        self.elems.iter_mut()
    }

    pub fn count(&self, el: &T) -> usize {
        *self.elems.get(el).unwrap_or(&0)
    }

    pub fn len(&self) -> usize {
        self.elems.values().sum()
    }

    pub fn is_empty(&self) -> bool {
        self.elems.is_empty()
    }

    pub fn clear(&mut self) {
        self.elems.clear();
    }

}

impl<T: Ord + Clone> FromIterator<T> for MultiSet<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut multiset = MultiSet::new();
        for el in iter {
            multiset.insert(el);
        }
        multiset
    }
}