Struct BKTreeSet

pub struct BKTreeSet<E, M> { /* private fields */ }

a set for quickly finding items separated by a small discrete distance, implemented as a thin wrapper over BKTreeMap

Implementations

impl<E, M> BKTreeSet<E, M>

pub fn append<M2>(&mut self, other: &mut BKTreeSet<E, M2>)

where M: DiscreteMetric<E, E>,

moves all elements from other into self, leaving other empty

pub fn close_iter<Q>( &self, key: Q, maxdistance: usize, ) -> CloseSetIter<'_, E, M, Q>

where M: DiscreteMetric<E, Q>,

gets the items whose distance is at most max distance from key

Examples found in repository

examples/pair_close_points.rs (line 6)

pub fn main(){
	let vertices=[[-1.5, 2.0],[-1.6, 1.6],[-1.6, 1.1],[ 1.5, 1.3],[ 1.0,-0.1],
				  [ 0.5, 0.3],[-2.0, 1.0],[ 0.5,-1.0],[ 0.9, 0.8],[ 2.0, 2.0]];
	let tree:BKTreeSet<[f32;2],CeilL2>=vertices.into_iter().collect();
	let mut edges:Vec<([f32;2],[f32;2])>=vertices.into_iter().flat_map(|u|{
		let close=tree.close_iter(u,1).map(|(v,_d)|*v).filter(move|&v|u!=v);
		close.map(move|v|if u<v{(u,v)}else{(v,u)})
	}).collect();
	edges.sort_unstable_by_key(|([ux,uy],[vx,vy])|[ux.to_bits(),uy.to_bits(),vx.to_bits(),vy.to_bits()]);
	edges.dedup();

	edges.iter().for_each(|(p,q)|{
		println!("([{}, {}], [{}, {}])",p[0],p[1],q[0],q[1]);
	});
}

pub fn close_sorted<'a, Q: ?Sized>( &self, key: &Q, maxdistance: usize, ) -> Vec<(&E, usize)>

where M: DiscreteMetric<E, Q>,

returns the elements at most maxdistance from the key, sorted by distance

pub fn contains<Q: ?Sized>(&self, key: &Q, maxdistance: usize) -> bool

where M: DiscreteMetric<E, Q>,

tests if the set contains an element within max distance of the key

pub fn get<Q: ?Sized>(&self, key: &Q, maxdistance: usize) -> Option<(&E, usize)>

where M: DiscreteMetric<E, Q>,

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

pub fn insert(&mut self, value: E) -> bool

where M: DiscreteMetric<E, E>,

inserts

pub fn is_empty(&self) -> bool

returns true if the set contains no elements

pub fn iter(&self) -> SetIter<'_, E>

makes an iterator over the items

pub fn len(&self) -> usize

returns the number of elements in the set

pub fn metric(&self) -> &M

references the metric. avoid modifying the metric in a way that changes the distances because that will most likely cause unspecified incorrect behavior

pub fn new(metric: M) -> Self

creates a new tree

pub fn remove<Q: ?Sized>(&mut self, key: &Q, maxdistance: usize) -> bool

where M: DiscreteMetric<E, Q> + DiscreteMetric<E, E>,

removes an item from the tree. This particular tree type doesn’t allow super efficient removal, so try to avoid using too much.

pub fn retain<F: FnMut(&E) -> bool>(&mut self, f: F)

where M: DiscreteMetric<E, E>,

removes all the elements for which f returns false

pub fn take<Q: ?Sized>( &mut self, key: &Q, maxdistance: usize, ) -> Option<(E, usize)>

where M: DiscreteMetric<E, Q> + DiscreteMetric<E, E>,

removes an item from the tree. This particular tree type doesn’t allow super efficient removal, so try to avoid using too much.

Trait Implementations

impl<E, M> AsMut<BKTreeSet<E, M>> for BKTreeSet<E, M>

fn as_mut(&mut self) -> &mut Self

Converts this type into a mutable reference of the (usually inferred) input type.

impl<E, M> AsRef<BKTreeSet<E, M>> for BKTreeSet<E, M>

fn as_ref(&self) -> &Self

Converts this type into a shared reference of the (usually inferred) input type.

impl<E: Clone, M: Clone> Clone for BKTreeSet<E, M>

fn clone(&self) -> BKTreeSet<E, M>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<E: Debug, M: Debug> Debug for BKTreeSet<E, M>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<E, M: Default> Default for BKTreeSet<E, M>

fn default() -> Self

Returns the “default value” for a type.

impl<E, M: DiscreteMetric<E, E>> Extend<E> for BKTreeSet<E, M>

fn extend<I: IntoIterator<Item = E>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<E, M: Default + DiscreteMetric<E, E>> FromIterator<E> for BKTreeSet<E, M>

fn from_iter<I: IntoIterator<Item = E>>(iter: I) -> Self

Creates a value from an iterator.

impl<'a, E, M> IntoIterator for &'a BKTreeSet<E, M>

type IntoIter = SetIter<'a, E>

Which kind of iterator are we turning this into?

type Item = &'a E

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<E, M> IntoIterator for BKTreeSet<E, M>

type IntoIter = SetIntoIter<E>

Which kind of iterator are we turning this into?

type Item = E

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.