summaryrefslogtreecommitdiffstats
path: root/src/kd.rs
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2020-11-18 08:47:12 -0500
committerTavian Barnes <tavianator@tavianator.com>2020-11-18 08:47:12 -0500
commit62fe810c118c37b596c5329b9360fec2b33b04b0 (patch)
treeb0512e3f46fa2f8446675417d46b8760565b0ed1 /src/kd.rs
parent7d3b49bff8c61820573b57a79a2dbfd3fe06c6fb (diff)
downloadacap-62fe810c118c37b596c5329b9360fec2b33b04b0.tar.xz
ks: Use sort_unstable_by_key rather than sort_by_cached_key
The comparison key is just a single coordinate, no need for the overhead of caching.
Diffstat (limited to 'src/kd.rs')
-rw-r--r--src/kd.rs8
1 files changed, 4 insertions, 4 deletions
diff --git a/src/kd.rs b/src/kd.rs
index dae73ec..5434ddd 100644
--- a/src/kd.rs
+++ b/src/kd.rs
@@ -14,7 +14,7 @@ use std::ops::Deref;
/// A node in a k-d tree.
#[derive(Debug)]
struct KdNode<T> {
- /// The vantage point itself.
+ /// The item stored in this node.
item: T,
/// The left subtree, if any.
left: Option<Box<Self>>,
@@ -51,7 +51,7 @@ impl<T: Coordinates> KdNode<T> {
return None;
}
- nodes.sort_by_cached_key(|x| Ordered::new(x.as_ref().unwrap().item.coord(level)));
+ nodes.sort_unstable_by_key(|x| Ordered::new(x.as_ref().unwrap().item.coord(level)));
let (left, right) = nodes.split_at_mut(nodes.len() / 2);
let (node, right) = right.split_first_mut().unwrap();
@@ -317,7 +317,7 @@ where
/// A node in a flat k-d tree.
#[derive(Debug)]
struct FlatKdNode<T> {
- /// The vantage point itself.
+ /// The item stored in this node.
item: T,
/// The size of the left subtree.
left_len: usize,
@@ -347,7 +347,7 @@ impl<T: Coordinates> FlatKdNode<T> {
/// Create a balanced subtree.
fn balance_recursive(nodes: &mut [Self], level: usize) {
if !nodes.is_empty() {
- nodes.sort_by_cached_key(|x| Ordered::new(x.item.coord(level)));
+ nodes.sort_unstable_by_key(|x| Ordered::new(x.item.coord(level)));
let mid = nodes.len() / 2;
nodes.swap(0, mid);