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