From 5f85a59d4be37d350bcf1ee62c25ac1f84d71770 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Mon, 6 Jul 2020 22:24:02 -0400
Subject: kd: Use a more traditional k-d tree implementation

The slight extra pruning possible in the previous implementation didn't
seem to be worth it.  The new, simpler implementation is also about 30%
faster in most of the benchmarks.

This gets rid of Coordinate{Proximity,Metric} as they're not necessary
any more (and the old ExactNeighbors impl was too restrictive anyway).
---
 src/lp.rs | 19 ++++++++++++++++---
 1 file changed, 16 insertions(+), 3 deletions(-)

(limited to 'src/lp.rs')

diff --git a/src/lp.rs b/src/lp.rs
index 4afd209..db9e65c 100644
--- a/src/lp.rs
+++ b/src/lp.rs
@@ -1,6 +1,10 @@
-//! [`$L^p$` spaces](https://en.wikipedia.org/wiki/Lp_space).
+//! [`$\ell^p$`]/[Minkowski] distance.
+//!
+//! [`$\ell^p$`]: https://en.wikipedia.org/wiki/Lp_space
+//! [Minkowski]: https://en.wikipedia.org/wiki/Minkowski_distance
 
 use crate::coords::Coordinates;
+use crate::distance::Proximity;
 
 use num_traits::real::Real;
 use num_traits::zero;
@@ -25,7 +29,7 @@ pub use crate::chebyshev::Chebyshev as Linf;
 /// Compute the L<sup>∞</sup> distance between two points.
 pub use crate::chebyshev::chebyshev_distance as linf_distance;
 
-/// Compute the [`$L^p$` distance] between two points.
+/// Compute the [`$\ell^p$`]/[Minkowski] distance between two points.
 ///
 /// ```math
 /// \begin{aligned}
@@ -34,7 +38,8 @@ pub use crate::chebyshev::chebyshev_distance as linf_distance;
 /// \end{aligned}
 /// ```
 ///
-/// [`$L^p$` distance]: https://en.wikipedia.org/wiki/Lp_space
+/// [`$\ell^p$`]: https://en.wikipedia.org/wiki/Lp_space
+/// [Minkowski]: https://en.wikipedia.org/wiki/Minkowski_distance
 pub fn lp_distance<T, U>(p: T::Value, x: T, y: U) -> T::Value
 where
     T: Coordinates,
@@ -51,6 +56,14 @@ where
     sum.powf(p.recip())
 }
 
+/// Marker trait for [Minkowski distances].
+///
+/// [Minkowski distances]: https://en.wikipedia.org/wiki/Minkowski_distance
+pub trait Minkowski<T: ?Sized = Self>: Proximity<T> {}
+
+/// Blanket [`Minkowski`] implementation for references.
+impl<'k, 'v, K: Minkowski<V>, V> Minkowski<&'v V> for &'k K {}
+
 #[cfg(test)]
 mod tests {
     use super::*;
-- 
cgit v1.2.3