A multiple to multiple bimap?

For a project I need a bidirectionnal map that allow multiple to multiple mapping.

I didn't found appropriate crate so I try to implement it myself.

#[derive(Debug, Default)]
pub struct BiMap<T>(HashMap<T, HashSet<T>>);

impl<T> BiMap<T>
where
    T: Eq + Hash + Clone,
{
    pub fn insert(&mut self, a: T, b: T) {
        self.0
            .entry(a.clone())
            .or_insert(HashSet::new())
            .insert(b.clone());
        self.0.entry(b).or_insert(HashSet::new()).insert(a);
    }
}

playground

Now I need to implement an iterator to iterate all couples (a, b) without repetion, because (a, b) is the same as (b, a).
I have no clue how to implement the iterator. Or maybe there is a better way to implement the bimap itself ?

If the items are Ord, only return (a, b) where a <= b.

If they're not Ord, you could make them so within each BiMap by maintaining an arbitrary internal order (e.g. insertion order).

Another option would be to check upon insertion of (a, b) whether (b, a) already exists, and then just not insert it.

E.g.

1 Like