[−][src]Struct qp_trie::Trie
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>
[src]
pub fn new() -> Trie<K, V>
[src]
Create a new, empty trie.
pub fn iter(&self) -> Iter<K, V>
[src]
Iterate over all elements in the trie.
pub fn iter_mut(&mut self) -> IterMut<K, V>
[src]
Iterate over all elements in the trie, given a mutable reference to the associated value.
pub fn keys(&self) -> Keys<K, V>
[src]
Iterate over all keys in the trie.
pub fn values(&self) -> Values<K, V>
[src]
Iterate over all values in the trie.
pub fn values_mut(&mut self) -> ValuesMut<K, V>
[src]
Iterate over all values in the trie, mutably.
pub fn clear(&mut self)
[src]
Remove all entries from the trie, leaving it empty.
pub fn is_empty(&self) -> bool
[src]
Returns true if the trie has no entries.
impl<K: Borrow<[u8]>, V> Trie<K, V>
[src]
pub fn iter_prefix<'a, Q: ?Sized>(&self, prefix: &'a Q) -> Iter<K, V> where
K: Borrow<Q>,
Q: Borrow<[u8]>,
[src]
K: Borrow<Q>,
Q: Borrow<[u8]>,
Iterate over all elements with a given prefix.
pub fn iter_prefix_mut<'a, Q: ?Sized>(&mut self, prefix: &'a Q) -> IterMut<K, V> where
K: Borrow<Q>,
Q: Borrow<[u8]>,
[src]
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]>,
[src]
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]>,
[src]
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
[src]
Count the number of entries in the tree.
pub fn contains_key<'a, Q: ?Sized>(&self, key: &'a Q) -> bool where
K: Borrow<Q>,
Q: Borrow<[u8]>,
[src]
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]>,
[src]
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]>,
[src]
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>
[src]
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]>,
[src]
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]>,
[src]
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>
[src]
Get the corresponding entry for the given key.
impl<V> Trie<BString, V>
[src]
pub fn iter_prefix_str<'a, Q: ?Sized>(&self, key: &'a Q) -> Iter<BString, V> where
Q: Borrow<str>,
[src]
Q: Borrow<str>,
Convenience function for iterating over suffixes with a string.
pub fn iter_prefix_mut_str<'a, Q: ?Sized>(
&mut self,
key: &'a Q
) -> IterMut<BString, V> where
Q: Borrow<str>,
[src]
&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>,
[src]
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>,
[src]
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>,
[src]
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>,
[src]
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>,
[src]
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>,
[src]
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>,
[src]
&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>
[src]
impl<K: Debug + ToOwned, V: Debug> Debug for Trie<K, V>
[src]
impl<K: Default, V: Default> Default for Trie<K, V>
[src]
impl<K: Eq, V: Eq> Eq for Trie<K, V>
[src]
impl<K: Borrow<[u8]>, V> Extend<(K, V)> for Trie<K, V>
[src]
fn extend<I>(&mut self, iterable: I) where
I: IntoIterator<Item = (K, V)>,
[src]
I: IntoIterator<Item = (K, V)>,
impl<K: Borrow<[u8]>, V> FromIterator<(K, V)> for Trie<K, V>
[src]
impl<'a, K: Borrow<[u8]>, V, Q: ?Sized> Index<&'a Q> for Trie<K, V> where
K: Borrow<Q>,
Q: Borrow<[u8]>,
[src]
K: Borrow<Q>,
Q: Borrow<[u8]>,
impl<'a, K: Borrow<[u8]>, V, Q: ?Sized> IndexMut<&'a Q> for Trie<K, V> where
K: Borrow<Q>,
Q: Borrow<[u8]>,
[src]
K: Borrow<Q>,
Q: Borrow<[u8]>,
impl<K, V> IntoIterator for Trie<K, V>
[src]
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
[src]
impl<K: PartialEq, V: PartialEq> PartialEq<Trie<K, V>> for Trie<K, V>
[src]
impl<K, V> StructuralEq for Trie<K, V>
[src]
impl<K, V> StructuralPartialEq for Trie<K, V>
[src]
Auto Trait Implementations
impl<K, V> RefUnwindSafe for Trie<K, V> where
K: RefUnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V> Send for Trie<K, V> where
K: Send,
V: Send,
K: Send,
V: Send,
impl<K, V> Sync for Trie<K, V> where
K: Sync,
V: Sync,
K: Sync,
V: Sync,
impl<K, V> Unpin for Trie<K, V> where
K: Unpin,
V: Unpin,
K: Unpin,
V: Unpin,
impl<K, V> UnwindSafe for Trie<K, V> where
K: UnwindSafe,
V: UnwindSafe,
K: UnwindSafe,
V: UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<I> IntoIterator for I where
I: Iterator,
[src]
I: Iterator,
type Item = <I as Iterator>::Item
The type of the elements being iterated over.
type IntoIter = I
Which kind of iterator are we turning this into?
fn into_iter(self) -> I
[src]
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,