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).

9 files changed, 84 insertions, 118 deletions

diff --git a/src/chebyshev.rs b/src/chebyshev.rs
index f6eba8a..a01b24f 100644
--- a/src/chebyshev.rs
+++ b/src/chebyshev.rs
@@ -1,7 +1,8 @@
 //! [Chebyshev distance](https://en.wikipedia.org/wiki/Chebyshev_distance).
 
-use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates};
+use crate::coords::Coordinates;
 use crate::distance::{Metric, Proximity};
+use crate::lp::Minkowski;
 
 use num_traits::{zero, Signed};
 
@@ -104,15 +105,12 @@ impl<T: Coordinates> Metric<T> for Chebyshev<T> {}
 
 impl<T: Coordinates> Metric<Chebyshev<T>> for T {}
 
-impl<T: Coordinates> CoordinateProximity<T::Value> for Chebyshev<T> {
-    type Distance = T::Value;
+/// Chebyshev distance is a [Minkowski] distance.
+impl<T: Coordinates> Minkowski for Chebyshev<T> {}
 
-    fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance {
-        chebyshev_distance(self, coords)
-    }
-}
+impl<T: Coordinates> Minkowski<T> for Chebyshev<T> {}
 
-impl<T: Coordinates> CoordinateMetric<T::Value> for Chebyshev<T> {}
+impl<T: Coordinates> Minkowski<Chebyshev<T>> for T {}
 
 #[cfg(test)]
 mod tests {
diff --git a/src/coords.rs b/src/coords.rs
index 2e292ae..7c83946 100644
--- a/src/coords.rs
+++ b/src/coords.rs
@@ -1,6 +1,6 @@
 //! [Coordinate spaces](https://en.wikipedia.org/wiki/Cartesian_coordinate_system).
 
-use crate::distance::{Distance, Value};
+use crate::distance::Value;
 
 /// A coordinate space.
 pub trait Coordinates {
@@ -88,26 +88,3 @@ impl<T: ?Sized + Coordinates> Coordinates for &T {
         (*self).coord(i)
     }
 }
-
-/// Types that support computing distances to raw slices of coordinates.
-pub trait CoordinateProximity<T> {
-    type Distance: Distance;
-
-    /// Compute the distance to a point specified by its coordinates.
-    fn distance_to_coords(&self, coords: &[T]) -> Self::Distance;
-}
-
-/// Blanket [`CoordinateProximity`] implementation for references.
-impl<T: CoordinateProximity<U>, U> CoordinateProximity<U> for &T {
-    type Distance = T::Distance;
-
-    fn distance_to_coords(&self, coords: &[U]) -> Self::Distance {
-        (*self).distance_to_coords(coords)
-    }
-}
-
-/// Marker trait for coordinate proximities that are [metrics][crate::distance::Metric].
-pub trait CoordinateMetric<T>: CoordinateProximity<T> {}
-
-/// Blanket [`CoordinateMetric`] implementation for references.
-impl<T: CoordinateMetric<U>, U> CoordinateMetric<U> for &T {}
diff --git a/src/euclid.rs b/src/euclid.rs
index 3833146..3ec0af9 100644
--- a/src/euclid.rs
+++ b/src/euclid.rs
@@ -1,7 +1,8 @@
 //! [Euclidean space](https://en.wikipedia.org/wiki/Euclidean_space).
 
-use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates};
+use crate::coords::Coordinates;
 use crate::distance::{Distance, Metric, Proximity, Value};
+use crate::lp::Minkowski;
 
 use num_traits::zero;
 
@@ -128,19 +129,20 @@ where
     EuclideanDistance<T::Value>: Distance,
 {}
 
-impl<T> CoordinateProximity<T::Value> for Euclidean<T>
+/// Euclidean distance is a [Minkowski] distance.
+impl<T> Minkowski for Euclidean<T>
 where
     T: Coordinates,
     EuclideanDistance<T::Value>: Distance,
