Crate twie

twie [twaɪ] - Fast, compressed prefix tries.

This crate provides a Trie type that implements an associative container with slice-like keys. It has the following properties.

• Most one-shot operations are worst-case O(n), where n is the length of the key in bytes. This may require at most 2n tree hops, but the internal representation tries to minimize this where possible.

• Finding all prefixes of a string that are in the trie is also O(n). These prefixes are provided in order.

• Building a trie out of, e.g., an iterator is quadratic.

• Subtries of the whole trie (i.e. all entries with some particular prefix) can be operated on like regular tries (insertion is only supported from the root, unfortunately).

• Memory for storing keys is shared.

• The trie’s internal indexing type is configurable, which allows trading off maximum key size for shrinking the size of tree nodes, and thus, memory usage.

let words = Trie::<str, i32>::from([
  ("poise", 0),
  ("poison", 1),
  ("poisonous", 2),
  ("poison #9", 3),
]);

assert_eq!(
  words.prefixes("poisonous snake").map(|(k, _)| k).collect::<Vec<_>>(),
  ["poison", "poisonous"],
)

Structs

• Iter
  An in-order iterator over all values of a Trie.
• IterMut
  An in-order mutable iterator over all values of a Trie.
• Prefixes
  An iterator over all values of a Trie whose keys start with a particular prefix.
• PrefixesMut
  A mutable iterator over all values of a Trie whose keys start with a particular prefix.
• Sub
  A reference to some subtrie of a Trie.
• SubMut
  A reference to some subtrie of a Trie.
• Trie
  An radix prefix trie, optimized for searching for known prefixes of a string (for a fairly open-ended definition of “string”).

Traits

• Buf
  A trait for abstracting over str, [u8], and other byte-string-like types.
• Index
  A type usable as the internal index parameter of a Trie.