From 5deaaf8e584fbb8634ca3aa88852bc75b470e9a6 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Thu, 28 May 2020 17:10:03 -0400 Subject: taxi: Implement taxicab distance --- src/lib.rs | 1 + src/taxi.rs | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 117 insertions(+) create mode 100644 src/taxi.rs (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs index 2b3c8fe..8cce2d8 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -95,6 +95,7 @@ pub mod distance; pub mod euclid; pub mod exhaustive; pub mod kd; +pub mod taxi; pub mod vp; mod util; diff --git a/src/taxi.rs b/src/taxi.rs new file mode 100644 index 0000000..be74fd3 --- /dev/null +++ b/src/taxi.rs @@ -0,0 +1,116 @@ +//! Taxicab (Manhattan) distance. + +use crate::coords::{Coordinates, CoordinateMetric, CoordinateProximity}; +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 metric]: https://en.wikipedia.org/wiki/Taxicab_geometry +#[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. +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); + } +} -- cgit v1.2.3