-{
-    type Distance = EuclideanDistance<T::Value>;
+{}
 
-    fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance {
-        euclidean_distance(self, coords)
-    }
-}
+impl<T> Minkowski<T> for Euclidean<T>
+where
+    T: Coordinates,
+    EuclideanDistance<T::Value>: Distance,
+{}
 
-impl<T> CoordinateMetric<T::Value> for Euclidean<T>
+impl<T> Minkowski<Euclidean<T>> for T
 where
     T: Coordinates,
     EuclideanDistance<T::Value>: Distance,
diff --git a/src/exhaustive.rs b/src/exhaustive.rs
index 221641c..37af4c6 100644
--- a/src/exhaustive.rs
+++ b/src/exhaustive.rs
@@ -80,10 +80,10 @@ impl<K: Proximity<V>, V> ExactNeighbors<K, V> for ExhaustiveSearch<V> {}
 pub mod tests {
     use super::*;
 
-    use crate::tests::test_nearest_neighbors;
+    use crate::tests::test_exact_neighbors;
 
     #[test]
     fn test_exhaustive_index() {
-        test_nearest_neighbors(ExhaustiveSearch::from_iter);
+        test_exact_neighbors(ExhaustiveSearch::from_iter);
     }
 }
diff --git a/src/kd.rs b/src/kd.rs
index 291028e..dae73ec 100644
--- a/src/kd.rs
+++ b/src/kd.rs
@@ -1,10 +1,13 @@
 //! [k-d trees](https://en.wikipedia.org/wiki/K-d_tree).
 
-use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates};
-use crate::distance::{Metric, Proximity};
+use crate::coords::Coordinates;
+use crate::distance::Proximity;
+use crate::lp::Minkowski;
 use crate::util::Ordered;
 use crate::{ExactNeighbors, NearestNeighbors, Neighborhood};
 
+use num_traits::Signed;
+
 use std::iter::FromIterator;
 use std::ops::Deref;
 
@@ -86,7 +89,7 @@ pub trait KdProximity<V: ?Sized = Self>
 where
     Self: Coordinates<Value = V::Value>,
     Self: Proximity<V>,
-    Self: CoordinateProximity<V::Value, Distance = <Self as Proximity<V>>::Distance>,
+    Self::Value: PartialOrd<Self::Distance>,
     V: Coordinates,
 {}
 
@@ -95,31 +98,14 @@ impl<K, V> KdProximity<V> for K
 where
     K: Coordinates<Value = V::Value>,
     K: Proximity<V>,
