Struct qp_trie::Trie

pub struct Trie<K, V> { /* private fields */ }

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.

The following example uses the provided string wrapper. Unfortunately, String/str cannot be used directly because they do not implement Borrow<[u8]> (as they do not hash the same way as a byte slice.) As a stopgap, qp_trie::wrapper::{BString, BStr} are provided, as are the .whatever_str() convenience methods on qp_trie::Trie<BString, _>.

Example

let mut trie = Trie::new();

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

// This will print the following string:
//
// `{"abbc": 1, "abcd": 2, "bcde": 3, "bdde": 4, "bddf": 5}`

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

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

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

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

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

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

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

Implementations

impl<K, V> Trie<K, V>

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

Create a new, empty trie.

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

Iterate over all elements in the trie.

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

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

pub fn keys(&self) -> Keys<'_, K, V>

Iterate over all keys in the trie.

pub fn values(&self) -> Values<'_, K, V>

Iterate over all values in the trie.

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

Iterate over all values in the trie, mutably.

pub fn clear(&mut self)

Remove all entries from the trie, leaving it empty.

pub fn is_empty(&self) -> bool

Returns true if the trie has no entries.

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

pub fn iter_prefix<'a, Q>(&'a self, prefix: &Q) -> Iter<'a, K, V> where K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

Iterate over all elements with a given prefix.

pub fn iter_prefix_mut<'a, Q>(&'a mut self, prefix: &Q) -> IterMut<'a, K, V> where K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

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

pub fn subtrie<'a, Q>(&'a self, prefix: &Q) -> SubTrie<'a, K, V>where K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

Get an immutable view into the trie, providing only values keyed with the given prefix.

pub fn longest_common_prefix<'a, Q>(&'a self, key: &Q) -> &'a K::Splitwhere K: Borrow<Q> + Break, Q: Borrow<[u8]> + ?Sized,

Get the longest common prefix of all the nodes in the trie and the given key.

pub fn count(&self) -> usize

Count the number of entries in the tree.

pub fn contains_key<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

Returns true if there is an entry for the given key.

pub fn get<'a, Q>(&'a self, key: &Q) -> Option<&'a V>where K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

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

pub fn get_mut<'a, Q>(&'a mut self, key: &Q) -> Option<&'a mut V>where K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

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

pub 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.

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>where K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

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

pub fn remove_prefix<Q>(&mut self, prefix: &Q) -> Trie<K, V>where K: Borrow<Q>, Q: Borrow<[u8]> + ?Sized,

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

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

Get the corresponding entry for the given key.

impl<V> Trie<BString, V>

pub fn iter_prefix_str<'a, Q>(&'a self, key: &Q) -> Iter<'a, BString, V> where Q: Borrow<str> + ?Sized,

Convenience function for iterating over suffixes with a string.

pub fn iter_prefix_mut_str<'a, Q>( &'a mut self, key: &Q ) -> IterMut<'a, BString, V> where Q: Borrow<str> + ?Sized,

Convenience function for iterating over suffixes with a string.

pub fn subtrie_str<'a, Q>(&'a self, prefix: &Q) -> SubTrie<'a, BString, V>where Q: Borrow<str> + ?Sized,

Convenience function for viewing subtries wit a string prefix.

pub fn contains_key_str<Q>(&self, key: &Q) -> boolwhere Q: Borrow<str> + ?Sized,

Returns true if there is an entry for the given string key.

pub fn get_str<'a, Q>(&'a self, key: &Q) -> Option<&'a V>where Q: Borrow<str> + ?Sized,

Convenience function for getting with a string.

pub fn get_mut_str<'a, Q>(&'a mut self, key: &Q) -> Option<&'a mut V>where Q: Borrow<str> + ?Sized,

Convenience function for getting mutably with a string.

pub fn insert_str<Q>(&mut self, key: &Q, val: V) -> Option<V>where Q: Borrow<str> + ?Sized,

Convenience function for inserting with a string.

pub fn remove_str<Q>(&mut self, key: &Q) -> Option<V>where Q: Borrow<str> + ?Sized,

Convenience function for removing with a string.

pub fn remove_prefix_str<Q>(&mut self, prefix: &Q) -> Trie<BString, V>where Q: Borrow<str> + ?Sized,

Convenience function for removing a prefix with a string.

Trait Implementations

impl<K: Clone, V: Clone> Clone for Trie<K, V>

fn clone(&self) -> Trie<K, V>

Returns a copy of the value.

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

Performs copy-assignment from source.

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, V> Default for Trie<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: Borrow<[u8]>, V> Extend<(K, V)> for Trie<K, V>

fn extend<I>(&mut self, iterable: I)where I: IntoIterator<Item = (K, V)>,

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K: 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<'a, K, V, Q> Index<&'a Q> for Trie<K, V>where K: Borrow<Q> + Borrow<[u8]>, Q: Borrow<[u8]> + ?Sized,

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<'a, K, V, Q> IndexMut<&'a Q> for Trie<K, V>where K: Borrow<Q> + Borrow<[u8]>, Q: Borrow<[u8]> + ?Sized,

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

Performs the mutable indexing (container[index]) operation.

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

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

type Item = (K, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: PartialEq, V: PartialEq> PartialEq for Trie<K, V>

fn eq(&self, other: &Trie<K, V>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: Eq, V: Eq> Eq for Trie<K, V>

impl<K, V> StructuralEq for Trie<K, V>

impl<K, V> StructuralPartialEq for Trie<K, V>