Type Definition triez::Trie

type Trie<T, FIndex> = Trie<T, FIndex>;

A generic tree based collection storing decomposed items

A generic tree based fixed width per node tree in which inserted elements are decomposed into their parts and stored such that shared prefixes are reused. Optimization used for nodes with single child such that nodes until a future split are condensed into a single node.

AKA "prefix tree", "Radix tree"

Examples

let mut trie = Trie::new(
    |c: &char| (c.to_lowercase().next().unwrap() as usize) - ('a' as usize),
    ('z' as usize) - ('a' as usize),
);
assert_eq!(trie.contains(&String::from("asd"))), false);
trie.insert(String::from("asd")));
assert_eq!(trie.contains(&String::from("asd"))), false);