b_k_tree/
map.rs

1impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseKeyIter<'a,K,M,Q,V>{
2	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(k,_v,d)|(k,d))}
3	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
4	type Item=(&'a K,usize);
5}
6impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseMapIter<'a,K,M,Q,V>{
7	fn next(&mut self)->Option<Self::Item>{
8		let (maxdistance,metric)=(self.maxdistance,self.metric);
9		let key=&self.key;
10		let nodes=&mut self.nodes;
11
12		while let Some(n)=nodes.pop(){
13			let (k,v,next)=(&n.key,&n.value,&n.connections);
14			let distance=metric.distance(k,key);
15			self.remaining-=1;
16
17			nodes.extend(next.range(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).map(|(_r,n)|n));
18			if distance<=maxdistance{return Some((k,v,distance))}
19		}
20		None
21	}
22	fn size_hint(&self)->(usize,Option<usize>){(0,Some(self.remaining))}
23	type Item=(&'a K,&'a V,usize);
24}
25impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseValIter<'a,K,M,Q,V>{
26	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v,d)|(v,d))}
27	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
28	type Item=(&'a V,usize);
29}
30impl<'a,K,M,Q:Clone,V> Clone for CloseKeyIter<'a,K,M,Q,V>{
31	fn clone(&self)->Self{
32		Self{inner:self.inner.clone()}
33	}
34	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
35}
36impl<'a,K,M,Q:Clone,V> Clone for CloseMapIter<'a,K,M,Q,V>{
37	fn clone(&self)->Self{
38		Self{key:self.key.clone(),maxdistance:self.maxdistance,metric:self.metric,nodes:self.nodes.clone(),remaining:self.remaining}
39	}
40	fn clone_from(&mut self,other:&Self){
41		(self.key.clone_from(&other.key),self.nodes.clone_from(&other.nodes));
42		(self.maxdistance,self.metric,self.remaining)=(other.maxdistance,other.metric,other.remaining);
43	}
44}
45impl<'a,K,M,Q:Clone,V> Clone for CloseValIter<'a,K,M,Q,V>{
46	fn clone(&self)->Self{
47		Self{inner:self.inner.clone()}
48	}
49	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
50}
51impl<'a,K,M,V> IntoIterator for &'a BKTreeMap<K,M,V>{
52	fn into_iter(self)->Self::IntoIter{self.iter()}
53	type IntoIter=MapIter<'a,K,V>;
54	type Item=(&'a K,&'a V);
55}
56impl<'a,K,M,V> IntoIterator for &'a mut BKTreeMap<K,M,V>{
57	fn into_iter(self)->Self::IntoIter{self.iter_mut()}
58	type IntoIter=MapIterMut<'a,K,V>;
59	type Item=(&'a K,&'a mut V);
60}
61impl<'a,K,V> Clone for KeyIter<'a,K,V>{
62	fn clone(&self)->Self{
63		Self{inner:self.inner.clone()}
64	}
65	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
66}
67impl<'a,K,V> Clone for MapIter<'a,K,V>{
68	fn clone(&self)->Self{
69		Self{nodes:self.nodes.clone(),remaining:self.remaining}
70	}
71	fn clone_from(&mut self,other:&Self){
72		self.nodes.clone_from(&other.nodes);
73		self.remaining=other.remaining;
74	}
75}
76impl<'a,K,V> Clone for ValIter<'a,K,V>{
77	fn clone(&self)->Self{
78		Self{inner:self.inner.clone()}
79	}
80	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
81}
82impl<'a,K,V> ExactSizeIterator for KeyIter<'a,K,V>{
83	fn len(&self)->usize{self.inner.len()}
84}
85impl<'a,K,V> ExactSizeIterator for MapIter<'a,K,V>{
86	fn len(&self)->usize{self.remaining}
87}
88impl<'a,K,V> ExactSizeIterator for MapIterMut<'a,K,V>{
89	fn len(&self)->usize{self.remaining}
90}
91impl<'a,K,V> ExactSizeIterator for ValIter<'a,K,V>{
92	fn len(&self)->usize{self.inner.len()}
93}
94impl<'a,K,V> Iterator for KeyIter<'a,K,V>{
95	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(k,_v)|k)}
96	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
97	type Item=&'a K;
98}
99impl<'a,K,V> Iterator for MapIter<'a,K,V>{
100	fn next(&mut self)->Option<Self::Item>{
101		let nodes=&mut self.nodes;
102		let node=nodes.pop()?;
103		let (k,v,next)=(&node.key,&node.value,&node.connections);
104		self.remaining-=1;
105
106		nodes.extend(next.values());
107		Some((k,v))
108	}
109	fn size_hint(&self)->(usize,Option<usize>){(self.remaining,Some(self.remaining))}
110	type Item=(&'a K,&'a V);
111}
112impl<'a,K,V> Iterator for MapIterMut<'a,K,V>{
113	fn next(&mut self)->Option<Self::Item>{
114		let nodes=&mut self.nodes;
115		let node=nodes.pop()?;
116		let (k,v,next)=(&node.key,&mut node.value,&mut node.connections);
117		self.remaining-=1;
118
119		nodes.extend(next.values_mut());
120		Some((k,v))
121	}
122	fn size_hint(&self)->(usize,Option<usize>){(self.remaining,Some(self.remaining))}
123	type Item=(&'a K,&'a mut V);
124}
125impl<'a,K,V> Iterator for ValIter<'a,K,V>{
126	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v)|v)}
127	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
128	type Item=&'a V;
129}
130impl<'a,K,V> Iterator for ValIterMut<'a,K,V>{
131	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v)|v)}
132	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
133	type Item=&'a mut V;
134}
135impl<K:Clone,V:Clone> Clone for IntoKeysIter<K,V>{
136	fn clone(&self)->Self{
137		Self{inner:self.inner.clone()}
138	}
139	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
140}
141impl<K:Clone,V:Clone> Clone for IntoValsIter<K,V>{
142	fn clone(&self)->Self{
143		Self{inner:self.inner.clone()}
144	}
145	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
146}
147impl<K:Clone,V:Clone> Clone for MapIntoIter<K,V>{
148	fn clone(&self)->Self{
149		let nodes=&self.nodes;
150		let remaining=self.remaining;
151
152		let nodes=MapIter::<K,V>{nodes:nodes.iter().collect(),remaining}.map(|(k,v)|Node::new(k.clone(),v.clone())).collect();
153		Self{nodes,remaining}
154	}
155	fn clone_from(&mut self,other:&Self){
156		let remaining=other.remaining;
157		let nodes=MapIter::<K,V>{nodes:other.nodes.iter().collect(),remaining}.map(|(k,v)|Node::new(k.clone(),v.clone()));
158
159		self.nodes.clear();
160		self.nodes.extend(nodes);
161		self.remaining=remaining;
162	}
163}
164impl<K,M:Default+DiscreteMetric<K,K>,V> FromIterator<(K,V)> for BKTreeMap<K,M,V>{
165	fn from_iter<I:IntoIterator<Item=(K,V)>>(iter:I)->Self{
166		let mut map=Self::default();
167		iter.into_iter().map(|(k,v)|map.insert(k,v)).for_each(|_|());
168		map
169	}
170}
171impl<K,M:Default,V> Default for BKTreeMap<K,M,V>{
172	fn default()->Self{Self::new(M::default())}
173}
174impl<K,M:DiscreteMetric<K,K>,V> Extend<(K,V)> for BKTreeMap<K,M,V>{
175	fn extend<I:IntoIterator<Item=(K,V)>>(&mut self,iter:I){iter.into_iter().map(|(k,v)|self.insert(k,v)).for_each(|_|())}
176}
177impl<K,M:DiscreteMetric<K,Q>,Q,V> Index<&Q> for BKTreeMap<K,M,V>{
178	fn index(&self,index:&Q)->&Self::Output{self.get(index,0).map(|(v,_d)|v).expect("mapping must exist to use index")}
179	type Output=V;
180}
181impl<K,M:DiscreteMetric<K,Q>,Q,V> IndexMut<&Q> for BKTreeMap<K,M,V>{
182	fn index_mut(&mut self,index:&Q)->&mut Self::Output{self.get_mut(index,0).map(|(v,_d)|v).expect("mapping must exist to use index")}
183}
184impl<K,M,V> AsMut<Self> for BKTreeMap<K,M,V>{
185	fn as_mut(&mut self)->&mut Self{self}
186}
187impl<K,M,V> AsRef<Self> for BKTreeMap<K,M,V>{
188	fn as_ref(&self)->&Self{self}
189}
190impl<K,M,V> BKTreeMap<K,M,V>{//TODO other sterotypical map operations
191	/// moves all elements from other into self, leaving other empty. If a key from other is already present in self, the respective value from self will be overwritten with the respective value from other
192	pub fn append<M2>(&mut self,other:&mut BKTreeMap<K,M2,V>) where M:DiscreteMetric<K,K>{
193		fn explore<K,M:DiscreteMetric<K,K>,V>(node:Node<K,V>,tree:&mut BKTreeMap<K,M,V>){
194			let (k,v,next)=(node.key,node.value,node.connections);
195			tree.insert(k,v);
196			next.into_iter().for_each(|(_d,n)|explore(n,tree));
197		}
198
199		if let Some(n)=other.root.take(){explore(n,self)}
200	}
201	/// clears the map, removing all elements
202	pub fn clear(&mut self){
203		self.length=0;
204		self.root=None;
205	}
206	/// gets the key value pairs whose distance is at most max distance from key
207	pub fn close_iter<Q>(&self,key:Q,maxdistance:usize)->CloseMapIter<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{//TODO close iter mut
208		CloseMapIter{key,maxdistance,metric:&self.metric,nodes:self.root.as_ref().into_iter().collect(),remaining:self.length}
209	}
210	/// gets the keys whose distance is at most max distance from key
211	pub fn close_keys<Q>(&self,key:Q,maxdistance:usize)->CloseKeyIter<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{
212		CloseKeyIter{inner:self.close_iter(key,maxdistance)}
213	}
214	/// gets the values whose keys are at most max distance from key
215	pub fn close_values<Q>(&self,key:Q,maxdistance:usize)->CloseValIter<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{
216		CloseValIter{inner:self.close_iter(key,maxdistance)}
217	}
218	/// returns the key value pairs at most maxdistance from the key, sorted by distance
219	pub fn close_sorted<'a,Q:?Sized>(&self,key:&Q,maxdistance:usize)->Vec<(&K,&V,usize)> where M:DiscreteMetric<K,Q>{
220		fn explore<'a,K,M:DiscreteMetric<K,Q>,Q:?Sized,V>(key:&Q,maxdistance:usize,metric:&M,node:&'a Node<K,V>,results:&mut Vec<(&'a K,&'a V,usize)>){
221			let distance=metric.distance(&node.key,key);
222
223			if distance<=maxdistance{results.push((&node.key,&node.value,distance))}
224			node.connections.range(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).for_each(|(_d,n)|explore(key,maxdistance,metric,n,results));
225		}
226		let metric=&self.metric;
227		let root=if let Some(r)=&self.root{r}else{return Vec::new()};
228		let mut results=Vec::with_capacity(10);
229
230		explore(key,maxdistance,metric,root,&mut results);
231		results.sort_unstable_by_key(|(_k,_v,d)|*d);
232		results
233	}
234	/// returns the key value pairs at most maxdistance from the key, sorted by distance
235	pub fn close_sorted_mut<'a,Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Vec<(&K,&mut V,usize)> where M:DiscreteMetric<K,Q>{
236		fn explore<'a,K,M:DiscreteMetric<K,Q>,Q:?Sized,V>(key:&Q,maxdistance:usize,metric:&M,node:&'a mut Node<K,V>,results:&mut Vec<(&'a K,&'a mut V,usize)>){
237			let distance=metric.distance(&node.key,key);
238
239			if distance<=maxdistance{results.push((&node.key,&mut node.value,distance))}
240			node.connections.range_mut(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).for_each(|(_d,n)|explore(key,maxdistance,metric,n,results));
241		}
242		let metric=&self.metric;
243		let root=if let Some(r)=&mut self.root{r}else{return Vec::new()};
244		let mut results=Vec::with_capacity(10);
245
246		explore(key,maxdistance,metric,root,&mut results);
247		results.sort_unstable_by_key(|(_k,_v,d)|*d);
248		results
249	}
250	/// tests if a key at most maxdistance from the given key is in the map
251	pub fn contains_key<Q:?Sized>(&self,key:&Q,maxdistance:usize)->bool where M:DiscreteMetric<K,Q>{self.get_key_value(key,maxdistance).is_some()}
252	/// gets the value whose key is closest to the given key, or None if the map contains no key at most max distance from the given key. If there are multiple closest keys, exactly which is returned is unspecified
253	pub fn get<Q:?Sized>(&self,key:&Q,maxdistance:usize)->Option<(&V,usize)> where M:DiscreteMetric<K,Q>{self.get_key_value(key,maxdistance).map(|(_k,v,d)|(v,d))}
254	/// gets the key value pair and distance whose key is closest to the given key, or None if the map contains no key at most max distance from the given key. If there are multiple closest keys, exactly which is returned is unspecified
255	pub fn get_key_value<Q:?Sized>(&self,key:&Q,maxdistance:usize)->Option<(&K,&V,usize)> where M:DiscreteMetric<K,Q>{
256		fn explore<'a,K,M:DiscreteMetric<K,Q>,Q:?Sized,V>(key:&Q,maxdistance:usize,metric:&M,node:&'a Node<K,V>)->Option<(&'a K,&'a V,usize)>{
257			let distance=metric.distance(&node.key,key);
258
259			if distance==0{return Some((&node.key,&node.value,0))}
260			let includecurrent=distance<=maxdistance;
261			let nextnodes=node.connections.range(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).filter_map(|(_d,n)|explore(key,maxdistance,metric,n));
262			nextnodes.chain(includecurrent.then_some((&node.key,&node.value,distance))).min_by_key(|(_k,_v,d)|*d)
263		}
264		let metric=&self.metric;
265		let root=if let Some(r)=&self.root{r}else{return None};
266
267		explore(key,maxdistance,metric,root)
268	}
269	/// gets the value whose key is closest to the given key, or None if the map contains no key at most max distance from the given key. If there are multiple closest keys, exactly which is returned is unspecified
270	pub fn get_mut<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Option<(&mut V,usize)> where M:DiscreteMetric<K,Q>{
271		fn explore<'a,K,M:DiscreteMetric<K,Q>,Q:?Sized,V>(key:&Q,maxdistance:usize,metric:&M,node:&'a mut Node<K,V>)->Option<(&'a mut V,usize)>{
272			let distance=metric.distance(&node.key,key);
273
274			if distance==0{return Some((&mut node.value,0))}
275			let includecurrent=distance<=maxdistance;
276			let nextnodes=node.connections.range_mut(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).filter_map(|(_d,n)|explore(key,maxdistance,metric,n));
277			nextnodes.chain(includecurrent.then_some((&mut node.value,distance))).min_by_key(|(_v,d)|*d)
278		}
279		let metric=&self.metric;
280		let root=if let Some(r)=&mut self.root{r}else{return None};
281
282		explore(key,maxdistance,metric,root)
283	}
284	/// inserts a key-value pair into the map, returning the previous value at that key, or None if there was no previous value. Keys are considered equal if the the distance between them is 0. If the old value is returned the key is not updated.
285	pub fn insert(&mut self,key:K,value:V)->Option<V> where M:DiscreteMetric<K,K>{
286		let metric=&self.metric;
287		let root=if let Some(n)=self.root.as_mut(){
288			n
289		}else{
290			self.length+=1;
291			self.root=Some(Node::new(key,value));
292			return None;
293		};
294
295		if let Some(v)=root.insert(key,metric,value){return Some(v)}
296		self.length+=1;
297		None
298	}
299	/// makes an iterator over the keys
300	pub fn into_keys(self)->IntoKeysIter<K,V>{
301		IntoKeysIter{inner:self.into_iter()}
302	}
303	/// makes an iterator over the values
304	pub fn into_values(self)->IntoValsIter<K,V>{
305		IntoValsIter{inner:self.into_iter()}
306	}
307	/// returns true if the map contains no entries
308	pub fn is_empty(&self)->bool{self.length==0}
309	/// makes an iterator over the mappings
310	pub fn iter(&self)->MapIter<'_,K,V>{
311		MapIter{nodes:self.root.as_ref().into_iter().collect(),remaining:self.length}
312	}
313	/// makes an iterator over the mappings
314	pub fn iter_mut(&mut self)->MapIterMut<'_,K,V>{
315		MapIterMut{nodes:self.root.as_mut().into_iter().collect(),remaining:self.length}
316	}
317	/// makes an iterator over the keys
318	pub fn keys(&self)->KeyIter<'_,K,V>{
319		KeyIter{inner:self.iter()}
320	}
321	/// references the metric. avoid modifying the metric in a way that changes the distances because that will most likely cause unspecified incorrect behavior
322	pub fn metric(&self)->&M{&self.metric}
323	/// returns the number of entries in the map
324	pub fn len(&self)->usize{self.length}
325	/// creates a new tree
326	pub fn new(metric:M)->Self{
327		Self{length:0,metric,root:None}
328	}
329	/// removes the closest mapping whose key at most maxdistance from the given key. If there are multiple closest keys, exactly which is removed is unspecified. This particular tree type doesn't allow super efficient removal, so try to avoid using too much.
330	pub fn remove<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Option<(V,usize)> where M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>{self.remove_entry(key,maxdistance).map(|(_k,v,d)|(v,d))}
331	/// removes the closest mapping whose key at most maxdistance from the given key. If there are multiple closest keys, exactly which is removed is unspecified. This particular tree type doesn't allow super efficient removal, so try to avoid using too much.
332	pub fn remove_entry<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Option<(K,V,usize)> where M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>{
333		fn restore_nodes<K,M:DiscreteMetric<K,K>,V>(branch:&mut Node<K,V>,metric:&M,nodes:BTreeMap<usize,Node<K,V>>){
334			nodes.into_iter().for_each(|(_d,n)|{
335				branch.insert(n.key,metric,n.value);
336				restore_nodes(branch,metric,n.connections);
337			})
338		}
339		let metric=&self.metric;
340		let mut path=Vec::with_capacity(10);
341		let mut branch=if let Some(r)=&mut self.root{r}else{return None};
342		let nodedistance=branch.get_path(key,maxdistance,metric,&mut path);
343		if nodedistance>maxdistance{return None}
344		let mut path=path.into_iter();
345		let lastindex=path.next_back();
346		for i in path{branch=branch.connections.get_mut(&i).unwrap()}
347		self.length-=1;
348		if let Some(i)=lastindex{
349			let node=branch.connections.remove(&i).unwrap();
350			restore_nodes(branch,metric,node.connections);
351			return Some((node.key,node.value,nodedistance))
352		}
353		let mut oldroot=self.root.take().unwrap();
354		if let Some((_d,mut newroot))=oldroot.connections.pop_first(){
355			restore_nodes(&mut newroot,metric,oldroot.connections);
356			self.root=Some(newroot);
357		}
358		Some((oldroot.key,oldroot.value,nodedistance))
359	}
360	/// removes all the mappings for which f returns false
361	pub fn retain<F:FnMut(&K,&mut V)->bool>(&mut self,mut f:F) where M:DiscreteMetric<K,K>{
362		fn explore<F:FnMut(&K,&mut V)->bool,K,M:DiscreteMetric<K,K>,V>(f:&mut F,node:Node<K,V>,tree:&mut BKTreeMap<K,M,V>){
363			let (connections,key)=(node.connections,node.key);
364			let mut value=node.value;
365
366			if f(&key,&mut value){
367				tree.insert(key,value);
368			}
369			for n in connections.into_values(){explore(f,n,tree)}
370		}
371		let root=if let Some(r)=self.root.take(){r}else{return};
372		self.length=0;
373		explore(&mut f,root,self);
374	}
375	/// makes an iterator over the values
376	pub fn values(&self)->ValIter<'_,K,V>{
377		ValIter{inner:self.iter()}
378	}
379	/// makes an iterator over the values
380	pub fn values_mut(&mut self)->ValIterMut<'_,K,V>{
381		ValIterMut{inner:self.iter_mut()}
382	}
383}
384impl<K,M,V> IntoIterator for BKTreeMap<K,M,V>{
385	fn into_iter(self)->Self::IntoIter{
386		MapIntoIter{nodes:self.root.into_iter().collect(),remaining:self.length}
387	}
388	type IntoIter=MapIntoIter<K,V>;
389	type Item=(K,V);
390}
391impl<K,V> ExactSizeIterator for IntoKeysIter<K,V>{
392	fn len(&self)->usize{self.inner.len()}
393}
394impl<K,V> ExactSizeIterator for IntoValsIter<K,V>{
395	fn len(&self)->usize{self.inner.len()}
396}
397impl<K,V> ExactSizeIterator for MapIntoIter<K,V>{
398	fn len(&self)->usize{self.remaining}
399}
400impl<K,V> Iterator for IntoKeysIter<K,V>{
401	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(k,_v)|k)}
402	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
403	type Item=K;
404}
405impl<K,V> Iterator for IntoValsIter<K,V>{
406	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v)|v)}
407	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
408	type Item=V;
409}
410impl<K,V> Iterator for MapIntoIter<K,V>{
411	fn next(&mut self)->Option<Self::Item>{
412		let nodes=&mut self.nodes;
413		let node=nodes.pop()?;
414		let (k,v,next)=(node.key,node.value,node.connections);
415		self.remaining-=1;
416
417		nodes.extend(next.into_values());
418		Some((k,v))
419	}
420	fn size_hint(&self)->(usize,Option<usize>){(self.remaining,Some(self.remaining))}
421	type Item=(K,V);
422}
423impl<K,V> Node<K,V>{
424	/// gets index path to a node, returning the distance. Returns greater than max distance if there is no node within maxdistance
425	fn get_path<M:DiscreteMetric<K,Q>,Q:?Sized>(&self,key:&Q,maxdistance:usize,metric:&M,v:&mut Vec<usize>)->usize{
426		let mut mindistance=metric.distance(&self.key,key);
427		if mindistance==0{return 0}
428		let l0=v.len();
429		for (i,n) in self.connections.range(mindistance.saturating_sub(maxdistance)..=mindistance.saturating_add(maxdistance)){
430			let l1=v.len();
431			v.push(*i);
432			let candidatedistance=n.get_path(key,maxdistance,metric,v);
433			if candidatedistance<=maxdistance&&candidatedistance<mindistance{
434				mindistance=candidatedistance;
435				v.drain(l0..l1);
436			}else{
437				v.truncate(l1);
438			}
439		}
440		mindistance
441	}
442	/// inserts a node in this one using the metric
443	fn insert<M:DiscreteMetric<K,K>>(&mut self,key:K,metric:&M,value:V)->Option<V>{
444		let (mut k,mut v)=(Some(key),Some(value));
445		let mut node=self;
446
447		loop{
448			let distance=if let Some(k)=&k{metric.distance(k,&node.key)}else{break};
449			if distance==0{return Some(replace(&mut node.value,v.unwrap()))}
450			node=node.connections.entry(distance).or_insert_with(||Node::new(k.take().unwrap(),v.take().unwrap()));
451		}
452		None
453	}
454	/// creates a new node
455	fn new(key:K,value:V)->Self{
456		Self{connections:BTreeMap::new(),key,value}
457	}
458}
459#[cfg(test)]
460mod tests{
461	#[test]
462	fn insert_get_rectangle(){
463		let mut map=BKTreeMap::new(Cheb2D);
464
465		assert_eq!(map.insert((-1,-1),'A'),None);
466		assert_eq!(map.insert((-1,2),'B'),None);
467		assert_eq!(map.insert((1,-1),'C'),None);
468		assert_eq!(map.insert((1,2),'D'),None);
469		assert_eq!(map.insert((-1,2),'b'),Some('B'));
470		assert_eq!(map.insert((1,2),'d'),Some('D'));
471		assert_eq!(map.insert((1,-1),'c'),Some('C'));
472		assert_eq!(map.insert((-1,-1),'a'),Some('A'));
473		assert_eq!(map.len(),4);
474
475		for n in 0..10{
476			assert_eq!(map.get_key_value(&(-1,-1),n),Some((&(-1,-1),&'a',0)));
477			assert_eq!(map.get_key_value(&(-1,2),n),Some((&(-1,2),&'b',0)));
478			assert_eq!(map.get_key_value(&(1,-1),n),Some((&(1,-1),&'c',0)));
479			assert_eq!(map.get_key_value(&(1,2),n),Some((&(1,2),&'d',0)));
480		}
481
482		assert_eq!(map.get_key_value(&(-1,-2),0),None);
483		assert_eq!(map.get_key_value(&(-1,3),0),None);
484		assert_eq!(map.get_key_value(&(2,-1),0),None);
485		assert_eq!(map.get_key_value(&(2,1),0),None);
486
487		assert_eq!(map.get_key_value(&(-1,-2),1),Some((&(-1,-1),&'a',1)));
488		assert_eq!(map.get_key_value(&(-1,3),1),Some((&(-1,2),&'b',1)));
489		assert_eq!(map.get_key_value(&(2,-1),1),Some((&(1,-1),&'c',1)));
490		assert_eq!(map.get_key_value(&(2,2),1),Some((&(1,2),&'d',1)));
491	}
492	#[test]
493	fn insert_remove_rectangle(){
494		let mut map=BKTreeMap::new(Cheb2D);
495
496		assert_eq!(map.insert((-1,-1),'A'),None);
497		assert_eq!(map.insert((-1,2),'B'),None);
498		assert_eq!(map.insert((1,-1),'C'),None);
499		assert_eq!(map.insert((1,2),'D'),None);
500
501		assert_eq!(map.remove(&(-1,2),0),Some(('B',0)));
502		assert_eq!(map.len(),3);
503		assert_eq!(map.remove(&(1,2),0),Some(('D',0)));
504		assert_eq!(map.len(),2);
505		assert_eq!(map.remove(&(1,-1),0),Some(('C',0)));
506		assert_eq!(map.len(),1);
507		assert_eq!(map.remove(&(-1,-1),0),Some(('A',0)));
508		assert_eq!(map.len(),0);
509
510		for n in 0..10{
511			assert_eq!(map.insert((-1,-1),'a'),None);
512			assert_eq!(map.insert((-1,2),'b'),None);
513			assert_eq!(map.insert((1,-1),'c'),None);
514			assert_eq!(map.insert((1,2),'d'),None);
515			assert_eq!(map.len(),4);
516
517			assert_eq!(map.remove(&(-1,-1),n),Some(('a',0)));
518			assert_eq!(map.get_key_value(&(-1,3),1),Some((&(-1,2),&'b',1)));
519			assert_eq!(map.get_key_value(&(2,-1),1),Some((&(1,-1),&'c',1)));
520			assert_eq!(map.remove(&(-1,2),n),Some(('b',0)));
521			assert_eq!(map.len(),2);
522			assert_eq!(map.remove(&(1,-1),n),Some(('c',0)));
523			assert_eq!(map.len(),1);
524			assert_eq!(map.remove(&(1,2),n),Some(('d',0)));
525		}
526
527		assert_eq!(map.insert((-1,-1),'a'),None);
528		assert_eq!(map.insert((-1,2),'b'),None);
529		assert_eq!(map.insert((1,-1),'c'),None);
530		assert_eq!(map.insert((1,2),'d'),None);
531		assert_eq!(map.len(),4);
532
533		assert_eq!(map.remove(&(-1,-2),0),None);
534		assert_eq!(map.remove(&(-1,3),0),None);
535		assert_eq!(map.remove(&(2,-1),0),None);
536		assert_eq!(map.remove(&(2,1),0),None);
537		assert_eq!(map.len(),4);
538
539		assert_eq!(map.get_key_value(&(-1,-2),1),Some((&(-1,-1),&'a',1)));
540		assert_eq!(map.get_key_value(&(-1,3),1),Some((&(-1,2),&'b',1)));
541		assert_eq!(map.get_key_value(&(2,-1),1),Some((&(1,-1),&'c',1)));
542		assert_eq!(map.get_key_value(&(2,2),1),Some((&(1,2),&'d',1)));
543	}
544
545
546	#[test]
547	fn test_insert_and_close_values() {
548		let mut map = BKTreeMap::<i32, AbsDiff, &'static str>::default();
549		map.insert(10, "ten");
550		map.insert(20, "twenty");
551		map.insert(15, "fifteen");
552
553		// Close to 12 within distance 3 -> only 10 (dist=2) and 15 (dist=3)
554		let mut results: Vec<(&&str, usize)> = map.close_values(12, 3).collect();
555		results.sort_unstable_by_key(|&(_v, d)| d);
556		assert_eq!(results, vec![(&"ten", 2), (&"fifteen", 3)]);
557	}
558
559	#[test]
560	fn test_closest_sorted_output() {
561		let mut map = BKTreeMap::<i32, AbsDiff, &'static str>::default();
562		for &(k, v) in &[(5, "five"), (2, "two"), (8, "eight"), (6, "six")] {
563			map.insert(k, v);
564		}
565		// close returns sorted by distance
566		let close = map.close_sorted(&6, 3);
567		let distances: Vec<usize> = close.iter().map(|&(_k, _v, d)| d).collect();
568		assert_eq!(distances, vec![0, 1, 2]);
569		let keys: Vec<i32> = close.iter().map(|&(k, _v, _d)| *k).collect();
570		assert_eq!(keys, vec![6, 5, 8]);
571	}
572
573	#[test]
574	fn test_iterators_key_map_val() {
575		let mut map = BKTreeMap::<i32, AbsDiff, i32>::default();
576		for i in 1..=5 {
577			map.insert(i, i * 10);
578		}
579
580		// Test key iterator
581		let mut keys: Vec<i32> = map.keys().cloned().collect();
582		keys.sort_unstable();
583		assert_eq!(keys, vec![1, 2, 3, 4, 5]);
584
585		// Test value iterator
586		let mut vals: Vec<i32> = map.values().cloned().collect();
587		vals.sort_unstable();
588		assert_eq!(vals, vec![10, 20, 30, 40, 50]);
589
590		// Test map iterator (key, value)
591		let mut pairs: Vec<(i32, i32)> = map.iter().map(|(&k, &v)| (k, v)).collect();
592		pairs.sort_unstable();
593		assert_eq!(pairs, vec![(1,10), (2,20), (3,30), (4,40), (5,50)]);
594	}
595
596	#[test]
597	fn test_clear_and_length() {
598		let mut map = BKTreeMap::<i32, AbsDiff, ()>::new(AbsDiff);
599		map.insert(1, ());
600		map.insert(2, ());
601		assert_eq!(map.len(), 2);
602		map.clear();
603		assert_eq!(map.len(), 0);
604		// After clear, no close results
605		assert_eq!(map.close_keys(1, 1).count(), 0);
606	}
607	#[test]
608	fn test_from_iterator_and_default() {
609		let data = vec![(0, "zero"), (3, "three"), (7, "seven")];
610		let map: BKTreeMap<_, AbsDiff, _> = data.clone().into_iter().collect();
611		// Using Default
612		let default_map: BKTreeMap<i32, AbsDiff, &str> = BKTreeMap::default();
613		assert_eq!(default_map.len(), 0);
614
615		let mut collected: Vec<(i32, &str)> = map.iter().map(|(&k, &v)| (k, v)).collect();
616		let mut expected = data;
617		collected.sort_unstable();
618		expected.sort_unstable();
619		assert_eq!(collected, expected);
620	}
621	impl DiscreteMetric<(isize,isize),(isize,isize)> for Cheb2D{
622		fn distance(&self,x:&(isize,isize),y:&(isize,isize))->usize{
623			let ((xx,xy),(yx,yy))=(x,y);
624			((xx-yx).abs() as usize).max((xy-yy).abs() as usize)
625		}
626	}
627	impl DiscreteMetric<i32,i32> for AbsDiff{
628		fn distance(&self,x:&i32,y:&i32)->usize{(*x-*y).abs() as usize}
629	}
630	#[derive(Clone,Copy,Debug,Default)]
631	/// A simple absolute difference metric for integers
632	struct AbsDiff;
633	#[derive(Clone,Copy,Debug,Default)]
634	/// 2d integer chebyshev distance
635	struct Cheb2D;
636	use super::*;
637}
638#[derive(Clone,Debug)]
639/// a tree for quickly finding items separated by a small discrete distance
640pub struct BKTreeMap<K,M,V>{length:usize,metric:M,root:Option<Node<K,V>>}
641#[derive(Debug)]
642/// iterator over keys close to some key
643pub struct CloseKeyIter<'a,K,M,Q,V>{inner:CloseMapIter<'a,K,M,Q,V>}
644#[derive(Debug)]
645/// iterator over mappings close to some key
646pub struct CloseMapIter<'a,K,M,Q,V>{key:Q,maxdistance:usize,metric:&'a M,nodes:Vec<&'a Node<K,V>>,remaining:usize}
647#[derive(Debug)]
648/// iterator over values with keys close to some key
649pub struct CloseValIter<'a,K,M,Q,V>{inner:CloseMapIter<'a,K,M,Q,V>}
650#[derive(Debug)]
651/// iterator over the keys in the tree
652pub struct IntoKeysIter<K,V>{inner:MapIntoIter<K,V>}
653#[derive(Debug)]
654/// iterator over the keys in the tree
655pub struct IntoValsIter<K,V>{inner:MapIntoIter<K,V>}
656#[derive(Debug)]
657/// iterator over the keys in the tree
658pub struct KeyIter<'a,K,V>{inner:MapIter<'a,K,V>}
659#[derive(Debug)]
660/// iterator over the mappings in the tree
661pub struct MapIter<'a,K,V>{nodes:Vec<&'a Node<K,V>>,remaining:usize}
662#[derive(Debug)]
663/// iterator over the mappings in the tree
664pub struct MapIntoIter<K,V>{nodes:Vec<Node<K,V>>,remaining:usize}
665#[derive(Debug)]
666/// iterator over the mappings in the tree
667pub struct MapIterMut<'a,K,V>{nodes:Vec<&'a mut Node<K,V>>,remaining:usize}
668#[derive(Debug)]
669/// iterator over the values in the tree
670pub struct ValIter<'a,K,V>{inner:MapIter<'a,K,V>}
671#[derive(Debug)]
672/// iterator over the values in the tree
673pub struct ValIterMut<'a,K,V>{inner:MapIterMut<'a,K,V>}
674#[derive(Clone,Debug)]
675/// tree node
676struct Node<K,V>{connections:BTreeMap<usize,Node<K,V>>,key:K,value:V}
677use {
678	crate::DiscreteMetric,
679	std::{
680		collections::BTreeMap,iter::{Extend,FromIterator},mem::replace,ops::{Index,IndexMut}
681	}
682};
b_k_tree/map.rs

b_k_tree/
map.rs
