Struct BinTrie

Source

pub struct BinTrie { /* private fields */ }

Implementations§

Source §

impl BinTrie

Source

pub fn new() -> Self

Makes a new trie with a maximum depth of 8192.

let trie = BinTrie::new();

Source

pub fn new_depth(depth: u32) -> Self

Makes a new trie with a given maximum depth.

let trie = BinTrie::new_depth(128);

Source

pub fn insert<K, F>(&mut self, item: u32, key: K, lookup: F) -> Option<u32>
where K: FnMut(u32) -> bool, F: FnMut(u32, u32) -> bool,

Inserts a number that does not have the most significant bit set.

K(n) - A function that provides the nth bit for the key. F(item, n) - A function that must be able to look up the nth bit
from a previously inserted item.

Returns Some of a replaced leaf if a leaf was replaced, otherwise None.

let mut trie = BinTrie::new();
// Note that the item, the key, and the lookup key all obey the
// unsafe requirements.
trie.insert(5, |_| false, |_, _| false);
assert_eq!(trie.items().collect::<Vec<u32>>(), vec![5]);

Source

pub fn get<K>(&self, key: K) -> Option<u32>
where K: FnMut(u32) -> bool,

Perform a lookup for a particular item.

K(n) - A function that provides the nth bit for the key.

let mut trie = BinTrie::new();
let key = |_| false;
let lookup = |_, _| false;
trie.insert(5, key, lookup);
assert_eq!(trie.get(key), Some(5));
assert_eq!(trie.get(|_| true), None);

Source

pub fn items<'a>(&'a self) -> impl Iterator<Item = u32> + 'a

Get an iterator over the items added to the trie.

let mut trie = BinTrie::new();
trie.insert(3, |_| false, |_, _| false);
assert_eq!(trie.items().collect::<Vec<u32>>(), vec![3]);

Source

pub fn explore<'a, H>(&'a self, heuristic: H) -> impl Iterator<Item = u32> + 'a
where H: IntoHeuristic, H::Heuristic: 'a,

Iterates over the trie while using the heuristic to guide iteration.

This can be used to limit the search space or to guide the search space for a fast constant distance or other spatial heuristic search. This is not capable of directly outputting kNN, and would need to be combined with either a heuristic search that gets everything below a discrete distance and then sorts the output or a search that gets items with a discrete distance and iterates over each distance desired.

heuristic must implement IntoHeuristic, which the normal Heuristic trait satisfies.

let mut trie = BinTrie::new();
let lookup = |n, l| match n {
    3 => false,
    5 => if l == 1 { true } else { false },
    7 => if l == 1 { false } else { true },
    _ => true,
};
trie.insert(3, |n| lookup(3, n), lookup);
trie.insert(5, |n| lookup(5, n), lookup);
trie.insert(7, |n| lookup(7, n), lookup);
assert_eq!(trie.explore(FilterHeuristic(|n| n)).collect::<Vec<u32>>(), vec![7]);
let mut level = 0;
// Try and find the 5.
assert_eq!(trie.explore(FilterHeuristic(move |n: bool| {
    level += 1;
    match level {
        // Go left.
        1 => !n,
        // Then go right.
        2 => n,
        _ => false,
    }
})).collect::<Vec<u32>>(), vec![5]);