Struct bk_tree::BKTree

pub struct BKTree<K, M = Levenshtein> {
    pub root: Option<BKNode<K>>,
    // some fields omitted
}

A representation of a BK-tree.

Fields

root: Option<BKNode<K>>

The root node. May be empty if nothing has been put in the tree yet.

Methods

impl<K, M> BKTree<K, M> where
    M: Metric<K>, 

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);

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");

fn find<'a, 'q, Q: ?Sized>(
    &'a self,
    key: &'q Q,
    tolerance: u64
) -> 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());

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: Debug, M: Debug> Debug for BKTree<K, M>

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.

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"]);

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

fn default() -> BKTree<K>

Returns the "default value" for a type.