Enum TrieHard 

pub enum TrieHard<'a, T> {
    U8(TrieHardSized<'a, T, u8>),
    U16(TrieHardSized<'a, T, u16>),
    U32(TrieHardSized<'a, T, u32>),
    U64(TrieHardSized<'a, T, u64>),
    U128(TrieHardSized<'a, T, u128>),
    U256(TrieHardSized<'a, T, U256>),
}

Enumeration of all the possible sizes of trie-hard tries. An instance of this enum can be created from any set of arbitrary string or byte slices. The variant returned will depend on the number of distinct bytes contained in the set.

let trie = ["and", "ant", "dad", "do", "dot"]
    .into_iter()
    .collect::<TrieHard<'_, _>>();

assert!(trie.get("dad").is_some());
assert!(trie.get("do").is_some());
assert!(trie.get("don't").is_none());

Note: This enum has a very large variant which dominates the size for the enum. That means that a small trie using u8s for storage will take up way (32x) more storage than it needs to. If you are concerned about extra space (and you know ahead of time the trie size needed), you should extract the inner, [TrieHardSized] which will use only the size required.

Variants

U8(TrieHardSized<'a, T, u8>)

Trie-hard using u8s for storage. For sets with 1..=8 unique bytes

U16(TrieHardSized<'a, T, u16>)

Trie-hard using u16s for storage. For sets with 9..=16 unique bytes

U32(TrieHardSized<'a, T, u32>)

Trie-hard using u32s for storage. For sets with 17..=32 unique bytes

U64(TrieHardSized<'a, T, u64>)

Trie-hard using u64s for storage. For sets with 33..=64 unique bytes

U128(TrieHardSized<'a, T, u128>)

Trie-hard using u128s for storage. For sets with 65..=126 unique bytes

U256(TrieHardSized<'a, T, U256>)

Trie-hard using U256s for storage. For sets with 129.. unique bytes

Implementations

impl<'a, T> TrieHard<'a, T>

where T: 'a + Copy,

pub fn new(values: Vec<(&'a [u8], T)>) -> Self

Create an instance of a trie-hard trie with the given keys and values. The variant returned will be determined based on the number of unique bytes in the keys.

let trie = TrieHard::new(vec![
    (b"and", 0),
    (b"ant", 1),
    (b"dad", 2),
    (b"do", 3),
    (b"dot", 4)
]);

// Only 5 unique characters produces a u8 TrieHard
assert!(matches!(trie, TrieHard::U8(_)));

assert_eq!(trie.get("dad"), Some(2));
assert_eq!(trie.get("do"), Some(3));
assert!(trie.get("don't").is_none());

pub fn get<K: AsRef<[u8]>>(&self, raw_key: K) -> Option<T>

Get the value stored for the given key. Any key type can be used here as long as the type implements AsRef<[u8]>. The byte slice referenced will serve as the actual key.

let trie = ["and", "ant", "dad", "do", "dot"]
    .into_iter()
    .collect::<TrieHard<'_, _>>();

assert!(trie.get("dad".to_owned()).is_some());
assert!(trie.get(b"do").is_some());
assert!(trie.get(b"don't".to_vec()).is_none());

pub fn get_from_bytes(&self, key: &[u8]) -> Option<T>

Get the value stored for the given byte-slice key

let trie = ["and", "ant", "dad", "do", "dot"]
    .into_iter()
    .collect::<TrieHard<'_, _>>();

assert!(trie.get_from_bytes(b"dad").is_some());
assert!(trie.get_from_bytes(b"do").is_some());
assert!(trie.get_from_bytes(b"don't").is_none());

pub fn iter(&self) -> TrieIter<'_, 'a, T>

Create an iterator over the entire trie. Emitted items will be ordered by their keys

let trie = ["dad", "ant", "and", "dot", "do"]
    .into_iter()
    .collect::<TrieHard<'_, _>>();

assert_eq!(
    trie.iter().map(|(_, v)| v).collect::<Vec<_>>(),
    ["and", "ant", "dad", "do", "dot"]
);

pub fn prefix_search<K: AsRef<[u8]>>(&self, prefix: K) -> TrieIter<'_, 'a, T>

Create an iterator over the portion of the trie starting with the given prefix

let trie = ["dad", "ant", "and", "dot", "do"]
    .into_iter()
    .collect::<TrieHard<'_, _>>();

assert_eq!(
    trie.prefix_search("d").map(|(_, v)| v).collect::<Vec<_>>(),
    ["dad", "do", "dot"]
);

Trait Implementations

impl<'a, T: Clone> Clone for TrieHard<'a, T>

fn clone(&self) -> TrieHard<'a, T>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<'a, T: Debug> Debug for TrieHard<'a, T>

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

Formats the value using the given formatter.

impl<'a, T> Default for TrieHard<'a, T>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T> FromIterator<&'a T> for TrieHard<'a, &'a T>

where T: 'a + AsRef<[u8]> + ?Sized,

fn from_iter<I: IntoIterator<Item = &'a T>>(values: I) -> Self

Creates a value from an iterator.