From 911ec5008fd78d726cd62768069fa5dbfb4212c0 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Thu, 28 May 2020 14:39:08 -0400 Subject: distance: Implement abstract distances, proximities, metrics --- src/distance.rs | 103 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 4 +++ 2 files changed, 107 insertions(+) create mode 100644 src/distance.rs (limited to 'src') diff --git a/src/distance.rs b/src/distance.rs new file mode 100644 index 0000000..9ff9fd4 --- /dev/null +++ b/src/distance.rs @@ -0,0 +1,103 @@ +//! Abstract notions of distance. + +use num_traits::{Num, NumAssign, Signed}; + +/// A number type suitable for distance values. +/// +/// This trait is automatically implemented for all types that support the required operations. +pub trait Value: Copy + Num + NumAssign + Signed + PartialOrd {} + +/// Blanket [Value] implementation. +impl Value for T {} + +/// A distance between two points. +/// +/// An implementation may be an actual numerical distance, or an [order embedding] of the true +/// distance. This allows for optimizations whenever distances can be compared more efficiently +/// than their exact values can be computed, as is the case for [Euclidean distance]. Implementors +/// must satisfy, for all distances `x` and `y`: +/// +/// * `x < y` iff `x.value() < y.value()` +/// * `x.value() < y` iff `x.value() < y.value()` +/// * `x < y.value()` iff `x.value() < y.value()` +/// +/// [order embedding]: https://en.wikipedia.org/wiki/Order_embedding +/// [Euclidean distance]: crate::euclid::EuclideanDistance +pub trait Distance +where + Self: Copy, + Self: Into<::Value>, + Self: PartialOrd<::Value>, + ::Value: PartialOrd, + Self: PartialOrd, +{ + /// The type of actual numerical distances. + type Value: Value; + + /// Get the real numerical value of this distance. + fn value(self) -> Self::Value { + self.into() + } +} + +/// Any numerical distance value can be a [Distance]. +impl Distance for T { + type Value = T; +} + +/// A space with some notion of distance between points. +/// +/// Distances in this space don't need to obey any particular rules like symmetry or the [triangle +/// inequality]. However, spaces that satisfy those rules, at least approximately, often allow for +/// more accurate and efficient searches. +/// +/// Type parameters: +/// +/// * `T`: The type to compare against. +/// +/// [triangle inequality]: https://en.wikipedia.org/wiki/Triangle_inequality +pub trait Proximity { + /// The type that represents distances. + type Distance: Distance; + + /// Calculate the distance between this point and another one. + fn distance(&self, other: &T) -> Self::Distance; +} + +// See https://github.com/rust-lang/rust/issues/38078 +/// Shorthand for `K::Distance::Value`. +pub type DistanceValue = <>::Distance as Distance>::Value; + +/// Blanket [Proximity] implementation for references. +impl<'k, 'v, K: Proximity, V> Proximity<&'v V> for &'k K { + type Distance = K::Distance; + + fn distance(&self, other: &&'v V) -> Self::Distance { + (*self).distance(*other) + } +} + +/// Marker trait for [metric spaces]. +/// +/// A metric must be symmetric and obey the [triangle inequality]. More precisely, let `x`, `y`, +/// and `z` be any elements of a metric space, and let `d(x, y) = x.distance(y).value()`. Then the +/// following rules must hold: +/// +/// * `d(x, x) == 0`, +/// * `d(x, y) == d(y, z)` (symmetry), and +/// * `d(x, z) <= d(x, y) + d(y, z)` (triangle inequality). +/// +/// Those conditions also imply the following condition: +/// +/// * `d(x, y) >= 0` (non-negativity) +/// +/// Because we do not prohibit `d(x, y) == 0` for distinct `x` and `y`, these spaces are more +/// properly known as [pseudometric spaces]. This distinction is usually unimportant. +/// +/// [metric spaces]: https://en.wikipedia.org/wiki/Metric_space +/// [triangle inequality]: https://en.wikipedia.org/wiki/Triangle_inequality +/// [pseudometric spaces]: https://en.wikipedia.org/wiki/Pseudometric_space +pub trait Metric: Proximity {} + +/// Blanket [Metric] implementation for references. +impl<'k, 'v, K: Metric, V> Metric<&'v V> for &'k K {} diff --git a/src/lib.rs b/src/lib.rs index 63d8a0e..8b0c32b 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -1,3 +1,7 @@ //! As Close As Possible — [nearest neighbor search] in Rust. //! //! [nearest neighbor search]: https://en.wikipedia.org/wiki/Nearest_neighbor_search + +pub mod distance; + +pub use distance::{Distance, Metric, Proximity}; -- cgit v1.2.3