-    K: CoordinateProximity<V::Value, Distance = <K as Proximity<V>>::Distance>,
-    V: Coordinates,
-{}
-
-/// Marker trait for [`Metric`] implementations that are compatible with k-d tree.
-pub trait KdMetric<V: ?Sized = Self>
-where
-    Self: KdProximity<V>,
-    Self: Metric<V>,
-    Self: CoordinateMetric<V::Value>,
-    V: Coordinates,
-{}
-
-/// Blanket [`KdMetric`] implementation.
-impl<K, V> KdMetric<V> for K
-where
-    K: KdProximity<V>,
-    K: Metric<V>,
-    K: CoordinateMetric<V::Value>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates,
 {}
 
 trait KdSearch<K, V, N>: Copy
 where
     K: KdProximity<V>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates + Copy,
     N: Neighborhood<K, V>,
 {
@@ -133,41 +119,29 @@ where
     fn right(self) -> Option<Self>;
 
     /// Recursively search for nearest neighbors.
-    fn search(self, level: usize, closest: &mut [V::Value], neighborhood: &mut N) {
+    fn search(self, level: usize, neighborhood: &mut N) {
         let item = self.item();
         neighborhood.consider(item);
 
         let target = neighborhood.target();
 
-        if target.coord(level) <= item.coord(level) {
-            self.search_near(self.left(), level, closest, neighborhood);
-            self.search_far(self.right(), level, closest, neighborhood);
+        let bound = target.coord(level) - item.coord(level);
+        let (near, far) = if bound.is_negative() {
+            (self.left(), self.right())
         } else {
-            self.search_near(self.right(), level, closest, neighborhood);
-            self.search_far(self.left(), level, closest, neighborhood);
-        }
-    }
+            (self.right(), self.left())
+        };
+
+        let next = (level + 1) % self.item().dims();
 
-    /// Search the subtree closest to the target.
-    fn search_near(self, near: Option<Self>, level: usize, closest: &mut [V::Value], neighborhood: &mut N) {
         if let Some(near) = near {
-            let next = (level + 1) % self.item().dims();
-            near.search(next, closest, neighborhood);
+            near.search(next, neighborhood);
         }
-    }
 
-    /// Search the subtree farthest from the target.
-    fn search_far(self, far: Option<Self>, level: usize, closest: &mut [V::Value], neighborhood: &mut N) {
         if let Some(far) = far {
-            // Update the closest possible point
-            let item = self.item();
-            let target = neighborhood.target();
-            let saved = std::mem::replace(&mut closest[level], item.coord(level));
-            if neighborhood.contains(target.distance_to_coords(closest)) {
-                let next = (level + 1) % item.dims();
-                far.search(next, closest, neighborhood);
+            if neighborhood.contains(bound.abs()) {
+                far.search(next, neighborhood);
             }
-            closest[level] = saved;
         }
     }
 }
@@ -175,6 +149,7 @@ where
 impl<'a, K, V, N> KdSearch<K, &'a V, N> for &'a KdNode<V>
 where
     K: KdProximity<&'a V>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates,
     N: Neighborhood<K, &'a V>,
 {
@@ -315,6 +290,7 @@ impl<T> IntoIterator for KdTree<T> {
 impl<K, V> NearestNeighbors<K, V> for KdTree<V>
 where
     K: KdProximity<V>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates,
 {
     fn search<'k, 'v, N>(&'v self, mut neighborhood: N) -> N
@@ -324,16 +300,17 @@ where
         N: Neighborhood<&'k K, &'v V>,
     {
         if let Some(root) = &self.root {
-            let mut closest = neighborhood.target().as_vec();
-            root.search(0, &mut closest, &mut neighborhood);
+            root.search(0, &mut neighborhood);
         }
         neighborhood
     }
 }
 
+/// k-d trees are exact for [Minkowski] distances.
 impl<K, V> ExactNeighbors<K, V> for KdTree<V>
 where
-    K: KdMetric<V>,
+    K: KdProximity<V> + Minkowski<V>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates,
 {}
 
@@ -389,6 +366,7 @@ impl<T: Coordinates> FlatKdNode<T> {
 impl<'a, K, V, N> KdSearch<K, &'a V, N> for &'a [FlatKdNode<V>]
 where
     K: KdProximity<&'a V>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates,
     N: Neighborhood<K, &'a V>,
 {
@@ -465,6 +443,7 @@ impl<T> IntoIterator for FlatKdTree<T> {
 impl<K, V> NearestNeighbors<K, V> for FlatKdTree<V>
 where
     K: KdProximity<V>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates,
 {
     fn search<'k, 'v, N>(&'v self, mut neighborhood: N) -> N
@@ -474,18 +453,17 @@ where
         N: Neighborhood<&'k K, &'v V>,
     {
         if !self.nodes.is_empty() {
-            let mut closest = neighborhood.target().as_vec();
-            self.nodes
-                .as_slice()
-                .search(0, &mut closest, &mut neighborhood);
+            self.nodes.as_slice().search(0, &mut neighborhood);
         }
         neighborhood
     }
 }
 
+/// k-d trees are exact for [Minkowski] distances.
 impl<K, V> ExactNeighbors<K, V> for FlatKdTree<V>
 where
-    K: KdMetric<V>,
+    K: KdProximity<V> + Minkowski<V>,
+    K::Value: PartialOrd<K::Distance>,
     V: Coordinates,
 {}
 
@@ -493,16 +471,16 @@ where
 mod tests {
     use super::*;
 
-    use crate::tests::test_nearest_neighbors;
+    use crate::tests::test_exact_neighbors;
 
     #[test]
     fn test_kd_tree() {
-        test_nearest_neighbors(KdTree::from_iter);
+        test_exact_neighbors(KdTree::from_iter);
     }
 
     #[test]
     fn test_unbalanced_kd_tree() {
-        test_nearest_neighbors(|points| {
+        test_exact_neighbors(|points| {
             let mut tree = KdTree::new();
             for point in points {
                 tree.push(point);
@@ -513,6 +491,6 @@ mod tests {
 
     #[test]
     fn test_flat_kd_tree() {
-        test_nearest_neighbors(FlatKdTree::from_iter);
+        test_exact_neighbors(FlatKdTree::from_iter);
     }
 }
diff --git a/src/lib.rs b/src/lib.rs
index d6e5579..57f3dac 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -464,10 +464,10 @@ pub mod tests {
 
     type Point = Euclidean<[f32; 3]>;
 
-    /// Test a [NearestNeighbors] implementation.
-    pub fn test_nearest_neighbors<T, F>(from_iter: F)
+    /// Test an [ExactNeighbors] implementation.
+    pub fn test_exact_neighbors<T, F>(from_iter: F)
     where
-        T: NearestNeighbors<Point>,
+        T: ExactNeighbors<Point>,
         F: Fn(Vec<Point>) -> T,
     {
         test_empty(&from_iter);
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::*;
diff --git a/src/taxi.rs b/src/taxi.rs
index 7c33ecb..e189a36 100644
--- a/src/taxi.rs
+++ b/src/taxi.rs
@@ -1,7 +1,8 @@
 //! [Taxicab (Manhattan) distance](https://en.wikipedia.org/wiki/Taxicab_geometry).
 
-use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates};
+use crate::coords::Coordinates;
 use crate::distance::{Metric, Proximity};
+use crate::lp::Minkowski;
 
 use num_traits::{zero, Signed};
 
@@ -100,15 +101,12 @@ impl<T: Coordinates> Metric<T> for Taxicab<T> {}
 
 impl<T: Coordinates> Metric<Taxicab<T>> for T {}
 
-impl<T: Coordinates> CoordinateProximity<T::Value> for Taxicab<T> {
-    type Distance = T::Value;
+/// Taxicab distance is a [Minkowski] distance.
+impl<T: Coordinates> Minkowski for Taxicab<T> {}
 
-    fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance {
-        taxicab_distance(self, coords)
-    }
-}
+impl<T: Coordinates> Minkowski<T> for Taxicab<T> {}
 
-impl<T: Coordinates> CoordinateMetric<T::Value> for Taxicab<T> {}
+impl<T: Coordinates> Minkowski<Taxicab<T>> for T {}
 
 #[cfg(test)]
 mod tests {
diff --git a/src/vp.rs b/src/vp.rs
index 85d3972..c44b323 100644
--- a/src/vp.rs
+++ b/src/vp.rs
@@ -532,16 +532,16 @@ where
 mod tests {
     use super::*;
 
-    use crate::tests::test_nearest_neighbors;
+    use crate::tests::test_exact_neighbors;
 
     #[test]
     fn test_vp_tree() {
-        test_nearest_neighbors(VpTree::from_iter);
+        test_exact_neighbors(VpTree::from_iter);
     }
 
     #[test]
     fn test_unbalanced_vp_tree() {
-        test_nearest_neighbors(|points| {
+        test_exact_neighbors(|points| {
             let mut tree = VpTree::new();
             for point in points {
                 tree.push(point);
@@ -552,6 +552,6 @@ mod tests {
 
     #[test]
     fn test_flat_vp_tree() {
-        test_nearest_neighbors(FlatVpTree::from_iter);
+        test_exact_neighbors(FlatVpTree::from_iter);
     }
 }