Struct qp_trie::Trie [−][src]
pub struct Trie<K, V> { /* fields omitted */ }
Expand description
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
Iterate over all elements in the trie.
Iterate over all elements in the trie, given a mutable reference to the associated value.
Iterate over all values in the trie, mutably.
Iterate over all elements with a given prefix.
Iterate over all elements with a given prefix, but given a mutable reference to the associated value.
Get an immutable view into the trie, providing only values keyed with the given prefix.
Get the longest common prefix of all the nodes in the trie and the given key.
Returns true if there is an entry for the given key.
Get an immutable reference to the value associated with a given key, if it is in the tree.
Get a mutable reference to the value associated with a given key, if it is in the tree.
Insert a key/value pair into the trie, returning the old value if an entry already existed.
Remove the key/value pair associated with a given key from the trie, returning
Some(val)
if a corresponding key/value pair was found.
Remove all elements beginning with a given prefix from the trie, producing a subtrie.
Convenience function for iterating over suffixes with a string.
Convenience function for iterating over suffixes with a string.
Convenience function for viewing subtries wit a string prefix.
Returns true if there is an entry for the given string key.
Convenience function for getting with a string.
Convenience function for getting mutably with a string.
Convenience function for inserting with a string.
Convenience function for removing with a string.
Trait Implementations
Extends a collection with the contents of an iterator. Read more
extend_one
)Extends a collection with exactly one element.
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
Auto Trait Implementations
impl<K, V> RefUnwindSafe for Trie<K, V> where
K: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V> UnwindSafe for Trie<K, V> where
K: UnwindSafe,
V: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more