Take element with lowest value from a HashSet?

Question

I'm trying to make a heap with a method that returns the node having the minimum f-value, and at the same time remove it from the heap itself.

The heap should still be usable afterwards, only without the removed value:

The Node struct and its implementations:

use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct Node {
    x: f64,
    y: f64,
    f: f64,
}

impl Node {
    fn to_bits(&self) -> u128 {
        let xb = self.x.to_bits() as u128;
        let yb = self.y.to_bits() as u128;
        (xb << 64) + yb
    }
}

impl PartialEq for Node {
    fn eq(&self, other: &Node) -> bool {
        self.x == other.x && self.y == other.y
    }
}

impl Eq for Node {}

impl Hash for Node {
    fn hash<H>(&self, state: &mut H) where H: Hasher {
        self.to_bits().hash(state)
    }
}

The Heap struct:

use std::f64;
use std::collections::HashSet;

#[derive(Debug)]
struct Heap {
    pool: HashSet<Node>,
}

impl Heap {
    fn add(mut self, node: Node) -> Heap {
        self.pool.insert(node);
        self
    }

    fn consume(mut self) -> Node {
      // find the node with minimum f-value in self.pool
      // and "take" it, aka remove it from the pool
      // and then return it
      Node { x: 0.0, y: 0.0, f: 0.0 } // dummy node so that the code compiles
    }
}

And the main function:

fn main() {
    let n1 = Node { x: 10.0, y: 11.0, f: 5.0 };
    let n2 = Node { x: 11.0, y: 12.0, f: 7.0 };
    let n3 = Node { x: 12.0, y: 13.0, f: 3.0 };
    let n4 = Node { x: 14.0, y: 14.0, f: 4.0 };

    let mut heap = Heap { pool: HashSet::new() };
    heap = heap.add(n1);
    heap = heap.add(n2);
    heap = heap.add(n3);
    heap = heap.add(n4);

    let minimal_n1 = heap.consume();
    println!("{:?}", minimal_n1);
    // should print
    // Node { x: 12.0, y: 13.0, f: 3.0 }

    let minimal_n2 = heap.consume();
    println!("{:?}", minimal_n2);
    // should print
    // Node { x: 14.0, y: 14.0, f: 4.0 }

    println!("Heap has {} nodes", heap.pool.len());
    // should print
    // Heap has 2 nodes
}

Here is what I've tried so far with regards to consume:

fn consume(mut self) -> Node {
    let mut min_f = f64::MAX;
    let mut min_node: Option<&Node> = None;

    for n in self.pool.iter() {
        if n.f < min_f {
            min_f = n.f;
            min_node = Some(n);
        }
    }

    self.pool.take(&min_node.unwrap()).unwrap()
}

The issue is that self.pool is borrowed immutably by the iter() method, and therefore the self.pool.take() cannot borrow it mutably at the same moment.

What would be the best approach to make this consume method take and return the node with has the minimal f-value among the pool?

Notes:

• a Set (or a Map) is needed because other methods need to retrieve any Node in O(1)
• I don't use an ordered set (which would easily solve the above issue) because add/update operations have to stay O(1)
• The heap needs to be accessed after having removed the minimum-f node, as shown in the example

Answer 1

Luckily, since you are taking self by value, this is an easy problem to solve. Just throw away everything that isn't the minimum Node:

fn consume(self) -> Node {
    self.pool
        .into_iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .expect("There was no minimum")
}

If you need to keep the Heap afterwards, you need to disassociate the found value from the heap before removing it. Cloning is the easiest solution:

fn consume(&mut self) -> Node {
    let min = self.pool
        .iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .cloned()
        .expect("There was no minimum");

    self.pool.remove(&min);

    min
}

This does require that you perform an "extra" hash lookup. Since you are iterating through the entire HashSet, that seems like it will be a comparatively small cost.

---

If you cannot easily clone the element, buckle up. Using the ideas from How to implement HashMap with two keys?, we can construct a trait object that can be used to look up a key based on parallel but equivalent hashing / equality implementations:

use std::borrow::Borrow;

trait Key {
    fn as_bits(&self) -> u128;
}

impl Key for Node {
    fn as_bits(&self) -> u128 {
        let xb = self.x.to_bits() as u128;
        let yb = self.y.to_bits() as u128;
        (xb << 64) + yb
    }
}

impl Key for u128 {
    fn as_bits(&self) -> u128 { *self }
}

impl<'a> Hash for Key + 'a {
    fn hash<H: Hasher>(&self, h: &mut H) {
        self.as_bits().hash(h)
    }
}

impl<'a> PartialEq for Key + 'a {
    fn eq(&self, other: &Self) -> bool {
        self.as_bits() == other.as_bits()        
    }
}

impl<'a> Eq for Key + 'a {}

impl<'a> Borrow<Key + 'a> for Node {
    fn borrow(&self) -> &(Key + 'a) {
        self
    }
}

impl<'a> Borrow<Key + 'a> for u128 {
    fn borrow(&self) -> &(Key + 'a) {
        self
    }
}

With this support, we can then convert the found element into a lightweight owned key and then look up again using it:

fn consume(&mut self) -> Node {
    let min_key = self.pool
        .iter()
        .min_by(|a, b| a.f.partial_cmp(&b.f).expect("Found a NaN"))
        .map(Node::as_bits)
        .expect("There was no minimum");

    let min_key: &Key = min_key.borrow();
    self.pool.take(min_key).unwrap()
}