From 4876b9799c6dc62ab34500559d4584f4671ddb0f Mon Sep 17 00:00:00 2001 From: Tavian Barnes 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(pub T); + +impl Chebyshev { + /// 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 Coordinates for Chebyshev { + 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(x: T, y: U) -> T::Value +where + T: Coordinates, + U: Coordinates, +{ + 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 Proximity for Chebyshev { + type Distance = T::Value; + + fn distance(&self, other: &Self) -> Self::Distance { + chebyshev_distance(self, other) + } +} + +impl Proximity for Chebyshev { + type Distance = T::Value; + + fn distance(&self, other: &T) -> Self::Distance { + chebyshev_distance(self, other) + } +} + +impl Proximity> for T { + type Distance = T::Value; + + fn distance(&self, other: &Chebyshev) -> Self::Distance { + chebyshev_distance(self, other) + } +} + +/// Chebyshev distance is a metric. +impl Metric for Chebyshev {} + +impl Metric for Chebyshev {} + +impl Metric> for T {} + +impl CoordinateProximity for Chebyshev { + type Distance = T::Value; + + fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance { + chebyshev_distance(self, coords) + } +} + +impl CoordinateMetric for Chebyshev {} + +#[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