[−][src]Struct radix_trie::Trie
Data-structure for storing and querying string-like keys and associated values.
Any keys which share a common prefix are stored below a single copy of that prefix. This saves space, and also allows the longest prefix of any given key to be found.
You can read more about Radix Tries on Wikipedia.
Lots of the methods on Trie
return optional values - they can be composed
nicely using Option::and_then
.
Implementations
impl<K, V> Trie<K, V> where
K: TrieKey,
[src]
K: TrieKey,
pub fn new() -> Trie<K, V>
[src]
Create an empty Trie.
pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
K: Borrow<Q>,
Q: TrieKey,
[src]
K: Borrow<Q>,
Q: TrieKey,
Fetch a reference to the given key's corresponding value, if any.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.
pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
K: Borrow<Q>,
Q: TrieKey,
[src]
K: Borrow<Q>,
Q: TrieKey,
Fetch a mutable reference to the given key's corresponding value, if any.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.
pub fn insert(&mut self, key: K, value: V) -> Option<V>
[src]
Insert the given key-value pair, returning any previous value associated with the key.
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where
K: Borrow<Q>,
Q: TrieKey,
[src]
K: Borrow<Q>,
Q: TrieKey,
Remove the value associated with the given key.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.
pub fn value_mut(&mut self) -> Option<&mut V>
[src]
Get a mutable reference to the value stored at this node, if any.
pub fn subtrie<'a, Q: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>> where
K: Borrow<Q>,
Q: TrieKey,
[src]
K: Borrow<Q>,
Q: TrieKey,
Fetch a reference to the subtrie for a given key.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.
pub fn subtrie_mut<'a, Q: ?Sized>(
&'a mut self,
key: &Q
) -> Option<SubTrieMut<'a, K, V>> where
K: Borrow<Q>,
Q: TrieKey,
[src]
&'a mut self,
key: &Q
) -> Option<SubTrieMut<'a, K, V>> where
K: Borrow<Q>,
Q: TrieKey,
Fetch a mutable reference to the subtrie for a given key.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.
pub fn get_ancestor<'a, Q: ?Sized>(
&'a self,
key: &Q
) -> Option<SubTrie<'a, K, V>> where
K: Borrow<Q>,
Q: TrieKey,
[src]
&'a self,
key: &Q
) -> Option<SubTrie<'a, K, V>> where
K: Borrow<Q>,
Q: TrieKey,
Fetch a reference to the closest ancestor node of the given key.
If key
is encoded as byte-vector b
, return the node n
in the tree
such that n
's key's byte-vector is the longest possible prefix of b
, and n
has a value.
Invariant: result.is_some() => result.key_value.is_some()
.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.
pub fn get_ancestor_value<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
K: Borrow<Q>,
Q: TrieKey,
[src]
K: Borrow<Q>,
Q: TrieKey,
Fetch the closest ancestor value for a given key.
See get_ancestor
for precise semantics, this is just a shortcut.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.
pub fn get_raw_ancestor<'a, Q: ?Sized>(&'a self, key: &Q) -> SubTrie<'a, K, V> where
K: Borrow<Q>,
Q: TrieKey,
[src]
K: Borrow<Q>,
Q: TrieKey,
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type
pub fn get_raw_descendant<'a, Q: ?Sized>(
&'a self,
key: &Q
) -> Option<SubTrie<'a, K, V>> where
K: Borrow<Q>,
Q: TrieKey,
[src]
&'a self,
key: &Q
) -> Option<SubTrie<'a, K, V>> where
K: Borrow<Q>,
Q: TrieKey,
Fetch the closest descendant for a given key.
If the key is in the trie, this is the same as subtrie
.
The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type
pub fn map_with_default<F>(&mut self, key: K, f: F, default: V) where
F: Fn(&mut V),
[src]
F: Fn(&mut V),
Take a function f
and apply it to the value stored at key
.
If no value is stored at key
, store default
.
Trait Implementations
impl<K: Clone, V: Clone> Clone for Trie<K, V>
[src]
impl<K: Debug, V: Debug> Debug for Trie<K, V>
[src]
impl<K: TrieKey, V> Default for Trie<K, V>
[src]
impl<K, V> FromIterator<(K, V)> for Trie<K, V> where
K: TrieKey,
[src]
K: TrieKey,
impl<K, V> PartialEq<Trie<K, V>> for Trie<K, V> where
K: TrieKey,
V: PartialEq,
[src]
K: TrieKey,
V: PartialEq,
impl<'a, K: 'a, V: 'a> TrieCommon<'a, K, V> for &'a Trie<K, V> where
K: TrieKey,
[src]
K: TrieKey,
fn len(self) -> usize
[src]
fn children(self) -> Children<'a, K, V>ⓘ
[src]
fn key(self) -> Option<&'a K>
[src]
fn value(self) -> Option<&'a V>
[src]
fn is_empty(self) -> bool
[src]
fn is_leaf(self) -> bool
[src]
fn iter(self) -> Iter<'a, K, V>ⓘ
[src]
fn keys(self) -> Keys<'a, K, V>ⓘ
[src]
fn values(self) -> Values<'a, K, V>ⓘ
[src]
fn prefix(self) -> &'a Nibblet
[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>
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,
pub 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<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
pub fn to_owned(&self) -> T
[src]
pub 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.
pub 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>,