//! [Chebyshev distance](https://en.wikipedia.org/wiki/Chebyshev_distance). use crate::coords::Coordinates; use crate::distance::{Metric, Proximity}; use crate::lp::Minkowski; 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]: 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. /// /// math /// \begin{aligned} /// \mathrm{chebyshev\_distance}(x, y) &= \|x - y\|_\infty \\ /// &= \max_i |x_i - y_i| /// \end{aligned} ///  /// /// [Chebyshev distance]: https://en.wikipedia.org/wiki/Chebyshev_distance 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 {} /// Chebyshev distance is a [Minkowski] distance. impl Minkowski for Chebyshev {} impl Minkowski for Chebyshev {} impl Minkowski> for 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); } }