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) where
    K: FnMut(u32) -> usize,
    F: FnMut(u32, u32) -> usize, 

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

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

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

pub unsafe fn insert_unchecked<K, F>(&mut self, item: u32, key: K, lookup: F) where
    K: FnMut(u32) -> usize,
    F: FnMut(u32, u32) -> usize, 

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

This version is unsafe because it doesn't verify that the output of K and F are below 16. It also doesn't verify that the item doesn't have its most significant bit set. Ensure these conditions are met before calling this. It still asserts that there aren't too many internal nodes.

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

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

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

Perform a lookup for a particular item.

K(n) - A function that provides the nth group of 4 bits for the key.

let mut trie = BinTrie::new();
// Note that the item, the key, and the lookup key all obey the
// unsafe requirements.
let key = |_| 0;
let lookup = |_, _| 0;
trie.insert(5, key, lookup);
assert_eq!(trie.get(key), Some(5));
assert_eq!(trie.get(|_| 1), None);

pub unsafe fn get_unchecked<K>(&self, key: K) -> Option<u32> where
    K: FnMut(u32) -> usize, 

Perform a lookup for a particular item.

K(n) - A function that provides the nth group of 4 bits for the key.

This is unsafe to call because key is assumed to return indices below 16.

let mut trie = BinTrie::new();
// Note that the item, the key, and the lookup key all obey the
// unsafe requirements.
let key = |_| 0;
let lookup = |_, _| 0;
trie.insert(5, key, lookup);
unsafe {
    assert_eq!(trie.get_unchecked(key), Some(5));
    assert_eq!(trie.get_unchecked(|_| 1), 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, |_| 0, |_, _| 0);
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 k-NN or other spatial heuristic search.

heuristic must implement UncheckedHeuristic, which the normal Heuristic trait satisfies. Implement Heuristic unless you are sure that you need UncheckedHeuristic, which is unsafe to implement.

let mut trie = BinTrie::new();
let lookup = |n, l| match n {
    3 => 0,
    5 => if l == 1 { 1 } else {0},
    _ => 0,
};
trie.insert(3, |n| lookup(3, n), lookup);
trie.insert(5, |n| lookup(5, n), lookup);
assert_eq!(trie.explore(FnHeuristic(|n| n < 2)).collect::<Vec<u32>>(), vec![3, 5]);
assert_eq!(trie.explore(FnHeuristic(|n| n == 0)).collect::<Vec<u32>>(), vec![3]);
let mut level = 0;
assert_eq!(trie.explore(FnHeuristic(move |n| {
    level += 1;
    match level {
        1 => n == 0,
        2 => n == 1,
        _ => false,
    }
})).collect::<Vec<u32>>(), vec![5]);

Trait Implementations

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 Default for BinTrie

fn default() -> Self

Returns the "default value" for a type.

impl Debug for BinTrie

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

Formats the value using the given formatter.