From 4876b9799c6dc62ab34500559d4584f4671ddb0f Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@tavianator.com>
Date: Fri, 29 May 2020 10:24:44 -0400
Subject: chebyshev: Implement Chebyshev distance

---
 src/chebyshev.rs | 120 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 src/lib.rs       |   1 +
 2 files changed, 121 insertions(+)
 create mode 100644 src/chebyshev.rs

(limited to 'src')

diff --git a/src/chebyshev.rs b/src/chebyshev.rs
new file mode 100644
index 0000000..9391c69
--- /dev/null
+++ b/src/chebyshev.rs
@@ -0,0 +1,120 @@
+//! Chebyshev distance.
+
+use crate::coords::{Coordinates, CoordinateMetric, CoordinateProximity};
+use crate::distance::{Metric, Proximity};
+
+use num_traits::{zero, Signed};
+
+/// A point in Chebyshev space.
+///
+/// This wrapper equips any [coordinate space] with the [Chebyshev distance] metric.
+///
+/// [coordinate space]: [Coordinates]
+/// [Chebyshev distance]: https://en.wikipedia.org/wiki/Chebyshev_distance
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub struct Chebyshev<T>(pub T);
+
+impl<T> Chebyshev<T> {
+    /// Wrap a point.
+    pub fn new(point: T) -> Self {
+        Self(point)
+    }
+
+    /// Unwrap a point.
+    pub fn inner(&self) -> &T {
+        &self.0
+    }
+
+    /// Unwrap a point.
+    pub fn into_inner(self) -> T {
+        self.0
+    }
+}
+
+impl<T: Coordinates> Coordinates for Chebyshev<T> {
+    type Value = T::Value;
+
+    fn dims(&self) -> usize {
+        self.0.dims()
+    }
+
+    fn coord(&self, i: usize) -> Self::Value {
+        self.0.coord(i)
+    }
+}
+
+/// Compute the Chebyshev distance between two points.
+pub fn chebyshev_distance<T, U>(x: T, y: U) -> T::Value
+where
+    T: Coordinates,
+    U: Coordinates<Value = T::Value>,
+{
+    debug_assert!(x.dims() == y.dims());
+
+    let mut max = zero();
+
+    for i in 0..x.dims() {
+        let diff = (x.coord(i) - y.coord(i)).abs();
+        if diff > max {
+            max = diff;
+        }
+    }
+
+    max
+}
+
+/// The Chebyshev distance function.
+impl<T: Coordinates> Proximity for Chebyshev<T> {
+    type Distance = T::Value;
+
+    fn distance(&self, other: &Self) -> Self::Distance {
+        chebyshev_distance(self, other)
+    }
+}
+
+impl<T: Coordinates> Proximity<T> for Chebyshev<T> {
+    type Distance = T::Value;
+
+    fn distance(&self, other: &T) -> Self::Distance {
+        chebyshev_distance(self, other)
+    }
+}
+
+impl<T: Coordinates> Proximity<Chebyshev<T>> for T {
+    type Distance = T::Value;
+
+    fn distance(&self, other: &Chebyshev<T>) -> Self::Distance {
+        chebyshev_distance(self, other)
+    }
+}
+
+/// Chebyshev distance is a metric.
+impl<T: Coordinates> Metric for Chebyshev<T> {}
+
+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;
+
+    fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance {
+        chebyshev_distance(self, coords)
+    }
+}
+
+impl<T: Coordinates> CoordinateMetric<T::Value> for Chebyshev<T> {}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_distance() {
+        assert_eq!(chebyshev_distance(&[-3, 4], &[4, -3]), 7);
+
+        assert_eq!(Chebyshev([-3, 4]).distance(&Chebyshev([4, -3])), 7);
+        assert_eq!(Chebyshev([-3, 4]).distance(&[4, -3]), 7);
+        assert_eq!([-3, 4].distance(&Chebyshev([4, -3])), 7);
+    }
+}
diff --git a/src/lib.rs b/src/lib.rs
index 8cce2d8..1ef5c29 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -90,6 +90,7 @@
 //! [`nearest_within()`]: NearestNeighbors#method.nearest_within
 //! [`k_nearest_within()`]: NearestNeighbors#method.k_nearest_within
 
+pub mod chebyshev;
 pub mod coords;
 pub mod distance;
 pub mod euclid;
-- 
cgit v1.2.3