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_close_iter(){
11		let mut tree=BKTreeSet::new(CeilL2::new());
12		tree.insert([0i32,0]);
13		tree.insert([1,1]);
14		tree.insert([2,2]);
15		let mut found:Vec<([i32;2],usize)>=tree.close_iter([0,0],2).map(|(pt,d)| (*pt,d)).collect();
16		found.sort_unstable();
17		assert_eq!(found,vec![([0,0],0),([1,1],2)]);
18	}
19	#[test]
20	fn ceil_l2_set_close_sorted(){
21		let mut tree=BKTreeSet::new(CeilL2::new());
22		tree.insert([0i32,0]);
23		tree.insert([1,1]);
24		tree.insert([2,2]);
25		let found:Vec<(&[i32;2],usize)>=tree.close_sorted(&[0,0],2);
26		assert_eq!(found,vec![(&[0,0],0),(&[1,1],2)]);
27	}
28	#[test]
29	fn hamming_set_close_iter(){
30		let mut tree = BKTreeSet::new(Hamming::new_for(StrRef));
31		tree.insert("karolin".to_string());
32		tree.insert("kathrin".to_string());
33		tree.insert("kerstin".to_string());
34		// hamming("karolin", "kathrin") = 3
35		// hamming("karolin", "kerstin") = 3
36		let karolin:Vec<(String,usize)>=tree.close_iter("karolin".to_string(),2).map(|(s,d)|(s.clone(),d)).collect();
37		assert_eq!(karolin,vec![("karolin".to_string(),0)]);
38		let mut radius3:Vec<(String,usize)>=tree.close_iter("karolin".to_string(),3).map(|(s,d)|(s.clone(),d)).collect();
39		radius3.sort_unstable();
40		assert_eq!(radius3,vec![("karolin".to_string(),0),("kathrin".to_string(),3),("kerstin".to_string(),3)]);
41	}
42	#[test]
43	fn hamming_set_close_sorted(){
44		let mut tree = BKTreeSet::new(Hamming::new_for(StrRef));
45		tree.insert("karolin".to_string());
46		tree.insert("kathrin".to_string());
47		tree.insert("kerstin".to_string());
48		// hamming("karolin", "kathrin") = 3
49		// hamming("karolin", "kerstin") = 3
50		// hamming("katolin", "kathrin") = 2
51		let karolin:Vec<(&String,usize)>=tree.close_sorted("karolin",2);
52		assert_eq!(karolin,vec![(&"karolin".to_string(),0)]);
53		let radius3:Vec<(&String,usize)>=tree.close_sorted("katolin",3);
54		assert_eq!(radius3,vec![(&"karolin".to_string(),1),(&"kathrin".to_string(),2)]);
55	}
56	#[test]
57	fn levenshtein_extend_retain(){
58		let mut tree=BKTreeMap::new(Levenshtein::new());
59		tree.extend([("bitten","bitten"),("calculate","mathematics"),("cat","pet"),("hello","greeting"),("hi","greeting"),("kat","name"),("kitten","kitten"),("linear","mathematics"),("mittens","mittens"),("sitting","sitting")]);
60		assert_eq!(tree[&"bitten"],"bitten");
61		assert_eq!(tree[&"calculate"],"mathematics");
62		assert_eq!(tree[&"cat"],"pet");
63		assert_eq!(tree[&"hello"],"greeting");
64		assert_eq!(tree[&"hi"],"greeting");
65		assert_eq!(tree[&"kat"],"name");
66		assert_eq!(tree[&"kitten"],"kitten");
67		assert_eq!(tree[&"linear"],"mathematics");
68		assert_eq!(tree[&"mittens"],"mittens");
69		assert_eq!(tree[&"sitting"],"sitting");
70		tree.retain(|k,v|if k==v{
71			false
72		}else{
73			*v=*k;
74			true
75		});
76		assert_eq!(tree[&"calculate"],"calculate");
77		assert_eq!(tree[&"cat"],"cat");
78		assert_eq!(tree[&"hello"],"hello");
79		assert_eq!(tree[&"hi"],"hi");
80		assert_eq!(tree[&"kat"],"kat");
81		assert_eq!(tree[&"linear"],"linear");
82		assert_eq!(tree.get(&"cal",1),Some((&"cat",1)));
83		assert_eq!(tree.get(&"calc",5),Some((&"cat",2)));
84		assert_eq!(tree.get(&"calculat",5),Some((&"calculate",1)));
85		assert_eq!(tree.get(&"hllo",2),Some((&"hello",1)));
86		assert_eq!(tree.get(&"i",3),Some((&"hi",1)));
87		assert_eq!(tree.get(&"line",3),Some((&"linear",2)));
88	}
89	#[test]
90	fn levenshtein_set_close_iter(){
91		let mut tree = BKTreeSet::new(Levenshtein::new());
92		tree.insert("kitten".to_string());
93		tree.insert("sitting".to_string());
94		tree.insert("bitten".to_string());
95		tree.insert("mitten".to_string());
96		// levenshtein("kitten", "bitten") = 1
97		// levenshtein("kitten", "mitten") = 1
98		// levenshtein("kitten", "sitting") = 3
99		let mut results:Vec<(String,usize)>=tree.close_iter("kitten".to_string(),1).map(|(s,d)|(s.clone(),d)).collect();
100		results.sort_unstable();
101		assert_eq!(results,vec![("bitten".to_string(),1),("kitten".to_string(),0),("mitten".to_string(),1)]);
102		let mut radius3:Vec<(String,usize)>=tree.close_iter("kitten".to_string(),3).map(|(s,d)| (s.clone(),d)).collect();
103		radius3.sort_unstable();
104		assert_eq!(radius3,vec![("bitten".to_string(),1),("kitten".to_string(),0),("mitten".to_string(),1),("sitting".to_string(),3)]);
105	}
106	#[test]
107	fn levenshtein_set_close_sorted(){
108		let mut tree = BKTreeSet::new(Levenshtein::new());
109		tree.insert("kitten".to_string());
110		tree.insert("sitting".to_string());
111		tree.insert("bitten".to_string());
112		tree.insert("mittens".to_string());
113		// levenshtein("kitten", "bitten") = 1
114		// levenshtein("kitten", "mittens") = 2
115		// levenshtein("kitten", "sitting") = 3
116		let results:Vec<(&String,usize)>=tree.close_sorted("kitten",1);
117		assert_eq!(results,vec![(&"kitten".to_string(),0),(&"bitten".to_string(),1)]);
118		let results:Vec<(&String,usize)>=tree.close_sorted("kitten",3);
119		assert_eq!(results,vec![(&"kitten".to_string(),0),(&"bitten".to_string(),1),(&"mittens".to_string(),2),(&"sitting".to_string(),3)]);
120	}
121	use crate::metrics::{CeilL2,Hamming,Levenshtein,StrRef};
122	use super::*;
123}
124/// provides a map data structure implemented using a bk tree
125pub mod map;
126/// builtin discrete metrics for use with bk tree structures
127pub mod metrics;
128/// provides a set data structure implemented using a bk tree
129pub mod set;
130/// a discrete distance metric. It should obey the usual axioms of a metric space. An invalid metric will probably cause unexpected behaviors
131pub trait DiscreteMetric<U:?Sized,V:?Sized>{
132	/// computes the distance between two elements of the metric space
133	fn distance(&self,u:&U,v:&V)->usize;
134}
135pub use {map::BKTreeMap,set::BKTreeSet};
b_k_tree/lib.rs

b_k_tree/
lib.rs
