Skip to main content

a_star/discovered/
min_heap.rs

1use crate::{DiscoveredSet, NodeCost};
2use std::cmp::Reverse;
3use std::collections::BinaryHeap;
4
5/// A binary min-heap implementation of the discovered set.
6#[derive(Clone, Debug, Default)]
7pub struct MinHeap<Node, Cost>
8where
9    Node: Copy,
10    Cost: Copy + Ord,
11{
12    heap: BinaryHeap<Reverse<NodeCost<Node, Cost>>>,
13}
14
15impl<Node, Cost> DiscoveredSet<Node, Cost> for MinHeap<Node, Cost>
16where
17    Node: Copy,
18    Cost: Copy + Ord,
19{
20    fn push(&mut self, node: NodeCost<Node, Cost>) {
21        self.heap.push(Reverse(node));
22    }
23
24    fn pop(&mut self) -> Option<NodeCost<Node, Cost>> {
25        self.heap.pop().map(|Reverse(node)| node)
26    }
27
28    fn clear(&mut self) {
29        self.heap.clear()
30    }
31}