Struct bintrie::BinTrie

pub struct BinTrie { /* fields omitted */ }

Methods

impl BinTrie

pub fn new() -> Self

Makes a new trie with a maximum depth of 8192.

let trie = BinTrie::new();

pub fn new_depth(depth: u32) -> Self

Makes a new trie with a given maximum depth.

let trie = BinTrie::new_depth(128);

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

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

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

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

Trait Implementations

impl Default for BinTrie

fn default() -> Self

Returns the "default value" for a type.

impl Clone for BinTrie

fn clone(&self) -> BinTrie

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BinTrie

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

Formats the value using the given formatter.