How to implement a HashSet of pairs that prevents inserting overlapping values?

Question

Ideally it would behave as such:

let mut set: HashSet<(usize, usize)> = todo!(); // I imagine `(usize, usize)` will instead be some struct
set.insert((1, 10))?; // Returning an error if insertion of an overlapping pair was attempted
set.insert((20, 2))?; // e.g. (1, 2) would return an error
let other = set.get(1); // other = Some(10), or other = Some((1, 10)), either works, the 2nd is just redundant
let other = set.get(2); // other = Some(20)

I think this sums up the question.

I have read through the related question How to implement HashMap with two keys? but this covers a different approach and while it gives some ideas, I do not know enough to make the leap from those ideas to this implementation.

An ideal implementation may look like:

fn insert_pair<T: Hash + Eq + Clone>(map: &mut HashMap<T, T>, pair: (T, T)) -> Result<(), ()> {
    match (map.entry(pair.0.clone()), map.entry(pair.1.clone())) {
        (Entry::Vacant(a), Entry::Vacant(b)) => {
            a.insert(pair.0);
            b.insert(pair.1);
            return Ok(());
        }
        _ => return Err(()),
    }
}

What happens if someone does `set.insert((20, 2));set.insert((4, 20));` and `set.get(20)`? — loganfsmyth, Jan 04 '21 at 20:27
@loganfsmyth I suppose insert would return a result on `set.insert((4,20))` that was an error. Did not think of that, will add it to the question, thank you. — Jonathan Woollett-light, Jan 04 '21 at 20:29

Aplet123 · Answer 1 · 2021-01-04T22:41:48.793

1

It sounds like you want a HashMap<usize, usize> where each element maps to the other:

// you can make it return an Option<()> or bool, doesn't really matter 
fn insert_pair<T: Hash + Eq + Clone>(map: &mut HashMap<T, T>, pair: (T, T)) -> Result<(), ()> {
    match map.entry(pair.0.clone()) {
        Entry::Occupied(_) => return Err(()),
        Entry::Vacant(e) => e.insert(pair.1.clone()),
    };
    match map.entry(pair.1) {
        Entry::Occupied(_) => return Err(()),
        Entry::Vacant(e) => e.insert(pair.0),
    };
    Ok(())
}

fn main() -> Result<(), ()> {
    let mut map: HashMap<usize, usize> = HashMap::new();
    insert_pair(&mut map, (1, 10))?;
    insert_pair(&mut map, (2, 20))?;
    // uncomment this line and it'll error
    // insert_pair(&mut map, (1, 3))?;
    println!("{:?}", map.get(&1)); // Some(10)
    println!("{:?}", map.get(&20)); // Some(2)
    Ok(())
}

Playground link

edited Jan 04 '21 at 22:41

answered Jan 04 '21 at 20:15

Aplet123

33,825
1
29
55

This is almost perfect, but it does allow overwriting pairs, I made the recent edit of `// Returning an error if insertion of an overlapping pair was attempted` apologies for missing this before, this solution does work for the purpose, but requires a bit of extra checking. – Jonathan Woollett-light Jan 04 '21 at 21:15
@JonathanWoollett-light No problem :) I've edited a check into my answer – Aplet123 Jan 04 '21 at 22:41
The only change that I'd make is to undo the first entry insertion if the second failed, but perhaps that's an exercise left to the reader – kmdreko Jan 05 '21 at 02:33
@Aplet123 A fix for the issue kmdreko mentioned https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=038c9f1ecbd8f4f3b74d7543b5faf8c2 . While this works, it is not as performant as it could be, something more like https://pastebin.com/AUak8ri1 would be ideal, of course this does not work due to the multiple mutable borrows and needs a way to guarantee they don't intersect. – Jonathan Woollett-light Jan 05 '21 at 07:11
@Aplet123 I imagine a solution may require some `unsafe` elements – Jonathan Woollett-light Jan 05 '21 at 07:23

How to implement a HashSet of pairs that prevents inserting overlapping values?

1 Answers1