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/taxi.rs | 14 ++++++--------
 1 file changed, 6 insertions(+), 8 deletions(-)

(limited to 'src/taxi.rs')

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