Struct radix_trie::Trie
[−]
[src]
pub struct Trie<K, V> {
// some fields omitted
}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.
Methods
impl<K, V> Trie<K, V> where K: TrieKey[src]
fn new() -> Trie<K, V>
Create an empty Trie.
fn len(&self) -> usize
Fetch the number of key-value pairs stored in the Trie.
fn is_empty(&self) -> bool
Determine if the Trie contains 0 key-value pairs.
fn is_leaf(&self) -> bool
Determine if the trie is a leaf node (has no children).
fn key(&self) -> Option<&K>
Get the key stored at this node, if any.
fn value(&self) -> Option<&V>
Get the value stored at this node, if any.
fn value_mut(&mut self) -> Option<&mut V>
Get a mutable reference to the value stored at this node, if any.
fn get(&self, key: &K) -> Option<&V>
Fetch a reference to the given key's corresponding value, if any.
fn get_mut(&mut self, key: &K) -> Option<&mut V>
Fetch a mutable reference to the given key's corresponding value, if any.
fn get_node(&self, key: &K) -> Option<&Trie<K, V>>
Fetch a reference to the given key's corresponding node, if any.
Note that there is no mutable version of this method, as mutating subtries directly violates the key-structure of the trie.
fn get_ancestor(&self, key: &K) -> Option<&Trie<K, V>>
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().
fn get_ancestor_value(&self, key: &K) -> Option<&V>
Fetch the closest ancestor value for a given key.
See get_ancestor for precise semantics, this is just a shortcut.
fn get_descendant(&self, key: &K) -> Option<&Trie<K, V>>
Fetch the closest descendant for a given key.
If the key is in the trie, this is the same as get_node.
fn insert(&mut self, key: K, value: V) -> Option<V>
Insert the given key-value pair, returning any previous value associated with the key.
fn remove(&mut self, key: &K) -> Option<V>
Remove and return the value associated with the given key.
fn iter(&self) -> Iter<K, V>
Return an iterator over the keys and values of the Trie.
fn keys(&self) -> Keys<K, V>
Return an iterator over the keys of the Trie.
fn values(&self) -> Values<K, V>
Return an iterator over the values of the Trie.