replace priority_queue crate with std BinaryHeap

azalea-rs · Dec 26, 2024 · 3c83e5b · 3c83e5b
1 parent e11a902
commit 3c83e5b
Show file tree

Hide file tree

Showing 4 changed files with 19 additions and 32 deletions.
diff --git a/Cargo.lock b/Cargo.lock
diff --git a/Cargo.toml b/Cargo.toml
@@ -56,7 +56,6 @@ nohash-hasher = "0.2.0"
 num-bigint = "0.4.6"
 num-traits = "0.2.19"
 parking_lot = "0.12.3"
-priority-queue = "2.1.1"
 proc-macro2 = "1.0.92"
 quote = "1.0.37"
 rand = "0.8.5"
@@ -79,6 +78,7 @@ tracing = "0.1.41"
 tracing-subscriber = "0.3.19"
 hickory-resolver = { version = "0.24.2", default-features = false }
 uuid = "1.11.0"
+num-format = "0.4.4"
 
 # --- Profile Settings ---
 

diff --git a/azalea/Cargo.toml b/azalea/Cargo.toml
@@ -35,10 +35,9 @@ derive_more = { workspace = true, features = ["deref", "deref_mut"] }
 futures = { workspace = true }
 futures-lite = { workspace = true }
 nohash-hasher = { workspace = true }
-num-format = "0.4.4"
+num-format = { workspace = true }
 num-traits = { workspace = true }
 parking_lot = { workspace = true }
-priority-queue = { workspace = true }
 rustc-hash = { workspace = true }
 serde = { workspace = true, optional = true }
 thiserror = { workspace = true }

diff --git a/azalea/src/pathfinder/astar.rs b/azalea/src/pathfinder/astar.rs
@@ -1,12 +1,12 @@
 use std::{
-    cmp::Reverse,
+    cmp::{self},
+    collections::BinaryHeap,
     fmt::Debug,
     hash::Hash,
     time::{Duration, Instant},
 };
 
 use num_format::ToFormattedString;
-use priority_queue::PriorityQueue;
 use rustc_hash::FxHashMap;
 use tracing::{debug, trace, warn};
 
@@ -52,8 +52,8 @@ where
 {
     let start_time = Instant::now();
 
-    let mut open_set = PriorityQueue::new();
-    open_set.push(start, Reverse(Weight(0.)));
+    let mut open_set = BinaryHeap::<WeightedNode<P>>::new();
+    open_set.push(WeightedNode(start, 0.));
     let mut nodes: FxHashMap<P, Node<P, M>> = FxHashMap::default();
     nodes.insert(
         start,
@@ -71,7 +71,7 @@ where
 
     let mut num_nodes = 0;
 
-    while let Some((current_node, _)) = open_set.pop() {
+    while let Some(WeightedNode(current_node, _)) = open_set.pop() {
         num_nodes += 1;
         if success(current_node) {
             debug!("Nodes considered: {num_nodes}");
@@ -106,7 +106,7 @@ where
                         f_score,
                     },
                 );
-                open_set.push(neighbor.movement.target, Reverse(Weight(f_score)));
+                open_set.push(WeightedNode(neighbor.movement.target, f_score));
 
                 for (coefficient_i, &coefficient) in COEFFICIENTS.iter().enumerate() {
                     let node_score = heuristic + tentative_g_score / coefficient;
@@ -118,8 +118,8 @@ where
             }
         }
 
-        // check for timeout every ~1ms
-        if num_nodes % 1000 == 0 {
+        // check for timeout every ~20ms
+        if num_nodes % 10000 == 0 {
             let timed_out = match timeout {
                 PathfinderTimeout::Time(max_duration) => start_time.elapsed() > max_duration,
                 PathfinderTimeout::Nodes(max_nodes) => num_nodes > max_nodes,
@@ -218,17 +218,17 @@ impl<P: Hash + Copy + Clone, M: Clone> Clone for Movement<P, M> {
 }
 
 #[derive(PartialEq)]
-pub struct Weight(f32);
-impl Ord for Weight {
-    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
-        self.0
-            .partial_cmp(&other.0)
-            .unwrap_or(std::cmp::Ordering::Equal)
+pub struct WeightedNode<P: PartialEq>(P, f32);
+
+impl<P: PartialEq> Ord for WeightedNode<P> {
+    fn cmp(&self, other: &Self) -> cmp::Ordering {
+        // intentionally inverted to make the BinaryHeap a min-heap
+        other.1.partial_cmp(&self.1).unwrap_or(cmp::Ordering::Equal)
     }
 }
-impl Eq for Weight {}
-impl PartialOrd for Weight {
-    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
+impl<P: PartialEq> Eq for WeightedNode<P> {}
+impl<P: PartialEq> PartialOrd for WeightedNode<P> {
+    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
         Some(self.cmp(other))
     }
 }