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/euclid.rs | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

(limited to 'src/euclid.rs')

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,
-- 
cgit v1.2.3