1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

//! [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<T>(pub T);

impl<T> Taxicab<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 Taxicab<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 [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<T, U>(x: T, y: U) -> T::Value
where
    T: Coordinates,
    U: Coordinates<Value = T::Value>,
{
    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<T: Coordinates> Proximity for Taxicab<T> {
    type Distance = T::Value;

    fn distance(&self, other: &Self) -> Self::Distance {
        taxicab_distance(self, other)
    }
}

impl<T: Coordinates> Proximity<T> for Taxicab<T> {
    type Distance = T::Value;

    fn distance(&self, other: &T) -> Self::Distance {
        taxicab_distance(self, other)
    }
}

impl<T: Coordinates> Proximity<Taxicab<T>> for T {
    type Distance = T::Value;

    fn distance(&self, other: &Taxicab<T>) -> Self::Distance {
        taxicab_distance(self, other)
    }
}

/// Taxicab distance is a metric.
impl<T: Coordinates> Metric for Taxicab<T> {}

impl<T: Coordinates> Metric<T> for Taxicab<T> {}

impl<T: Coordinates> Metric<Taxicab<T>> for T {}

impl<T: Coordinates> CoordinateProximity<T::Value> for Taxicab<T> {
    type Distance = T::Value;

    fn distance_to_coords(&self, coords: &[T::Value]) -> Self::Distance {
        taxicab_distance(self, coords)
    }
}

impl<T: Coordinates> CoordinateMetric<T::Value> for Taxicab<T> {}

#[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);
    }
}