[−][src]Struct bintrie::BinTrie
Methods
impl BinTrie
[src]
pub fn new() -> Self
[src]
Makes a new trie with a maximum depth
of 8192
.
let trie = BinTrie::new();
pub fn new_depth(depth: u32) -> Self
[src]
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,
[src]
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 n
th 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,
[src]
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 n
th 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,
[src]
K: FnMut(u32) -> usize,
Perform a lookup for a particular item.
K(n)
- A function that provides the n
th 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,
[src]
K: FnMut(u32) -> usize,
Perform a lookup for a particular item.
K(n)
- A function that provides the n
th 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
[src]
&'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,
[src]
&'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 Default for BinTrie
[src]
impl Clone for BinTrie
[src]
fn clone(&self) -> BinTrie
[src]
fn clone_from(&mut self, source: &Self)
1.0.0[src]
Performs copy-assignment from source
. Read more
impl Debug for BinTrie
[src]
Auto Trait Implementations
Blanket Implementations
impl<T, U> Into for T where
U: From<T>,
[src]
U: From<T>,
impl<T> From for T
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
impl<T, U> TryFrom for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = !
try_from
)The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T> Borrow for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T, U> TryInto for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,
type Error = <U as TryFrom<T>>::Error
try_from
)The type returned in the event of a conversion error.
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>
[src]
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,