//! [Taxicab (Manhattan) distance](https://en.wikipedia.org/wiki/Taxicab_geometry). use crate::coords::{CoordinateMetric, CoordinateProximity, Coordinates}; use crate::distance::{Metric, Proximity}; use num_traits::{zero, Signed}; /// A point in taxicab space. /// /// This wrapper equips any [coordinate space] with the [taxicab distance] metric. /// /// [coordinate space]: Coordinates /// [taxicab distance]: taxicab_distance #[derive(Clone, Copy, Debug, Eq, PartialEq)] pub struct Taxicab(pub T); impl Taxicab { /// 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 Taxicab { type Value = T::Value; fn dims(&self) -> usize { self.0.dims() } fn coord(&self, i: usize) -> Self::Value { self.0.coord(i) } } /// Compute the [taxicab distance] between two points. /// /// math /// \begin{aligned} /// \mathrm{taxicab\_distance}(x, y) &= \|x - y\|_1 \\ /// &= \sum_i |x_i - y_i| /// \end{aligned} ///  /// /// [taxicab distance]: https://en.wikipedia.org/wiki/Taxicab_geometry pub fn taxicab_distance(x: T, y: U) -> T::Value where T: Coordinates, U: Coordinates, { debug_assert!(x.dims() == y.dims()); let mut sum = zero(); for i in 0..x.dims() { sum += (x.coord(i) - y.coord(i)).abs(); } sum } /// The taxicab distance function. impl Proximity for Taxicab { type Distance = T::Value; fn distance(&self, other: &Self) -> Self::Distance { taxicab_distance(self, other) } } impl Proximity for Taxicab { type Distance = T::Value; fn distance(&self, other: &T) -> Self::Distance { taxicab_distance(self, other) } } impl Proximity> for T { type Distance = T::Value; fn distance(&self, other: &Taxicab) -> Self::Distance { taxicab_distance(self, other) } } /// Taxicab distance is a metric. impl Metric for Taxicab {} impl Metric for Taxicab {} impl Metric> for T {} impl CoordinateProximity for Taxicab { type Distance = T::Value; fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance { taxicab_distance(self, coords) } } impl CoordinateMetric for Taxicab {} #[cfg(test)] mod tests { use super::*; #[test] fn test_distance() { assert_eq!(taxicab_distance([-3, 4], [4, -3]), 14); assert_eq!(Taxicab([-3, 4]).distance(&Taxicab([4, -3])), 14); assert_eq!(Taxicab([-3, 4]).distance(&[4, -3]), 14); assert_eq!([-3, 4].distance(&Taxicab([4, -3])), 14); } }