//! [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(pub T); impl Hamming { /// 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(x: T, y: T) -> i32 { (x ^ y).count_ones() as i32 } /// The hamming distance function. impl Proximity for Hamming { type Distance = i32; fn distance(&self, other: &Self) -> Self::Distance { hamming_distance(self.0, other.0) } } impl Proximity for Hamming { type Distance = i32; fn distance(&self, other: &T) -> Self::Distance { hamming_distance(self.0, *other) } } impl Proximity> for T { type Distance = i32; fn distance(&self, other: &Hamming) -> Self::Distance { hamming_distance(*self, other.0) } } /// Hamming distance is a metric. impl Metric for Hamming {} impl Metric for Hamming {} impl Metric> 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); } }