summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2020-06-24 09:15:21 -0400
committerTavian Barnes <tavianator@tavianator.com>2020-06-24 10:03:44 -0400
commit73422e8221cd0334fb9fbf3f33059b9e531e1487 (patch)
tree4b8e815191a77840f1dc14e522bf384ed13fd808
parent4876b9799c6dc62ab34500559d4584f4671ddb0f (diff)
downloadacap-73422e8221cd0334fb9fbf3f33059b9e531e1487.tar.xz
hamming: Implement Hamming distance0.1.0
-rw-r--r--src/hamming.rs76
-rw-r--r--src/lib.rs1
2 files changed, 77 insertions, 0 deletions
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<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.
+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);
+ }
+}
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;