Struct BKTree

pub struct BKTree<K, M = Levenshtein> { /* private fields */ }

A representation of a BK-tree.

Implementations

impl<K, M> BKTree<K, M>

where M: Metric<K>,

pub fn new(metric: M) -> BKTree<K, M>

Constructs a new BKTree<K> using the provided metric.

Note that we make no assumptions about the metric function provided. Ideally it is actually a valid metric, but you may choose to use one that is not technically a valid metric. If you do not use a valid metric, however, you may find that the tree behaves confusingly for some values.

Examples

use bk_tree::{BKTree, metrics};

let tree: BKTree<&str> = BKTree::new(metrics::Levenshtein);

pub fn add(&mut self, key: K)

Adds a key to the tree.

If the tree is empty, this simply sets the root to Some(BKNode::new(key)). Otherwise, we iterate downwards through the tree until we see a node that does not have a child with the same distance. If we encounter a node that is exactly the same distance from the root node, then the new key is the same as that node’s key and so we do nothing. Note: This means that if your metric allows for unequal keys to return 0, you will see improper behavior!

Examples

use bk_tree::{BKTree, metrics};

let mut tree: BKTree<&str> = BKTree::new(metrics::Levenshtein);

tree.add("foo");
tree.add("bar");

pub fn find<'a, 'q, Q: ?Sized>( &'a self, key: &'q Q, tolerance: u32, ) -> Find<'a, 'q, K, Q, M>

where K: Borrow<Q>, M: Metric<Q>,

Searches for a key in the BK-tree given a certain tolerance.

This traverses the tree searching for all keys with distance within tolerance of of the key provided. The tolerance may be zero, in which case this searches for exact matches. The results are returned as an iterator of (distance, key) pairs.

Note: There is no guarantee on the order of elements yielded by the iterator. The elements returned may or may not be sorted in terms of distance from the provided key.

Examples

use bk_tree::{BKTree, metrics};

let mut tree: BKTree<&str> = BKTree::new(metrics::Levenshtein);

tree.add("foo");
tree.add("fop");
tree.add("bar");

assert_eq!(tree.find("foo", 0).collect::<Vec<_>>(), vec![(0, &"foo")]);
assert_eq!(tree.find("foo", 1).collect::<Vec<_>>(), vec![(0, &"foo"), (1, &"fop")]);
assert!(tree.find("foz", 0).next().is_none());

pub fn find_exact<Q: ?Sized>(&self, key: &Q) -> Option<&K>

where K: Borrow<Q>, M: Metric<Q>,

Searches for an exact match in the tree.

This is equivalent to calling find with a tolerance of 0, then picking out the first result.

Examples

use bk_tree::{BKTree, metrics};

let mut tree: BKTree<&str> = BKTree::new(metrics::Levenshtein);

tree.add("foo");
tree.add("fop");
tree.add("bar");

assert_eq!(tree.find_exact("foz"), None);
assert_eq!(tree.find_exact("foo"), Some(&"foo"));

Trait Implementations

impl<K: AsRef<str>> Default for BKTree<K>

fn default() -> BKTree<K>

Returns the “default value” for a type.

impl<K, M: Metric<K>> Extend<K> for BKTree<K, M>

fn extend<I: IntoIterator<Item = K>>(&mut self, keys: I)

Adds multiple keys to the tree.

Given an iterator with items of type K, this method simply adds every item to the tree.

Examples

use bk_tree::{BKTree, metrics};

let mut tree: BKTree<&str> = BKTree::new(metrics::Levenshtein);

tree.extend(vec!["foo", "bar"]);

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.