Struct qp_trie::Trie

pub struct Trie<K: ToOwned, V> { /* fields omitted */ }

A QP-trie. QP stands for - depending on who you ask - either "quelques-bits popcount" or "quad-bit popcount". In any case, the fact of the matter is that this is a compressed radix trie with a branching factor of 16. It acts as a key-value map where the keys are any value which can be converted to a slice of bytes.

It can be used with strings, although it is worth noting how inconvenient doing so is - as some &str does not hash to the same value as that same &str converted to an &[u8] (currently - see issue https://github.com/rust-lang/rust/issues/27108 which unfortunately appears to be abandoned.) The following example uses strings and also showcases the necessary inconveniences.

Example

let mut trie = Trie::new();

trie.insert("abbc".as_bytes(), 1);
trie.insert("abcd".as_bytes(), 2);
trie.insert("bcde".as_bytes(), 3);
trie.insert("bdde".as_bytes(), 4);
trie.insert("bddf".as_bytes(), 5);

// This will print the following string:
//
// {[97, 98, 98, 99]: 1, [97, 98, 99, 100]: 2, [98, 99, 100, 101]: 3, [98, 100, 100, 101]: 4, [98, 100, 100, 102]: 5}
//
// Unfortunately, for Reasons, we cannot debug-print strings in this way (because strings do
// implement `Borrow<[u8]>` due to "hashing differences".) So in debug we get a list of byte
// values.

println!("{:?}", trie);

assert_eq!(trie.get("abcd".as_bytes()), Some(&2));
assert_eq!(trie.get("bcde".as_bytes()), Some(&3));

// We can take subtries, removing all elements of the trie with a given prefix.
let mut subtrie = trie.remove_prefix("b".as_bytes());

assert_eq!(trie.get("abbc".as_bytes()), Some(&1));
assert_eq!(trie.get("abcd".as_bytes()), Some(&2));
assert_eq!(trie.get("bcde".as_bytes()), None);
assert_eq!(trie.get("bdde".as_bytes()), None);
assert_eq!(trie.get("bddf".as_bytes()), None);

assert_eq!(subtrie.get("abbc".as_bytes()), None);
assert_eq!(subtrie.get("abcd".as_bytes()), None);
assert_eq!(subtrie.get("bcde".as_bytes()), Some(&3));
assert_eq!(subtrie.get("bdde".as_bytes()), Some(&4));
assert_eq!(subtrie.get("bddf".as_bytes()), Some(&5));

// We can remove elements:
assert_eq!(trie.remove("abbc".as_bytes()), Some(1));
assert_eq!(trie.get("abbc".as_bytes()), None);

// We can mutate values:
*subtrie.get_mut("bdde".as_bytes()).unwrap() = 0;
assert_eq!(subtrie.get("bdde".as_bytes()), Some(&0));

Methods

impl<K: ToOwned + Borrow<[u8]>, V> Trie<K, V>

fn new() -> Trie<K, V>

Create a new, empty trie.

fn iter(&self) -> Iter<K, V>

Iterate over all elements in the trie.

fn iter_mut(&mut self) -> IterMut<K, V>

Iterate over all elements in the trie, given a mutable reference to the associated value.

fn iter_prefix<L: Borrow<[u8]>>(&self, prefix: L) -> Iter<K, V>

Iterate over all elements with a given prefix.

fn iter_prefix_mut<L: Borrow<[u8]>>(&mut self, prefix: L) -> IterMut<K, V>

Iterate over all elements with a given prefix, but given a mutable reference to the associated value.

fn count(&self) -> usize

Count the number of entries in the tree. This is currently slow - it traverses the entire trie!

TODO: Speed this up by tracking the size of the trie for each insert/removal.

fn get<L: Borrow<[u8]>>(&self, key: L) -> Option<&V>

Get an immutable reference to the value associated with a given key, if it is in the tree.

fn get_mut<L: Borrow<[u8]>>(&mut self, key: L) -> Option<&mut V>

Get a mutable reference to the value associated with a given key, if it is in the tree.

fn insert(&mut self, key: K, val: V) -> Option<V>

Insert a key/value pair into the trie, returning the old value if an entry already existed.

fn remove<L: Borrow<[u8]>>(&mut self, key: L) -> Option<V>

Remove the key/value pair associated with a given key from the trie, returning Some(val) if a corresponding key/value pair was found.

fn remove_prefix<L: Borrow<[u8]>>(&mut self, prefix: L) -> Trie<K, V>

Remove all elements beginning with a given prefix from the trie, producing a subtrie.

fn entry(&mut self, key: K) -> Entry<K, V>

Get the corresponding entry for the given key.

Trait Implementations

impl<K: Debug + ToOwned, V: Debug> Debug for Trie<K, V>

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

Formats the value using the given formatter.

impl<K: ToOwned, V> IntoIterator for Trie<K, V>

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

type Item = (K::Owned, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: ToOwned + Borrow<[u8]>, V> FromIterator<(K, V)> for Trie<K, V>

fn from_iter<I>(iterable: I) -> Trie<K, V> where
    I: IntoIterator<Item = (K, V)>, 

Creates a value from an iterator.

impl<K: ToOwned + Borrow<[u8]>, V, L: Borrow<[u8]>> Index<L> for Trie<K, V>

type Output = V

The returned type after indexing

fn index(&self, key: L) -> &V

The method for the indexing (container[index]) operation

impl<K: ToOwned + Borrow<[u8]>, V, L: Borrow<[u8]>> IndexMut<L> for Trie<K, V>

fn index_mut(&mut self, key: L) -> &mut V

The method for the mutable indexing (container[index]) operation