b_k_tree/
lib.rs

1impl<M:?Sized+DiscreteMetric<U,V>,U:?Sized,V:?Sized> DiscreteMetric<U,V> for &M{
2	fn distance(&self,u:&U,v:&V)->usize{(**self).distance(u,v)}
3}
4impl<M:?Sized+DiscreteMetric<U,V>,U:?Sized,V:?Sized> DiscreteMetric<U,V> for &mut M{
5	fn distance(&self,u:&U,v:&V)->usize{(**self).distance(u,v)}
6}
7#[cfg(test)]
8mod tests{
9	#[test]
10	fn ceil_l2_set_radius_2() {
11		// Points in the plane: L2 distances are ceil(sqrt(dx²+dy²))
12		let mut tree = BKTreeSet::new(CeilL2::new());
13		tree.insert([0i32, 0]);
14		tree.insert([1, 1]);
15		tree.insert([2, 2]);
16
17		// From (0,0) with radius = 2, should get:
18		//  (0,0) at d=0
19		//  (1,1) at d=ceil(√2)=2
20		//  but NOT (2,2) at d=ceil(√8)=3
21		let mut found: Vec<([i32;2], usize)>=tree.close_iter([0, 0], 2).map(|(pt, d)| (*pt, d)).collect();
22		found.sort_unstable();
23		assert_eq!(found, vec![([0, 0], 0),  ([1, 1], 2)]);
24	}
25	#[test]
26	fn hamming_set_radius_3() {
27		// Byte‐string Hamming distance: count of differing positions
28		let mut tree = BKTreeSet::new(Hamming::new_for(StrRef));
29		tree.insert("karolin".to_string());
30		tree.insert("kathrin".to_string());
31		tree.insert("kerstin".to_string());
32
33		// Hamming("karolin","kathrin") = 3,
34		// Hamming("karolin","kerstin") = 3
35		// radius = 2 should only return self
36		let self_only: Vec<(String,usize)>=tree.close_iter("karolin".to_string(), 2).map(|(s, d)| (s.clone(), d)).collect();
37		assert_eq!(self_only, vec![("karolin".to_string(), 0)]);
38
39		// radius = 3 should also pick up both others
40		let mut radius3: Vec<(String, usize)>=tree.close_iter("karolin".to_string(),3).map(|(s, d)| (s.clone(), d)).collect();
41		radius3.sort_unstable();
42		assert_eq!(radius3, vec![("karolin".to_string(),0),("kathrin".to_string(),3),("kerstin".to_string(),3)]);
43	}
44	#[test]
45	fn levenshtein_set_various() {
46		// Levenshtein distance: insertions/deletions/substitutions
47		let mut tree = BKTreeSet::new(Levenshtein::new());
48		tree.insert("kitten".to_string());
49		tree.insert("sitting".to_string());
50		tree.insert("bitten".to_string());
51		tree.insert("mitten".to_string());
52
53		// Known distances:
54		//  kitten→bitten = 1  (k→b)
55		//  kitten→mitten = 1  (k→m)
56		//  kitten→sitting = 3 (kitten→sitten→sittin→sitting)
57		let mut results: Vec<(String, usize)>=tree.close_iter("kitten".to_string(), 1).map(|(s, d)| (s.clone(), d)).collect();
58		results.sort_unstable();
59		assert_eq!(results,vec![("bitten".to_string(), 1), ("kitten".to_string(), 0),("mitten".to_string(),1)]);
60
61		// radius = 3 should also include "sitting"
62		let mut radius3: Vec<(String, usize)>=tree.close_iter("kitten".to_string(), 3).map(|(s, d)| (s.clone(), d)).collect();
63		radius3.sort_unstable();
64		assert_eq!(radius3, vec![("bitten".to_string(), 1),("kitten".to_string(), 0), ("mitten".to_string(), 1),("sitting".to_string(), 3)]);
65	}
66	use crate::{
67		metrics::{CeilL2,Hamming,Levenshtein,StrRef},set::BKTreeSet
68	};
69}
70/// provides a map data structure implemented using a bk tree
71pub mod map;
72/// builtin discrete metrics for use with bk tree structures
73pub mod metrics;
74/// provides a set data structure implemented using a bk tree
75pub mod set;
76/// a discrete distance metric. It should obey the usual axioms of a metric space. An invalid metric will probably cause unexpected behaviors
77pub trait DiscreteMetric<U:?Sized,V:?Sized>{
78	/// computes the distance between two elements of the metric space
79	fn distance(&self,u:&U,v:&V)->usize;
80}
81pub use {map::BKTreeMap,set::BKTreeSet};
b_k_tree/lib.rs

b_k_tree/
lib.rs
