From 0bc4df6a1ab14ecf55d68cc86134d14b26eca6e5 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Thu, 28 May 2020 14:47:10 -0400 Subject: exhaustive: Implement an exhaustive search index --- Cargo.toml | 1 + src/exhaustive.rs | 89 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/lib.rs | 32 ++++++++++++++++++++ 3 files changed, 122 insertions(+) create mode 100644 src/exhaustive.rs diff --git a/Cargo.toml b/Cargo.toml index 724f6ea..5971ae6 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -11,3 +11,4 @@ categories = ["algorithms", "data-structures"] [dependencies] num-traits = "0.2.11" +rand = "0.7.3" diff --git a/src/exhaustive.rs b/src/exhaustive.rs new file mode 100644 index 0000000..909edda --- /dev/null +++ b/src/exhaustive.rs @@ -0,0 +1,89 @@ +//! Exhaustive nearest neighbor search. + +use crate::distance::Proximity; +use crate::{ExactNeighbors, NearestNeighbors, Neighborhood}; + +use std::iter::FromIterator; + +/// A [NearestNeighbors] implementation that does exhaustive search. +#[derive(Debug)] +pub struct ExhaustiveSearch(Vec); + +impl ExhaustiveSearch { + /// Create an empty ExhaustiveSearch index. + pub fn new() -> Self { + Self(Vec::new()) + } + + /// Add a new item to the index. + pub fn push(&mut self, item: T) { + self.0.push(item); + } + + /// Get the size of this index. + pub fn len(&self) -> usize { + self.0.len() + } + + /// Check if this index is empty. + pub fn is_empty(&self) -> bool { + self.0.is_empty() + } +} + +impl Default for ExhaustiveSearch { + fn default() -> Self { + Self::new() + } +} + +impl FromIterator for ExhaustiveSearch { + fn from_iter>(items: I) -> Self { + Self(items.into_iter().collect()) + } +} + +impl IntoIterator for ExhaustiveSearch { + type Item = T; + type IntoIter = std::vec::IntoIter; + + fn into_iter(self) -> Self::IntoIter { + self.0.into_iter() + } +} + +impl Extend for ExhaustiveSearch { + fn extend>(&mut self, iter: I) { + for value in iter { + self.push(value); + } + } +} + +impl, V> NearestNeighbors for ExhaustiveSearch { + fn search<'k, 'v, N>(&'v self, mut neighborhood: N) -> N + where + K: 'k, + V: 'v, + N: Neighborhood<&'k K, &'v V>, + { + for e in &self.0 { + neighborhood.consider(e); + } + neighborhood + } +} + +impl, V> ExactNeighbors for ExhaustiveSearch {} + +#[cfg(test)] +pub mod tests { + use super::*; + + use crate::tests::test_nearest_neighbors; + + #[test] + fn test_exhaustive_index() { + test_nearest_neighbors(ExhaustiveSearch::from_iter); + } +} diff --git a/src/lib.rs b/src/lib.rs index b1639d7..2f6504a 100644 --- a/src/lib.rs +++ b/src/lib.rs @@ -5,6 +5,7 @@ pub mod coords; pub mod distance; pub mod euclid; +pub mod exhaustive; pub use coords::Coordinates; pub use distance::{Distance, Metric, Proximity}; @@ -303,6 +304,12 @@ pub trait ExactNeighbors, V = K>: NearestNeighbors {} pub mod tests { use super::*; + use crate::exhaustive::ExhaustiveSearch; + + use rand::prelude::*; + + use std::iter::FromIterator; + type Point = Euclidean<[f32; 3]>; /// Test a [NearestNeighbors] implementation. @@ -313,6 +320,7 @@ pub mod tests { { test_empty(&from_iter); test_pythagorean(&from_iter); + test_random_points(&from_iter); } fn test_empty(from_iter: &F) @@ -385,4 +393,28 @@ pub mod tests { ] ); } + + fn test_random_points(from_iter: &F) + where + T: NearestNeighbors, + F: Fn(Vec) -> T, + { + let mut points = Vec::new(); + for _ in 0..256 { + points.push(Euclidean([random(), random(), random()])); + } + + let index = from_iter(points.clone()); + let eindex = ExhaustiveSearch::from_iter(points.clone()); + + let target = Euclidean([random(), random(), random()]); + + assert_eq!( + index.k_nearest(&target, 3), + eindex.k_nearest(&target, 3), + "target: {:?}, points: {:#?}", + target, + points, + ); + } } -- cgit v1.2.3