summaryrefslogtreecommitdiffstats
path: root/src/hamming.rs
blob: b3a7e78fc8c36aa4342ab5bde27f9e094f0f4f5a (plain)
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
//! [Hamming space](https://en.wikipedia.org/wiki/Hamming_space).

use crate::distance::{Metric, Proximity};

use num_traits::PrimInt;

/// A point in Hamming space.
///
/// This wrapper equips any integer with the [Hamming distance] metric.
///
/// [Hamming distance]: hamming_distance
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub struct Hamming<T>(pub T);

impl<T> Hamming<T> {
    /// Wrap a point.
    pub fn new(point: T) -> Self {
        Self(point)
    }

    /// Unwrap a point.
    pub fn into_inner(self) -> T {
        self.0
    }
}

/// Compute the [Hamming distance] between two integers.
///
/// ```math
/// \begin{aligned}
/// \mathrm{hamming\_distance}(x, y) &= |\{i \mid x_i \ne y_i\}| \\
/// &= \mathrm{popcount}(x \wedge y)
/// \end{aligned}
/// ```
///
/// [Hamming distance]: https://en.wikipedia.org/wiki/Hamming_distance
pub fn hamming_distance<T: PrimInt>(x: T, y: T) -> i32 {
    (x ^ y).count_ones() as i32
}

/// The hamming distance function.
impl<T: PrimInt> Proximity for Hamming<T> {
    type Distance = i32;

    fn distance(&self, other: &Self) -> Self::Distance {
        hamming_distance(self.0, other.0)
    }
}

impl<T: PrimInt> Proximity<T> for Hamming<T> {
    type Distance = i32;

    fn distance(&self, other: &T) -> Self::Distance {
        hamming_distance(self.0, *other)
    }
}

impl<T: PrimInt> Proximity<Hamming<T>> for T {
    type Distance = i32;

    fn distance(&self, other: &Hamming<T>) -> Self::Distance {
        hamming_distance(*self, other.0)
    }
}

/// Hamming distance is a metric.
impl<T: PrimInt> Metric for Hamming<T> {}

impl<T: PrimInt> Metric<T> for Hamming<T> {}

impl<T: PrimInt> Metric<Hamming<T>> for T {}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_distance() {
        assert_eq!(hamming_distance(0, 0xFFFFFFFFu32), 32);

        assert_eq!(Hamming(0xFFFFFFFFu32).distance(&Hamming(0xAAAAAAAAu32)), 16);
        assert_eq!(Hamming(0x55555555u32).distance(&0xAAAAAAAAu32), 32);
        assert_eq!(0xDEADBEEFu32.distance(&Hamming(0xACABACABu32)), 10);
    }
}