b_k_tree/
map.rs

1impl<'a,K,M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>,Q,V> Drop for DrainMapIter<'a,K,M,Q,V>{
2	fn drop(&mut self){self.for_each(|_|())}
3}
4impl<'a,K,M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>,Q,V> Iterator for DrainMapIter<'a,K,M,Q,V>{
5	fn next(&mut self)->Option<Self::Item>{
6		fn explore<'a,K,M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>,Q,V>(insertionindex:usize,insertionnode:&mut Node<K,V>,key:&Q,matches:&mut Vec<(Node<K,V>,usize)>,mut matchesstart:usize,maxdistance:usize,metric:&'a M,nodes:&mut Vec<(Option<&'a mut Node<K,V>>,usize)>){
7			while matchesstart<matches.len(){
8				take(&mut matches[matchesstart].0.connections).into_values().for_each(|n|{
9					let distance=metric.distance(&n.key,key);
10					if distance<=maxdistance{
11						matches.push((n,distance));
12					}else{
13						if let Some(node)=insertionnode.connections.get_mut(&insertionindex){
14							node.insert_existing(metric,n);
15						}else{
16							insertionnode.connections.insert(insertionindex,n);
17						}
18						nodes.push((None,distance));
19					}
20				});
21				matchesstart+=1;
22			}
23		}
24		let (maxdistance,metric)=(self.maxdistance,self.metric);
25		let (maplen,matches,nodes)=(&mut self.maplen,&mut self.matches,&mut self.nodes);
26		let key=&self.key;
27
28		if let Some((node,distance))=matches.pop(){
29			**maplen-=1;
30			return Some((node.key,node.value,distance))
31		}
32		while let Some((Some(node),distance))=nodes.pop(){
33			let candidaterange=distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance);
34			let mut d=0;
35			let start=nodes.len();
36
37			take(&mut node.connections).into_iter().for_each(|(r,n)|if candidaterange.contains(&r)&&{
38				d=metric.distance(&n.key,key);
39				let remove=d<=maxdistance;
40				if !remove{nodes.push((None,d))}
41				remove
42			}{
43				matches.push((n,d));
44				explore(r,&mut *node,key,matches,matches.len()-1,maxdistance,metric,&mut *nodes);
45			}else{
46				node.connections.insert(r,n);
47			});
48			node.connections.range_mut(candidaterange).zip(nodes[start..].iter_mut()).for_each(|((_r,n),(node,_d))|*node=Some(n));
49			if let Some((n,d))=matches.pop(){
50				**maplen-=1;
51				return Some((n.key,n.value,d))
52			}
53		}
54		None
55	}
56	fn size_hint(&self)->(usize,Option<usize>){(self.matches.len(),Some(*self.maplen))}
57	type Item=(K,V,usize);
58}
59impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseKeyIter<'a,K,M,Q,V>{
60	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(k,_v,d)|(k,d))}
61	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
62	type Item=(&'a K,usize);
63}
64impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseMapIter<'a,K,M,Q,V>{
65	fn next(&mut self)->Option<Self::Item>{
66		let (maxdistance,metric)=(self.maxdistance,self.metric);
67		let key=&self.key;
68		let nodes=&mut self.nodes;
69
70		while let Some(n)=nodes.pop(){
71			let (k,v,next)=(&n.key,&n.value,&n.connections);
72			let distance=metric.distance(k,key);
73			self.remaining-=1;
74
75			nodes.extend(next.range(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).map(|(_r,n)|n));
76			if distance<=maxdistance{return Some((k,v,distance))}
77		}
78		None
79	}
80	fn size_hint(&self)->(usize,Option<usize>){(0,Some(self.remaining))}
81	type Item=(&'a K,&'a V,usize);
82}
83impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseMapIterMut<'a,K,M,Q,V>{
84	fn next(&mut self)->Option<Self::Item>{
85		let (maxdistance,metric)=(self.maxdistance,self.metric);
86		let key=&self.key;
87		let nodes=&mut self.nodes;
88
89		while let Some(n)=nodes.pop(){
90			let (k,v,next)=(&n.key,&mut n.value,&mut n.connections);
91			let distance=metric.distance(k,key);
92			self.remaining-=1;
93
94			nodes.extend(next.range_mut(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).map(|(_r,n)|n));//TODO remaining can have a tighter bound by subtracting one for every node not examined here, or the number of total sub nodes if that becomes tracked
95			if distance<=maxdistance{return Some((k,v,distance))}
96		}
97		None
98	}
99	fn size_hint(&self)->(usize,Option<usize>){(0,Some(self.remaining))}
100	type Item=(&'a K,&'a mut V,usize);
101}
102impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseValIter<'a,K,M,Q,V>{
103	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v,d)|(v,d))}
104	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
105	type Item=(&'a V,usize);
106}
107impl<'a,K,M:DiscreteMetric<K,Q>,Q,V> Iterator for CloseValIterMut<'a,K,M,Q,V>{
108	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v,d)|(v,d))}
109	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
110	type Item=(&'a mut V,usize);
111}
112impl<'a,K,M,Q:Clone,V> Clone for CloseKeyIter<'a,K,M,Q,V>{
113	fn clone(&self)->Self{
114		Self{inner:self.inner.clone()}
115	}
116	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
117}
118impl<'a,K,M,Q:Clone,V> Clone for CloseMapIter<'a,K,M,Q,V>{
119	fn clone(&self)->Self{
120		Self{key:self.key.clone(),maxdistance:self.maxdistance,metric:self.metric,nodes:self.nodes.clone(),remaining:self.remaining}
121	}
122	fn clone_from(&mut self,other:&Self){
123		(self.key.clone_from(&other.key),self.nodes.clone_from(&other.nodes));
124		(self.maxdistance,self.metric,self.remaining)=(other.maxdistance,other.metric,other.remaining);
125	}
126}
127impl<'a,K,M,Q:Clone,V> Clone for CloseValIter<'a,K,M,Q,V>{
128	fn clone(&self)->Self{
129		Self{inner:self.inner.clone()}
130	}
131	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
132}
133impl<'a,K,M,V> IntoIterator for &'a BKTreeMap<K,M,V>{
134	fn into_iter(self)->Self::IntoIter{self.iter()}
135	type IntoIter=MapIter<'a,K,V>;
136	type Item=(&'a K,&'a V);
137}
138impl<'a,K,M,V> IntoIterator for &'a mut BKTreeMap<K,M,V>{
139	fn into_iter(self)->Self::IntoIter{self.iter_mut()}
140	type IntoIter=MapIterMut<'a,K,V>;
141	type Item=(&'a K,&'a mut V);
142}
143impl<'a,K,V> Clone for KeyIter<'a,K,V>{
144	fn clone(&self)->Self{
145		Self{inner:self.inner.clone()}
146	}
147	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
148}
149impl<'a,K,V> Clone for MapIter<'a,K,V>{
150	fn clone(&self)->Self{
151		Self{nodes:self.nodes.clone(),remaining:self.remaining}
152	}
153	fn clone_from(&mut self,other:&Self){
154		self.nodes.clone_from(&other.nodes);
155		self.remaining=other.remaining;
156	}
157}
158impl<'a,K,V> Clone for ValIter<'a,K,V>{
159	fn clone(&self)->Self{
160		Self{inner:self.inner.clone()}
161	}
162	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
163}
164impl<'a,K,V> ExactSizeIterator for KeyIter<'a,K,V>{
165	fn len(&self)->usize{self.inner.len()}
166}
167impl<'a,K,V> ExactSizeIterator for MapIter<'a,K,V>{
168	fn len(&self)->usize{self.remaining}
169}
170impl<'a,K,V> ExactSizeIterator for MapIterMut<'a,K,V>{
171	fn len(&self)->usize{self.remaining}
172}
173impl<'a,K,V> ExactSizeIterator for ValIter<'a,K,V>{
174	fn len(&self)->usize{self.inner.len()}
175}
176impl<'a,K,V> Iterator for KeyIter<'a,K,V>{
177	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(k,_v)|k)}
178	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
179	type Item=&'a K;
180}
181impl<'a,K,V> Iterator for MapIter<'a,K,V>{
182	fn next(&mut self)->Option<Self::Item>{
183		let nodes=&mut self.nodes;
184		let node=nodes.pop()?;
185		let (k,v,next)=(&node.key,&node.value,&node.connections);
186		self.remaining-=1;
187
188		nodes.extend(next.values());
189		Some((k,v))
190	}
191	fn size_hint(&self)->(usize,Option<usize>){(self.remaining,Some(self.remaining))}
192	type Item=(&'a K,&'a V);
193}
194impl<'a,K,V> Iterator for MapIterMut<'a,K,V>{
195	fn next(&mut self)->Option<Self::Item>{
196		let nodes=&mut self.nodes;
197		let node=nodes.pop()?;
198		let (k,v,next)=(&node.key,&mut node.value,&mut node.connections);
199		self.remaining-=1;
200
201		nodes.extend(next.values_mut());
202		Some((k,v))
203	}
204	fn size_hint(&self)->(usize,Option<usize>){(self.remaining,Some(self.remaining))}
205	type Item=(&'a K,&'a mut V);
206}
207impl<'a,K,V> Iterator for ValIter<'a,K,V>{
208	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v)|v)}
209	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
210	type Item=&'a V;
211}
212impl<'a,K,V> Iterator for ValIterMut<'a,K,V>{
213	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v)|v)}
214	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
215	type Item=&'a mut V;
216}
217impl<K:Clone,V:Clone> Clone for IntoKeysIter<K,V>{
218	fn clone(&self)->Self{
219		Self{inner:self.inner.clone()}
220	}
221	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
222}
223impl<K:Clone,V:Clone> Clone for IntoValsIter<K,V>{
224	fn clone(&self)->Self{
225		Self{inner:self.inner.clone()}
226	}
227	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
228}
229impl<K:Clone,V:Clone> Clone for MapIntoIter<K,V>{
230	fn clone(&self)->Self{
231		let nodes=&self.nodes;
232		let remaining=self.remaining;
233
234		let nodes=MapIter::<K,V>{nodes:nodes.iter().collect(),remaining}.map(|(k,v)|Node::new(k.clone(),v.clone())).collect();
235		Self{nodes,remaining}
236	}
237	fn clone_from(&mut self,other:&Self){
238		let remaining=other.remaining;
239		let nodes=MapIter::<K,V>{nodes:other.nodes.iter().collect(),remaining}.map(|(k,v)|Node::new(k.clone(),v.clone()));
240
241		self.nodes.clear();
242		self.nodes.extend(nodes);
243		self.remaining=remaining;
244	}
245}
246impl<K,M:Default+DiscreteMetric<K,K>,V> FromIterator<(K,V)> for BKTreeMap<K,M,V>{
247	fn from_iter<I:IntoIterator<Item=(K,V)>>(iter:I)->Self{
248		let mut map=Self::default();
249		iter.into_iter().map(|(k,v)|map.insert(k,v)).for_each(|_|());
250		map
251	}
252}
253impl<K,M:Default,V> Default for BKTreeMap<K,M,V>{
254	fn default()->Self{Self::new(M::default())}
255}
256impl<K,M:DiscreteMetric<K,K>,V> Extend<(K,V)> for BKTreeMap<K,M,V>{
257	fn extend<I:IntoIterator<Item=(K,V)>>(&mut self,iter:I){iter.into_iter().map(|(k,v)|self.insert(k,v)).for_each(|_|())}
258}
259impl<K,M:DiscreteMetric<K,Q>,Q,V> Index<&Q> for BKTreeMap<K,M,V>{
260	fn index(&self,index:&Q)->&Self::Output{self.get(index,0).map(|(v,_d)|v).expect("mapping must exist to use index")}
261	type Output=V;
262}
263impl<K,M:DiscreteMetric<K,Q>,Q,V> IndexMut<&Q> for BKTreeMap<K,M,V>{
264	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")}
265}
266impl<K,M,V> AsMut<Self> for BKTreeMap<K,M,V>{
267	fn as_mut(&mut self)->&mut Self{self}
268}
269impl<K,M,V> AsRef<Self> for BKTreeMap<K,M,V>{
270	fn as_ref(&self)->&Self{self}
271}
272impl<K,M,V> BKTreeMap<K,M,V>{//TODO other sterotypical map operations
273	/// 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
274	pub fn append<M2>(&mut self,other:&mut BKTreeMap<K,M2,V>) where M:DiscreteMetric<K,K>{
275		fn explore<K,M:DiscreteMetric<K,K>,V>(node:Node<K,V>,tree:&mut BKTreeMap<K,M,V>){
276			let (k,v,next)=(node.key,node.value,node.connections);
277			tree.insert(k,v);
278			next.into_iter().for_each(|(_d,n)|explore(n,tree));
279		}
280
281		if let Some(n)=other.root.take(){explore(n,self)}
282	}
283	/// clears the map, removing all elements
284	pub fn clear(&mut self){
285		self.length=0;
286		self.root=None;
287	}
288	/// gets the key value pairs whose distance is at most max distance from key
289	pub fn close_iter<Q>(&self,key:Q,maxdistance:usize)->CloseMapIter<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{
290		CloseMapIter{key,maxdistance,metric:&self.metric,nodes:self.root.as_ref().into_iter().collect(),remaining:self.length}
291	}
292	/// gets the key value pairs whose distance is at most max distance from key
293	pub fn close_iter_mut<Q>(&mut self,key:Q,maxdistance:usize)->CloseMapIterMut<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{
294		CloseMapIterMut{key,maxdistance,metric:&self.metric,nodes:self.root.as_mut().into_iter().collect(),remaining:self.length}
295	}
296	/// gets the keys whose distance is at most max distance from key
297	pub fn close_keys<Q>(&self,key:Q,maxdistance:usize)->CloseKeyIter<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{
298		CloseKeyIter{inner:self.close_iter(key,maxdistance)}
299	}
300	/// returns the key value pairs at most maxdistance from the key, sorted by distance
301	pub fn close_sorted<'a,Q:?Sized>(&self,key:&Q,maxdistance:usize)->Vec<(&K,&V,usize)> where M:DiscreteMetric<K,Q>{
302		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)>){
303			let distance=metric.distance(&node.key,key);
304
305			if distance<=maxdistance{results.push((&node.key,&node.value,distance))}
306			node.connections.range(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).for_each(|(_d,n)|explore(key,maxdistance,metric,n,results));
307		}
308		let metric=&self.metric;
309		let root=if let Some(r)=&self.root{r}else{return Vec::new()};
310		let mut results=Vec::with_capacity(10);
311
312		explore(key,maxdistance,metric,root,&mut results);
313		results.sort_unstable_by_key(|(_k,_v,d)|*d);
314		results
315	}
316	/// returns the key value pairs at most maxdistance from the key, sorted by distance
317	pub fn close_sorted_mut<'a,Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Vec<(&K,&mut V,usize)> where M:DiscreteMetric<K,Q>{
318		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)>){
319			let distance=metric.distance(&node.key,key);
320
321			if distance<=maxdistance{results.push((&node.key,&mut node.value,distance))}
322			node.connections.range_mut(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).for_each(|(_d,n)|explore(key,maxdistance,metric,n,results));
323		}
324		let metric=&self.metric;
325		let root=if let Some(r)=&mut self.root{r}else{return Vec::new()};
326		let mut results=Vec::with_capacity(10);
327
328		explore(key,maxdistance,metric,root,&mut results);
329		results.sort_unstable_by_key(|(_k,_v,d)|*d);
330		results
331	}
332	/// gets the values whose keys are at most max distance from key
333	pub fn close_values<Q>(&self,key:Q,maxdistance:usize)->CloseValIter<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{
334		CloseValIter{inner:self.close_iter(key,maxdistance)}
335	}
336	/// gets the values whose keys are at most max distance from key
337	pub fn close_values_mut<Q>(&mut self,key:Q,maxdistance:usize)->CloseValIterMut<'_,K,M,Q,V> where M:DiscreteMetric<K,Q>{
338		CloseValIterMut{inner:self.close_iter_mut(key,maxdistance)}
339	}
340	/// tests if a key at most maxdistance from the given key is in the map
341	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()}
342	/// drains the values close to the key
343	pub fn drain<Q>(&mut self,key:Q,maxdistance:usize)->DrainMapIter<'_,K,M,Q,V> where M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>{
344		let (matches,nodes)=if self.root.as_ref().map(|r|self.metric.distance(&r.key,&key)<=maxdistance).unwrap_or(true){
345			let mut matches:Vec<(K,V,usize)>=MapIntoIter{nodes:self.root.take().into_iter().collect(),remaining:self.length}.map(|(k,v)|{
346				let d=self.metric.distance(&k,&key);
347				(k,v,d)
348			}).collect();
349			self.length=0;
350			self.extend(matches.extract_if(..,|(_k,_v,d)|*d>maxdistance).map(|(k,v,_d)|(k,v)));
351			let matches=matches.into_iter().map(|(k,v,d)|(Node::new(k,v),d)).collect();
352			let nodes=Vec::new();
353			(matches,nodes)
354		}else{
355			let matches=Vec::new();
356			let nodes=self.root.as_mut().into_iter().map(|n|{
357				let d=self.metric.distance(&n.key,&key);
358				(Some(n),d)
359			}).collect();
360			(matches,nodes)
361		};
362		let maplen=&mut self.length;
363		let metric=&self.metric;
364		DrainMapIter{key,maxdistance,maplen,matches,metric,nodes}
365	}
366	/// 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
367	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))}
368	/// 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
369	pub fn get_key_value<Q:?Sized>(&self,key:&Q,maxdistance:usize)->Option<(&K,&V,usize)> where M:DiscreteMetric<K,Q>{
370		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)>{
371			let distance=metric.distance(&node.key,key);
372
373			if distance==0{return Some((&node.key,&node.value,0))}
374			let includecurrent=distance<=maxdistance;
375			let nextnodes=node.connections.range(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).filter_map(|(_d,n)|explore(key,maxdistance,metric,n));
376			nextnodes.chain(includecurrent.then_some((&node.key,&node.value,distance))).min_by_key(|(_k,_v,d)|*d)
377		}
378		let metric=&self.metric;
379		let root=if let Some(r)=&self.root{r}else{return None};
380
381		explore(key,maxdistance,metric,root)
382	}
383	/// 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
384	pub fn get_mut<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Option<(&mut V,usize)> where M:DiscreteMetric<K,Q>{
385		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)>{
386			let distance=metric.distance(&node.key,key);
387
388			if distance==0{return Some((&mut node.value,0))}
389			let includecurrent=distance<=maxdistance;
390			let nextnodes=node.connections.range_mut(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).filter_map(|(_d,n)|explore(key,maxdistance,metric,n));
391			nextnodes.chain(includecurrent.then_some((&mut node.value,distance))).min_by_key(|(_v,d)|*d)
392		}
393		let metric=&self.metric;
394		let root=if let Some(r)=&mut self.root{r}else{return None};
395
396		explore(key,maxdistance,metric,root)
397	}
398	/// 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.
399	pub fn insert(&mut self,key:K,value:V)->Option<V> where M:DiscreteMetric<K,K>{
400		let metric=&self.metric;
401		let root=if let Some(n)=self.root.as_mut(){
402			n
403		}else{
404			self.length+=1;
405			self.root=Some(Node::new(key,value));
406			return None;
407		};
408
409		if let Some(v)=root.insert(key,metric,value){return Some(v)}
410		self.length+=1;
411		None
412	}
413	/// makes an iterator over the keys
414	pub fn into_keys(self)->IntoKeysIter<K,V>{
415		IntoKeysIter{inner:self.into_iter()}
416	}
417	/// makes an iterator over the values
418	pub fn into_values(self)->IntoValsIter<K,V>{
419		IntoValsIter{inner:self.into_iter()}
420	}
421	/// returns true if the map contains no entries
422	pub fn is_empty(&self)->bool{self.length==0}
423	/// makes an iterator over the mappings
424	pub fn iter(&self)->MapIter<'_,K,V>{
425		MapIter{nodes:self.root.as_ref().into_iter().collect(),remaining:self.length}
426	}
427	/// makes an iterator over the mappings
428	pub fn iter_mut(&mut self)->MapIterMut<'_,K,V>{
429		MapIterMut{nodes:self.root.as_mut().into_iter().collect(),remaining:self.length}
430	}
431	/// makes an iterator over the keys
432	pub fn keys(&self)->KeyIter<'_,K,V>{
433		KeyIter{inner:self.iter()}
434	}
435	/// references the metric. avoid modifying the metric in a way that changes the distances because that will most likely cause unspecified incorrect behavior
436	pub fn metric(&self)->&M{&self.metric}
437	/// returns the number of entries in the map
438	pub fn len(&self)->usize{self.length}
439	/// creates a new tree
440	pub fn new(metric:M)->Self{
441		Self{length:0,metric,root:None}
442	}
443	/// 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.
444	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))}
445	/// 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.
446	pub fn remove_entry<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Option<(K,V,usize)> where M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>{
447		fn restore_nodes<K,M:DiscreteMetric<K,K>,V>(branch:&mut Node<K,V>,metric:&M,nodes:BTreeMap<usize,Node<K,V>>){
448			nodes.into_iter().for_each(|(_d,n)|{
449				branch.insert(n.key,metric,n.value);
450				restore_nodes(branch,metric,n.connections);
451			})
452		}
453		let metric=&self.metric;
454		let mut path=Vec::with_capacity(10);
455		let mut branch=if let Some(r)=&mut self.root{r}else{return None};
456		let nodedistance=branch.get_path(key,maxdistance,metric,&mut path);
457		if nodedistance>maxdistance{return None}
458		let mut path=path.into_iter();
459		let lastindex=path.next_back();
460		for i in path{branch=branch.connections.get_mut(&i).unwrap()}
461		self.length-=1;
462		if let Some(i)=lastindex{
463			let node=branch.connections.remove(&i).unwrap();
464			restore_nodes(branch,metric,node.connections);
465			return Some((node.key,node.value,nodedistance))
466		}
467		let mut oldroot=self.root.take().unwrap();
468		if let Some((_d,mut newroot))=oldroot.connections.pop_first(){
469			restore_nodes(&mut newroot,metric,oldroot.connections);
470			self.root=Some(newroot);
471		}
472		Some((oldroot.key,oldroot.value,nodedistance))
473	}
474	/// removes all the mappings for which f returns false
475	pub fn retain<F:FnMut(&K,&mut V)->bool>(&mut self,mut f:F) where M:DiscreteMetric<K,K>{
476		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>){
477			let (connections,key)=(node.connections,node.key);
478			let mut value=node.value;
479
480			if f(&key,&mut value){
481				tree.insert(key,value);
482			}
483			for n in connections.into_values(){explore(f,n,tree)}
484		}
485		let root=if let Some(r)=self.root.take(){r}else{return};
486		self.length=0;
487		explore(&mut f,root,self);
488	}
489	/// splits off the items close to the key
490	pub fn split_off<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Self where M:Clone+DiscreteMetric<K,K>+DiscreteMetric<K,Q>{
491		let metric=self.metric.clone();
492		let mut y=Self::new(metric.clone());
493		let x=BKTreeMap{length:self.length,metric,root:self.root.take()};
494
495		self.length=0;
496		x.into_iter().map(|(k,v)|if y.metric.distance(&k,key)<=maxdistance{&mut y}else{&mut *self}.insert(k,v)).for_each(|_|());
497		y
498	}
499	/// makes an iterator over the values
500	pub fn values(&self)->ValIter<'_,K,V>{
501		ValIter{inner:self.iter()}
502	}
503	/// makes an iterator over the values
504	pub fn values_mut(&mut self)->ValIterMut<'_,K,V>{
505		ValIterMut{inner:self.iter_mut()}
506	}
507}
508impl<K,M,V> IntoIterator for BKTreeMap<K,M,V>{
509	fn into_iter(self)->Self::IntoIter{
510		MapIntoIter{nodes:self.root.into_iter().collect(),remaining:self.length}
511	}
512	type IntoIter=MapIntoIter<K,V>;
513	type Item=(K,V);
514}
515impl<K,V> ExactSizeIterator for IntoKeysIter<K,V>{
516	fn len(&self)->usize{self.inner.len()}
517}
518impl<K,V> ExactSizeIterator for IntoValsIter<K,V>{
519	fn len(&self)->usize{self.inner.len()}
520}
521impl<K,V> ExactSizeIterator for MapIntoIter<K,V>{
522	fn len(&self)->usize{self.remaining}
523}
524impl<K,V> Iterator for IntoKeysIter<K,V>{
525	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(k,_v)|k)}
526	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
527	type Item=K;
528}
529impl<K,V> Iterator for IntoValsIter<K,V>{
530	fn next(&mut self)->Option<Self::Item>{self.inner.next().map(|(_k,v)|v)}
531	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
532	type Item=V;
533}
534impl<K,V> Iterator for MapIntoIter<K,V>{
535	fn next(&mut self)->Option<Self::Item>{
536		let nodes=&mut self.nodes;
537		let node=nodes.pop()?;
538		let (k,v,next)=(node.key,node.value,node.connections);
539		self.remaining-=1;
540
541		nodes.extend(next.into_values());
542		Some((k,v))
543	}
544	fn size_hint(&self)->(usize,Option<usize>){(self.remaining,Some(self.remaining))}
545	type Item=(K,V);
546}
547impl<K,V> Node<K,V>{
548	/*/// recursive depth first search of the items within maxdistance
549	fn bkdfs<B,F:FnMut(&Node<K,V>,usize)->ControlFlow<B>,M:DiscreteMetric<K,Q>,Q:?Sized>(&self,behavior:&mut F,key:&Q,maxdistance:usize,metric:&M)->ControlFlow<B>{
550		let distance=metric.distance(&self.key,key);
551		if distance<=maxdistance{behavior(self,distance)?}
552		self.connections.range(distance.saturating_sub(maxdistance)..=distance.saturating_add(maxdistance)).try_for_each(|(_r,n)|n.bkdfs(&mut *behavior,key,maxdistance,metric))?;
553		ControlFlow::Continue(())
554	}*/
555	/// gets index path to a node, returning the distance. Returns greater than max distance if there is no node within maxdistance
556	fn get_path<M:DiscreteMetric<K,Q>,Q:?Sized>(&self,key:&Q,maxdistance:usize,metric:&M,v:&mut Vec<usize>)->usize{
557		let mut mindistance=metric.distance(&self.key,key);
558		if mindistance==0{return 0}
559		let l0=v.len();
560		for (i,n) in self.connections.range(mindistance.saturating_sub(maxdistance)..=mindistance.saturating_add(maxdistance)){
561			let l1=v.len();
562			v.push(*i);
563			let candidatedistance=n.get_path(key,maxdistance,metric,v);
564			if candidatedistance<=maxdistance&&candidatedistance<mindistance{
565				mindistance=candidatedistance;
566				v.drain(l0..l1);
567			}else{
568				v.truncate(l1);
569			}
570		}
571		mindistance
572	}
573	/// inserts a node in this one using the metric
574	fn insert<M:DiscreteMetric<K,K>>(&mut self,key:K,metric:&M,value:V)->Option<V>{self.insert_existing(metric,Node::new(key,value))}
575	/// inserts a node in this one using the metric
576	fn insert_existing<M:DiscreteMetric<K,K>>(&mut self,metric:&M,node:Node<K,V>)->Option<V>{
577		let mut n=Some(node);
578		let mut node=self;
579
580		loop{
581			let distance=if let Some(n)=&n{metric.distance(&n.key,&node.key)}else{break};
582			if distance==0{return Some(replace(&mut node.value,n.unwrap().value))}
583			node=node.connections.entry(distance).or_insert_with(||n.take().unwrap());
584		}
585		None
586	}
587	/// creates a new node
588	fn new(key:K,value:V)->Self{
589		Self{connections:BTreeMap::new(),key,value}
590	}
591}
592#[cfg(test)]
593mod tests{
594	#[test]
595	fn drain(){
596		let mut map=BKTreeMap::new(Cheb2D);
597		map.insert((-1,-1),'A');
598		map.insert((-1,2),'B');
599		map.insert((1,-1),'C');
600		map.insert((1,2),'D');
601		map.insert((0,0),'a');
602		map.insert((1,0),'b');
603		map.insert((0,1),'c');
604		map.insert((1,1),'d');
605		map.insert((10,10),'w');
606		map.insert((11,10),'x');
607		map.insert((10,11),'y');
608		map.insert((11,11),'z');
609		map.insert((-1,4),'W');
610		map.insert((5,6),'X');
611		map.insert((12,10),'Y');
612		map.insert((-10,2),'Z');
613		assert_eq!(map.len(),16);
614
615		let mut drained:Vec<((isize,isize),char,usize)>=map.drain((10,10),1).collect();
616		drained.sort_unstable();
617		assert_eq!(drained,vec![((10,10),'w',0),((10,11),'y',1),((11,10),'x',1),((11,11),'z',1)]);
618		assert_eq!(map.len(),12);
619	}
620	#[test]
621	fn insert_get_rectangle(){
622		let mut map=BKTreeMap::new(Cheb2D);
623
624		assert_eq!(map.insert((-1,-1),'A'),None);
625		assert_eq!(map.insert((-1,2),'B'),None);
626		assert_eq!(map.insert((1,-1),'C'),None);
627		assert_eq!(map.insert((1,2),'D'),None);
628		assert_eq!(map.insert((-1,2),'b'),Some('B'));
629		assert_eq!(map.insert((1,2),'d'),Some('D'));
630		assert_eq!(map.insert((1,-1),'c'),Some('C'));
631		assert_eq!(map.insert((-1,-1),'a'),Some('A'));
632		assert_eq!(map.len(),4);
633
634		for n in 0..10{
635			assert_eq!(map.get_key_value(&(-1,-1),n),Some((&(-1,-1),&'a',0)));
636			assert_eq!(map.get_key_value(&(-1,2),n),Some((&(-1,2),&'b',0)));
637			assert_eq!(map.get_key_value(&(1,-1),n),Some((&(1,-1),&'c',0)));
638			assert_eq!(map.get_key_value(&(1,2),n),Some((&(1,2),&'d',0)));
639		}
640
641		assert_eq!(map.get_key_value(&(-1,-2),0),None);
642		assert_eq!(map.get_key_value(&(-1,3),0),None);
643		assert_eq!(map.get_key_value(&(2,-1),0),None);
644		assert_eq!(map.get_key_value(&(2,1),0),None);
645
646		assert_eq!(map.get_key_value(&(-1,-2),1),Some((&(-1,-1),&'a',1)));
647		assert_eq!(map.get_key_value(&(-1,3),1),Some((&(-1,2),&'b',1)));
648		assert_eq!(map.get_key_value(&(2,-1),1),Some((&(1,-1),&'c',1)));
649		assert_eq!(map.get_key_value(&(2,2),1),Some((&(1,2),&'d',1)));
650	}
651	#[test]
652	fn insert_remove_rectangle(){
653		let mut map=BKTreeMap::new(Cheb2D);
654
655		assert_eq!(map.insert((-1,-1),'A'),None);
656		assert_eq!(map.insert((-1,2),'B'),None);
657		assert_eq!(map.insert((1,-1),'C'),None);
658		assert_eq!(map.insert((1,2),'D'),None);
659
660		assert_eq!(map.remove(&(-1,2),0),Some(('B',0)));
661		assert_eq!(map.len(),3);
662		assert_eq!(map.remove(&(1,2),0),Some(('D',0)));
663		assert_eq!(map.len(),2);
664		assert_eq!(map.remove(&(1,-1),0),Some(('C',0)));
665		assert_eq!(map.len(),1);
666		assert_eq!(map.remove(&(-1,-1),0),Some(('A',0)));
667		assert_eq!(map.len(),0);
668
669		for n in 0..10{
670			assert_eq!(map.insert((-1,-1),'a'),None);
671			assert_eq!(map.insert((-1,2),'b'),None);
672			assert_eq!(map.insert((1,-1),'c'),None);
673			assert_eq!(map.insert((1,2),'d'),None);
674			assert_eq!(map.len(),4);
675
676			assert_eq!(map.remove(&(-1,-1),n),Some(('a',0)));
677			assert_eq!(map.get_key_value(&(-1,3),1),Some((&(-1,2),&'b',1)));
678			assert_eq!(map.get_key_value(&(2,-1),1),Some((&(1,-1),&'c',1)));
679			assert_eq!(map.remove(&(-1,2),n),Some(('b',0)));
680			assert_eq!(map.len(),2);
681			assert_eq!(map.remove(&(1,-1),n),Some(('c',0)));
682			assert_eq!(map.len(),1);
683			assert_eq!(map.remove(&(1,2),n),Some(('d',0)));
684		}
685
686		assert_eq!(map.insert((-1,-1),'a'),None);
687		assert_eq!(map.insert((-1,2),'b'),None);
688		assert_eq!(map.insert((1,-1),'c'),None);
689		assert_eq!(map.insert((1,2),'d'),None);
690		assert_eq!(map.len(),4);
691
692		assert_eq!(map.remove(&(-1,-2),0),None);
693		assert_eq!(map.remove(&(-1,3),0),None);
694		assert_eq!(map.remove(&(2,-1),0),None);
695		assert_eq!(map.remove(&(2,1),0),None);
696		assert_eq!(map.len(),4);
697
698		assert_eq!(map.get_key_value(&(-1,-2),1),Some((&(-1,-1),&'a',1)));
699		assert_eq!(map.get_key_value(&(-1,3),1),Some((&(-1,2),&'b',1)));
700		assert_eq!(map.get_key_value(&(2,-1),1),Some((&(1,-1),&'c',1)));
701		assert_eq!(map.get_key_value(&(2,2),1),Some((&(1,2),&'d',1)));
702	}
703
704
705	#[test]
706	fn test_insert_and_close_values() {
707		let mut map = BKTreeMap::<i32, AbsDiff, &'static str>::default();
708		map.insert(10, "ten");
709		map.insert(20, "twenty");
710		map.insert(15, "fifteen");
711
712		// Close to 12 within distance 3 -> only 10 (dist=2) and 15 (dist=3)
713		let mut results: Vec<(&&str, usize)> = map.close_values(12, 3).collect();
714		results.sort_unstable_by_key(|&(_v, d)| d);
715		assert_eq!(results, vec![(&"ten", 2), (&"fifteen", 3)]);
716	}
717
718	#[test]
719	fn test_closest_sorted_output() {
720		let mut map = BKTreeMap::<i32, AbsDiff, &'static str>::default();
721		for &(k, v) in &[(5, "five"), (2, "two"), (8, "eight"), (6, "six")] {
722			map.insert(k, v);
723		}
724		// close returns sorted by distance
725		let close = map.close_sorted(&6, 3);
726		let distances: Vec<usize> = close.iter().map(|&(_k, _v, d)| d).collect();
727		assert_eq!(distances, vec![0, 1, 2]);
728		let keys: Vec<i32> = close.iter().map(|&(k, _v, _d)| *k).collect();
729		assert_eq!(keys, vec![6, 5, 8]);
730	}
731
732	#[test]
733	fn test_iterators_key_map_val() {
734		let mut map = BKTreeMap::<i32, AbsDiff, i32>::default();
735		for i in 1..=5 {
736			map.insert(i, i * 10);
737		}
738
739		// Test key iterator
740		let mut keys: Vec<i32> = map.keys().cloned().collect();
741		keys.sort_unstable();
742		assert_eq!(keys, vec![1, 2, 3, 4, 5]);
743
744		// Test value iterator
745		let mut vals: Vec<i32> = map.values().cloned().collect();
746		vals.sort_unstable();
747		assert_eq!(vals, vec![10, 20, 30, 40, 50]);
748
749		// Test map iterator (key, value)
750		let mut pairs: Vec<(i32, i32)> = map.iter().map(|(&k, &v)| (k, v)).collect();
751		pairs.sort_unstable();
752		assert_eq!(pairs, vec![(1,10), (2,20), (3,30), (4,40), (5,50)]);
753	}
754
755	#[test]
756	fn test_clear_and_length() {
757		let mut map = BKTreeMap::<i32, AbsDiff, ()>::new(AbsDiff);
758		map.insert(1, ());
759		map.insert(2, ());
760		assert_eq!(map.len(), 2);
761		map.clear();
762		assert_eq!(map.len(), 0);
763		// After clear, no close results
764		assert_eq!(map.close_keys(1, 1).count(), 0);
765	}
766	#[test]
767	fn test_from_iterator_and_default() {
768		let data = vec![(0, "zero"), (3, "three"), (7, "seven")];
769		let map: BKTreeMap<_, AbsDiff, _> = data.clone().into_iter().collect();
770		// Using Default
771		let default_map: BKTreeMap<i32, AbsDiff, &str> = BKTreeMap::default();
772		assert_eq!(default_map.len(), 0);
773
774		let mut collected: Vec<(i32, &str)> = map.iter().map(|(&k, &v)| (k, v)).collect();
775		let mut expected = data;
776		collected.sort_unstable();
777		expected.sort_unstable();
778		assert_eq!(collected, expected);
779	}
780	impl DiscreteMetric<(isize,isize),(isize,isize)> for Cheb2D{
781		fn distance(&self,x:&(isize,isize),y:&(isize,isize))->usize{
782			let ((xx,xy),(yx,yy))=(x,y);
783			((xx-yx).abs() as usize).max((xy-yy).abs() as usize)
784		}
785	}
786	impl DiscreteMetric<i32,i32> for AbsDiff{
787		fn distance(&self,x:&i32,y:&i32)->usize{(*x-*y).abs() as usize}
788	}
789	#[derive(Clone,Copy,Debug,Default)]
790	/// A simple absolute difference metric for integers
791	struct AbsDiff;
792	#[derive(Clone,Copy,Debug,Default)]
793	/// 2d integer chebyshev distance
794	struct Cheb2D;
795	use super::*;
796}
797#[derive(Clone,Debug)]
798/// a tree for quickly finding items separated by a small discrete distance
799pub struct BKTreeMap<K,M,V>{length:usize,metric:M,root:Option<Node<K,V>>}
800#[derive(Debug)]
801/// iterator over keys close to some key
802pub struct CloseKeyIter<'a,K,M,Q,V>{inner:CloseMapIter<'a,K,M,Q,V>}
803#[derive(Debug)]
804/// iterator over mappings close to some key
805pub struct CloseMapIter<'a,K,M,Q,V>{key:Q,maxdistance:usize,metric:&'a M,nodes:Vec<&'a Node<K,V>>,remaining:usize}
806#[derive(Debug)]
807/// iterator over mappings close to some key
808pub struct CloseMapIterMut<'a,K,M,Q,V>{key:Q,maxdistance:usize,metric:&'a M,nodes:Vec<&'a mut Node<K,V>>,remaining:usize}
809#[derive(Debug)]
810/// iterator over values with keys close to some key
811pub struct CloseValIter<'a,K,M,Q,V>{inner:CloseMapIter<'a,K,M,Q,V>}
812#[derive(Debug)]
813/// iterator over values with keys close to some key
814pub struct CloseValIterMut<'a,K,M,Q,V>{inner:CloseMapIterMut<'a,K,M,Q,V>}
815#[derive(Debug)]
816/// iterator that removes mappings close to a key
817pub struct DrainMapIter<'a,K,M:DiscreteMetric<K,K>+DiscreteMetric<K,Q>,Q,V>{key:Q,maxdistance:usize,maplen:&'a mut usize,matches:Vec<(Node<K,V>,usize)>,metric:&'a M,nodes:Vec<(Option<&'a mut Node<K,V>>,usize)>}
818#[derive(Debug)]
819/// iterator over the keys in the tree
820pub struct IntoKeysIter<K,V>{inner:MapIntoIter<K,V>}
821#[derive(Debug)]
822/// iterator over the keys in the tree
823pub struct IntoValsIter<K,V>{inner:MapIntoIter<K,V>}
824#[derive(Debug)]
825/// iterator over the keys in the tree
826pub struct KeyIter<'a,K,V>{inner:MapIter<'a,K,V>}
827#[derive(Debug)]
828/// iterator over the mappings in the tree
829pub struct MapIter<'a,K,V>{nodes:Vec<&'a Node<K,V>>,remaining:usize}
830#[derive(Debug)]
831/// iterator over the mappings in the tree
832pub struct MapIntoIter<K,V>{nodes:Vec<Node<K,V>>,remaining:usize}
833#[derive(Debug)]
834/// iterator over the mappings in the tree
835pub struct MapIterMut<'a,K,V>{nodes:Vec<&'a mut Node<K,V>>,remaining:usize}
836#[derive(Debug)]
837/// iterator over the values in the tree
838pub struct ValIter<'a,K,V>{inner:MapIter<'a,K,V>}
839#[derive(Debug)]
840/// iterator over the values in the tree
841pub struct ValIterMut<'a,K,V>{inner:MapIterMut<'a,K,V>}
842#[derive(Clone,Debug)]
843/// tree node
844struct Node<K,V>{connections:BTreeMap<usize,Node<K,V>>,key:K,value:V}
845use {
846	crate::DiscreteMetric,
847	std::{
848		collections::BTreeMap,iter::{Extend,FromIterator},mem::{replace,take},ops::{Index,IndexMut}
849	}
850};
b_k_tree/map.rs

b_k_tree/
map.rs
