From 73422e8221cd0334fb9fbf3f33059b9e531e1487 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Wed, 24 Jun 2020 09:15:21 -0400 Subject: hamming: Implement Hamming distance --- src/hamming.rs | 76 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 1 + 2 files changed, 77 insertions(+) create mode 100644 src/hamming.rs diff --git a/src/hamming.rs b/src/hamming.rs new file mode 100644 index 0000000..c223bac --- /dev/null +++ b/src/hamming.rs @@ -0,0 +1,76 @@ +//! 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]: https://en.wikipedia.org/wiki/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. +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); + } +} diff --git a/src/lib.rs b/src/lib.rs index 1ef5c29..0bbd835 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -95,6 +95,7 @@ pub mod coords; pub mod distance; pub mod euclid; pub mod exhaustive; +pub mod hamming; pub mod kd; pub mod taxi; pub mod vp; -- cgit v1.2.3