Struct BKTreeMap

pub struct BKTreeMap<K, M, V> { /* private fields */ }

a tree for quickly finding items separated by a small discrete distance

Implementations

impl<K, M, V> BKTreeMap<K, M, V>

pub fn append<M2>(&mut self, other: &mut BKTreeMap<K, M2, V>)

where M: DiscreteMetric<K, K>,

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

pub fn clear(&mut self)

clears the map, removing all elements

pub fn close_iter<Q>( &self, key: Q, maxdistance: usize, ) -> CloseMapIter<'_, K, M, Q, V>

where M: DiscreteMetric<K, Q>,

gets the key value pairs whose distance is at most max distance from key

pub fn close_keys<Q>( &self, key: Q, maxdistance: usize, ) -> CloseKeyIter<'_, K, M, Q, V>

where M: DiscreteMetric<K, Q>,

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

pub fn close_values<Q>( &self, key: Q, maxdistance: usize, ) -> CloseValIter<'_, K, M, Q, V>

where M: DiscreteMetric<K, Q>,

gets the values whose keys are at most max distance from key

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

where M: DiscreteMetric<K, Q>,

returns the key value pairs at most maxdistance from the key, sorted by distance

pub fn close_sorted_mut<'a, Q: ?Sized>( &mut self, key: &Q, maxdistance: usize, ) -> Vec<(&K, &mut V, usize)>

where M: DiscreteMetric<K, Q>,

returns the key value pairs at most maxdistance from the key, sorted by distance

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

where M: DiscreteMetric<K, Q>,

tests if a key at most maxdistance from the given key is in the map

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

where M: DiscreteMetric<K, Q>,

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

Examples found in repository

examples/string_matching.rs (line 10)

pub fn main(){
	let mut tree=BKTreeMap::new(Levenshtein::new());
	tree.insert("calculate","mathematics");
	tree.insert("cat","pet");
	tree.insert("kat","name");
	tree.insert("hello","greeting");
	tree.insert("hi","greeting");
	tree.insert("linear","mathematics");

	println!("{}",tree.get("calculator",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("hey",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("kate",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("line",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("serotonin",2).map(|(s,_d)|*s).unwrap_or("not found"));
}

pub fn get_key_value<Q: ?Sized>( &self, key: &Q, maxdistance: usize, ) -> Option<(&K, &V, usize)>

where M: DiscreteMetric<K, Q>,

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

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

where M: DiscreteMetric<K, Q>,

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

pub fn insert(&mut self, key: K, value: V) -> Option<V>

where M: DiscreteMetric<K, K>,

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.

Examples found in repository

examples/string_matching.rs (line 3)

pub fn main(){
	let mut tree=BKTreeMap::new(Levenshtein::new());
	tree.insert("calculate","mathematics");
	tree.insert("cat","pet");
	tree.insert("kat","name");
	tree.insert("hello","greeting");
	tree.insert("hi","greeting");
	tree.insert("linear","mathematics");

	println!("{}",tree.get("calculator",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("hey",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("kate",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("line",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("serotonin",2).map(|(s,_d)|*s).unwrap_or("not found"));
}

pub fn into_keys(self) -> IntoKeysIter<K, V>

makes an iterator over the keys

pub fn into_values(self) -> IntoValsIter<K, V>

makes an iterator over the values

pub fn is_empty(&self) -> bool

returns true if the map contains no entries

pub fn iter(&self) -> MapIter<'_, K, V>

makes an iterator over the mappings

pub fn iter_mut(&mut self) -> MapIterMut<'_, K, V>

makes an iterator over the mappings

pub fn keys(&self) -> KeyIter<'_, K, V>

makes an iterator over the keys

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 len(&self) -> usize

returns the number of entries in the map

pub fn new(metric: M) -> Self

creates a new tree

Examples found in repository

examples/string_matching.rs (line 2)

pub fn main(){
	let mut tree=BKTreeMap::new(Levenshtein::new());
	tree.insert("calculate","mathematics");
	tree.insert("cat","pet");
	tree.insert("kat","name");
	tree.insert("hello","greeting");
	tree.insert("hi","greeting");
	tree.insert("linear","mathematics");

	println!("{}",tree.get("calculator",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("hey",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("kate",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("line",2).map(|(s,_d)|*s).unwrap_or("not found"));
	println!("{}",tree.get("serotonin",2).map(|(s,_d)|*s).unwrap_or("not found"));
}

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

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

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.

pub fn remove_entry<Q: ?Sized>( &mut self, key: &Q, maxdistance: usize, ) -> Option<(K, V, usize)>

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

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.

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

where M: DiscreteMetric<K, K>,

removes all the mappings for which f returns false

pub fn values(&self) -> ValIter<'_, K, V>

makes an iterator over the values

pub fn values_mut(&mut self) -> ValIterMut<'_, K, V>

makes an iterator over the values

Trait Implementations

impl<K, M, V> AsMut<BKTreeMap<K, M, V>> for BKTreeMap<K, M, V>

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

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

impl<K, M, V> AsRef<BKTreeMap<K, M, V>> for BKTreeMap<K, M, V>

fn as_ref(&self) -> &Self

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

impl<K: Clone, M: Clone, V: Clone> Clone for BKTreeMap<K, M, V>

fn clone(&self) -> BKTreeMap<K, M, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, M: Debug, V: Debug> Debug for BKTreeMap<K, M, V>

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

Formats the value using the given formatter.

impl<K, M: Default, V> Default for BKTreeMap<K, M, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K, M: DiscreteMetric<K, K>, V> Extend<(K, V)> for BKTreeMap<K, M, V>

fn extend<I: IntoIterator<Item = (K, V)>>(&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<K, M: Default + DiscreteMetric<K, K>, V> FromIterator<(K, V)> for BKTreeMap<K, M, V>

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<K, M: DiscreteMetric<K, Q>, Q, V> Index<&Q> for BKTreeMap<K, M, V>

type Output = V

The returned type after indexing.

fn index(&self, index: &Q) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K, M: DiscreteMetric<K, Q>, Q, V> IndexMut<&Q> for BKTreeMap<K, M, V>

fn index_mut(&mut self, index: &Q) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, K, M, V> IntoIterator for &'a BKTreeMap<K, M, V>

type IntoIter = MapIter<'a, K, V>

Which kind of iterator are we turning this into?

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, M, V> IntoIterator for &'a mut BKTreeMap<K, M, V>

type IntoIter = MapIterMut<'a, K, V>

Which kind of iterator are we turning this into?

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, M, V> IntoIterator for BKTreeMap<K, M, V>

type IntoIter = MapIntoIter<K, V>

Which kind of iterator are we turning this into?

type Item = (K, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.