Struct qp_trie::Trie

pub struct Trie<K, 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.

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));

Methods

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

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

Create a new, empty trie.

Important traits for Iter<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);

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

Iterate over all elements in the trie.

Important traits for IterMut<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V);

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>

Important traits for Iter<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);

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

Iterate over all elements with a given prefix.

Important traits for IterMut<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V);

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

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

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

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

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

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. This is currently slow - it traverses the entire trie!

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

pub fn contains_key<'a, Q: ?Sized>(&self, key: &'a Q) -> bool where     K: Borrow<Q>,     Q: Borrow<[u8]>,

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

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

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

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

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: ?Sized>(&mut self, key: &Q) -> Option<V> where     K: Borrow<Q>,     Q: Borrow<[u8]>,

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<'a, Q: ?Sized>(&mut self, prefix: &'a Q) -> Trie<K, V> where     K: Borrow<Q>,     Q: Borrow<[u8]>,

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

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

Get the corresponding entry for the given key.

impl<V> Trie<BString, V>

Important traits for Iter<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);

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

Convenience function for iterating over suffixes with a string.

Important traits for IterMut<'a, K, V>

impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V);

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

Convenience function for iterating over suffixes with a string.

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

Convenience function for viewing subtries wit a string prefix.

pub fn contains_key_str<'a, Q: ?Sized>(&self, key: &'a Q) -> bool where     Q: Borrow<str>,

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

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

Convenience function for getting with a string.

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

Convenience function for getting mutably with a string.

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

Convenience function for inserting with a string.

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

Convenience function for removing with a string.

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

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: 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: &Trie<K, V>) -> bool

This method tests for !=.

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

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

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

Returns the "default value" for a type.

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

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

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

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

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

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