1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
#![warn(rust_2018_idioms)] #![warn(missing_docs)] //! # KNN //! //! `knn` provides for fast method of finding exact k nearest neighbours //! for higher dimensional data. Also supports custom distance function. mod heap; #[derive(Clone)] /// The core datastructure of the package. /// Stores the points and the distance function. pub struct PointCloud<'a, T> { // stores all points points: Vec<&'a T>, // return the distance given 2 ponints dist_fn: fn(&T, &T) -> f64, } impl<'a, T> PointCloud<'a, T> { /// Constructs a new `PointCloud<T>`. /// /// It accepts a function to compute distance between any 2 objects. /// /// # Examples /// ``` /// extern crate knn; /// use knn::PointCloud; /// let manhattan_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {(p[0] - q[0]).abs() + (p[1] - q[1]).abs()}; /// let pc = PointCloud::new(manhattan_dist); /// ``` pub fn new(dist_fn: fn(&T, &T) -> f64) -> Self { Self { points: Vec::new(), dist_fn: dist_fn, } } /// Adds a point to the PointCloud. /// /// It accepts a reference to an object. /// /// # Examples /// ``` /// extern crate knn; /// use knn::PointCloud; /// let dummy_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {0.0}; /// let mut pc = PointCloud::new(dummy_dist); /// let p = [1.89, 5.63]; /// pc.add_point(&p); /// ``` pub fn add_point(&mut self, p: &'a T) { self.points.push(p) } /// Gets the k nearest neighbours of an object. /// /// It accepts a reference to the object and how many neighbours to return. /// /// # Example /// ``` /// extern crate knn; /// use knn::PointCloud; /// let manhattan_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {(p[0] - q[0]).abs() + (p[1] - q[1]).abs()}; /// let mut pc = PointCloud::new(manhattan_dist); /// let points = vec![[1.0, 1.0], [2.0, 2.0], [3.0, 2.0]]; /// for p in &points { /// pc.add_point(&p); /// } /// let q = [0.5, 0.5]; /// pc.get_nearest_k(&q, 2); /// /// ``` pub fn get_nearest_k(&self, p: &T, k: usize) -> Vec<(f64, &T)> { let mut h = heap::Heap::new(k); for i in 0..self.points.len() { let d = (self.dist_fn)(self.points[i], p); h.insert(d, &self.points[i]); } let mut knn = Vec::new(); for i in h.get_elements() { knn.push((i.0, *i.1)); } knn } /// Get the len / number of objects in PointCloud /// Example: /// ``` /// extern crate knn; /// use knn::PointCloud; /// let manhattan_dist = |p: &[f64;2], q: &[f64;2]| -> f64 {(p[0] - q[0]).abs() + (p[1] - q[1]).abs()}; /// let mut pc = PointCloud::new(manhattan_dist); /// let points = vec![[1.0, 1.0], [2.0, 2.0], [3.0, 2.0]]; /// for p in &points { /// pc.add_point(&p); /// } /// pc.len(); /// ``` pub fn len(&self) -> usize { self.points.len() } }