A multiple to multiple bimap?

help
#1

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 ?

#2

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).

#3

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

#4

E.g.

1 Like