b_k_tree/
set.rs

1impl<'a,E,M:DiscreteMetric<E,Q>,Q> Iterator for CloseSetIter<'a,E,M,Q>{
2	fn next(&mut self)->Option<Self::Item>{self.inner.next()}
3	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
4	type Item=(&'a E,usize);
5}
6impl<'a,E,M,Q:Clone> Clone for CloseSetIter<'a,E,M,Q>{
7	fn clone(&self)->Self{
8		Self{inner:self.inner.clone()}
9	}
10	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
11}
12impl<'a,E,M> IntoIterator for &'a BKTreeSet<E,M>{
13	fn into_iter(self)->Self::IntoIter{
14		SetIter{inner:self.inner.keys()}
15	}
16	type IntoIter=SetIter<'a,E>;
17	type Item=&'a E;
18}
19impl<'a,E> Clone for SetIter<'a,E>{
20	fn clone(&self)->Self{
21		Self{inner:self.inner.clone()}
22	}
23	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
24}
25impl<'a,E> ExactSizeIterator for SetIter<'a,E>{
26	fn len(&self)->usize{self.inner.len()}
27}
28impl<'a,E> Iterator for SetIter<'a,E>{
29	fn next(&mut self)->Option<Self::Item>{self.inner.next()}
30	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
31	type Item=&'a E;
32}
33impl<E:Clone> Clone for SetIntoIter<E>{
34	fn clone(&self)->Self{
35		Self{inner:self.inner.clone()}
36	}
37	fn clone_from(&mut self,other:&Self){self.inner.clone_from(&other.inner)}
38}
39impl<E,M:Default> Default for BKTreeSet<E,M>{
40	fn default()->Self{Self::new(M::default())}
41}
42impl<E,M:Default+DiscreteMetric<E,E>> FromIterator<E> for BKTreeSet<E,M>{
43	fn from_iter<I:IntoIterator<Item=E>>(iter:I)->Self{
44		Self{inner:iter.into_iter().map(|e|(e,())).collect()}
45	}
46}
47impl<E,M:DiscreteMetric<E,E>> Extend<E> for BKTreeSet<E,M>{
48	fn extend<I:IntoIterator<Item=E>>(&mut self,iter:I){iter.into_iter().map(|e|self.insert(e)).for_each(|_|())}
49}
50impl<E,M> AsMut<Self> for BKTreeSet<E,M>{
51	fn as_mut(&mut self)->&mut Self{self}
52}
53impl<E,M> AsRef<Self> for BKTreeSet<E,M>{
54	fn as_ref(&self)->&Self{self}
55}
56impl<E,M> BKTreeSet<E,M>{//TODO other sterotypical set operations
57	/// moves all elements from other into self, leaving other empty
58	pub fn append<M2>(&mut self,other:&mut BKTreeSet<E,M2>) where M:DiscreteMetric<E,E>{self.inner.append(&mut other.inner)}
59	/// gets the items whose distance is at most max distance from key
60	pub fn close_iter<Q>(&self,key:Q,maxdistance:usize)->CloseSetIter<'_,E,M,Q> where M:DiscreteMetric<E,Q>{
61		CloseSetIter{inner:self.inner.close_keys(key,maxdistance)}
62	}
63	/// returns the elements at most maxdistance from the key, sorted by distance
64	pub fn close_sorted<'a,Q:?Sized>(&self,key:&Q,maxdistance:usize)->Vec<(&E,usize)> where M:DiscreteMetric<E,Q>{self.inner.close_sorted(key,maxdistance).into_iter().map(|(k,_v,d)|(k,d)).collect()}
65	/// tests if the set contains an element within max distance of the key
66	pub fn contains<Q:?Sized>(&self,key:&Q,maxdistance:usize)->bool where M:DiscreteMetric<E,Q>{self.inner.contains_key(key,maxdistance)}
67	/// returns a reference to the element in the set that is closest to the key within max distance, or None if the set contains no element at most max distance from the given element. If there are multiple closest elements, exactly which is returned is unspecified
68	pub fn get<Q:?Sized>(&self,key:&Q,maxdistance:usize)->Option<(&E,usize)> where M:DiscreteMetric<E,Q>{self.inner.get_key_value(key,maxdistance).map(|(k,_v,d)|(k,d))}
69	/// inserts
70	pub fn insert(&mut self,value:E)->bool where M:DiscreteMetric<E,E>{self.inner.insert(value,()).is_none()}
71	/// returns true if the set contains no elements
72	pub fn is_empty(&self)->bool{self.inner.is_empty()}
73	/// makes an iterator over the items
74	pub fn iter(&self)->SetIter<'_,E>{
75		SetIter{inner:self.inner.keys()}
76	}
77	/// returns the number of elements in the set
78	pub fn len(&self)->usize{self.inner.len()}
79	/// references the metric. avoid modifying the metric in a way that changes the distances because that will most likely cause unspecified incorrect behavior
80	pub fn metric(&self)->&M{self.inner.metric()}
81	/// creates a new tree
82	pub fn new(metric:M)->Self{
83		Self{inner:BKTreeMap::new(metric)}
84	}
85	/// removes an item from the tree. This particular tree type doesn't allow super efficient removal, so try to avoid using too much.
86	pub fn remove<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->bool where M:DiscreteMetric<E,Q>+DiscreteMetric<E,E>{self.inner.remove_entry(key,maxdistance).is_some()}
87	/// removes all the elements for which f returns false
88	pub fn retain<F:FnMut(&E)->bool>(&mut self,mut f:F) where M:DiscreteMetric<E,E>{self.inner.retain(|k,_v|f(k))}
89	/// removes an item from the tree. This particular tree type doesn't allow super efficient removal, so try to avoid using too much.
90	pub fn take<Q:?Sized>(&mut self,key:&Q,maxdistance:usize)->Option<(E,usize)> where M:DiscreteMetric<E,Q>+DiscreteMetric<E,E>{self.inner.remove_entry(key,maxdistance).map(|(k,_v,d)|(k,d))}
91}
92impl<E,M> IntoIterator for BKTreeSet<E,M>{
93	fn into_iter(self)->Self::IntoIter{
94		SetIntoIter{inner:self.inner.into_keys()}
95	}
96	type IntoIter=SetIntoIter<E>;
97	type Item=E;
98}
99impl<E> ExactSizeIterator for SetIntoIter<E>{
100	fn len(&self)->usize{self.inner.len()}
101}
102impl<E> Iterator for SetIntoIter<E>{
103	fn next(&mut self)->Option<Self::Item>{self.inner.next()}
104	fn size_hint(&self)->(usize,Option<usize>){self.inner.size_hint()}
105	type Item=E;
106}
107#[cfg(test)]
108mod tests{
109	#[test]
110	fn retain_cluster(){
111		let mut tree=BKTreeSet::new(Cheb2D);
112
113		tree.insert((0,0));
114		tree.insert((1,0));
115		tree.insert((0,1));
116		tree.insert((1,1));
117
118		tree.insert((10,10));
119		tree.insert((11,10));
120		tree.insert((10,11));
121		tree.insert((11,11));
122
123		tree.retain(|&(x,y)|x<10&&y<10);
124
125		let mut a:Vec<(isize,isize,usize)>=tree.close_iter((-1,-1),2).map(|((x,y),d)|(*x,*y,d)).collect();
126		let mut b:Vec<(isize,isize,usize)>=tree.close_iter((12,12),2).map(|((x,y),d)|(*x,*y,d)).collect();
127		a.sort_unstable();
128		b.sort_unstable();
129		assert_eq!(a,[(0,0,1),(0,1,2),(1,0,2),(1,1,2)]);
130		assert_eq!(b,[]);
131	}
132	#[test]
133	fn two_clusters(){
134		let mut tree=BKTreeSet::new(Cheb2D);
135
136		tree.insert((0,0));
137		tree.insert((1,0));
138		tree.insert((0,1));
139		tree.insert((1,1));
140
141		tree.insert((10,10));
142		tree.insert((11,10));
143		tree.insert((10,11));
144		tree.insert((11,11));
145
146		let mut a:Vec<(isize,isize,usize)>=tree.close_iter((-1,-1),2).map(|((x,y),d)|(*x,*y,d)).collect();
147		let mut b:Vec<(isize,isize,usize)>=tree.close_iter((12,12),2).map(|((x,y),d)|(*x,*y,d)).collect();
148		a.sort_unstable();
149		b.sort_unstable();
150		assert_eq!(a,[(0,0,1),(0,1,2),(1,0,2),(1,1,2)]);
151		assert_eq!(b,[(10,10,2),(10,11,2),(11,10,2),(11,11,1)]);
152	}
153	impl DiscreteMetric<(isize,isize),(isize,isize)> for Cheb2D{
154		fn distance(&self,x:&(isize,isize),y:&(isize,isize))->usize{
155			let ((xx,xy),(yx,yy))=(x,y);
156			((xx-yx).abs() as usize).max((xy-yy).abs() as usize)
157		}
158	}
159	#[derive(Clone,Copy,Debug,Default)]
160	/// 2d integer chebyshev distance
161	struct Cheb2D;
162	use super::*;
163}
164#[derive(Clone,Debug)]
165/// a set for quickly finding items separated by a small discrete distance, implemented as a thin wrapper over BKTreeMap
166pub struct BKTreeSet<E,M>{inner:BKTreeMap<E,M,()>}
167#[derive(Debug)]
168/// iterator over the items close to some key
169pub struct CloseSetIter<'a,E,M,Q>{inner:CloseKeyIter<'a,E,M,Q,()>}
170#[derive(Debug)]
171/// iterator over the items in the tree
172pub struct SetIntoIter<E>{inner:IntoKeysIter<E,()>}
173#[derive(Debug)]
174/// iterator over the items in the tree
175pub struct SetIter<'a,E>{inner:KeyIter<'a,E,()>}
176use {
177	crate::{
178		DiscreteMetric,map::{BKTreeMap,CloseKeyIter,IntoKeysIter,KeyIter}
179	},
180	std::iter::{Extend,FromIterator}
181};
b_k_tree/set.rs

b_k_tree/
set.rs
